RSA 暗号について

1
◆ RSA 暗号について◆
鍵生成
素数 p, q(p ̸= q) を生成し,n = p ∗ q,λ(n) = LCM (p − 1, q − 1) を計算する。適当な
e(1 < e < n),(GCD(λ(n), e) = 1) を定め,ed = λ(n)x + 1(x は自然数) を計算する
秘密鍵
d(または,p,q)
公開鍵
e,n
暗号化
M e ≡ C(modn)
復号
C d ≡ M (modn)
今回 RSA 暗号の理論をまとめるためにフェルマーの小定理と拡張ユークリッド互除法を用いた。
以下その証明である。
フェルマーの小定理
フェルマーの小定理とは ap ≡ a(modp) が p が素数で a が任意の自然数のとき成り立つこと
をいう
数学的帰納法を用いて証明する
a = 1 のとき明らかに ap ≡ a ここで二項定理を用いると (a = m + 1 のとき成り立つと仮定)
p
p
(m + 1) = p Cp m +
p−1
∑
p Ck m
p
+ p C0 1p ≡ mp + 1(modp)
k=1
p が素数で 1 ≦ k ≦ p − 1 のときp Ck =
で割り切れる
p Pk
k!
=
p(p − 1)(p − 2)...(p − k + 1)
が p の倍数であるの
k!
mp ≡ m(modp) の式に両辺から 1 を加える
mp + 1 ≡ m + 1
(m + 1)p ≡ m + 1
以上数学的帰納法より ap ≡ a(modp) が成り立つ。また両辺を a で割ると ap−1 ≡ 1(modp) が成
り立つ
拡張ユークリッド互除法
a, b を 0 でない自然数とし，GCD(a, b) = m とする。このとき，
ax + by = m
となる整数 x,y が存在する。そして，この x,y は実際に計算することが出来る。
RSA の鍵生成と照らし合わせると、GCD(λ(n), e) = 1 なので
ey = λ(n)x + 1
2
と表せられる。
◆拡張ユークリッド互除法について◆
上記の
ey = λ(n)x + 1
となる整数 x,y が存在するか調べる。
λ(n) = r0 , e = r1 (r1 < r0 とする) においてユークリッド互除法の過程を繰り返すと
r0 = k0 r1 + r2 (0 < r2 < r1 )
r1 = k1 r2 + r3 (0 < r3 < r2 )
r2 = k2 r3 + r4 (0 < r4 < r3 )
..
.
rn−1 = kn−1 rn + 0
r0 = k0 r1 + r2 より r1 と r2 の約数は r0 も割り切れるし、r0 の式を r2 について変形すれば
r2 = r0 − k0 r1 より r0 と r1 の約数は r2 も割り切れるといえる。従って r0 と r1 の最大公約数が r1
と r2 の最大公約数と同じだと言える。これを余りが 0 の地点まで再帰的に行うと r0 と r1 の最大公
約数は rn となる。また k は商であり、さらに
( ) (
)( )
r0
k0 1
r1
=
r1
1 0
r2
( ) (
)( )
r1
k1 1
r2
=
r2
1 0
r3
( ) (
)( )
r2
k2 1
r3
=
r3
1 0
r4
..
(
) ( .
)( )
rn−1
kn−1 1
rn
=
rn
1
0
0
すなわち
ここで(
Ki =
( ) (
r0
k0
=
r1
1
ki
)
1
1
0
)(
1
k1
0
1
(
とおき、Ki
−1
=
0
)(
1
k2
0
1
1
1 −ki
)(
1
k3
0
1
) (
1
k
· · · n−1
0
1
)( )
1
rn
0
0
)
を前述の式から左にかけあわせる
(
)−1 (
)−1
(
)−1 (
)−1 (
)−1 ( ) ( )
kn−1 1
kn−2 1
k2 1
k1 1
k0 1
r0
r
···
= n
1
0
1
0
1 0
1 0
1 0
r1
0
(
)(
)
(
)(
)(
)( ) ( )
0
1
0
1
0
1
0
1
0
1
r0
r
···
= n
1 −kn−1
1 −kn−2
1 −k2
1 −k1
1 −k0
r1
0
これらの過程において、λ(n) = r0 , e = r1 , 上記のユークリッド互除法により rn = gcd(λ(n), e) で
あるから
(
0
1
1
−kn−1
)(
)
(
)(
)(
0
1
0
1
0
1
0
···
1 −kn−2
1 −k2
1 −k1
1
1
−k0
)(
) (
)
λ(n)
gcd(λ(n), e)
=
e
0
3
となる。
(
x
u
y
v
)
(
)(
)
(
)(
)(
0
1
0
1
0
1
0
1
0
=
···
1 −kn−1
1 −kn−2
1 −k2
1 −k1
1
1
−k0
)
とおき、ユークリッド互除法の過程で得られた k0 ∼kn−1 を用いて右辺を計算すれば、左辺の x,y
が求まり
ey = λ(n)x + gcd(λ(n), e) = λ(n)x + 1
を満たす。
1. 理論
・相異な素数 p,q を選ぶ。
・n = p ∗ q と λ(n) = LCM (p − 1, q − 1) を計算する。
・e は n を法として平文を e 乗すると暗号文になる 1 < e < n でλ(n) と互いに素な数と定
義する。(平文 M, 暗号文 C とする)
M e ≡ C(modn)
また d は n を法として暗号文 C を d 乗すると平文にもどる ed = λ(n)x + 1(拡張ユークリ
ッドから) を満たす数と定義する。
C d ≡ M (modn)
・C d ≡ M (modn) を証明する。上記より
C d ≡ M ed
ここでフェルマーの小定理を用いる。
フェルマーの小定理を用いると、M p−1 は指数部分 p − 1 にいくら値をかけても p を法にし
た場合答えは 1 となるので
M k(p−1) ≡ 1(modp)
と表せることができる (k は自然数) また同じく q の場合も
M k(q−1) ≡ 1(modq)
と表すことができる
つまり (p − 1) の倍数で 1(modp) となり
同様に (q − 1) の倍数でも 1(modq) となっている
従って (p − 1) と (q − 1) の両方の倍数である最小公倍数λ(n) について
M λ(n)k ≡ 1(modp), M λ(n)k ≡ 1(modq)
と表すことができる
p, q は n の要素であり法を p, q にした場合どちらも M λ(n)k に対して答えが 1 になるので法
を pq にした場合でも M λ(n)k に対して答えが 1 になるか考える
上記の式より
M λ(n)k = pa + 1
4
M λ(n)k = qb + 1
と表せられ (a, b は自然数とする)
pa = qb
となる
p と q は互いに素なので b は p の倍数, a は q の倍数であるといえる。従って b = pt(t は自
然数) となり
M λ(n)k = pqt + 1
となる。この式は M λ(n) を pq すなわち n を法にすると答えが 1 になるということがわかる
ので
M λ(n)k ≡ 1(modn)
と表すことができる
M λ(n)k ≡ 1(modn) の両辺に M をかける
M λ(n)k+1 ≡ M (modn)
拡張ユークリッド互除法より
ey = λ(n)x + 1
を用いる。x, k はそれぞれλ(n) の係数なので
M λ(n)k+1 ≡ M ey (modn)
従って
M λ(n)k+1 ≡ M ey ≡ M (modn)
と表すことができる
ここで y は上記の式を満たす秘密鍵 d となるので
C d ≡ M ed ≡ M (modn)
が成り立ち復号ができる。以上のことから ey は必ずλ(n) を法としたとき答えが 1 になら
なければいけない値であることがわかる。
2. 例
・p = 7, q = 11 とする
・n = p ∗ q = 77, λ(n) = LCM (p − 1)(q − 1) = 30
・e = 17 とする。ここで拡張ユークリッド互除法を用いて d を求める
λ(n) = 30, e = 17 より
30 = 1 ∗ 17 + 13
17 = 1 ∗ 13 + 4
13 = 3 ∗ 4 + 1
4=4∗1+0
5
前述の行列式より
(
x
u
y
v
)
(
)(
0 1
0
=
1 −4
1
)(
1
0
−3
1
)(
)
(
1
0 1
4
=
−1
1 −1
−16
従って
30 ∗ 4 + 17 ∗ (−7) = 1
と表せられ、この式の左辺に 17 ∗ 30 − 30 ∗ 17 を加えると
30 ∗ (−21) + 17 ∗ 23 = 1
17 ∗ 23 = 30 ∗ 21 + 1
となりこれから 17 ∗ 23 は 30 を法とすると答えは 1 であることが言える。
従って秘密鍵 d = 23
・平文 M = 3 とするとき M ed ≡ M (modn) より
317∗23 = 3391 ≡ 3(mod77)
−7
−28
)

Download Report