だいぶ以前、大学時代「数学科教育法」という授業に参加していたとき、公開鍵暗号として有名なRSA暗号というものについて、すこし知っていたことを発表しました。しかし、その暗号が具体的にどのように使われるのかいまいちピンと来ていなかったから、ちょっと整理するために書いてみます。教育法の講義だから、高校生に授業するときのネタとして覚えておきたいという動機だったのですが、そういう素材としてはちょっと難易度が高いものかも知れません。


―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*

たとえばインターネットで買い物をするときに、クレジットカードの番号を入力・送信するようなことがよくあるが、途中で情報が流出して、誰かにその番号を盗み見られるようだとまずい。そこでRSA暗号を使うと、次のようにカード番号を暗号化して送信することができる。

買い物をする人をA、注文を受ける側をB、Aさんのカード番号をxとする。Bはある数n,eを公開していて（ただしn>x）、Aさん側はx^e（xのe乗）を計算し、それをnで割った余りcを暗号文としてBに送信する。ここでeはxを暗号化しているから「公開鍵」と呼ばれる。で、cを受け取ったBは、Bだけが持っている「秘密鍵」dを使って、c^dを計算し、それをnで割ると余りがxとなって、カード番号を受け取ることに成功する（＊1）。

（実際のインターネットの商取引が全くこのままの形で行われているのかどうかは分からないが、ネットで使われる暗号は基本的にこのようなものではあるまいか。またアルファベットも数字で置き換えることが可能だから、「パスワード」の暗号化も同じ方法で出来る。）

で、その原理は、高校生にきちんと伝えるのは困難かもしれず、実際には適当にはしょりながら説明することになるだろうけど、だいたい以下の通り。

まず、記号の説明。
整数a, b, nがあって、a-bがnで割り切れるとき、
a ≡ b (mod n)
と書き、「aとbはnを法として合同である」と読む。これは、aをnで割ったときの余りと、bをnで割ったときの余りが同じである、といいかえてもよい。
また、aをnで割ったときの余りがcなら a ≡ c (mod n) で、とくにaがnで割り切れるなら a ≡ 0 (mod n).
ここで、a ≡ b, c ≡ d (mod n) のとき
a + c ≡ b + d (mod n),
a - c ≡ b - d (mod n),
ac ≡ bd (mod n)
のように、「≡」を「＝」のように思って和、差、積が計算できるということが重要で、以下この事実を暗に使う。

（高校のカリキュラムでは合同式は基本的にやらないようだ。ただ僕が高校生のときはやらされたし、今も合同式の話が出来る高校の教室があると信じたい。）

で、次の定理が必要になる。

■フェルマーの小定理:
pが素数、xが整数のとき、
x^p ≡ x (mod p).
とくにxがpで割り切れないなら
x^{ p-1} ≡ 1 (mod p). (証明は＊2)

つまり最初の式は、x^p-xがpで割り切れる、後の式はx^{ p-1} -1がpで割り切れるということ。。。
（あ、素数というのは、2,3,5,7,11,13のように、「1とそれ自身以外では割り切れない正の整数」のことです。ただし1は素数に含めません。）

で、カード番号の受け渡しの話で使われたRSA暗号は以下の原理に基づいている。

p,qを相異なる素数とし、n = pq, φ(n) = (p-1)(q-1) とする。
またeをφ(n)と互いに素な正の整数とする（つまりeとφ(n)の最大公約数が1ということ）。
こういう状況のとき、ed + φ(n)f = 1 となる整数d,fが存在することが知られていて、またここでd > 0としてよいことが分かる。このとき、
0≦x< n なら　x^{ ed} ≡ x (mod n).

∵）k = -fとすれば ed = kφ(n)+1 = k(p-1)(q-1)+1となるが
i ) xがpの倍数でないとき
フェルマーの小定理から x^{ p-1} ≡ 1 (mod p) となるから、
x^{ ed} = x^{ 1+k(p-1)(q-1)} = x(x^{ k(p-1)(q-1)} )
= x(x^{ p-1} )^{ k(q-1)} ≡ x (mod p).
ii ) xがpの倍数のとき
x^{ ed} ≡ x ≡0 (mod p).
i ),ii )より、x^{ ed} -x はpの倍数。同様にして、x^{ ed} -x はqの倍数であることも分かる。
結局、x^{ ed} -x は n=pq の倍数となる（∵p,qは相異なる素数）。つまり
x^{ ed} ≡ x (mod n).　□

上のn,eは「公開」されており、p, q, d は「秘密」になっている。
もとのインターネットでの買い物の話に戻ると、Aさんはn,eを知らされているが、p, q, d はBの側しか知らない。
x^eをnで割った余りがcということは x^e ≡ c (mod n)で、cが暗号文としてBに送信されたが
c^d ≡ (x^e)^d = x^{ ed} ≡ x (mod n).
つまりカード番号xを、Aは公開鍵eで暗号化してBに送ったが、BはBだけが持っている秘密鍵dでそれを解読してxを知る、ということになる。

p,qは秘密、従ってφ(n)=(p-1)(q-1)もBしか知らないということが大事で、eとφ(n)を知っている者は秘密鍵も知ることが出来る。
実際、eとφ(n)は互いに素だったから、eu+φ(n)v = 1 となる整数u,vがある。このようなuを見つければ（それはそう難しくない）、dと一致はしないかもしれないが、秘密鍵としてdと全く同じように使え、暗号文を見破ることが出来る。

n = pqで、nは公開されているのだから、秘密のp,qを求めるのは難しくないようにも見える。nが小さな数なら実際難しくないが、ただ巨大な数になってくると、素因数p,qに分解するのは一般に難しいことと信じられている。
仮にnが100桁を超える数だとすると、p,qは同時に50桁を超える可能性があるが、例えば10^50までに存在する素数の個数は、素数定理によっておよそ(10^50)/log(10^50)≒8.7×10^47個。単純に考えると、pやqを知るには、これだけの素数について１つ１つnを割る計算をしなければならないが、１つの計算に1/10^10秒しかかからなかったとしても、最悪10^30年（100万年の1兆倍の1兆倍）以上かかることになる。
ただ因数分解や素数について得られている知識から、実際はそんなしらみつぶしの計算はやらなくてよい。事実、最近は数百台のコンピュータを連結して、効率的な方法で何ヶ月か計算させ続けることで、困難と思われていた百数十桁の数の分解に成功したりということも起きている。で、nの桁数を上げていくことで、現在も暗号の安全性を保つことが図られていると聞く。

つまり現在のところ電子化社会の秩序は、「大きな数の素因数分解の難しさ」に負う部分が非常に大きいといえる。


上の例はAからの暗号文をBが解く、という一方通行の暗号になっている。
双方向にするためには、上に現れたn, p, q, e, dのような数を二組用意する。
つまりn_1, p_1, q_1, e_1, d_1; n_2, p_2, q_2, e_2, d_2 を用意し、ここで n_1, e_1, n_2, e_2 は公開され、p_1, q_1, d_1 はAが所有する秘密、p_2, q_2, d_2 はBが所有する秘密とする。
このときAからBへ、またBからAへ暗号を送るのに、上と全く同じ方法でもやれるがそれだと面白くないから、次のようにする。
Aからxを暗号化してBに送るとき、まず秘密鍵d_1で暗号化して、
x^d_1 ≡ y (mod n_1)
となったとする。次にyを公開鍵e_2で暗号化して
y^e_2 ≡ z (mod n_2)
として、zをBに向けて送信する。Bは秘密鍵d_2でzを開錠できて
z^d_2 ≡ y (mod n_2).
yはまた公開鍵e_1で解読できて
y^e_1 ≡ x (mod n_1).
つまり、Bは元の文xを得られた。
BからAに暗号を送るときも同様にする。公開鍵e_1でyを解読できるということで、Bはそれが秘密鍵d_1で施錠されたものだとわかり、送信者がAであることが確かめられるという利点がある。つまりこれは「デジタル署名つき」の暗号となる。



＊1：ただcを傍受した者がいたら、n,eが公開されていてx^e-cがnで割り切れることから、もしxが小さな数なら実行可能な計算の範囲内でxを推測できてしまうかも知れない。だからxはカード番号でも16桁に限らず、もっと大きな数でもよいことにして、その下16桁をカード番号と読むことにすれば、暗号文cの傍受者もxを特定するのがより困難になるのではないか（xをカード番号そのままにしても暗号は充分実用にたえる、と言っている本も見たので、実際は16桁のままやっているのかも知れない）。


＊2:
pが素数、xをpで割り切れない整数とする。
x, 2x, 3x, ... ,(p-1)x をそれぞれpで割ったときの余りは全て異なっている。
（∵ 相異なるs,t(0< s< t< p) について、sx,txをpで割ったときの余りが等しいとすると、tx-sx = (t-s)x はpで割り切れる。pは素数だからt-s かxのどちらかはpで割り切れることになるが、仮定からxはpで割れず、また 0< t-s< p よりt-sもpで割れないから矛盾する。）
そこでxをpで割ったときの余りをr_1、 2xをpで割ったときの余りをr_2、 3xをpで割ったときの余りをr_3,...などとする。
上で述べたことから、r_1, r_2, ... ,r_{ p-1} は全て異なっていて、0を含まないこともすぐ分かるから、これらは1,2, ... ,p-1を並べ替えたものである。これと
x≡r_1、 2x≡r_2、 ... 、(p-1)x≡r_{ p-1} (mod p)
であることを合わせると、上の合同式に関する注意から
1・2・3・...・(p-1)・x^{ p-1} = x・2x・3x・...・(p-1)x
≡ r_1・r_2・r_3・...・r_{ p-1} = 1・2・3・...・(p-1) (mod p).
よって、
1・2・3・...・(p-1)・x^{ p-1} - 1・2・3・...・(p-1) = 1・2・3・...・(p-1)・(x^{ p-1} -1)
はpで割り切れる。素数pは 1・2・3・...・(p-1)を割り切らないから、x^{ p-1}-1がpで割り切れる。
よって
x^{ p-1} ≡ 1 (mod p).
xがpで割り切れるときは、x^p-x = x(x^{ p-1} -1)がpで割り切れるのは明らかだから
x^p ≡ x (mod p). □


(c) 2009 ntr ,all rights reserved.