RSA暗号

RSA暗号とは、公開鍵暗号のひとつであり、現在インターネットで広く使われている暗号である。

概要

大きな数を素因数分解するのは、現代の技術力をもってしても非常に時間がかかる。RSA暗号はこれを利用しているのである。どんなに大きな数でも素因数分解は不可能ではないので、いつかは解読されてしまう。しかし、その頃には情報としての価値はなくなっているので、暗号としての役割を果たす。

方法

鍵生成

まず、暗号で用いる鍵を次のようにして用意する。

1. 異なる2つの素数p,qを適当にとる。
2. n = pqとする。
3. 自然数eを、(p-1)(q-1)との最大公約数が1となるように適当にとる。
4. 自然数dを、edを(p-1)(q-1)で割った余りが1となるように適当にとる。
5. (e,n)を公開鍵とし、(d,n)を秘密鍵とする。

dを求める際には、ユークリッドの互除法を応用することで簡単に求めることができる。詳しく説明すると長くなるのでここでは割愛する。eとnは公開鍵なので公開するものだが、p,q,dはいずれも他人に知られてはならない。

暗号化

公開鍵で平文xを暗号化し、暗号文yを得る方法。ここでxは1以上n未満の自然数とする。xがn以上であれば、分割して複数のn未満の数にする。自然数以外の情報を扱う場合、適当な自然数に対応させてから暗号化する。

1. xをe乗する。
2. それをnで割った余りをyとする。

これで完成。ね、簡単でしょ?

復号

秘密鍵で暗号文yを復号し、平文xを得る方法。

1. yをd乗する。
2. それをnで割った余りをxとする。

前項でのxと本項でのxは一致する。ね、簡単で(ry

実際にやってみよう

暗号化してみよう

暗号化なら鍵と平文を適当に用意すれば可能だけど、見るだけでいいという人のためにひとつ例をあげよう。尚、計算を簡単にするために次の定理を用いるよ。

「余りが等しい2つの数は、同じだけ累乗しても同じ数を掛けても余りは等しい」

p = 5 , q = 7 , n = 35 , e = 5 , d = 5とし、12を暗号化する。
12⁵ = (12²)²×12 = 144²×12
144を35で割った余りは4なので、144²×12と4²×12は余りが等しい。
4²×12 = 192であり、これを35で割った余りは17
よって暗号文17を得る。

復号も同じ要領でやればおｋ。ちゃんと12になるか確かめてみよう。

解読してみよう

今度はこちらで作成した公開鍵と暗号文だけを見せるので、元の数を当ててみよう。

公開鍵 (e,n) = (27,123)
暗号文 105

正解は72でした。ちなみにdの値は3。dはこれである必要はないけど、一番小さいのがこれ。小さいほうが計算少なくて済むね。

解説(選択して読んでね)

秘密鍵がわかればよいので、ここではdの値を求めることを目的とする。eの値は既にわかっているので、鍵生成の方法から、(p-1)(q-1)の値がわかればdの値を求めることができる。(p-1)(q-1)の値は、nを素因数分解すれば求められる。

n = 123 = 3×41なので、(p-1)(q-1) = 2×40 = 80
よって、27dを80で割って1余ればよい。つまり、27d = 1,81,161,・・・のいずれか。
dは適当にひとつ選べばよいので、例えばd = 3をとればよい。d = 83等でもかまわない。 

あとは、105を3乗して123で割った余りを求めるだけ。

安全性

前項で解読した方は、「あれっ、簡単じゃないか?」と思った方が多いのではないだろうか。実際、nを素因数分解できればdの値を求めることができ、簡単に平文が得られる。一方、素因数分解を用いるよりも効率的かつ実用的な解読法は現在のところ考え出されていない。つまり、RSA暗号の解読が容易であるか困難であるかは素因数分解のそれに依存するのである。現在RSA暗号において実際に使われているnの値は300桁以上である。これを素因数分解するのに、いかに時間がかかるかおわかりだろうか。

このページを開いた方の中には、現在でも使われている暗号なだけあって、難解なことでもするのかと思った方もいらっしゃるかもしれない。しかし、暗号化や復号のやりかただけ見れば、さほど難しいことではない。最悪、累乗と余りの知識さえあれば十分である。暗号の本質的価値は解読の困難さにあり、暗号そのもののわかりにくさは関係ない。また、実際に暗号を運用するにあたって、正規の方法による暗号化や復号は高速かつ容易に行う必要がある。RSA暗号はそれらを満たす、優れた暗号であった。

しかし、注意深く実装しないと脆弱性を含めてしまうことになりかねないこと、より短い鍵長で同等以上のセキュリティを実現できる楕円曲線暗号方式の広まりなどもあり、第一線からは引退しつつある。今後新しく公開鍵暗号方式を実装するときは、楕円曲線暗号方式や耐量子暗号方式を第一に考えるべきであろう。

証明

暗号化する前と復号した後が一致することを証明する。

まず、記号を準備する。ここで扱う記号は≡と|である。どちらも2つの整数の関係性を表す記号である。a≡b (mod n)は、「aとbはnで割った余りが等しい」という意味である。詳しくは≡の記事を参照されたし。a|bは、「aはbの約数である」という意味である。「bはaの倍数である」とも言う。a≡b (mod n)とn|a-bは同値である。というかこれが合同関係の定義。また、この証明はフェルマーの小定理を前提とする。

平文をx,暗号文をy,それを復号したものをzとする。z = xを示す。

暗号化の方法より、y≡x^e (mod n)
復号の方法より、z≡y^d (mod n)
よって、z≡(x^e)^d≡x^ed (mod n)

鍵生成の方法より、ed≡1 (mod (p-1)(q-1))
よって、(p-1)(q-1)|ed-1
p-1|(p-1)(q-1)なので、p-1|ed-1
q-1|(p-1)(q-1)なので、q-1|ed-1
よって、ed≡1 (mod p-1) かつ ed≡1 (mod q-1)

xとpが互いに素であれば、フェルマーの小定理よりx^p-1≡1 (mod p)
ed≡1 (mod p-1)より、ある整数kが存在し、ed = k(p-1)+1
よって、x^ed≡x^k(p-1)+1≡(x^p-1)^kx≡1^kx≡x (mod p)
xとpが互いに素でなければ、pは素数なのでp|x
よって、x≡0 (mod p)したがって、x^ed≡0 (mod p)

いずれにせよ、x^ed≡x (mod p)が成り立つ。
qに関しても同様に、x^ed≡x (mod q)
よって、p|x^ed-x かつ q|x^ed-x
pとqは互いに素なので、pq|x^ed-x
n = pqより、x^ed≡x (mod n)
よって、z≡x (mod n)
どちらも0以上n未満なので、z = x 

認証

秘密鍵(d,n)を先に使うことで、秘密鍵の所持を証明することができる(RSA署名)。これにより、秘密鍵を誰にも明かさずに本人確認ができる。

1. 鍵生成は暗号化の時と同じ。公開鍵(e,n)を本人確認したい相手に渡しておく。
2. 本人確認したい相手は、一時的な値cをランダムに生成し、秘密鍵(d,n)の所持者に渡す。
3. 秘密鍵(d,n)の所持者は、cを受け取るとs=(c^dをnで割った余り)を相手に渡す。このsは署名と呼ばれる。
4. 本人確認したい相手は、署名sを受け取ると(s^eをnで割った余り)を計算し、それがcと等しければsを送ってきた相手が本人であることを信じる。

sの値を使い回されてなりすましされるのを防ぐために、cは毎回異なる値を選ばなければならない。(ランダムに選んでいるのであれば問題はない。)

このプロセス自体は暗号化プロセスを一切含まない。この通信自体を暗号化すべきかどうかは全く状況により、暗号化する場合は別の手段を用いる必要がある。

実例

自分の書いたメッセージに、自分が書いたことの証明をつけたい場合

(RSASSA-PSS というアルゴリズムの概説を書く。詳しい仕様はRFC 8017を参照。)

メッセージmに本人確認(署名)をつけることを考える。あらかじめ以下のものを固定しておく。

• ハッシュ関数H (SHA-256など)
• {0,1,...,n-1}の上のほぼ全単射な関数f (撹乱のため)

署名を作る側は以下のような手順を踏む。

1. ハッシュ値H(m)を計算する。
2. 乱数rを選ぶ。
3. c=f(r || H(m))とする。r || H(m)はrとH(m)を並べたデータである。fを挟むのはパターンを不規則にして安全性を増すため。
4. 署名s=(c^dをnで割った余り)を計算する。(この場合、ランダムにcを選んでくれる第三者が存在しないので、ハッシュ関数を挟んで擬似的にcをランダム化するイメージ)

署名を検証する側は、以下のような手順を踏む。

1. c=(s^eをnで割った余り)を計算する。
2. c=f(r || H(m))という式から、fの逆関数を計算してrとH(m)を割り出す。
3. H(m)と、こちらで改めて計算したmのハッシュ値が等しいか検証する。等しければその署名が妥当なものであることを信じる。

関連項目

• 数学
• 暗号
• 素数
• フェルマーの小定理