RSA暗号化アルゴリズムの証明

ホームアルゴリズム入門講座 > RSA暗号化アルゴリズムの証明

RSA暗号化アルゴリズムの証明

n を法とする世界

今回は「なぜ違う鍵で復号化できるか」ということをわかりやすく証明します。少し高度なトピックですが、理解してください。

mod 151乗2乗3乗4乗5乗6乗7乗8乗9乗10乗11乗12乗13乗14乗
1の11111111111111
2の24812481248124
3の39126391263912639
4の41414141414141
5の510510510510510510510
6の66666666666666
7の74131741317413174
8の84218421842184
9の96969696969696
10の1010101010101010101010101010
11の111111111111111111111
12の129361293612936129
13の134711347113471134
14の141141141141141141141

「n を法とする世界」というとき、全ての数は「n で割った余り」になります。たとえば、3を法とする世界では、1と4と7はすべて同じ値です。「n を法とする世界」であることを「 mod n 」と書きます。上の表は「 mod 15 」です。

この表は私がプログラムでつくり出したものです。太字になっているところを見てください。5乗・9乗・13乗はすべてもとの値に戻っています。これがRSA暗号の暗号化と復号化の基本的なアルゴリズムのもとになっています。

x * (p - 1) * (q - 1) + 1

上の表で確認した5乗・9乗・13乗はすべて、「4で割った余りが1」の数です。要するに「 mod n 」を使って、このように表すことができます。

1 = 5 = 9 = 13 (mod 4)

ここで「4」という数字に注目してください。実は、上の表のもとになった「 mod 15 」の 15 は以下のように表すことができます。

p = 3
q = 5
n = p * q

15 は2つの素数の積だったのです。このように考えると、4という数字は以下のように導き出せます。

(p - 1) と (q - 1) の最小公倍数

p - 1 = 3 - 1 = 2
q - 1 = 5 - 1 = 4
2と4の最小公倍数は 4

これを使えば、5,9,13 を一つの数式で表すことができます。

x * {(p - 1) と (q - 1) の最小公倍数} + 1
x = 1,2,3 を代入すれば、5,9,13 が出力される

最小公倍数に限定せず、(p - 1) * (q - 1) で割って1余る数、としても9については成立します。もちろん、17も25も成立します。

x * (p - 1) * (q - 1) + 1

復号化

ところで、暗号化の式は以下のようになります。

平文 m , 暗号 c, e = 35537

c = me (mod n)

ここで、秘密鍵 d があるとすると、復号化の式は以下のようになります。

秘密鍵 d

cd (mod n)

暗号化の際に e乗 したものにさらに d乗 すると元に戻るような d を発見すれば、それが秘密鍵になるということです。分かりますか?

そこで、上で使った式を使います。

d * e = x * (p - 1) * (q - 1) + 1

この式が成り立てばいいわけです。「e乗 したものにさらに d乗 する」というのは「(d * e)乗する」ということですからね。さらに、この式を「(p - 1) * (q - 1) を法とする世界」で考えてみます。

d * e = x * (p - 1) * (q - 1) + 1

「(p - 1) * (q - 1) を法とする世界」で考えると、右辺は途中まで割り切れるので、

d * e = 1 (mod (p - 1) * (q - 1))

オイラー関数

ここで、上の式をさらに整理するために、新たな概念を紹介します。それは、オイラー関数です。

φ() をオイラー関数とすると、

φ(n) = 1からnまでの中で、nと互いに素なものの個数

ただし、φ は「ファイ」と呼ぶ

p が素数のときには φ(p) = p - 1 が成り立ちます。同じように考えて、以下のようになります。

p, q が違いにことなる素数のとき、
n = p * q
とすると
φ(n) = (p - 1) * (q - 1)

これで、上の式がよりきれいに表せます。

d * e = 1 (mod (p - 1) * (q - 1))
φ(n)を用いて、
d * e = 1 (mod φ(n))

この式を言い替えれば、「φ(n)を法とする世界で、d は e の逆数である」となります。d と e をかけると 1 になってますね。

もう一度、復号化のアルゴリズムに戻りましょう。

(暗号化)
c = me (mod n)
(復号化)
b = m((1 / e) * e (mod φ(n)) (mod n)
  = md * e (mod n)
  = m(x * φ(n) + 1) (mod n)

オイラーの定理

とうとう最終段階です。ここでオイラーの定理という概念を導入します。もう一度、一番上の表に戻ってください。

その表で、「8乗」の縦のラインを見てください。そのラインで、1になっているのはどんな数のときですか。あるいは、1になっているのは何個ありますか?

1,2,4,7,8,11,13,14 の 8 個
つまり、
a = 1,2,4,7,8,11,13,14
のとき、
a8 = 1 (mod 15)

これらの数字はいずれも 15 と互いに素な数です。15 より小さく、15 と互いに素な数が 8 個あり、それらはいずれも 8 乗すると1になるのです(15 を法としているから)。これは、φで簡単に表すことができそうです。

a と n が互いに素なとき

aφ(n) = 1 (mod n)

この定理をオイラーの定理と呼びます。そして、これは前の項で導き出した数式に適応できます。一気に、復号化の証明を終わらせてみます。

b = m(x * φ(n) + 1) (mod n)
  = (mφ(n))x * m (mod n)    (←指数定理:高校数学)
  = (1)x * m (mod n)    (←オイラーの定理)
  = m (mod n)

よって、暗号化した後、復号化した b は、平文 m と一致する。

m が n よりも大きいときは成立しません。厳密にはこれよりさらに証明はありますが、ここまでで納得できるのではないかと思います。

ポイントは、一番最初に示した表のように、「n を法とする世界」では「x * (p - 1) * (q - 1) + 1」で循環するということと、オイラーの定理を用いることです。

拡張版ユークリッドの互除法

残る問題は、d を求める方法です。d は以下のように定義されていました。

d * e = 1 (mod φ(n))

これは「d * e をφ(n)で割った余りは 1」ですから、割ったときの商を x とすると、このようにも変形できます。

d * e = x * φ(n) + 1

もちろん、この式はすでに見覚えがあると思いますが、それはさておき、x を -x と置き換えて移項すると、このような式になります。

d * e = (-x) * φ(n) + 1
つまり
φ(n) * x + e * d = 1

ここで、φ(n) = (p - 1) * (q - 1)で、e = 35537 ですから、φ(n) と e は既知で、x と d が未知です。そこで、既知は(a,b)、未知は(x,y) に文字を統一すると、こうなります。

a * x + b * y = 1

このような(x,y)の組を探せば、y が d になります。これを探す方法が「拡張版ユークリッドの互除法」です。

実は、この拡張版ユークリッドの互除法を解くために、eはφ(n)と互いに素なければならないのです。が、実際には e=35537 もしくは e=11 で固定されていますので、深く考える必要はありません。

発展的考察

これで納得できればいいのですが、さらに発展して考えることもできます。まずは、φ(n) を攻略しましょう。

このページの最初の方で最小公倍数に関する記述があったと思います。そこで以下の式を使いました。

x * {(p - 1) と (q - 1) の最小公倍数} + 1

φ(n) = (p - 1) * (q - 1) というのは、{(p - 1) と (q - 1) の最小公倍数} の整数倍です。かりに a 倍であるとします。すると、以下のように変形できます。

{(p - 1) と (q - 1) の最小公倍数} を l とする

φ(n) = a * l
であるから、
φ(n) * x + e * d = 1
は
(l * a) * x + e * d = 1
となり、
l * (a * x) + e * d = 1
である

a,x はともに未知数なので a * x を x で置き換えて、
l * x + e * d = 1

φ(n) で計算するよりも、最小公倍数で計算した方が値が小さいので、より効率的に計算できます。

もう一つの考察は、(x,y)の組で、y が負になったときです。実際に拡張版ユークリッドの互除法を行うと、頻繁に y が負になります。その際にどうするか、という考察です。

まず、式変形をしましょう。式を(x,y)座標でとらえることができるように変形します。

φ(n) * x + e * d = 1
φ(n)を上でやった最小公倍数 l に置き換えて
l * x + e * d = 1
わかりやすくするために置き換える
a = l
b = e
x = x
y = d
よって( * ものけて)
ax + by = 1
これは
y = (-a/b)x + 1/b

ここで、整数解(m,n)が発見されたとします。だたし、n が負なので困っています。そこで、直線の傾きが (-a/b) ですので、点を移動します。(m-b,n+a) に移動しても、a,b ともに整数なので、整数です。

マウスで書いたので、汚いですが許してください。(m,n)を(m-b,n+a)に移動しても、等式は成立します。直線上ですから。

a とは l のことです。つまり、n が負になったら、n + l が秘密鍵 d になるということです。分かってもらえましたか?

まとめ

RSA暗号化のアルゴリズムはこのページで説明し尽くしました。あとはこのアルゴリズムをプログラミング言語で実現するだけです。

とはいえ、このページでは何気なく使っていた

me mod n

も、e = 35537 ですから、単純に計算することはできません。工夫が必要です。そのような考察は、各々のアルゴリズム紹介ページにまわします。

ともあれ、ここまで読み進めることのできたみなさんは、もうほとんどRSA暗号を習得しています。自信を持ってください。