Python で公開鍵暗号アルゴリズム RSA を実装してみる

はじめに

数年前、はてなブログに 公開鍵暗号アルゴリズム RSA を使って実際に暗号化してみる という記事を書きました。これは Ruby を使って公開鍵暗号アルゴリズムを実際に実装してみるという内容です。数年を経て、久しぶりにこの記事の内容を復習しようと思い立ちました。今度は Python で実装してみます。

RSA について

RSA は 公開鍵暗号 アルゴリズムのひとつです。現在、公開鍵暗号アルゴリズムの中では最も広く使われています。

公開鍵暗号アルゴリズムでは 2 つの鍵を使いますが、RSA では公開鍵と呼ばれる鍵で暗号化し、秘密鍵と呼ばれる鍵で復号します。その名の通り、公開鍵は誰にでも公開できる鍵で、それに対して秘密鍵は決して自分以外に見られないように隠しておく必要のある鍵です。そして、RSA のアルゴリズムはべき乗と余剰のみで表すことのできる、非常にシンプルなものです。

暗号化は次の式で表せます。

暗号文 =  {平文}^{E} \bmod N

$\left\{ E, N \right\}$ のペアが公開鍵に相当します。

復号は次の式で表せます。

平文 =  {暗号文}^{D} \bmod N

$\left\{ D, N \right\}$ のペアが秘密鍵に相当します。

この $E, D, N$ を求めるには 2 つの素数を使います。なんと、材料はこれらの素数のみです

まず $N$ を求めます。

N = p \cdot q

$p, q$ はそれぞれランダムで十分に大きい素数です。

次に $L$ を求めます。$L$ は前述の式には登場しない値ですが、残りの値を求めるために利用します。

L = lcm (p - 1, q - 1)

ここで $lcm$ とは最小公倍数 (Least Common Multiple) のことです。

それから $E$ を求めます。

1 \lt E \lt L

gcd (E, L) = 1

$gcd$ とは最大公約数 (Greatest Common Divisor) のことです。つまり $E, L$ は 互いに素 な任意の整数です。

最後に $D$ を求めます。

1 \lt D \lt L

(E \cdot D) \bmod L = 1

つまり $D$ は $E$ との積の余剰が 1 となる任意の整数です。

なお、秘密鍵を使わずに暗号化の際の $暗号文 = {平文}^{E} \bmod N$ という式を解いて暗号文から平文を得るのは難しいです。離散対数問題 を解くことになり、その計算が非常に困難だからです。また $N$ を 素因数分解 して $p, q$ を得、それから $D$ を求めるという解読方法も考えられます。しかし、大きな 2 つの素数の積である大きな整数 $N$ を素因数分解することが非常に困難です。これらの性質が RSA の安全性の根拠となっています。

実装

RSA のアルゴリズムを Python で実装し、実際に平文 (テキスト) を暗号化して、さらに暗号文を復号してみます。

from math import gcd


def lcm(p, q):
  '''
  最小公倍数を求める。
  '''
  return (p * q) // gcd(p, q)


def generate_keys(p, q):
  '''
  与えられた 2 つの素数 p, q から秘密鍵と公開鍵を生成する。
  '''
  N = p * q
  L = lcm(p - 1, q - 1)

  for i in range(2, L):
    if gcd(i, L) == 1:
      E = i
      break

  for i in range(2, L):
    if (E * i) % L == 1:
      D = i
      break

  return (E, N), (D, N)


def encrypt(plain_text, public_key):
  '''
  公開鍵 public_key を使って平文 plain_text を暗号化する。
  '''
  E, N = public_key
  plain_integers = [ord(char) for char in plain_text]
  encrypted_integers = [pow(i, E, N) for i in plain_integers]
  encrypted_text = ''.join(chr(i) for i in encrypted_integers)

  return encrypted_text


def decrypt(encrypted_text, private_key):
  '''
  秘密鍵 private_key を使って暗号文 encrypted_text を復号する。
  '''
  D, N = private_key
  encrypted_integers = [ord(char) for char in encrypted_text]
  decrypted_intergers = [pow(i, D, N) for i in encrypted_integers]
  decrypted_text = ''.join(chr(i) for i in decrypted_intergers)

  return decrypted_text


def sanitize(encrypted_text):
  '''
  UnicodeEncodeError が置きないようにする。
  '''
  return encrypted_text.encode('utf-8', 'replace').decode('utf-8')


if __name__ == '__main__':
  public_key, private_key = generate_keys(101, 3259)

  plain_text = 'Welcome to ようこそジャパリパーク！'
  encrypted_text = encrypt(plain_text, public_key)
  decrypted_text = decrypt(encrypted_text, private_key)

  print(f'''
秘密鍵: {public_key}
公開鍵: {private_key}

平文:
「{plain_text}」

暗号文:
「{sanitize(encrypted_text)}」

平文 (復号後):
「{decrypted_text}」
'''[1:-1])

stdout

秘密鍵: (7, 329159)
公開鍵: (46543, 329159)

平文:
「Welcome to ようこそジャパリパーク！」

暗号文:
「㬨段Ɖ𗁣턐揅段𣸲𫲮턐𣸲񐌅𮦙嬷𴱔掀𠦅𑆜𵨀𑆜?񈚫ꭜ」

平文 (復号後):
「Welcome to ようこそジャパリパーク！」

解説

gcd(), lcm()

最大公約数を求めるための関数 gcd() は math モジュールで提供されています。しかし、最小公倍数を求めるための関数 lcm() は提供されていないため自前で実装する必要があります。

しかし心配いりません。2 つの整数 $p, q$ について

p \cdot q = gcd(p, q) \cdot lcm(p, q)

という式が成り立ちます。つまり

lcm(p, q) = \frac{p \cdot q}{gcd(p, q)}

という簡単な式で最小公倍数を求めることができます。

def lcm(p, q):
  return (p * q) // gcd(p, q)

なお // は切り捨て除算演算子です。/ で除算した結果に math.floor() を適用したものです。浮動小数点数ではなく整数を return するために使っています。

generate_keys()

2 つの素数から公開鍵と秘密鍵を生成する関数です。上述のアルゴリズムをそのまま素直に実装しています。なお、返り値は公開鍵と秘密鍵のタプルで、それぞれの鍵は 2 つの整数のタプルで表現しています。

def generate_keys(p, q):
  # ここに E, D, N を求める処理を実装する。

  # (E, N) が公開鍵で (D, N) が秘密鍵を表す。
  return (E, N), (D, N)

encrypt()

公開鍵を使って平文を暗号化する関数です。文字列である平文 plain_text を整数値である $E, N$ を使って計算するために、まず文字列を整数のリストに変換します。具体的には ord() を使って文字列を 1 文字ずつ Unicode コードポイントを表す整数に変換します。

>>> plain_text = 'Welcome to ようこそジャパリパーク！'
>>> plain_integers = [ord(char) for char in plain_text]
>>> plain_integers
[87, 101, 108, 99, 111, 109, 101, 32, 116, 111,
 32, 12424, 12358, 12371, 12381, 12472, 12515, 12497, 12522, 12497,
 12540, 12463, 65281]

そして、それぞれの整数に ${平文}^{E} \bmod N$ という式を適用します。なお冪剰余の計算には組み込み関数の pow() を使います。

>>> encrypted_integers = [pow(i, E, N) for i in plain_integers]
>>> encrypted_integers
[15144, 27573, 393, 94307, 53520, 25541, 27573, 146994, 179374, 53520,
 146994, 328453, 190873, 23351, 216148, 25472, 133509, 70044, 219648, 70044,
 56034, 296619, 43868]

最後に、暗号化した整数を chr() で文字に変換し、連結して暗号文の文字列を生成します。

>>> encrypted_text = ''.join(chr(i) for i in encrypted_integers)
>>> encrypted_text
'㬨段Ɖ𗁣턐揅段𣸲𫲮턐𣸲\U00050305\U0002e999嬷\U00034c54掀𠦅𑆜\U00035a00𑆜\udae2\U000486abꭜ'

ただし、暗号化された整数は Unicode コードポイントとして必ずしも正しいわけではありません。そのため、元の平文によっては暗号文を print() するとエラーになる可能性があります。

>>> print(encrypted_text)
UnicodeEncodeError: 'utf-8' codec can't encode character '\udae2' in position 20: surrogates not allowed

なお説明の都合上、不正な文字列を無理やり print() するために下処理する関数 sanitize() を実装しています。

decrypt()

秘密鍵を使って暗号文を復号して平文に戻す関数です。encrypt() と同様に、文字列である暗号文 encrypted_text を整数値である $D, N$ を使って計算するために、まず整数のリストに変換します。

>>> encrypted_integers = [ord(char) for char in encrypted_text]
>>> encrypted_integers  # encrypt() 内の encrypted_integers と同じリスト。

そして、それぞれの整数に ${暗号文}^{D} \bmod N$ という式を適用します。

>>> decrypted_intergers = [pow(i, D, N) for i in encrypted_integers]
>>> decrypted_intergers
[87, 101, 108, 99, 111, 109, 101, 32, 116, 111,
 32, 12424, 12358, 12371, 12381, 12472, 12515, 12497, 12522, 12497,
 12540, 12463, 65281]

お、見覚えのある整数ですね

最後に、復号した整数を chr() で文字に変換し、連結して平文の文字列を生成します。

>>> decrypted_text = ''.join(chr(i) for i in decrypted_intergers)
>>> decrypted_text
'Welcome to ようこそジャパリパーク！'

見事、ジャパリパークが戻ってきました

感想

相変わらず、RSA のシンプルさ、そして公開鍵と秘密鍵、暗号化と復号の対称性に惚れ惚れします。そして Python は本当にアルゴリズムを表現しやすいですね。特にリスト内包表記の強力さにより、シンプルで快適に書けました