暗号技術 ～公開鍵暗号方式の仕組み～ （３週目） 情報工学科 04A1004 石川 真悟 公開鍵暗号 公開鍵を使って暗号化し、秘密鍵を使って復 号化する。 事前に暗号化する人に公開鍵を渡し、自分が 持っている秘密鍵を使って複合化する。 公開鍵と秘密鍵の２つの鍵を使うことで、対称 暗号方式が持っていた鍵配送問題を解決した。 公開鍵暗号の種類 • RSA（公開鍵暗号で最も普及している） • ElGamal（離散対数問題を応用した） • Rabin（RSAを改良して安全性証明をつけ た） RSAの暗号化処理 平文の値を「E」回掛け合わせ、この結果の値を「N」で割り、余りの 値を求める。この計算結果が暗号文になる。「E」と「N」は公開鍵 の値になる。 暗号文＝平文 Emod N 平文 暗号化処理 暗号文＝平文E mod N 暗号文 公開鍵 E N 例）平文１２、Ｅ＝５、Ｎ＝２２１ ５ 暗号文＝１２ mod ２２１ 暗号文＝２０７ 暗号化処理そのものは、 とてもシンプルだが、 秘密鍵の情報がわからない限り、 現実的な時間で解読するのは困難 RSAの復号化処理 暗号文の値を「D」回掛け合わせ、この結果の値を「N」で割り、余 りの値を求める。この計算結果が暗号文になる。「D」と「N」は秘密 鍵の値になる。 平文＝暗号文 Dmod N 暗号文 暗号化処理 平文＝暗号文D mod N 平文 秘密鍵 D N 例）暗号文２０７、Ｄ＝２９、Ｎ＝２２１ ２９ 平文＝２０７ mod ２２１ 平文＝１２ 暗号化処理同様、 復号化処理もとてもシンプルなため、 秘密鍵が他の人の手に渡ると 解読は簡単にできてしまうため、 秘密鍵は厳重に管理する必要がある。 キーペアの生成手順 公開鍵と秘密鍵は対（ペア）になっている必要が あり、この２つのキーのことをキーペアと呼ぶ。 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を求める キーペアの生成の具体例 まずＰとＱの２つの素数を用意（説明を簡単にするため小さい数字で行なう） Ｐ＝１３、Ｑ＝１７ Ｎ＝ＰｘＱ＝１３ｘ１７＝２２１ Ｌ＝１ｃｍ（Ｐ－１，Ｑ－１）＝１ｃｍ（１３－１，１７－１）＝１ｃｍ（１２，１６） １２と１６の最小公倍数は４８なのでＬ＝４８ １＜Ｅ＜Ｌ god（Ｅ，Ｌ）＝１ God（Ｅ，４８）＝１ Ｅと４８の最大公約数が１になるようなＥを求める。 Ｅ＝5，7，11，13，17，19，23，25,29,31,35,37,41,43,47 この中から素数を１つを選ぶ。ただし、２５、３５は素数ではないので外す。 仮に５を選ぶ。 ＥｘＤ mod Ｌ＝１ ５ｘＤ mod ４８＝１ Ｄ＝２９ ＥｌＧａｍａｌの暗号化処理 Ｋ＝Ｐ－１と互いに素な乱数 暗号文a＝Ｇ Kmod Ｐ 暗号文b＝Ｙ K平文mod Ｐ この暗号文aと暗号文bがペアになって１つの暗号文になる。 例）平文１２、Ｇ＝１３、Ｙ＝４、Ｐ＝１７ Ｇ，Ｙ，Ｐが公開鍵の値になる。 平文 暗号化処理 Ｋ＝Ｐ－１と互いに素な乱数 暗号文a＝Ｇ k mod Ｐ k 暗号文b＝Ｙ 平文mod Ｐ 暗号文 公開鍵 G Y P Ｋ＝（１７－１）と互いに素な乱数 Ｋ＝３，５，７，１１，１３ この中から１つ選択 暗号文a＝１３３ mod １７＝４ 暗号文b＝４３ ｘ１２ mod １７＝３ ＥｌＧａｍａｌの復号化処理 平文ｘ暗号文a x mod P＝暗号文b XとPが秘密鍵の値になる。 暗号文 秘密鍵 暗号化処理 X P x 平文ｘ暗号文a mod P＝暗号文b 平文 例）暗号文a＝４、暗号文b＝３、 Ｘ＝１１、Ｐ＝１７ 平文ｘ４１１mod １７＝３ 平文＝１２ キーペアの生成手順 まず１つの大きな素数を準備。 この１つの素数をＰとしてＧ、Ｙ、Ｘを計算で生成。 Ｇ、Ｙ、Ｐが公開鍵、Ｘ、Ｐが秘密鍵 Pを使ってGを計算する Pを使ってXを計算する PとGとXを使ってYを計算する G<P X<P Y=Gx mod P キーペアの生成の具体例 まず素数Pを用意（説明を簡単にするため小さい数字で行なう） Ｐ＝１７ Ｇ＜Ｐ Ｇ＜１７ 仮にＧ＝１３とする。 Ｘ＜Ｐ Ｘ＜１７ 仮にＸ＝１１とする。 11 Ｙ＝Ｇ mod Ｐ 11 ＝１３ mod １７ ＝４ Rabinの暗号化処理 暗号文＝平文ｘ（平文＋Ｂ） mod N ＢとＮが公開鍵になる。 平文 暗号化処理 公開鍵 B N 暗号文＝平文ｘ（平文＋Ｂ） mod N 暗号文 例）平文１３５、Ｂ＝２０１、Ｎ＝２０９ 暗号文＝１３５ｘ（１３５＋２０１）mod ２０９ 暗号文＝７ Rabinの復号化処理 2 （平文 ＋平文ｘＢ－暗号文） ｍｏｄ Ｐ＝０ 2 （平文 ＋平文ｘＢ－暗号文） ｍｏｄ Ｑ＝０ この連立方程式を満たす平文の値を求める。 ＢとＰとＱが秘密鍵になる。 秘密鍵 暗号文 2 B 暗号化処理 P Q （平文 ＋平文ｘＢ－暗号文） ｍｏｄ Ｐ＝０ 2 （平文 ＋平文ｘＢ－暗号文） ｍｏｄ Ｑ＝０ 平文 例）暗号文７、Ｂ＝２０１、Ｐ＝１１、Ｑ＝１９ （平文２ ＋平文ｘ２０１－７） ｍｏｄ １１＝０ ２ （平文 ＋平文ｘ２０１－７） ｍｏｄ １９＝０ 平文＝１３５ キーペアの生成手順 まず２つの大きな素数を準備。 この２つの素数をＰ、ＱとしてＮとＢを計算で生成。 Ｂ，Ｎが公開鍵、Ｂ，Ｐ，Ｑが秘密鍵 PとQを使ってNを計算する Nを使ってBを計算する N=PxQ B<N キーペアの生成の具体例 まず素数PとQを用意（説明を簡単にするため小さい数字で行なう） Ｐ＝１１、Ｑ＝１９ Ｎ＝ＰｘＱ ＝１１ｘ１９ ＝２０９ Ｂ＜Ｎ Ｂ＜２０９ 仮に値を決める。
© Copyright 2024 ExpyDoc
