RSA暗号を実装してみる
こんにちは。今回も暗号について取り上げます。今回はRSA暗号です。
RSA暗号とは
１９７７年にリベスト(Rivest)・シャミア(Shamir)・エーデルマン(Adleman)によって発明された暗号で、3人の頭文字をとってRSA暗号と呼ばれています。原理はフェルマーの小定理に基づいています。
https://ja.wikipedia.org/wiki/RSA暗号数学的に込み入った話になるのですが、できるだけ簡単な例を用いて話を進めていきます。
RSA暗号の原理
鍵生成
\(k\)をセキュリティパラメータとします。ここでは\(k=8\)とします。
次に\(k/2\)ビットの2つの素数\(p,q(p \neq q)\)をランダムに生成します。ここでは、\(p=11,q=13\)とします。この\(p,q\)を用いて\(N=pq=143\)とします。本来はp,qは十分に大きな素数を選択する必要があります。
続いて、\(\varphi(N)\)という関数（オイラー関数）を考えます。オイラー関数は、\(N\)を正の整数としたとき、\(1\)以上\(N\)以下の整数で\(N\)と互いに素（公約数を\(1\)以外にもたない）である整数の個数を求める関数です。証明は割愛しますが、\(p\)が素数であるとき\(\varphi(p)=p-1\)であること、および、\(p,q\)が互いに素であるとき、\(\varphi(pq)=\varphi(p)\varphi(q)\)が成り立つことが知られています。これより、\(\varphi(143)=\varphi(11)\varphi(13)=(11-1)(13-1)=120\)となります。
その次に、\(\varphi(N)\)と互いに素である\(e(1<e<\varphi(N))\)をランダムに生成します。ここでは、\(e=7\)とします。
次に、\(ed\equiv 1 \bmod \varphi(N)\)となる\(d\)を求めます。この式の意味は、\(e\)と\(d\)をかけた値を\(\varphi(N)\)で割った余りが\(1\)になる\(d\)を求めるということです。この値を求めるには、拡張ユークリッドの互除法を用いると求められますが、ここでは拡張ユークリッドの互除法についての説明は割愛します。拡張ユークリッドの互除法により、\(d=103\)が求まります。ここで、\(ed=7 \times 103 = 841\)で、これを\(\varphi(143)=120\)で割った余りは\(1\)となることが確かめられます。
ここまでの操作により求まった\(d=103\)が秘密鍵、\(N=143,e=7\)が公開鍵になります。ここで、\(p,q\)を知られてしまうと簡単に\(d\)を計算できてしまうので、\(p,q\)は安全に破棄する必要があります。
暗号化
平文を\(m(0 \leq m < N)\)とします。この平文に対して、\(c \equiv m^e \bmod N\)を求めたものが暗号文になります。
例として"R"を暗号化してみます。"R"の文字コードは\(82\)です。\(m^e=82^7=24928547056768\)を\(N=143\)で割った余りは\(c=69\)となります。これが暗号化された値になります。
復号
暗号化された\(c\)を復号するには、\(m’ \equiv c^d \bmod N\)を求めたものが復号された値になります。
先ほどの\(c=69\)を復号すると、\(c^d=69^{103}\)を\(N=143\)で割った余りは\(82\)となり復号されたことが確認できます。
RSA暗号を実装してみる
毎度のPythonです。きれいに書けなかったので残念です。
import random
def make_prime( N ):
while True:
n = random.randint( 11, N )
i = 2
flag = True
while i*i <= n and flag:
if n % i == 0:
flag = False
i += 1
if flag:
return n
def key_generate( k ):
b = 1 << int( k/2 )
e = 7
flag = True
while flag:
p = make_prime( b )
q = p
while p == q:
q = make_prime( b )
N = p * q
phi = ( p-1 ) * ( q-1 )
d = euclid( phi, e )
if phi%e != 0:
flag = False
return ( N, e ), d
def euclid( a, b ):
r2, r1 = a, b
u2, u1 = 1, 0
v2, v1 = 0, 1
while r1 > 0:
q = int( r2/r1 )
u = u2 - q*u1
v = v2 - q*v1
r2, r1 = r1, r2%r1
u2, u1 = u1, u
v2, v1 = v1, v
return v2 if v2 >=0 else v2+a
def encrypt( m, pk ):
cipher = []
N, e = pk
for l in m:
c = ord(l)
for i in range( e-1 ):
c = ( c*ord(l) ) % N
cipher.append( c )
return cipher
def decrypt( c, pk, sk ):
decode = ''
N = pk[0]
for c1 in c:
m = c1
for i in range( sk-1 ):
m = ( m*c1 ) % N
decode += chr( m )
return decode
if __name__ == '__main__':
pk, sk = key_generate(8)
plain_text = 'Read Me'
cipher = encrypt( plain_text, pk )
decode = decrypt( cipher, pk, sk )
print( 'N =', pk[0] )
print( 'e =', pk[1] )
print( 'd =', sk, '\n' )
print( 'plain → cipher → decode' )
for i in range( len(plain_text) ):
print( plain_text[i], ord(plain_text[i]), '(', format(ord(plain_text[i]), '08b'), ')→',
cipher[i], '(', format(cipher[i], '08b'), ')→',
ord(decode[i]), '(', format(ord(decode[i]),'08b'), ')', decode[i] )
実行結果です。
N = 143
e = 7
d = 103
plain → cipher → decode
R 82 ( 01010010 )→ 69 ( 01000101 )→ 82 ( 01010010 ) R
e 101 ( 01100101 )→ 62 ( 00111110 )→ 101 ( 01100101 ) e
a 97 ( 01100001 )→ 59 ( 00111011 )→ 97 ( 01100001 ) a
d 100 ( 01100100 )→ 100 ( 01100100 )→ 100 ( 01100100 ) d
32 ( 00100000 )→ 98 ( 01100010 )→ 32 ( 00100000 )
M 77 ( 01001101 )→ 77 ( 01001101 )→ 77 ( 01001101 ) M
e 101 ( 01100101 )→ 62 ( 00111110 )→ 101 ( 01100101 ) e
深入りすると、数学的な話題がいっぱい出てくるのですが、今回はRSA暗号の仕組みだけに着目して整理しました。拡張ユークリッドの互除法であるとか、合同式であるとか、フェルマーの小定理とか、本当は触れなければならない話はいっぱいあるのですが、今回はこれでおしまいにします。それではまた。