RSA暗号の数理

RSA暗号を最短で解説してみたい.

暗号学の習わしにならって,暗号はAliceとBobの間で交換されるとする.そして,第三者Eveが盗聴しているとする.

Aliceは

1. 2つの大きな素数p,qを選ぶ.

2. 合成数n=p\times qを計算する.

3. \phi(x)をオイラー関数として,\phi(n)=\phi(pq)=(p-1)(q-1)を計算する.

4. \phi(n)以下で,これと互いに素な数kを求める.

5. ku-\phi(n)v=1を満たすu,vを求める.

6. Bobにn,kを伝える.(これは公開通信路でEveにも傍受できる.)

Bobは

7. 伝えたい平文のメッセージMを用意する.

8. M^k \equiv b \ \ \ (mod\ n)を計算し,bを求める.

9. Aliceにbを伝える.(これも公開通信路でEveにも傍受できる.)

Aliceは

10. b^u\equiv M \ \ \ (mod\ n)を計算し,不思議なことにMを得る.

この摩訶不思議な操作の理論的な根拠は次の定理に依る.

gcd(b,n) = 1, gcd(k,\phi(n)) = 1 を満たすb,k,nが与えられたとき,

M^k \equiv b\ \ \ (mod\ n) の解を求める.

1. 一次方程式 ku - \phi(n)v = 1 を満たす正の整数解u,vを求める.

2. b^u \equiv M\ \ \ (mod\ n)を計算して得られた値がMとなる.

つまり,b^u \equiv (M^k)^u \equiv M^{ku} \equiv M^{1+\phi(n)v} \equiv M\times (M^{\phi(n)})^v \equiv M\ \ \ (mod\ n)

というだけの話.

ちなみに,M^{\phi(n)}\equiv 1\ \ \ (mod\ n)はオイラーの定理(数論)です.

これと,もう一つStep5の背景には次の定理

a,bを0でない任意の整数とするとき,

方程式 ax+by = gcd(a,b) は常に整数解を持つ.

が使われている.

そして,Eveはb,k,nを知っている.

しかし,上記定理のuを求める過程で,\phi(n)が必要だということが分かるが,\phi(n)nの素因数分解が分かっていないと計算できない.

だから,これだけではMを得ることはできない.

では,実際コンピュータはどうするのか.

Step1の巨大素数を見つける段階.ここでは,まず例えば5000以下ぐらいの雑魚な素数をエラトステネスの篩で取り除く.続いて,フェルマー素数判定法(フェルマーの小定理)の対偶を用いて,「素数っぽいヤツ」を見つける.しかしここではまだ分からない.カーマイケル数などがあるからだ.最終的には,ミラーラビン素数判定法で決定する.

Step4,Step5の互いに素な数を見つけるには,ユークリッドの互除法で最大公約数が求まるので大丈夫.

Step8,Step10の巨大数の巨大数乗は,繰り返し二乗法を使う.これは,冪の数を2進数で表して,底の2,4,8,16,,,2^n乗を各々計算して最後に掛ける.これをすると,計算が省略できる.

最後に,

k,nを公開鍵と言い,uを秘密鍵という.公開鍵は平文Mを暗号化するだけの鍵であり,秘密鍵は暗号bを復号化するだけの鍵である.

このような暗号のやり取りを公開鍵暗号方式という.(これに対して,1つの鍵で暗号化と復号化を行う方式を共通鍵暗号方式という.)

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中