暗号技術 ～公開鍵暗号方式の仕組み～ （３週目） 暗号技術 ～公開鍵暗号方式の仕組み～ （３週目） 情報工学科　　04A1004 石川　真悟

公開鍵暗号 公開鍵を使って暗号化し、秘密鍵を使って復号化する。 事前に暗号化する人に公開鍵を渡し、自分が持っている秘密鍵を使って複合化する。 公開鍵と秘密鍵の２つの鍵を使うことで、対称暗号方式が持っていた鍵配送問題を解決した。

公開鍵暗号の種類 RSA（公開鍵暗号で最も普及している） ElGamal（離散対数問題を応用した） Rabin（RSAを改良して安全性証明をつけた）

RSAの暗号化処理 平文の値を「E」回掛け合わせ、この結果の値を「N」で割り、余りの値を求める。この計算結果が暗号文になる。「E」と「N」は公開鍵の値になる。 暗号文＝平文　mod N E 例）平文１２、Ｅ＝５、Ｎ＝２２１ 暗号文＝１２　mod　２２１ 暗号文＝２０７ 平文 公開鍵 ５ E N 暗号化処理 暗号文＝平文　mod N E 暗号化処理そのものは、 とてもシンプルだが、 秘密鍵の情報がわからない限り、 現実的な時間で解読するのは困難 暗号文

RSAの復号化処理 暗号文の値を「D」回掛け合わせ、この結果の値を「N」で割り、余りの値を求める。この計算結果が暗号文になる。「D」と「N」は秘密鍵の値になる。 平文＝暗号文　mod N D 暗号文 例）暗号文２０７、Ｄ＝２９、Ｎ＝２２１ 平文＝２０７　mod　２２１ 平文＝１２ 秘密鍵 ２９ D N 暗号化処理 平文＝暗号文　mod N D 暗号化処理同様、 復号化処理もとてもシンプルなため、 秘密鍵が他の人の手に渡ると 解読は簡単にできてしまうため、 秘密鍵は厳重に管理する必要がある。 平文

公開鍵と秘密鍵は対（ペア）になっている必要があり、この２つのキーのことをキーペアと呼ぶ。 キーペアの生成手順 公開鍵と秘密鍵は対（ペア）になっている必要があり、この２つのキーのことをキーペアと呼ぶ。 PとQを使ってNを計算する N=PxQ L=1cm(P-1,Q-1) P-1とQ-1の最小公倍数 PとQを使ってLを計算する 1<E<L god(E,L)=1 EとLの最大公約数が1になるEを求める Lを使ってEを計算する EとLを使ってDを計算する E x D mod L =1 EとDを掛けmodLを計算した値が 1になるようにDを求める

キーペアの生成の具体例 まずＰとＱの２つの素数を用意（説明を簡単にするため小さい数字で行なう） Ｐ＝１３、Ｑ＝１７ Ｎ＝ＰｘＱ＝１３ｘ１７＝２２１ Ｌ＝１ｃｍ（Ｐ－１，Ｑ－１）＝１ｃｍ（１３－１，１７－１）＝１ｃｍ（１２，１６） １２と１６の最小公倍数は４８なのでＬ＝４８ １＜Ｅ＜Ｌ　　god（Ｅ，Ｌ）＝１ God（Ｅ，４８）＝１ Ｅと４８の最大公約数が１になるようなＥを求める。 Ｅ＝5，7，11，13，17，19，23，25,29,31,35,37,41,43,47 この中から素数を１つを選ぶ。ただし、２５、３５は素数ではないので外す。 仮に５を選ぶ。 ＥｘＤ mod　Ｌ＝１ ５ｘＤ mod　４８＝１ Ｄ＝２９

ＥｌＧａｍａｌの暗号化処理 Ｋ＝Ｐ－１と互いに素な乱数 暗号文a＝Ｇ mod Ｐ 暗号文b＝Ｙ 平文mod Ｐ この暗号文aと暗号文bがペアになって１つの暗号文になる。 Ｇ，Ｙ，Ｐが公開鍵の値になる。 K K 例）平文１２、Ｇ＝１３、Ｙ＝４、Ｐ＝１７ Ｋ＝（１７－１）と互いに素な乱数 Ｋ＝３，５，７，１１，１３ この中から１つ選択 暗号文a＝１３　mod　１７＝４ 暗号文b＝４　ｘ１２ mod　１７＝３ 平文 公開鍵 ３ G Y P ３ 暗号化処理 Ｋ＝Ｐ－１と互いに素な乱数 暗号文a＝Ｇ　mod Ｐ 暗号文b＝Ｙ　平文mod　Ｐ k k 暗号文

平文ｘ暗号文a mod P＝暗号文b XとPが秘密鍵の値になる。 ＥｌＧａｍａｌの復号化処理 平文ｘ暗号文a　mod P＝暗号文b XとPが秘密鍵の値になる。 x 暗号文 秘密鍵 X P 暗号化処理 平文ｘ暗号文a　mod P＝暗号文b x 例）暗号文a＝４、暗号文b＝３、 Ｘ＝１１、Ｐ＝１７ 平文ｘ４　mod 　１７＝３ 平文＝１２ 平文 １１

まず１つの大きな素数を準備。 この１つの素数をＰとしてＧ、Ｙ、Ｘを計算で生成。 Ｇ、Ｙ、Ｐが公開鍵、Ｘ、Ｐが秘密鍵 キーペアの生成手順 まず１つの大きな素数を準備。 この１つの素数をＰとしてＧ、Ｙ、Ｘを計算で生成。 Ｇ、Ｙ、Ｐが公開鍵、Ｘ、Ｐが秘密鍵 Pを使ってGを計算する G<P X<P Pを使ってXを計算する x Y=G mod P PとGとXを使ってYを計算する

キーペアの生成の具体例 まず素数Pを用意（説明を簡単にするため小さい数字で行なう） Ｐ＝１７ Ｇ＜Ｐ Ｇ＜１７ 仮にＧ＝１３とする。 Ｘ＜Ｐ Ｘ＜１７ 仮にＸ＝１１とする。 Ｙ＝Ｇ　mod　Ｐ 　＝１３　mod １７ 　＝４ 11 11

暗号文＝平文ｘ（平文＋Ｂ） mod N ＢとＮが公開鍵になる。 Rabinの暗号化処理 暗号文＝平文ｘ（平文＋Ｂ）　mod N ＢとＮが公開鍵になる。 平文 公開鍵 B N 暗号化処理 暗号文＝平文ｘ（平文＋Ｂ）　mod N 例）平文１３５、Ｂ＝２０１、Ｎ＝２０９ 暗号文＝１３５ｘ（１３５＋２０１）mod　２０９ 暗号文＝７ 暗号文

Rabinの復号化処理 （平文 ＋平文ｘＢ－暗号文） ｍｏｄ Ｐ＝０ （平文 ＋平文ｘＢ－暗号文） ｍｏｄ Ｑ＝０ 2 （平文　＋平文ｘＢ－暗号文）　ｍｏｄ Ｐ＝０ （平文　＋平文ｘＢ－暗号文）　ｍｏｄ Ｑ＝０ この連立方程式を満たす平文の値を求める。 ＢとＰとＱが秘密鍵になる。 2 秘密鍵 暗号文 B P Q 暗号化処理 （平文　＋平文ｘＢ－暗号文）　ｍｏｄ Ｐ＝０ （平文　＋平文ｘＢ－暗号文）　ｍｏｄ Ｑ＝０ 2 2 平文 例）暗号文７、Ｂ＝２０１、Ｐ＝１１、Ｑ＝１９ （平文　＋平文ｘ２０１－７）　ｍｏｄ １１＝０ （平文　＋平文ｘ２０１－７）　ｍｏｄ １９＝０ 平文＝１３５ ２ ２

まず２つの大きな素数を準備。 この２つの素数をＰ、ＱとしてＮとＢを計算で生成。 Ｂ，Ｎが公開鍵、Ｂ，Ｐ，Ｑが秘密鍵 キーペアの生成手順 まず２つの大きな素数を準備。 この２つの素数をＰ、ＱとしてＮとＢを計算で生成。 Ｂ，Ｎが公開鍵、Ｂ，Ｐ，Ｑが秘密鍵 PとQを使ってNを計算する N=PxQ B<N Nを使ってBを計算する

キーペアの生成の具体例 まず素数PとQを用意（説明を簡単にするため小さい数字で行なう） Ｐ＝１１、Ｑ＝１９ Ｎ＝ＰｘＱ ＝１１ｘ１９ 　＝１１ｘ１９ 　＝２０９ Ｂ＜Ｎ Ｂ＜２０９ 仮に値を決める。