趣味の数学とプログラム。楽しい数学の世界へようこそ!

RSA暗号

RSA暗号は公開鍵暗号方式の一つです。1977年、ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンによって発明され、3人の頭文字をとってRSA暗号と呼ばれています。

共通鍵暗号と公開鍵暗号

【共通鍵方式】

暗号化に使う鍵、復号に使う鍵が共通な方法です。処理は比較的高速ですが、鍵を送る必要があり、リスクが生じます。

相手ごとに鍵を作るので、管理が大変になります。

【公開鍵方式】

公開鍵方式では、受信側が鍵を用意します。公開鍵を公開し、秘密鍵は送受信しないので、鍵の安全な配布が容易で管理は楽です。
ただし、処理時間は遅くなります。

RSA暗号の仕組み

1.受信側が鍵を作る
・十分大きな素数 \(p,q\) を準備して、\(n=pq\)とする
・\((p-1)(q-1)\)と互いに素な自然数\(e\)を見つける
・\(ed\equiv 1 (\mod(p-1)(q-1))\) となる\(d\)を見つける
\(n\)と\(e\)が公開鍵\(d\)が秘密鍵

2.送信側の暗号化方法
・送りたいメッセージを \(x\)(ただし、\(0\leq x  \lt n\))とする
・公開鍵で暗号化 \(f(x)=x^e \mod n\)(\(x\)を\(e\)乗して\(n\)で割った余り)
・暗号文\(f(x)\)を送信する

3.受信側の復号方法
・\(f(x)^d \mod n\)を計算すると、元の\(x\)になる(\(f(x)\)を\(d\)乗して\(n\)で割った余り)

RSA暗号の証明

暗号化:\(f(x)=x^e \mod n\)
復号:\(f(x)^d \mod n\)

復号したら、\(x\)になることを証明します。

・\(x\)が\(p\)の倍数と仮定すると、\((x^e)^d\)も\(p\)の倍数
\((x^e)^d\equiv 0 \equiv x(\mod p)\)

・\(x\)が\(p\)の倍数でないと仮定
\(ed\equiv 1 (\mod(p-1)(q-1))\)より
整数\(N\)を用いて、\(ed-1=N(p-1)(q-1)\)と表せる
\((x^e)^d=x^{ed-1}\cdot x=x^{N(p-1)(q-1)}\cdot x=(x^{p-1})^{N(q-1)}\cdot x\\\equiv 1^{N(q-1)}\cdot x\equiv x(\mod p)\)
(フェルマーの小定理を用いた)

\(q\)についても同様に成り立つので
\((x^e)^d\equiv x(\mod p)\)、\((x^e)^d\equiv x(\mod q)\)

\((x^e)^d-x\)は、\(p\)の倍数であるとともに\(q\)の倍数で、\(p,q\)は互いに素なので
\((x^e)^d-x\)は\(n\)の倍数

\(x \lt n\)なので、\(x=(x^e)^d \mod n\)となり証明できた

\(n\)を素因数分解すると\(p,q\)がわかるので、秘密鍵\(d\)も求められて復号できてしまいます。そのため、\(p,q\)を十分大きくして\(n\)を300~1000桁にするように推奨されています。

大きな数の素因数分解は時間がかかることがRSA暗号の安全性の根拠ですが、素因数分解が多項式時間で解けないことは証明されていません。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です