単語記事: 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桁以上である。これを素因数分解するのに、いかに時間がかかるかおわかりだろうか。

このページを開いた方の中には、現在でも使われている暗号なだけあって、難解なことでもするのかと思った方もいらっしゃるかもしれない。しかし、暗号化や復号のやりかただけ見れば、さほど難しいことではない。最悪、累乗と余りの知識さえあれば十分である。実際、暗号の本質的価値は解読のしにくさにあり、暗号そのもののわかりにくさは関係ない。むしろわかりやすいほうが優れているとも言える。

証明

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

まず、記号を準備する。ここで扱う記号は≡と|である。どちらも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 

関連項目

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

ページ番号: 4188581 リビジョン番号: 1075822
読み：アールエスエーアンゴウ
初版作成日: 09/10/23 23:45 ◆ 最終更新日: 11/02/14 20:38
編集内容についての説明/コメント: ゆとり削除
記事編集 / 編集履歴を閲覧 / Twitterで紹介