公開鍵暗号:RSA暗号

 1978年R. L. Rivest, A. Shamir, L. M. Adleman は新しい公開鍵暗号システムを発表しました。この暗号は現在,3人の名前を取ってRSA暗号と呼ばれ,現在インターネット上で実際に 広く使われています。

 ここでは,公開鍵暗号とその中で代表的な暗号である RSA暗号を紹介します。

公開鍵暗号

 現在使われている暗号の分類法で,共通鍵暗号,公開鍵暗号というものがあります。

 暗号は

平文→(暗号化)→暗号文→(復号)→平文

のように,暗号化と復号によって構成されます。この暗号化と復号では各々鍵を使います,それらをそれぞれ暗号化鍵,復号鍵と言います。

 普通の暗号は

暗号化鍵と復号鍵が同じか,一方から他方が簡単に計算できる

性質があります。この場合,暗号化鍵または復号鍵の両方を秘密にする必要があります。このような暗号を共通鍵暗号と言います。

 これに対して,暗号化鍵からは復号鍵が分からない暗号を作ることができます。このような暗号では,暗号化鍵を公開しても,復号鍵は分かりません。このように

暗号化鍵を公開する暗号を公開鍵暗号

と言います。公開鍵暗号は,現在のインターネット社会では大変便利な暗号として,色々な場面で使われています。


 例えば,Cさんがインターネットで買い物をするとします。あるB社にインターネットを使って商品を注文するとき,注文の内容は相手のB社だけに知らせて,(プライバシーの保護の視点から)他の人には分からないようにしたいと思うのは自然です。このような状況は,公開鍵暗号を使うことで実現できます。

 それには,B社は公開鍵暗号を使用し,

暗号化鍵を広く公開します

この鍵は広く公開されているので,誰でも使うことができます。そこでCさんは

この暗号化鍵を使って注文書を暗号文にします

そしてそれをB社に送ります。

B社では暗号化された注文書を復号鍵を使って元の注文書に戻します。

 ここで,B社以外の人或いは組織が暗号化された注文書を見たとしても,復号鍵が分からないので,元の注文書の中身は分かりません。

 これが目的とするものでした。


 では,暗号化鍵から,復号鍵が分からないような暗号は作れるのでしょうか?

 このアイデアが始めて提案されたとき,多くの人が実現に懐疑的でした。実際,数学的に見れば,暗号化鍵と復号鍵は互いに逆写像になっています。当然ですが,逆写像は元の写像から一 通りに決ります。ですから,数学的に見れば,暗号化鍵から,復号鍵が一通りに決定します。従って,暗号化鍵から復号鍵を求めることができる筈です。

 確かに理論的に見れば,暗号化鍵から復号鍵を求めることができます。しかし,ここで着目するのは理論的と言う言葉です。数学で理論的といった場合,それを計算する時間について特に断らない限り無制限です。ですから,求めることができるが,時間が大変かかると言い換えると,求める性質は数学の理論と矛盾しません。

 つまり,正確に言うと,

暗号化鍵から復号鍵を求めるには大変時間がかかる

というものなら作れそうです。そしてこの復号鍵を求める時間が,暗号を解読として意味が無いくらい長くかかるものであれば,実際に使うことが出来ます。

 そしてこの性質を満たす暗号として始めて提案されたのがこのRSA暗号でした。

 以下,RSA暗号について説明します。現在使われている,公開鍵暗号としてはRSA暗号の他,離散対数型公開鍵暗号があります。これについては項を改めて説明します。

RSA暗号の数学的仕組み

 nを相異なる素数p,p,・・・,pの積とします。 e を gcd(e,φ(n))=1 となる正整数とします。 ここで,φ(n) は nのオイラー関数です。このとき,,φ(n) を法とするeの逆元が存在します(整数の合同参照)。それを d (1≦d≦p-1)とします。このとき,

ed ≡ 1 (mod φ(n))

が成立します。従って x (0≦x<n)に対して,オイラーの定理から,

xed≡x (mod n)

となります。(gcd(x,n)>0のときはオイラーの定理は使えませんが,この場合でも上の式は成立することが分かります。)


 上の性質からxの範囲が0≦x<n であることを使うと,dを知っていれば,xeから x が求められることになります。従って

x →(暗号化)→ xe →(復号)→ xed≡ x (mod n)

によって,eを暗号化鍵,dを復号鍵とする暗号が得られます。ここまでは指数型暗号(exponentiation cipher)と よく似ています。しかし,1つだけ重要な違いがあります。それは,次のことです。

e から d を計算するとき,φ(n)が必要となります。しかし他方,xから  xe を計算するときはnが必要ですが,φ(n)は必要 はありません。さらに,nからφ(n)を求めるには nの素因数分解が必要になります。

 そこで次のような場合を考えます。

nの素因数分解が難しい場合

この場合は,仮にeを知られても,dを求めることは出来ません。つまりこの場合,e だけを知っていた場合,暗号化は出来ますが,復号は出来ません。

 この場合,eとnを公開し,dとnの素因数分解を秘密にします。

RSA暗号の例

 具体的な例を使って説明しましょう。Tiny Basic で扱える範囲の数ということと,例ということから,実際に使われているものより小さい数を使います。(実際に使われるnは数百桁という大きな整数です。)

まず,

p = 9010279,q =  9623083

として,

n = p ×q = 86706662670157

とします。また例えば,

e = 184436886841

とします。ここで,φ(n)=(p-1)*(q-1)= 86706644036796 と e との最大公約数は 1 となり,上の条件を満たします。そこで,

ed ≡ 1 (mod φ(n))

となるn未満の正整数 d を計算します。この計算は拡張ユークリッドの互除法を使うと高速に計算できます。実際に求めてみると,

d = 70276475859277

となります。

 そこで,e と n の組 (e, n) = (184436886841, 86706662670157) を公開し,n 未満の非負整数 x に対して,

 xe (mod n)

によって暗号化します。例えば,x = 1234567890123 を暗号化するとします。このとき,

e (mod n) = 1234567890123184436886841 (mod 86706662670157) = 17175526914607

となります。この計算は冪乗法を使うと高速に計算できます。17175526914607が暗号文です。これを受け取った側は,これを d 乗してもとの文を求めます。実際,これを計算すると,

17175526914607d (mod n) = 1234567890123

が得られ,復号されたことが分かります。


 d の計算には,φ(n)= 86706644036796 が必要でした。しかし,φ(n) の計算には n の素因数分解が必要です。ここで,

大きな数 n の素因数分解は大変時間がかかる

ことが経験上知られています。ですから,pとqを知らない場合,φ(n) の計算は難しいことになります。

 勿論,この例の数くらいであれば,すぐに因数分解できますが,100桁も越える数が与えられたとき,その因数分解は特別なもの以外できません。

例の続き

 上の例をもう少し,暗号らしい形にして見ましょう。

 暗号は文字などを変換して暗号化するものですから,上の例にある,数を変換するのはあまり適当ではないかもししれません。コンピュータで扱うデータの基本はバイト=8ビットです。ですから,コンピュータで扱われる全てのデータは8ビットの列と見ることができます。この8ビット列を上の方法で,暗号化する方法を考えましょう。

上の例では,n=86706662670157でした。そこで,256 の冪でn未満の最大のものを考えます。今の場合は

2565 < 86706662670157 < 2566

ですから,5が最大冪です。そこで,5個の8ビット列を一まとまりとして

a

b

c

d

e

とします。ここで,各桁は1バイトですから,aからeは0から255までの数です。これを256進法で考えると,

x = a・2564 + b・2563 + c・2562 + d・256 + e

という数が得られます。この数は 0 ≦ x < 2565 を満たします。この x に対して,上の暗号化された数

y = xe (mod n)

を計算します。これは, 0 ≦ y < 86706662670157 < 2566 を満たしますから,これを256進法として表すと

y = f・2565 + g・2564 + h・2563 + i・2562 + j・256 + k

と一通りに表されます。ここで, f から k は 0から255までの数です。これに対して,

f

g

h

i

j

k

と8ビット6個の列と考えて,これを暗号文とします。この方法だと,

5バイト → 6バイト

の暗号化ということが出来ます。


 この考えで,

Basic

という文字列を暗号化してみましょう。この文字列を5個の8ビット列と見ると,各文字のアスキーコードを並べて,

66

97

115

105

99

が得られます。これらを5桁256進数としてみると

66*256^4 + 97*256^3+115*256^2+105*256+99=285102795107

になります。これを暗号化すると,

xe = 285102795107 184436886841  (mod 86706662670157) ≡14123999253219

が得られます。ここで

14123999253219= 12*256^5+216*256^4+127*256^3+245*256^2+82*256+227

ですから,暗号化された8ビット列は

12

216

127

245

82

227

となります。このバイト列は文字列として表示するとは出来ませんので,例えば16進数列として表すと

CD87FF552E3

となります。

暗号の効率と安全性

 RSA暗号は便利な暗号ですが,現実への適用は,効率と安全性との間の微妙でなバランスの上で成立します。pとqが大きな数になればなるほど,n=pqの素因数分解が難しくなり,暗号の安全性は高くなります。他方,p,qが大きくなればなるほど,逆に計算に時間がかかり,暗号の効率は落ちます。現在では200桁程度の数であれば,特別な性質をもつものでなければその素因数分解は難しいとされています。しかし,200桁の数を使って上のような計算を大量に行うのは現在の計算機ででも簡単なこととは言えません。

 計算をいかに効率的に行うかは工夫をする価値のあるものですが,比較的簡単な数学的原理に基づいているRSA暗号の計算法は 標準的な方法に限られます。必要な計算をまとめてみると:

  1. p,q,e,dの計算

  2. 暗号化

  3. 復号

 1.の計算は一度だけ行えば良いので,実際は,余り問題ではありません。2と3が本質的です。

 2.暗号化では冪乗法を使って計算しますが,大きなeに対しても冪乗法でほぼeの桁数に比例する回数で計算できます。この回数はeに比べて非常小さくなり,効率的な計算が可能ですが,ここで,nの桁数が大きいと1回の計算そのものにある程度時間がかかります。従って,効率的には計算できますが,非常に高速と言うわけには行きません。

 3.復号も基本的に2と同じですが,2より少し有利です。復号する側はnの素因数分解を知っています。従って,各素因数についてd乗を冪乗法で計算して,中国の剰余定理を使って復元することが出来ます。これは,プログラムとしては複雑になりますが,高速な計算法です。この方法は実際のRSA暗号でも使われています。


 これを上の例で説明します。

 上の Basic と言う文字列の暗号化数 14123999253219 を復号するには,今の場合,d = 70276475859277ですから,

1412399925321970276475859277 (mod 86706662670157)

を計算します。これをそのまま計算すると,答えとして 285102795107 が得られます。これをそのままではなく,

n=86706662670157=9010279×9623083

に注目して,

1412399925321970276475859277 (mod 9010279)

1412399925321970276475859277 (mod 9623083)

を計算するわけですが,この左辺はそれぞれp,qを法として考えればよい訳ですから,もっと簡単です。実際は,d ではなく,

edp ≡ 1 (mod p-1),edq ≡ 1 (mod q-1)

となるdp=1673257,dq  = 2959903 を使って,

141239992532191673257 (mod 9010279)

141239992532192959903 (mod 9623083)

を計算します。この計算は,法の桁数,冪の桁数がそれぞれ半分程度になっているので,元のものより高速に計算されます。(勿論この例の場合のような桁数では関係ありません。数百桁の場合です。)計算すると,

8557268 (mod 9010279)

9338149 (mod 9623083)

が得られます。これを中国の剰余定理を使って解くと求める 285102795107 が得られます。

まとめ

 RSA暗号は便利な暗号ですが,普通に使われる共通鍵暗号に比べて計算量が多くなります。ですから,大きなファイルを暗号化するには時間がかかり,実用上問題があります。このため,RSA暗号(一般に現在使われている公開鍵暗号)の実際上の利用の多くは,秘密鍵の送信に使われます。

 公開鍵暗号(dを公開鍵,eを復号鍵)を使って,大きな文章Pを暗号化して送る場合を考えます。これは次のように行います。

  • Pを暗号化するには,特定の(秘密鍵)暗号法、例えばDESのようなものを使います。

  • その秘密鍵(暗号化鍵=復号鍵)を適当に作りSとします。

  • ここで,秘密鍵Sは使い捨てにします。つまり一度しか使わないことにします。

  • Sを使って暗号文S(P)を作ります。

  • そして更に,秘密鍵Sを公開鍵暗号方式で暗号化し,それをe(S)とし,e(S)とS(P)を一緒に相手に送ります。

  • 受け取った側はe(S)を復号鍵dを使って,Sを求めます。

  • このSを使ってPを求めます。

このような方法を使えば,公開鍵暗号で大きな文章Pを暗号化して送ったのと同様なことになります。

 上の計算に使ったプログラムRSA.tbt はここにあります。