1. No category

暗証番号とフェルマーの小定理
§1 数値の暗号化と暗号の解読
我々は ATM で銀行預金を引き出すとき, 本人確認の為, ATM に暗証番号
を入力する. ATM は入力された暗証番号を変換して銀行に送る. 銀行は受け
取った暗号を解読して入力された暗証番号に戻し, 銀行に保管されている暗証
番号と照合する. 一致すれば, 本人確認が終わる. インターネットでのパスワー
ド入力による本人確認でも, 同じような処理が行われる.
暗証番号を暗号に変換し, 更に暗号を解読してもとの暗証番号に戻す方法と
して, 最初に考案された公開鍵暗号が RSA 暗号であり, 1976 年 R. Rivest,
A. Shamir, L. Adelman によって考案された. この暗号に応用されている数学
の定理について説明する.
以下, 整数とは非負整数 0, 1, 2, · · · のこととする. 暗証番号は, アルファ
ベットや記号を含まない, 4 桁の整数と仮定する. 従って, 暗証番号の最大の
値は 9999 になる. 先ず, 異なる素数 p, q を決め, n = pq を求める. ただし
n > 9999 となるように p, q を決める.
次に p − 1 と q − 1 の公倍数 ` を 1 つ決める. 最小公倍数でもかまわない.
そして, この ` と a の最大公約数が 1 となるように, 整数 a を 1 つ決める. 最
後に, ad − 1 が ` で割り切れるように整数 d の値を 1 つ決める. このような
d が存在することは後 (補題 4) で証明します. 以上の整数に関して次の定理が
成立する.
定理 1. 9999 以下の整数 M に対して, M ad を n で割った余りは M に等
しい.
定理 1 を認めて, 暗証番号の暗号化と暗号の解読法を具体的に説明する. 暗
証番号として ATM に M が入力されたとする. ATM は M a を n で割った余
り x を計算して x を銀行に送る. 銀行は受け取った x から xd を計算し, xd
を n で割った余り y を求める. すると, 定理 1 により y = M となる.
RSA 暗号では a と n の値は秘密ではなく公開鍵と呼ばれている. しかし d
の値は秘密鍵と呼ばれ, 暗号の解読者のみが厳重に管理しなければならない.
理論的には n の値から d の値を求めることがでる. しかし, n の素因数分解
が必要で, n の値が大きいときは膨大な時間がかかる. 今後ハードやソフトが
1
改良されるにしても, 「当分は n が 300 桁の数なら大丈夫」とされている.
§2 定理 1 の証明
数学的な記号を導入し, 幾つかの補題 (補助定理) を示した後, 定理 1 を証明
する. p, q, n, `, a, d は §1 で使われた特定の整数とする.
定義 2. (1) 整数 b (b = 1) と c (c = 1) の最大公約数が 1 のとき, b と c は
互いに素であると言う.
(2) 整数 b を整数 r (r = 1) で割った余りを (b)r で表す.
(3) 有限集合 A の要素の数を #A で表す.
補題 3. 整数 b, c, r (r = 1) に対して (bc)r = ((b)r (c)r )r .
証明. 適当な整数 x, y, β (β 5 r − 1), γ (γ 5 r − 1) により b = xr + β,
c = yr + γ と表すと, bc = (xyr + xγ + yβ)r + βγ により, (bc)r = (βγ)r =
((b)r (c)r )r である.
□
補題 4. (ad)` = 1 を満たす d が存在する.
証明. a と ` は互いに素であるので, a, 2a, · · · , (` − 1)a は ` で割り切れな
い. 1 以上 ` − 1 以下の ` − 1 個の整数 (a)` , (2a)` , · · · , ((` − 1)a)` を考える
と, この中に同じ整数はない. もしあれば, 例えば (ia)` = (ja)` (i < j) とす
れば, (j − i)a は ` で割り切れることになり, 矛盾を生ずる. 従って (da)` = 1
を満たす d が存在する.
□
補題 5. 整数 N が素数 r の倍数でないとき, ある整数 i (1 5 i 5 r − 1) に
対し (N i )r = 1 が成立する.
証明. 1 以上 r − 1 以下の r − 1 個の整数 (N )r , (N 2 )r , · · · , (N r−1 )r を考え
る. この中に同じ整数がなければ, ある i に対し (N i )r = 1 となる. 同じ整数
があれば, 例えば (N j )r = (N k )r (j < k) とすれば, N k − N j = N j (N k−j − 1)
は r で割り切れる. N と r は互いに素であるので N k−j − 1 は r で割り切れ,
やはり, (N i )r = 1 を満たす i が存在する.
□
以下, r は素数, N は r の倍数でない整数とする. 従って N と r は互いに
素であり, N = 1 である. また, i は (N i )r = 1 を満たす最小の整数とし,
Bλ = {(λN )r , (λN 2 )r , · · · , (λN i )r } (λ = 1, 2, · · · , r − 1)
2
とおく.
補題 6. (1) #Bλ = i. (2) Bλ ∩ Bµ 6= ∅ のとき Bλ = Bµ .
証明. (1) (λN j )r = (λN k )r (1 5 j < k 5 i) とすると, λN k − λN j =
λN j (N k−j − 1) が r で割り切れる. N j と r は互いに素だから, λ(N k−j − 1)
が r で割り切れる. r が素数で 1 5 λ 5 r − 1 だから λ と r は互いに素
であり, 補題 4(と同じ理由) により, (µλ)r = 1 を満たす整数 µ が存在する.
µλ(N k−j − 1) も r で割り切れるので, (µλN k−j )r = (µλ)r = 1 となる. 補題
3 により, (µλN k−j )r = ((µλ)r (N k−j )r )r = (1(N k−j )r )r = (N k−j )r だから,
結局 (N k−j )r = 1 となる. ところが k − j < i だから, この式は i の定義に矛
盾する. 以上により, #B = #{λ : λ = 1, · · · , i} = i である.
(2) Bλ ∩ Bµ 6= ∅ のとき, ある j, k に対して (λN j )r = (µN k )r であり, 従っ
て, 任意の h = 1, · · · , i − 1 に対して, (N h )r (λN j )r = (N h )r (µN k )r であり,
補題 3 により, (λN j+h )r = (µN k+h )r である. j + h > i のとき (λN j+h )r =
((N i )r (λN j+h−i )r )r = (1(λN j+h−i )r )r = (λN j+h−i )r だから, {(λN j+h )r :
h = 1, · · · , i − 1} = Bλ である. 同様に {(µN k+h )r : h = 1, · · · , i − 1} = Bµ
であり, {(λN j+h )r : h = 1, · · · , i − 1} = {(µN k+h )r : h = 1, · · · , i − 1} によ
り Bλ = Bµ となる.
□
補題 7 (フェルマー (P. Fermat) の小定理). 整数 N と素数 r が互いに素
であるとき (N r−1 )r = 1.
証明. 集合 Bλ は集合 A = {1, 2, , · · · , r − 1} の部分集合であり, (λN i )r = λ
により, A = ∪r−1
λ=1 Bλ である. 特に補題 6(2) により, A は互いに交わらない幾つ
かの Bλ の和集合になっている. 従って補題 6(1) により, #A = r−1 は #B = i
で割り切れ, r − 1 = gi として, 補題 3 により, (N r−1 )r = (((N i )r )g )r = 1 が
成立する.
□
補題 8. M が p とも q とも互いに素であるとき, 整数 m に対し (M m` )n = 1.
証明. ` は p−1 と q −1 の公約数だから ` = b(p−1) = c(q −1) と表せる. 補
題 3, 7 により (M m` )p = (((M p−1 )p )mb )p = (1mb )p = 1, 同様に (M m` )q = 1
である. 即ち M m` = xp + 1 = yq + 1 と表せる. p と q は互いに素で xp = yq
だから, x = zq, y = zp と表せる. 従って M m` = zpq + 1 = zn + 1 と表され,
(M m` )n = 1 となる.
□
補題 9. M (6= 0) が p の倍数のとき, 整数 m に対して (M m`+1 )n = M .
3
証明. M < n = pq により整数 s (= 1) 及び p とも q とも互いに素な整数
N を使って, M = ps N と表せる. ` は整数 c により ` = c(q − 1) と表せる
ので M m`+1 = psmc(q−1) ps N m` N である. 補題 7 により psmc(q−1) = xq + 1
と表せるので, 補題 3, 8 により, (M m`+1 )n = ((xps q + ps )n (N m` )n (N )n )n =
((xps q + ps )n · 1 · N )n = ((ps )n N )n = (ps N )n = (M )n = M となる.
□
定理 1 の証明. M 6= 0 としてよい. (ad)` = 1 により ad = m` + 1 と
表せる. M が p とも q とも互いに素のときは, 補題 3, 8 により (M ad )n =
((M m` )n (M )n )n = (1 · M )n = M である. M が p の倍数のときは, 補題 9
により (M ad )n = (M m`+1 )n = M である. M が q の倍数のときも同様に
(M ad )n = 1 である.
□
例 10. p = 3, q = 5, n = pq = 15, p − 1 = 2 と q − 1 = 4 の最小公倍数
` = 4, a と ` = 4 との最大公約数が 1 であるような数 a = 7, ad = 7d を ` = 4
で割った余りが 1 でるような数 d = 3 に対して, M の暗号値 A = (M 7 )15 と
その解読値 (A3 )15 は次の値になる.
M
M7
A = (M 7 )15
A3
(A3 )15
2
3
4
5
6
7
8
9
10
11
12
13
14
128
2187
16384
78125
279936
823543
2097152
4782969
10000000
19487171
35831808
62748517
105413504
8
12
4
5
6
13
2
9
10
11
3
7
14
512
1728
64
125
216
2197
8
729
1000
1331
27
343
2744
2
3
4
5
6
7
8
9
10
11
12
13
14
4