RSA暗号体験入門
目次 | 第１章 | 第２章 | 第３章 | 第４章
本章ではRSA暗号に関する研究を行う人を対象に，より深い内容について説明します。
そのため，単に公開鍵暗号やRSA暗号の概要を知りたいだけの人は読む必要はありません。
RSA暗号によって暗号化や復号化などの処理を行う際に，もし全く工夫のない計算手
順を取れば，それは膨大な計算量となるでしょう。例えば，111＾37 mod 323を計算するこ
とを考えます。単純な方法では，111に自分自身を36回掛けて（非常に大きな値になる），
それを323で割った余りを求めることになります。
この程度であればコンピュータを用いれば簡単に計算できますが，
もしここで用いた数を100桁以上に増やした場合はどうでしょうか。
実際RSA暗号が安全であるためには，数は150桁は必要です。この方法を用いて150桁の
数を150桁の数でべき乗するとなると，どんなコンピュータを用いても人間の寿命よりも
はるかに長い時間を要することになるでしょう。したがって，この方法ではRSA暗号を実
用化することは不可能です。そこで，もっと効率的に計算できる方法が求められます。
実はそのような単純な計算方法よりもずっと効率的な方法は存在します。すなわち，乗算
をするたびに剰余を取っていく方法です。この方法を用いると，上の例の式を次のよう
に計算できます。
111＾2 mod 323＝111＊111 mod 323＝12321 mod 323＝47
111＾3 mod 323＝111＊47 mod 323＝5217 mod 323＝49
111＾4 mod 323＝111＊49 mod 323＝5439 mod 323＝271
・・・・・・・・・・
111＾37 mod 323＝111＊305 mod 323＝33855 mod 323＝263
この方法では，36回の小さな乗算と36回の小さな除算により値が大きくならないため，
上の単純な方法と比べると圧倒的に計算量が少なくて済みます。
しかし，これでもRSAで使われる大きさの指数ではまだ実現不可能なほど計算量が多いのです。
ただしそれほど心配することはありません。実は，これよりもさらに効率的な方法が存在します。具体的には以下の通りです。
最初に指数（上の例では37）の２進表現を求め，自分自身の値を１に設定しておきます。
まず，その２進表現の左端の値から見ていきます。もし１の場合は，自分自身の平方にその元
になる数（上の例では111）を乗じます。また，もし０の場合は，自分自身を平方します。
次に，ここで求められた値の剰余をmod nで取ります。この値が次の２進表現の値を見る際の自
分自身の値となります。以上の操作を２進表現の右端まで見終わるまで繰り返します。この作業に
よって，非常に効率的に暗号化や復号化などの計算ができるようになります。
では，ここで実際に計算例を示しましょう。
上の例では111を37乗しましたが，指数の37は２進表現では100101と表されます。
また，最初に自分自身の値を１に設定しておきます。
この左端の値は１なので，１を平方して元になる数111で乗じます。さらに，その値の剰
余をmod 323で取ります。
つまり，111 mod 323となります。次に，２進表現の左から２番目の値
を見ると０なので，自分自身の値を平方してその剰余をmod 323で取ります。
つまり，
111＾2 mod 323＝111＾2 mod 323＝12321 mod 323＝47
となります。次に，２進表現の左から３番目の値を見ると０なので，自分自身の値を平方して
その剰余をmod 323で取ります。つまり，
111＾4 mod 323＝47＾2 mod 323＝2209 mod 323＝271
となります。次に，２進表現の左から４番目の値を見ると１なので，自分自身の値を平方して，
さらに元になる数111で乗じ，その剰余をmod 323で取ります。つまり，
111＾9 mod 323＝271＾2＊111 mod 323＝8151951 mod 323＝77
となります。次に，２進表現の左から５番目の値を見ると０なので，自分自身の値を平方して
その剰余をmod 323で取ります。つまり，
111＾18 mod 323＝77＾2 mod 323＝5929 mod 323＝115
となります。次に，２進表現の左から６番目（最後）の値を見ると１なので，自分自身の値を
平方して，さらに元になる数111で乗じ，その剰余をmod 323で取ります。つまり，
111＾37 mod 323＝115＾2＊111 mod 323＝1467975 mod 323＝263
となります。
以上のように，111＾37 mod 323をたった６回の小さな乗算と除算によって求めること
ができます。この方法を用いることにより，たとえ扱う数が150桁を超えていようとも，
RSA暗号の処理の効率は十分現実的なものとなります。
暗号の処理を行うためには，暗号化のための鍵（公開鍵）と復号化のための鍵（秘密鍵）
を予め作っておく必要があります。
そのための手順は第２章で説明しましたが，復習も兼ねて以下にもう一度示しておきます。
[1] ２つの大きな素数ｐ，ｑを選択する。
[2] ｎ＝ｐｑとφ(ｎ)＝（ｐ−１）（ｑ−１）を計算する。このｎを係数と呼ぶ。
[3] gcd（ｅ,φ(ｎ)）＝１の関係をもつ乱数ｅ（公開指数）を選択する。この公開指数
ｅと係数ｎが公開鍵（ｅ,ｎ）となる。
[4] 拡張Euclidアルゴリズムを用いて，１＝ｄｅ mod φ(ｎ)となるｄ（秘密指数）を計算する。
つまり，mod φ(ｎ)でのｅの乗法の逆数を探し，これをd（秘密指数）とする。この秘密指数
ｄと係数ｎが秘密鍵（ｄ,ｎ）となる。
[5] 公開鍵（ｅ,ｎ）を直接公開する。ｐ，ｑ，ｄは誰にも知られないようにしておく。
以上の手順により，公開鍵（ｅ,ｎ）と秘密鍵（ｄ,ｎ）を作成することができます。以下
にその過程の詳細について述べます。
[1]で選択した素数ｐ，ｑは，それぞれ256ビット前後が一般的です。
素数の数は無限ですが，数が大きくなればなるほど，その割合は小さくなります。無作為
に選んだ数ｐが素数である確率は，約1/ln ｐです。100桁の数では，それが素数であ
る確率は約230分の1です。素数を見つける場合，√ｐ以下のすべての数でｐを割って
みて，割り切れるかどうかを調べていく方法もありますが，桁数が大きくなると膨大な時間が
掛かってしまい，現実的に不可能です。実際のところ，ある大きな数が絶対に素数かど
うかを判定するための現実的な方法は知られていません。
しかし，ある数がおそらく素数であろうことを判定する方法はあります。
その方法を以下に示します（証明にはフェルマーの小定理を用いますがここでは触れません）。
(1) 適当な範囲で奇数の乱数ｎを選択する。
(2) 小さい素数でｎが割り切れるかどうかを調べ，もし因数が見つかれば，手順(1)に戻
る。
(3) 以下の作業を，ｎが素数でないと証明されるか，ｎが素数であると感じるのに必要
な回数だけ繰り返す。
(3-1) ａを無作為に選択し，a^c mod n を計算する（ｃはn-1=(2^b)*c となるよう
な奇数）。a^c mod n を計算する間，mod n での平方を計算するたびに，その結果が１で
あるか調べる。もしそうであれば，その平方された数が±１（１の平方根）であるかどう
かを調べる。もし異なれば，ｎは素数ではない。
(3-2) 次に，a^c mod n の計算の結果が±１であれば，ｎはこのａについては素数か
どうかの検査は合格である。そうでなければ，最高でもｂ−１回その結果をそれを平方し
たもので置き換え，それが±１であるかどうかを調べる。もし１であれば，ｎは素数では
ない。もし−１ならば，ｎはａについて素数かどうかの検査は合格である。もしｂ−１回
平方し終わったら，ｎは素数ではない。
この方法では，その数を調べるのに時間を掛ければ掛けるほど，
その数が素数である確率は高まります。
[3]でｅを選択しますが，これはどんな値でもよいというわけではありません。
φ(ｎ)＝（ｐ−１）（ｑ−１）の最小公倍数と互いに素な数でなければなりません。
しかしながら，実際にはφ(ｎ)を因数分解せずに，Euclidアルゴリズムを用いて，
gcd（φ(ｎ),ｅ）＝１を確認できます。
以下にEuclidアルゴリズム（最大公約数を求るためのアルゴリズム）を簡単に示します。
ただし，ａとｂの最大公約数を求めるものとします。
(1) ａとｂを交換することによりａ＞ｂとする。
(2) ｃ＝ａ mod ｂなるｃを見つける。もしＣ＝０なら終了する。
(3) ａ＜＝ｂ＜＝ｃとする。手順(1)に戻る。
これによりｅを求めることができます。
次に，[4]でｄを求めますが，そのためには拡張Euclidアルゴリズムを用います。以下に拡
張Euclidアルゴリズムを簡単に示します。
(1) (u1,u2,u3)=(1,u,0), (v1,v2,v3)=(0,v,1)
(2) v2=0になるまで以下の計算を繰り返す。
(2-1) (t1,t2,t3)=(u1,u2,u3)-(v1,v2,v3)(u2/v2) （ただしu2/v2はu2をv2で割
ったときの商）
(2-2) (u1,u2,u3)=(v1,v2,v3)
(2-3) (v1,v2,v3)=(t1,t2,t3)
これにより，ｄを求めることができます。
実はｅを常に同じ値にしてもRSA暗号の安全性は低くならないことが分かっています。
これを利用して，ｅが小さいか計算しやすい値にすれば，そのｅを用いた計算は効率的に
なります。ｄはｅを使って求められる（その逆でも構わない）ので，ｅを小さな定数にするこ
とは容易です。これを利用すると，ｄを使った復号化の処理時間は変わりませんが，ｅを
使った暗号化の処理時間はより短くできます。
ただし，ｄの値を小さくすることはできません。
もしｄの値が小さければ，攻撃者が暗号文を解読しようとしたときにｄを探す回数が少な
くなってしまうからです。つまり，ｅは小さくてもRSA暗号の安全性に影響は生じませんが，
ｄは小さいと安全性が保たれないということです。
よく利用されるｅの値は３と６５５３７です。３をよく使う理由は，２は(p-1)(q-1)
と互いに素でないため使えませんが，３は素になりうまく使えるからです。
しかも，暗号する際にたった２回乗算をするだけで済むので非常に効率的なのです。
ｅに３を用いても，いくつかの現実的な使い方に関する制限を守っていれば，
RSA暗号の安全性を弱めることがないことが知られています。
ｅを３として普通にRSAで暗号化する場合，いくつかの問題が発生します。１つ目は，
暗号化される平文Ｍが小さい場合，特にＭがｎの３乗根より小さい場合，Ｍを３乗してmod
nで余りを取っても，結果は単にＭとなり，簡単に暗号文から平文を求められてしまうと
いう事です。この問題は，暗号化する前に平文Ｍに乱数をパディング（連結）して，そ
の３乗がｎよりも大きくなるようにしてやることによって解決されます。
また，３を公開指数ｅとして使う場合の問題として，３がφ(n)と互いに素である場合
にしかうまく働かないということがあります（そうでないと逆数ｄを持たない）。
３とφ(ｎ)＝（ｐ−１）（ｑ−１）が互いに素になるためには，
どのようにｐとｑを選択するのかが問題となります。
ｐ−１が３と互いに素であることを確かにするためには，ｐ mod ３を２にすればよいでしょう。
そうすれば，ｐ−１mod ３は１となります。
同様に，ｑ mod ３も２にすればよいです。
選択する素数 mod ３を，２にするには，奇数の乱数を３倍して２を加え，
素数かどうか調べる値としてその値を使えばよい。
また，公開指数ｅの値として65537もよく使われますが，その理由としては，
これが素数であり，しかも65537＝2＾16＋1 が成り立つためです。これを２進表現したものは１を
２つしか含まないので，この値でべき乗するには17回の乗算で済みます。
これは３を指数ｅとした場合の２回と比べると多いですが，
512ビットを無作為に選択した場合に必要とする平均乗算回数768回と比べると圧倒的に少ないといえます。
また，65537をｅとして使う場合，ｅに３を使う場合に生じる問題をほとんど避けることが可能です。
ｅに３を用いた場合の問題として，平文Ｍの３乗Ｍ＾３が係数ｎより小さい場合に簡単
に暗号文から平文Ｍを求められてしまうということがありました。
しかし，ｅが65537の場合には，Ｍ＾65537がｎより小さくなることはほとんどないので，
暗号文の65537乗根を求められて平文を知られてしまうということにはなりません。
また，ｅに３を用いた場合，φ(n)が３と互いに素であるようなｎを選ばなければなりませんでした。
しかし，ｅが65537の場合には，ｐ mod 65537またはｑ mod 65537が１になったらそれを捨て
るだけでよく，その確率は非常に低いので，ｎを見つけるのは非常に簡単です。
以上のように，RSA暗号の公開指数ｅを３または65537にすると暗号化の処理が非常
に簡単になるので，公開指数ｅの選択の際にはこれら値を用いるとよいでしょう。
RSAで暗号化する際に，平文ｍが係数ｎと比べて非常に短い場合，いくつかの問題が
生じます。例えば，２．４で示した簡単な電子投票の例で，暗号化されるべき投票内容
Ｍが各候補者の名前ではなく各候補者に付けられた１桁の番号（２〜７）であったとします。
このとき，投票者が選んだ候補者の番号（２〜７のどれか）が暗号化されて送られること
になります。RSAでの暗号化の計算方法はＭ＾ｅ mod ｎを求めることなので，Ｍが１桁の
数であればｅが小さいとき（普通はｅが小さくても安全性は保証される）にはＭ＾ｅ＜ｎ
となってしまいます。
したがって，このとき送信される暗号文はＭ＾ｅとなります。
これを盗聴した者は，ｅの値を知っている場合，簡単に投票内容Ｍを知ることができるでしょう。
また，ｅが大きな値でありＭ＾ｅ＞ｎとなる場合であっても，Ｍが６通りしかないので
暗号文Ｍ＾ｅ mod ｎも当然６通りしか存在しありません。そのため，暗号文の盗聴者は，その
盗聴して得られた暗号文と６通りの各候補者に付けられた番号を暗号化した結果とを比較
していき，一致するものを調べれば簡単に投票内容を知ることができます。つまり，暗号化
したものが盗聴して得られた暗号文と同一の内容となる候補者の番号が投票内容であるこ
とから，盗聴者は誰が誰に投票したかを知ることができるのです。
実際RSA暗号では，このような平文の値が小さい場合でも安全性を確保できるようにする
ために，ＰＫＣＳ（Public-Key Cryptography Standard）と呼ばれる符号化の手段が開発
されています。しかし，それは一般的なRSAの利用で用いられる手法であり，上の例のよ
うに平文の長さが常に一定の場合には，後述するもっと単純化されたパディングの手法を
用いる方が効率的です。
単純化されたパディングの手法とは以下の通りです。すなわち，暗号化する前に，平
文（投票内容）の左側に０でない正の乱数をパディング（連結）すればよいのです。乱
数をパディングしてできた値は，係数ｎの桁数よりも１桁少ない程度の大きさが理想的です。
ただし，パディングしてできた値は，ｎ未満でなくてはならありません。この手法を用い
ることにより，上述した問題はすべて解決されます。
ちなみに，ＰＫＣＳでは，パディングされた乱数と元の平文データとの境目を表すための
特別の数をその間に挿入したりする必要があるので，
このような単純に乱数をパディングするだけの手法よりも若干複雑になります。
ところで，たった１桁の平文ｍの前（左側）に乱数ｒを連結した場合，平文ｍが常に同
じ場合には暗号文（ｒ.ｍ）＾ｅ mod ｎの１の位（右端）に偏りは生じないのでしょうか。
ただし，”.”を連結演算子とします。一見すると，ｍが同じものどうしではそれぞれ暗号文
の１の位が等しくなる，あるいは何らかの偏りが生じるように感じられるかもしれありません。
しかし，実はそのようなことは全くありません。それどころか，この暗号文，すなわち平文ｍの
左側に乱数ｒを連結したものを暗号化したものは，平文ｍにどのような偏りが存在してい
ようとも，その暗号文全体において全く数字的な偏りは生じないのです。以下にそれを
証明してみましょう。
”.”を連結演算子，ｘ及びｙを非負の整数とすると，左側のｒ（ただしｒ>>ｍ）は完
全にランダムな値なので，
（ｒ.ｍ）＾ｅ＝ｎ＊ｘ＋ｙ （ｎ＞ｙ）
と表すとき，ｘは１の位の値も含めてランダムな値となります（均等にばらつく）。
ところで，ある程度以上（２桁以上）の素数ｐ，ｑの１の位の値はすべて必ず１，３，
７，９のどれかです。したがって，ｎ＝ｐ＊ｑの１の位の値はすべて必ず１，３，７，
９のどれかとなります。
これら４つの数は，次のような興味深い数学的性質を持ちます。
すなわち，ｎの１の位の候補１，３，７，９のどれに対して０から９までの数を掛けても，それらの答
えの１の位には必ず０から９までの数がすべて１つずつ均等に現れるのです。
この１，３，７，９の数学的性質から，ｎ＊ｘの値は１の位も含めて必ずランダムな値となります。
したがって，ｒがランダムであれば，（ｒ.ｍ）＾ｅもランダムなので，
ｙの値は１の位を含めて必ずランダムな値となります。
以上のことから，たとえｍ，ｅ，ｎが常に同じでも，ｒが乱数で常に異なれば，
（ｒ.ｍ）＾ｅ mod ｎの１の位の値は完全に０から９まで均等にばらつくことになります。
したがって，パディングする際に平文ｍを右端に連結しても全く問題ないといえます。
目次 | 第１章 | 第２章 | 第３章 | 第４章
CyberSyndrome - The Proxy Search Engine