暗号技術 ~公開鍵暗号方式の仕組み~ (3週目) 情報工学科 04A1004 石川 真悟 公開鍵暗号 公開鍵を使って暗号化し、秘密鍵を使って復 号化する。 事前に暗号化する人に公開鍵を渡し、自分が 持っている秘密鍵を使って複合化する。 公開鍵と秘密鍵の2つの鍵を使うことで、対称 暗号方式が持っていた鍵配送問題を解決した。 公開鍵暗号の種類 • RSA(公開鍵暗号で最も普及している) • ElGamal(離散対数問題を応用した) • Rabin(RSAを改良して安全性証明をつけ た) RSAの暗号化処理 平文の値を「E」回掛け合わせ、この結果の値を「N」で割り、余りの 値を求める。この計算結果が暗号文になる。「E」と「N」は公開鍵 の値になる。 暗号文=平文 Emod N 平文 暗号化処理 暗号文=平文E mod N 暗号文 公開鍵 E N 例)平文12、E=5、N=221 5 暗号文=12 mod 221 暗号文=207 暗号化処理そのものは、 とてもシンプルだが、 秘密鍵の情報がわからない限り、 現実的な時間で解読するのは困難 RSAの復号化処理 暗号文の値を「D」回掛け合わせ、この結果の値を「N」で割り、余 りの値を求める。この計算結果が暗号文になる。「D」と「N」は秘密 鍵の値になる。 平文=暗号文 Dmod N 暗号文 暗号化処理 平文=暗号文D mod N 平文 秘密鍵 D N 例)暗号文207、D=29、N=221 29 平文=207 mod 221 平文=12 暗号化処理同様、 復号化処理もとてもシンプルなため、 秘密鍵が他の人の手に渡ると 解読は簡単にできてしまうため、 秘密鍵は厳重に管理する必要がある。 キーペアの生成手順 公開鍵と秘密鍵は対(ペア)になっている必要が あり、この2つのキーのことをキーペアと呼ぶ。 PとQを使ってNを計算する N=PxQ PとQを使ってLを計算する L=1cm(P-1,Q-1) P-1とQ-1の最小公倍数 Lを使ってEを計算する EとLを使ってDを計算する 1<E<L god(E,L)=1 EとLの最大公約数が1になるEを求める E x D mod L =1 EとDを掛けmodLを計算した値が 1になるようにDを求める キーペアの生成の具体例 まずPとQの2つの素数を用意(説明を簡単にするため小さい数字で行なう) P=13、Q=17 N=PxQ=13x17=221 L=1cm(P-1,Q-1)=1cm(13-1,17-1)=1cm(12,16) 12と16の最小公倍数は48なのでL=48 1<E<L god(E,L)=1 God(E,48)=1 Eと48の最大公約数が1になるようなEを求める。 E=5,7,11,13,17,19,23,25,29,31,35,37,41,43,47 この中から素数を1つを選ぶ。ただし、25、35は素数ではないので外す。 仮に5を選ぶ。 ExD mod L=1 5xD mod 48=1 D=29 ElGamalの暗号化処理 K=P-1と互いに素な乱数 暗号文a=G Kmod P 暗号文b=Y K平文mod P この暗号文aと暗号文bがペアになって1つの暗号文になる。 例)平文12、G=13、Y=4、P=17 G,Y,Pが公開鍵の値になる。 平文 暗号化処理 K=P-1と互いに素な乱数 暗号文a=G k mod P k 暗号文b=Y 平文mod P 暗号文 公開鍵 G Y P K=(17-1)と互いに素な乱数 K=3,5,7,11,13 この中から1つ選択 暗号文a=133 mod 17=4 暗号文b=43 x12 mod 17=3 ElGamalの復号化処理 平文x暗号文a x mod P=暗号文b XとPが秘密鍵の値になる。 暗号文 秘密鍵 暗号化処理 X P x 平文x暗号文a mod P=暗号文b 平文 例)暗号文a=4、暗号文b=3、 X=11、P=17 平文x411mod 17=3 平文=12 キーペアの生成手順 まず1つの大きな素数を準備。 この1つの素数をPとしてG、Y、Xを計算で生成。 G、Y、Pが公開鍵、X、Pが秘密鍵 Pを使ってGを計算する Pを使ってXを計算する PとGとXを使ってYを計算する G<P X<P Y=Gx mod P キーペアの生成の具体例 まず素数Pを用意(説明を簡単にするため小さい数字で行なう) P=17 G<P G<17 仮にG=13とする。 X<P X<17 仮にX=11とする。 11 Y=G mod P 11 =13 mod 17 =4 Rabinの暗号化処理 暗号文=平文x(平文+B) mod N BとNが公開鍵になる。 平文 暗号化処理 公開鍵 B N 暗号文=平文x(平文+B) mod N 暗号文 例)平文135、B=201、N=209 暗号文=135x(135+201)mod 209 暗号文=7 Rabinの復号化処理 2 (平文 +平文xB-暗号文) mod P=0 2 (平文 +平文xB-暗号文) mod Q=0 この連立方程式を満たす平文の値を求める。 BとPとQが秘密鍵になる。 秘密鍵 暗号文 2 B 暗号化処理 P Q (平文 +平文xB-暗号文) mod P=0 2 (平文 +平文xB-暗号文) mod Q=0 平文 例)暗号文7、B=201、P=11、Q=19 (平文2 +平文x201-7) mod 11=0 2 (平文 +平文x201-7) mod 19=0 平文=135 キーペアの生成手順 まず2つの大きな素数を準備。 この2つの素数をP、QとしてNとBを計算で生成。 B,Nが公開鍵、B,P,Qが秘密鍵 PとQを使ってNを計算する Nを使ってBを計算する N=PxQ B<N キーペアの生成の具体例 まず素数PとQを用意(説明を簡単にするため小さい数字で行なう) P=11、Q=19 N=PxQ =11x19 =209 B<N B<209 仮に値を決める。
© Copyright 2024 ExpyDoc