公開鍵暗号方式：RSAについて

RSAは、GitLabでの登録など開発でも利用する公開鍵暗号方式の暗号です。鍵生成はコマンド実行で作成されていますが、どんなアルゴリズムで動作しているのか調査しました。

RSAの概要

RSAは、公開鍵暗号方式（Public Key Cryptography）の一つで、暗号化やデジタル署名に広く使われています。この仕組みは、1977年にロナルド・リベスト（Ronald Rivest）、アディ・シャミア（Adi Shamir）、レオナルド・エーデルマン（Leonard Adleman）の3名が考案しました。それぞれの頭文字から「RSA」という名前がついています。

RSAは公開鍵暗号方式のため、次の2つの鍵を使います：

• 公開鍵（Public Key）：公開していて誰でも使える鍵 。暗号化に使用。
• 秘密鍵（Private Key）：所有者だけが知っている鍵。復号化に使用。

安全性の理由

RSAは「素因数分解」の難しさを安全性の根拠にしています。巨大な数（n）を2つの素数（pとq）に分解するのが非常に難しいため、秘密鍵の推測を難しくしています。

RSAのアルゴリズム

①鍵の作成

1. 大きな素数を2つ選ぶ（pとq）
   例：p = 61, q = 53
2. これらを掛け合わせて「n」を計算 n = p × q
   例： n = 61 × 53 = 3233
3. オイラー関数 ϕ(n) = (p − 1) × (q − 1) を計算
   例：ϕ(3233) = (61 − 1) × (53 − 1) = 3120
4. 「公開鍵」の指数e を選ぶ
   1 < e < ϕ(n) で、かつ ϕ(n) と互いに素である値(「互いに素」とは、「共通の約数が1のみ」という意味)
   例：e = 17（よく使われる値）
5. 「秘密鍵」の指数d を計算
   d は e × d ≡ 1(modϕ(n)) を満たす値 (e × d をϕ(n)で割った余りが1になるようなd)
   例：17 × 2753 mod 3120 = 46801 mod 3120 = 1
   d = 2753 (詳細な計算は省略)
6. 鍵の完成
   公開鍵：(e, n) 例：(17,3233)
   秘密鍵：(d, n) 例：(2753, 3233)

②メッセージの暗号化

1. 送りたいメッセージを数値Mに変換
   例：「HELLO」をASCIIコードやUnicode値などで1文字ずつ数値に変換
2. 公開鍵 (e,n)を使って暗号文Cを計算

③メッセージの復号化

1. 暗号化されたメッセージCを受信
2. 秘密鍵(d,n)を使って元の数値化されたメッセージMを計算

PythonによるRSAアルゴリズムの実装

RSAを用いた暗号・復号について、Pythonで実装してみます。

generate_large_prime

# 素数生成
def generate_large_prime(bits=8):
  while True:
    prime = random.getrandbits(bits)
    if isprime(prime):
      return prime

非常に大きな素数をランダムに生成します。今回はサンプルのため8ビットの数値を生成していますが、実際の鍵生成では2048ビットから生成されます。
sympyモジュールのisprime(x)はxが素数化を判定する関数です。

generate_keys

 # 鍵の生成
def generate_keys(bits=8):
  p = generate_large_prime(bits)
  q = generate_large_prime(bits)
  while p == q: # 異なる素数にする
    q = generate_large_prime(bits)

  n = p * q
  phi = (p - 1) * (q - 1)

  # 公開鍵の指数eを選ぶ
  e = random.choice([3, 5, 17, 257, 65537]) # よく使われる値
  while gcd(e, phi) != 1: # phiと互いに素な値を選ぶ
    e = random.randint(2, phi - 1)

  # 秘密鍵の指数dを選ぶ
  d = mod_inverse(e, phi)

  return (e, n), (d, n) # 公開鍵, 秘密鍵

前述したアルゴリズムに従って公開鍵・秘密鍵を生成します。 秘密鍵の指数dの計算については、Pythonのsympyモジュールのmod_inverseを利用しています。

encrypt

# 暗号化
def encrypt(plaintext, public_key):
  e, n = public_key
  plaintext_int = [ord(char) for char in plaintext]
  chipertext = [pow(m, e, n) for m in plaintext_int]

  return chipertext

公開鍵を使ってメッセージを暗号化します。
まずメッセージの各文字をord()でUnicode値に変換して数値の配列にします。
その後、各数値を暗号化しますが、暗号化の際にpow()を用います。
powは引数が3つ渡されたとき、以下のような計算を行います。（暗号の計算にとても都合がよい機能です）

• pow(a, b, c) == a ** b % c # aのb乗をcで割った余り

decrypt

# 復号化
def decrypt(ciphertext, private_key):
  d, n = private_key
  decrypted_int = [pow(c, d, n) for c in ciphertext]
  decrypted_text = ''.join(chr(m) for m in decrypted_int)

  return decrypted_text

秘密鍵を使って暗号化されたメッセージを復号します。
暗号化と逆にpow()で各Unicode値を計算し、対応する文字に変換してメッセージを復元します。

実行例

以下に鍵生成し、メッセージ「Hello, world」を暗号化・復号化した結果を記載します。

まとめ

今回は、RSAについて解説しました。暗号化の技術は、業務・私生活問わず様々なところで利用されています。 機会がありましたら各自で調べてみるのも面白いかもしれません。

参考サイト