このエントリーをはてなブックマークに追加このエントリをつぶやく

暗号技術入門05 公開鍵暗号

目次

  1. 公開鍵暗号とは
  2. RSA暗号
  3. 他の公開鍵暗号
  4. 公開鍵暗号の問題

公開鍵暗号とは

暗号化の鍵を一般に公開できる

公開鍵暗号の歴史

出来事
1976 ホイットフィールド・ディファーとマーティン・ヘルマンがアイデアを発表
1977 ナップサック暗号が作られる
1978 ロン・リヴェスト、アディ・シャミア、レナード・アルマンによりRSA暗号が発表される

1976年に公開鍵暗号のアイデアが発表され、その1年後ナップサック暗号という暗号が作られました。しかし、この暗号は後に安全でないことがわかりました。
そして、1978年RSA暗号が発表され、このRSA暗号が現在の標準となっています。

しかし、この歴史には裏話があり

1960年代に公開鍵暗号と同じアイデアがすでに考案されており、
1973年RSAと同様の暗号を生み出していたそうです

公開鍵暗号とは

受信者が公開鍵とプライベート鍵のペアを作成し、
メッセージの送信者へ送ります。

送信者は受け取った公開鍵で暗号化した暗号文を受信者へ送ります
その暗号文を受信者はプライベートキーで複合化します。

RSA暗号

平文を示す数をE乗して、Nで割ったあまりが暗号文になります。
このE乗してNで割るというのが暗号化をあらわしています
秘密鍵暗号ではXORやらビットの移動やらしていましたが、これだけです
また、複合化はD乗してN割ったあまりが平文となります
もちろんD乗してN割るというのが複合化をしめしています。

ここでEとNが公開鍵
DとNが秘密鍵となります
ここで登場するN、E,Dを決めるというのは
すなわち公開鍵とプライベート鍵を作るというのと同じいみです
次のページから実際にどうやって鍵を作るか見てみます

Nは二つの素数pとqをかけたものです
このpとqはだいたい約300桁の素数になります
次に
Lはp-1とq-1の最小公倍数です
Eは1~Lの間でEとLの最大公約数は1になる数字です。
これは、EとLの素数で共通部分がない組→これが最大公約数が1になります
次にDこれは
Eとかけて割ったあまりが1になる数字です。

これで
EとDとLを求めることが出来ました。
公開鍵とプライベート鍵を作る際には中でこんなことが起こってるそうです

ここで公開鍵の中で
EとNの値がわかってしまいます。
どうにかしてDの値が求められないかやってみましょう

EとNからDはわかるか?

EとDの関係式は

E×D mod L=1

2つの素数pとqを知られると不味い

他の公開鍵暗号

  • ElGamal方式
  • Rabin方式
  • 楕円曲線暗号

他の公開鍵暗号として
えるがまる方式
ラビン方式
楕円曲線暗号が存在します

この中で覚えていてほしいのが楕円曲線暗号通称ECCです
これはRSAにくらべビット数を少なく出来、最近注目されている暗号アルゴリズムです
詳しくは調べてください

公開鍵暗号の問題

共通鍵暗号よりもとても遅い

公開鍵暗号は共通鍵暗号に比べてデータの処理速度が遅いという問題があります。

そこで、ハイブリット方式という手法がとられます

共通鍵を渡すときに公開鍵暗号を使い
それ以降は渡した共通鍵でやり取りをするという方式です

このハイブリット方式については次の章で紹介します。

結論

鍵を作るときは2048bitで

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第5章 公開鍵暗号(p112-p152)

カテゴリー: 勉強会   タグ: ,   この投稿のパーマリンク

コメントは受け付けていません。