暗証番号とフェルマーの小定理 §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