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暗号は暗号としての意味を失う。

関連用語

  • 情報科学
  • 暗号


リスト::数学関連

ネットの話題: RSA暗号

人気

新着

新着ブログ: RSA暗号