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種類です。 X14までを表にしてみると X5 と X9 のところで Xと同じになっていることがわかります。 ちょうど元の数に戻る巾乗の回数は以下のように書くことができます。

X(元の数)X 2X 3X 4X5X 6X 7X 8X9X10X11X12X13X14
00000000000000
11111111111111
24862486248624
39713971397139
46464646464646
55555555555555
66666666666666
79317931793179
84268426842684
91919191919191

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

X(元の数)X 2X 3...X29X30X31X32...X59X60X61X62
000...0000...0000
111...1111...1111
248...39124...39124
3927...26139...26139
41664...581416...581416
52548...311525...311525
63662...131636...131636
74935...6356749...6356749
86450...291864...291864
9436...60194...60194
102376...5411023...5411023
114422...44221144...44221144
126734...4511267...4511267
............................
74950...511749...511749
75469...381754...381754
76176...761761...761761

実は、『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」 乗のときに元の整数に戻っています。

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

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)
で暗字 C を作ります。 逆に、暗字 C を原字 M に翻訳するには非公開の翻訳鍵 (d,m) を 用いて
    M = D(C) ≡ Cd (mod m)
を計算します。 MもCも 0以上 m-1 以下の値をとる同じ桁数のデータです。 2つの鍵 e, d の作成方法は以下のようにして作ります。

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

    m = p × q
とします。つぎに、(p-1)と(q-1)の最小公倍数 (Least Common Multiplier: LCM) Lと互いに素で、これより小さい任意の整数 e を選びます。ただし
2e > m
を満たすように選んだ方がよいでしょう。 eが決定できたならば
    e ・ d ≡ 1 (mod L)
となるように d を定めます。ただし
    φ(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 
mが大きいと何文字文かまとめて数字化するのですが、 今回は1文字ずつ暗号化することにしてみます。 「元の数字を掛けては323で割った余りを計算する」ことを23回ずつ 各文字に関して行った結果です。
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   .