RSA暗号を実装してみる

情報セキュリティ

こんにちは。今回も暗号について取り上げます。今回はRSA暗号です。

RSA暗号とは

1977年にリベスト(Rivest)・シャミア(Shamir)・エーデルマン(Adleman)によって発明された暗号で、3人の頭文字をとって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暗号の仕組みだけに着目して整理しました。拡張ユークリッドの互除法であるとか、合同式であるとか、フェルマーの小定理とか、本当は触れなければならない話はいっぱいあるのですが、今回はこれでおしまいにします。それではまた。

Posted by 春日井 優