スマートフォン用の表示で見る

rsa暗号

サイエンス

RSA暗号

あーるえすえーあんごう

概要

公開鍵暗号の一種。

1977年マサチューセッツ工科大学(MIT)にいたRivest, Shamir, Adleman という三人の研究者によって開発された。

準備

  1. 2つの大きな素数p,qを選択する。
  2. n=p*qとφ(n)=(p-1)(q-1)を計算する。このnを係数と呼ぶ。
  3. gcd(e,φ(n))=1の関係をもつ数e(公開指数)を選択する。ここでgcdは2つの引数最大公約数(Greatest Common Divisor)を意味する。この公開指数eと係数nが公開鍵(e,n)となる。
  4. 1=de mod φ(n)となるd(秘密指数)を計算する。この秘密指数dと係数nが秘密鍵(d,n)となる。
  5. 公開鍵(e,n)を公開する。p,q,dは誰にも知られないようにしておく。

実行

平文をMとし、暗号化された文章をCとする。M,Cともに{0,1,...,n-1}の要素である。

暗号時は

C=M^e ¥bmod{n}

復号時には

M=C^d ¥bmod{n}

という関係が成り立つ。

原理

まだ分からない。巨大な数nの素因数分解を行ないpとqを求めればφ(n)が分かるので、公開鍵から秘密鍵dを入手出来る。しかしnの素因数分解は今のところ多項式時間では解けないと予想されている。

参考

多項式時間で素因数分解が出来れば、RSA暗号多項式時間で解読される。しかし、RSA暗号多項式時間で解読されれば、多項式時間で素因数分解が可能かどうかは未解決である。

1994年にShorが量子コンピュータを使うと素因数分解が確率的多項式時間で解けることを示した。したがって、量子コンピュータが開発されるとRSA暗号暗号としての意味を失う。