公開鍵暗号アルゴリズム RSA を使って実際に暗号化してみる (Python 編)

rsa.py

from fractions 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 + 1):
    if gcd(i, L) == 1:
      E = i
      break

  for i in range(2, L + 1):
    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 = [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 = [i ** D % N for i in encrypted_integers]
  decrypted_text = ''.join(chr(i) for i in decrypted_intergers)

  return decrypted_text


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


if __name__ == '__main__':
  # 本当は十分に大きい素数を選ぶ必要があるが、
  # 説明のために小さな素数を選ぶ。
  # なお、素数が大きいと encrypted_text を求める際に
  # ValueError: chr() arg not in range(0x110000) になる。
  public_key, private_key = generate_keys(101, 3259)

  plain_text = 'Welcome to ようこそジャパリパーク！'
  print(plain_text)

  encrypted_text = encrypt(plain_text, public_key)
  # print() では
  # UnicodeEncodeError: 'utf-8' codec can't encode character '\udae2' in position 20: surrogates not allowed
  # となる可能性がある。
  safe_print(encrypted_text)

  decrypted_text = decrypt(encrypted_text, private_key)
  print(decrypted_text)