情報セキュリティメモ (2024/11/13)
p が素数のとき$ Z_p^*=\{a|(a,p)=1\}=Z_p-\{0\}となり$ Z_pは体 $ F_p=Z_p=\{0,1,2,...,p-1\}を有限体 $ F_7=\{0,1,2,3,4,5,6\},\ F_7^*=\{1,2,3,4,5,6\}
定理
有限体$ F_pの乗法群$ F_p^*=F_p-\{0\}は巡回群になり，$ F_p^*=<g>=\{1=g^0,g^1,g^2,...g^{p-1}\}と書ける (g を生成元) ex. p=7 の場合
$ F_7=\{0,1,2,3,4,5,6\}， F_7^*=\{1,2,3,4,5,6\}
乗法群$ F_7^*の構造
$ F_7^*=<3>=\{3^0=1,3^1=3,3^2=2,3^3=6,3^4=4,3^5=5\}
乗法群$ F_7^*の部分群
$ <2>=\{3^0=1,3^2=2,3^4=4\}=\{2^0=1,2^1=2,2^2=4\}
$ <6>=\{3^0=1,3^3=6\}=\{6^0=1,6^1=2\}
有限体$ F_pの乗法群$ F_p^*(またはその部分群) は巡回群$ <g>=\{1=g^0,g^1,g^2,...,g^{n-1}\} 「<g> の元 g, g^x から x を計算する」問題
ex. p=7 の場合
$ F_7^*=<3>=\{3^0=1,3^1=3,3^2=2,3^3=6,3^4=4,3^5=5\}
g=3, g^x=6 の離散対数は x=3
関数 $ f(k) が negligible とは，全ての $ c に対して，ある $ K が存在して，全ての $ k>K について $ f(k) < 1/k^c となること どんな高次の多項式の逆数よりも早く 0 に近づく，ということ
ex. $ f(k)=1/2^kは negligible
任意の確率的多項式時間アルゴリズム $ B について，$ B が $ g, $ g^x から $ x を計算する確率$ Adv_B(k)が negligible であることを仮定すること
任意の確率的多項式時間アルゴリム $ Bについて，$ Bが$ g, $ g^a,$ g^bから$ g^{ab}を計算する確率$ Adv_B(k)が negligible であることを仮定すること
CDH 仮定 → DL 仮定
DL が解けたとすると$ aが計算できるので$ g^{ab}を計算でき CDH が解ける
任意の確率的多項式時間アルゴリズム $ Bについて，$ Bが$ (g,g^a,g^b,g^{ab})と$ (g,g^a,g^b,g^r)とを識別する確率を $ pとし$ Adv_B(k)=|P-1/2|が negligible であることを仮定すること
DDH 仮定 → CDH 仮定
CDH が解けたとすると$ g^{ab}が計算できるので$ g^rと見分けられ DDH が解ける
任意の確率的多項式時間アルゴリズム$ Bについて，$ Bが$ n=pqから$ p,qを計算する確率$ Adv_B(k)が negligible であることを仮定すること
任意の確率的多項式時間アルゴリズム $ B について，$ Bが$ n=pq,e,cから$ c=x^e\mod nとなる$ xを計算する確率$ Adv_B(k)が negligible であることを仮定すること
RSA 仮定 → Factoring 仮定
Factoring が解けたとすると$ p,qが計算できるので，$ ed=1\mod (p-1)(q-1)となる$ dが計算でき$ x=c^d\mod nが計算でき RSA が解ける
鍵生成
鍵長$ k,k'(例えば k=2048, k'=256) が与えられ
k bit の素数$ p=hq+1と k' bit の素数$ qを生成し
乗法群$ Z_p^*の部分群$ <g>=\{1=g^0,g^1,g^2,...,g^{q-1}\}で位相が$ qとなるものを生成する
$ p,q,g,y=g^xを公開鍵として公開し，$ xを秘密鍵として秘密に保持する 暗号化
平文 $ mに対して，乱数$ rを生成し，暗号文$ (R=g^r,M=my^r)を計算する
確率的暗号 (同じ平文に対して毎回異なる暗号文が得られる → より安全) $ (M, R)から$ mを取りだすのは CDH 仮定により不可能 復号化
暗号文$ (M,R)に対して，平文$ m'=M/R^xを計算する
Correctness: $ m=Dec(sk,Enc(pk,m))
$ m'=M/R^x=my^r/R^x=mg^{xr}/g^{rx}=m
Correctness は正しく暗号化したものを正しく復号化すると平文に戻ることのみを保証 (安全性を保証するものではない)
ex. $ p=23=2*11+1, q=11
$ F_{23}^*の位数は $ 23-1=22
$ F_{23}^*の位数 11 の部分群$ <2>と生成元$ g=2を考える
復号鍵$ x=6, 暗号化鍵$ y=g^x=2^6=18\mod 23
平文 $ m=1を暗号化，$ r=2とすると
$ R=g^r=2^2=4\mod 23,\ M=m*y^r=1*18^2=2\mod 23
暗号文$ (R=4\mod 23,\ M=2\mod 23)
$ R^x=((4^2)4)^2=2\mod 23
$ m=2/2=1\mod 23
鍵生成
鍵長$ k (例えば$ k=1024)が与えられ，$ kbit の素数$ p,qを生成し，$ n=pqとする
$ (e, (p-1)(q-1))=1となる$ eを求め，$ ed=1\mod (p-1)(q-1)となる $ dを求める
$ n,eを公開鍵として公開し，$ dを秘密鍵として保持する 暗号化
平文$ m\mod nに対して，暗号文$ c=m^e\mod n
暗号文が平文に対して一意なので，複数の暗号文が送信されたとき，それらの暗号文が同じか異なっているかという情報 (1 bit) が漏洩していると言える
→ 現代では使用されない
復号化
暗号文$ c\mod nに対して，平文$ m'=c^d\mod n
Correctness
ex.