RSA暗号を解読する - Ex18.1 - パンの木を植えて

『はじめての数論』の演習問題をやっていきます．

はじめての数論原著第4版

作者:Joseph H. Silverman
丸善出版

Amazon

今回扱うのは演習問題18.1で，RSA暗号を解読せよという内容です．

問題文

次のメッセージを解読せよ．これは法 $m=7081$ と指数 $k=1789$ に関して暗号化されている．（最初に $m$ を因数分解する必要があることに気をつける）

$$ 5192, \quad 2604, \quad 4222 $$

この問題の背景

RSA暗号の仕組みを説明しておきます．

まず（大きな）互いに異なる素数 $p,q$ を選びます．

$p,q$ を掛け合わせて $m = pq$ を得ます．

$φ(m)$ を計算しておきます．$φ(m) = (p-1)(q-1)$ なのでこれは容易にできます．

次に指数 $k$ を選びます．$k$ は任意に選んでいいのですが，$\gcd(k, φ(m))=1$ であるように選ぶ必要があります．

このとき $(m,k)$ が公開鍵であり， $(p,q)$ が秘密鍵です．

暗号化したいメッセージ $C$ を適当な符号化により整数として扱います.

$C$ を適当に何桁かで区切り，それぞれが $m$ より一桁小さい数になるようにします．それを $a_1, \cdots , a_r$ とします．

繰り返し自乗法により $a_1^k \mod m, \cdots , a_r^k \mod m$ を計算します．それを $b_1, \cdots , b_r$ とします．この $b_1, \cdots , b_r$ が暗号化されたメッセージです．

解読する時には，$φ(m)$ を計算する必要があります．

最初に $k$ と $φ(m)$ が互いに素になるようにしたので，$k^ {-1} \mod φ(m)$ が存在します．

だから $b_i$ を $k^ {-1} \mod φ(m)$ 乗すればいいわけです．

合同式 $x^k \equiv b \mod m$ を解くのに $φ(m)$ が必要だというのは明らかではない気がしますが，まあいいでしょう．

回答

Pythonを呼び出して計算してもらいます．

まず $m=7081$ の素因数分解から．

次のコードを使います．

# 素因数分解 - O(√n)
## 入力
n = 7081
## 手続き
N = n
d = 2
A = {}
while d*d <= N :
    r = N % d
    if r==0:
        if d in A:
            A[d] = A[d] + 1
        else:
            A[d] = 1
        N = N // d
    else:
        d = d+1
#### AにNを追加
if N in A:
    A[N] = A[N]+1
else:
    A[N] = 1
## 結果を見栄えよく出力する
print(str(n) + " =", end = ' ')
primes = list(A)
for p in primes:
    if A[p] >= 2:
        print(str(p) +  "^" + str(A[p]),end=' ')
    else:
        print(p,end=' ')

結果は $7081 = 73 \times 97$ でした．したがって $φ(m) = 72 \times 96 = 6912$ です．

次に，法 $φ(m)=6912$ に対する指数 $k=1789$ の逆数を求めます．

これはユークリッドの互助法でできます．

次のコードでPythonに計算していただきます．

# Euclidの互除法
## 入力
a = 1789
b = 6912
## 手続き
if b==0 and a==0:
    print(0,0,0)
elif b==0 and a!=0:  
    print(a,1,0)
else:
    ### aもbもゼロでない場合
    x = 1
    g = a 
    v = 0
    w = b 
    while w != 0:
        q = g // w
        t = g % w
        s = x - q*v 
        x = v
        v = s
        g = w
        w = t
    y = (g - a*x)//b
    ### x > 0であるような解を返すように細工をする
    if x < 0 and b>0:
        while x < 0:
            x = x + b
            y = y - a
    elif x < 0 and b<0:
        while x < 0:
            x = x - b
            y = y + a      
    else:
        pass  
    print(g,x,y)

出力は $1 = 1789 \times 85 -6912 \times 22$ です．つまり $k^ {-1} \equiv 85 \mod φ(m)$ であることがわかります．

あとは暗号文の $85$ 乗を計算すればいいです．

これはJuliaにやってもらいます．

次のコードを使います．

# 繰り返し自乗法
## 入力
## a^k mod m を求める
a = 
m = 7081
k = 85
## 手続き
b = 1
while k >= 1
    if k % 2 == 1
        b = (a * b) % m
    end
    a = (a*a) % m
    k = div(k,2)
end
print(b)

計算結果を書くと，こんな感じです．

$$ 5192^ {85} \equiv 1615 \mod 7081 $$

$$ 2604^ {85} \equiv 2823 \mod 7081 $$

$$ 4222^ {85} \equiv 1130 \mod 7081 $$

このようにして $1615, 2823, 1130$ というメッセージを得ます．

これを18章の冒頭の表に従って平文に戻すと

$$ F E R M A T $$

……なるほど．Fermat（フェルマー）でしたか．

感想とまとめ

計算をやりました．

やってみると意外と楽しかったです．