Updated: 2001.07.05
Updated: 2002.06.19

RSA暗号

「Nを法とする世界」

C言語において x % m と書くと「xをmで割った余り」の計算を表します。 さて、全ての計算に関して最後に「mで割算をして余りを求める」計算を 行なうことにすると、0, 1, ..., (m-1) というm種類の整数だけが存在 する世界を考えることができます。 このような世界を「mを法とする世界」といいます。

「mを法とする世界」で左辺と右辺が等しいことを以下のように ≡ で表します。 mを法とする世界で考えていることを表すために、式の右側に 括弧でくくって (mod m) と書きます。

    左辺 ≡ 右辺   (mod m)

「mを法とする世界」では、加算、減算、乗算は可能ですが 割算は行なえません。

  例:
    8 ＋ 7 ≡ 5 (mod 10)
    5 − 7 ≡ 8 (mod 10)
    3 × 4 ≡ 2 (mod 10)
    8 × 4 ≡ 2 (mod 10)
    2 ÷ 4 ≡ ??? (mod 10) ← 計算できません (3または8の可能性があるので)

Nを法とする世界における巾乗計算

Nを法とする世界において巾乗はどうなるかを計算してみましょう。

まず、「10を法とする世界」で巾乗を計算してみます。 「10を法とした世界」ですから、使える文字は 0〜9 の10種類です。 X¹⁴までを表にしてみると X⁵ と X⁹ のところで Xと同じになっていることがわかります。 ちょうど元の数に戻る巾乗の回数は以下のように書くことができます。

• 5 ＝ 1×4 ＋ 1
• 9 ＝ 2×4 ＋ 1

次に77を法とする世界で巾乗計算を計算してみましょう。 X⁶²までを表にしてみると X³¹とX⁶¹のところでXと 同じになっていることがわかります。 ちょうど元の数に戻る巾乗の回数は以下のように書くことができます。

• 31＝1×30＋1
• 61＝2×30＋1

実は、『2つの素数 p, q に対して、 p×q＝mとなる整数 m を法とする世界では、 「p-1とq-1の最小公倍数」をLとして (L×n＋1) 回だけ 整数の巾乗を計算すると元に戻ってしまう』 という性質があるのです。

p=2, q=5の場合を見てみましょう。 p×q=10 で、「p-1とq-1の最小公倍数」は4です。 で、「10を法とする世界」では整数の巾乗を計算すると 確かに 「4×n＋1」 乗のときに元の整数に戻っています。

p=7, q=11の場合を見てみましょう。 p×q=77 で、「p-1とq-1の最小公倍数」は30です。 で、「77を法とする世界」では整数の巾乗を計算すると 確かに「30×n＋1」 乗のときに元の整数に戻っています。

この性質を利用すると、次のような手順でデータの 暗号化、復号化が行えることになります。

• 受信者側の準備
  1. 2つの素数p, qを用意します。
  2. p×q＝mで整数mを求めます。
  3. p-1とq-1の最小公倍数Lを求めます。
  4. e×d＝L×n＋1を満たす整数 e, d の組を選びます。(nは適当な整数)。
  5. eとmを公開します。
• 送信者側の作業

  送りたいデータ C をmより小さい整数で表します。 E ≡ C^e (mod m) によって E を計算して、Eを送ります。

• 受信者側の作業

  受け取った E を用いて C ≡ E^d (mod m) を計算し、Cを得ます。

e,mを公開しますから、「mの素因数分解が難しい」ことが 秘密を守るための条件となります。 もしp×q＝mを満たす整数p,qを求められてしまうと eを使って簡単にdが求められて、誰でも通信内容を復号化できてしまいます。 したがって mは因数分解の難しい、桁数の大きい整数である必要があります。 どの程度の桁数がmとして適切かは、その時代に使うことの できる計算機の速度に依存します。

ちなみに、Eのe乗根を直接求めてCを得ようとする試みは 成功しません。 「mを法とする世界」では割算が行えないので、e乗根を 求めることはできないからです。

RSA暗号化

RSA 暗号 (Rivest-Shamir-Adleman scheme cipher) は桁数の大きな数を素因数分解することが困難で あることを利用した暗号です。

入力データとなる原字を整数 M (mod m)で表します。 Mを暗号化するために正整数からなる組み立て鍵 (e,m) を準備し、 これらを公開して

    C ＝ E(M) ≡ Me (mod m)

    M ＝ D(C) ≡ Cd (mod m)

任意の異なる2つの素数 p, q を選び、法 m を

    m ＝ p × q

2e ＞ m

    e ・ d ≡ 1 (mod L)

    φ(m) ＞ d ＞ max{p,q}

暗号化する側は「各文字をe乗してmで割った余りを求める計算」 を行います。 復号化する側は「各文字をd乗してmで割った余りを求める計算」 を行います。

RSA暗号の例(1)

p=2,q=5の場合を考えましょう。 p×q＝10 なので 使える文字は 0〜9 の10種類です。

LCM(2-1,5-1)=4となりますので、e=3 とおいてみましょう。 3・d ≡1 (mod 4) を解いてd=3 と求まります。 暗号化する側は「各文字を3乗して 10で割った余りを求める計算」を行います。 元の文が 2 3 7 8 だとすると3乗 (e = 3)して 8 7 3 2 と暗号化されます。

復号化する側は「各文字を3乗して10で割った余りを求める計算」を行います。 暗号文 8 7 3 2 を復号化すると平文 2 3 7 8 が得られます。

RSA暗号の例(2)

p=17, q=19 の場合を考えましょう。 m ＝ p ×q ＝ 323、LCM(16,18)=144となります。 適当に e=23 と選ぶと e・d ≡ 1 (mod 144) を解いて d = 119 が得られます。 そこでe=23, m=323を公開します。

送信者が "This is a secret." という文を送りたいものとします。 ASCIIコードで1文字ずつ表すと以下のようになります。

T  h   i   s      i   s      a     s   e   c  r   e   t   .
84 104 105 115 32 105 115 32 97 32 115 101 99 114 101 116 46 

50 111 79 191 280 79 191 280 279 280 191 271 74 228 271 108 126 

暗号文を受け取った受信者は、各データに関して 「元の数字を掛けては323で割った余りを計算する」ことを119回ずつ 各文字に関して行ってもとの文を取り出します。

84 104 105 115 32 105 115 32 97 32 115 101 99 114 101 116 46 
T  h   i   s      i   s      a     s   e   c  r   e   t   .