banner

  富山大学 > 理学部・大学院理工学教育部理学領域 > トピックス > 2007年10月
トピックス
 RSA暗号 〜360年の時を越えて〜 (数学科)
D(E(M))=M
この式はなんでしょうか?  M はメッセージを数で表したものです。関数 E (encryption:暗号化)によって M とはまったく異なる数 E(M) に変換されます。さらに他の関数 D (decryption:復号)によって、再び数 M に戻されることを意味しています。関数 E によって数 M とはまったく異なる数 E(M) に暗号化するのです。この式は暗号の最も基本的なシステムを表しています。暗号は、本来公開してはいけない超極秘事項であったのですが、1978年にアメリカの3人の数学者リベスト、シャミール、エイデルマンによって公開鍵暗号(3人の名前−R. L. Rivest, A. Shamir & L. Adelman−の頭文字をとってRSA暗号と呼ばれています)が発表され、これまでの暗号のパラダイムに大変革を起こしました。この暗号は公開することによってその真価を発揮する暗号なのです。
 彼等が着目したのは、なんと今から360年も昔、フランスの数学者フェルマーが発見したフェルマーの小定理と呼ばれる素数に関する定理です。もう1つはコンピュータの弱点を利用することです。現在使われているデジタル方式のコンピュータではその数が2つの素数の積であることがわかっていても、素因数分解には非常に長い時間を要するのです。このRSA暗号は現代の情報通信の安全性を支えていますが、それが360年も昔に発見された定理と、コンピュータの弱点を突くという逆転の発想が生み出したものであったのです。


●合同式  正の整数 m を選んで固定しておく。整数 a, b に対して、 a−b が m で割り切れるとき a と b は m を法として合同であるといい、
a≡b (mod m)

と書く。例えば、 m=6 に固定すると、
5≡11 (mod 6), 16≡4 (mod 6)

のように表すことができる。さらに、合同式では次の計算式が成り立つ。
  1. a≡b (mod m)  a−b≡0 (mod m)  (例: 5−11=−6≡0 (mod 6), 16−4=12≡0 (mod 6))
  2. a≡b (mod m), c≡d (mod m)  a+c≡b+d (mod m)  (例: 5+16≡11+4 (mod 6) → 21≡15 (mod 6))
  3. a≡b (mod m), c≡d (mod m)  ac≡bd (mod m)  (例: 5・16≡11・4 (mod 6) → 80≡44 (mod 6))

●フェルマーの小定理  フェルマーがフレニクルへ宛てた手紙(1640年10月18日)に記されていた。オイラーが1742年に再発見するが、後に、フェルマーの小定理と呼ばれるようになる。(フェルマーの大定理はご存知の方が多いのではないだろうか。)

整数 N が p の倍数でないならば Np−1≡1 (mod p)が成り立つ。
よって、任意の整数 Z に対して Zp≡Z (mod p)が成り立つ。

証明  数学的帰納法を用いる。 Zp≡Z (mod p) を仮定する。
(Z+1)p≡Zp+1 (mod p)

を示そう。2項展開
p−1
(Z+1)p=ZpΣ pCi Zp−i+1
i=1

において、 pCi≡0 (mod p) はつぎのことから容易にわかる:一般に、自然数 m>n に対して (m-n) mCn=m m-1Cn であるから、 m と n が素であれば、 mCn は m の倍数である。
 従って、
(Z+1)p≡Zp+1 (mod p)

が成り立つ。このとき、帰納法の仮定より
Zp+1≡Z+1 (mod p)

となるから
(Z+1)p≡Z+1 (mod p)

が示された。
 さて、 Z(Zp−1−1)≡0 (mod p) であるから、 Z が p の倍数でないときは、(因数分解を考えると) Zp−1−1≡0 (mod p) が得られる。


●RSA暗号の仕組 

 ■ 受信者(公開鍵と秘密鍵の生成)
  1. 2つの異なる素数 p, q を選び、その積 n=pq を計算する。
  2. L=(p-1)(q-1) を計算する。
  3. 適当な e を L と素に選ぶ。即ち、 e と L の最大公約数が 1 。
  4. d を ed≡1 (mod L) に取る。(ユークリッドの互除法を用いて見つける。)
  5. n と e を公開する。 d は受信者だけが知っている。

 ■ 送信(公開鍵で暗号化)
  1. 平文 P (plain text)を n−1 以下の自然数 M で表す。
  2. Me≡E(M) (mod n) を計算して、 E(M) を送信する。
 ■ 受信(秘密鍵で復号)
  1. 受信者は E(M)d≡M (mod n) を計算する。 M に復号される。
  2. M を P に書き直す。

n を因数分解して p と q を求めることは難しい。

n が 100 桁なら 74 年、 n が 200 桁なら 27×109 年かかる。いつか遠い将来に実現するかもしれない量子計算機では、多項式時間で因数分解をするアルゴリズムがある。(P. W. Shor 1994年)


●RSA暗号の具体例 

 ■ 受信者(公開鍵と秘密鍵の生成)
  1. 2つの異なる素数 p=11, q=3461 を選び、その積 n=pq=11・3461=38071 を計算する。
  2. L=(p-1)(q-1)=10・3460=34600 を計算する。
  3. 適当な e=99 を L=34600 と素に選ぶ。即ち、 e と L の最大公約数が 1 。
  4. d=699 を ed=99・699=69201=2・34600+1≡1 (mod 34600) に取る。
  5. n=38071 と e=99 を公開する。 d=699 は受信者だけが知っている。

 ■ 送信(公開鍵で暗号化)
  1. 平文 P="A"を n−1=38071−1=38070 以下の自然数 M=65 で表す。
  2. Me=6599≡17764=E(M) (mod 38071) を計算して、 E(M)=17764 を送信する。
     6599=652・49+1=(652)49・65=422549・65
        ≡422549・65 (mod 38071)
        =42252・24+1・65=(42252)24・4225・65=1785062524・274625=(38071・468+33397)24・(38071・7+8128)
        ≡3339724・8128 (mod 38071)

        … このような計算手順を繰り返す … 

        ≡17764 (mod 38071)
 ■ 受信(秘密鍵で復号)
  1. 受信者は E(M)d=17764699≡65=M (mod 38071) を計算する。 M=65 に復号される。
  2. M=65 を P="A" に書き直す。

具体例の検証  M が 11 の倍数なら、 Med≡0≡M (mod 11) である。よって、 M は 11 の倍数でないと仮定する。

Med(M99)699
M99・699
M2・34600+1
M2(10・3460)・M
(M2・3460)10・M
(M2・3460)(11−1)・M
1・M (mod 11)  (∵フェルマーの小定理)
M (mod 11)

となる。同様に
Med≡M (mod 3461)

となる。
 さて、相異なる2つの素数 p, q に対して
A≡B (mod p), A≡B (mod q)

ならば
A≡B (mod pq)

であることは、 A−B の因数分解から明らかである。
 従って、
Med≡M (mod 11・3461)

が成り立つ。


●補足 

  • 公開鍵暗号(非対称鍵暗号)に対して従来の暗号を秘密鍵暗号(対称鍵暗号;共通鍵暗号)と呼ぶ。その歴史は非常に古く、紀元前19世紀、古代エジプトで用いられたヒエログリフ(象形文字)にはじまる。(→ 暗号の歴史(三菱電気株式会社)
  • 秘密鍵暗号は平文がある程度以上の長さになると解読可能な場合がある(各言語によって、特定の文字が頻発することが手がかりになって、解読される危険性がある。英語では文字出現度は e, t, a, o, i, n, s, … 順であるといわれている。語頭に s がくる場合が多い)が、文字置換をいくつか組み合わせることによりかなり強力な暗号が得られる。ただし暗号化の鍵と復号用の鍵が同じである。(乱数表などの鍵を盗まれることなく遠隔地の味方に届けるのが大変。鍵を輸送中の飛行機が敵の制圧地域に不時着でもすれば一大事である。)
  • 1976年にデュフイとヘルマンによって出された公開鍵暗号のアイデアは、2年後の1978年にリベスト、シャミール、エイデルマンの3人の数学者が具体的な方法を与えた。公開鍵暗号は公開することによってはじめて暗号としての機能をはたすのであり、しかもこのことにより多くの研究者によって暗号の研究が活発におこなわれるようになった。
  • 暗号化の鍵と復号用の鍵が異なる暗号系であれば、安全性は飛躍的に高まる。さらに、暗号化の鍵が公開されていれば暗号化の鍵を知っている人はだれでも秘密通信の送信者になることができる。つまり、不特定多数の相互間通信が可能になる。(電話帳から番号を知って電話が出来るように、暗号化鍵帳を公開しておけばよい。)
  • 従来の暗号(秘密鍵暗号)では、規則(アルゴリズム)を公開しても安全であることが保障されている場合でも、公開しなければなお安全であるといえるし、また公開された規則の弱点を見いだしたとき、その事実を公開しないであろうから公開することによる利点はほとんどないことになる。
  • 公開鍵暗号では、送信者の秘密鍵で暗号化することで署名をおこなうことができる。従って受信者(検証者)は送信の途中でメッセージが改ざんされていないこと、および送信者本人からのメッセージであることを確かめることができる。
  • RSA暗号の欠点は、暗号化および復号に時間がかかることである。そこで実用上 e は小さい方が有用である。しかし、 e が小さすぎると n を因数分解しなくても暗号が破られる危険性のあることを、加藤やシモンズらが示唆している。現在の暗号通信は、始めに公開鍵暗号を使って秘密鍵暗号の共通鍵を通信相手に安全に送信し、その後は安全に送られてきた共通鍵を使って安全に通信をおこなう。これにより、暗号通信の安全性と高速性を両立している。
  • 記事:教授 菅谷 孝
    戻る

    Last modified 2007.10.01
    富山大学理学部広報委員会情報・広報部会作成