RSA暗号

RSA 暗号は、1977 年に Rivest, Shamir, Adleman が提案した公開鍵暗号です。

登場人物と役割

メッセージを送る人が暗号化を行います。ここでは、インターネットのユーザーとします。
メッセージを受け取る人が復号します。ここでは Google のような、不特定多数のユーザーから通信をリクエストされるサーバーとします。

使用するデータ

メッセージを受け取る人（サーバー）が、以下のデータを用意します。

データ	説明
$p,q$	大きな素数（通常は 1024 ビットほど）
$n$	$=pq$ （通常は 2048 ビットほど）
$\phi(n)$	$=(p-1)(q-1)$
$e$	$\phi(n)$ と互いに素な整数
$d$	$ed=1 \mod{\phi(n)}$ を満たす

例

p = 16880257378027019788074864340275252535154933609161575622590215294476509272692245240226073342153800325766890817875651475286366033603531042578023499649593293973836601851619163529124441048069147347776941889130390750049976595791974711694003205841886418632416382457385831936891663906403927286260058808974780117219
q = 14085105182901904812605159547109048856176943154419273108551583801026252307188953192477344960956654295764752991644074063405434038316342059813221639534278417189036039939172505905242459250885954876680850446688524853664278308502899897230257044699508388549097567665391759276584107510673356892960338745601683217957
n = 237760200683966494720286134646012922961768521156342766505379416363935452536548405435288083418180501332982110023401504372780456916584325797453285387269485858326675561659966805225729554286687407231335709990164390576854705803533475901790363566074643194723777683588167061235666497943076200323869820150424820245716063616021082204755637328858279022367569724723491264472416865417921025970143153118858170822613382235986494533741578244303265926856261989532814938021251315936558510077095058857006433624554882538142874124466520668483290413603043302044173982042692956741224320616106020310242710500607093513057803139829585701583
φ(n) = 237760200683966494720286134646012922961768521156342766505379416363935452536548405435288083418180501332982110023401504372780456916584325797453285387269485858326675561659966805225729554286687407231335709990164390576854705803533475901790363566074643194723777683588167061235666497943076200323869820150424820245685098253460153280154957304970894720976237847959910415741275066322418264390261954686154752519502927614454850724221852705611465854936388887141569798837379604773685868286303389422639533325599780313685081788647605064769035509308168693119913731501298149559710370493328429096766939083529809333837405585253122366408
e = 65537
d = 103561388051398562007496345569755785264303282190655059167532246204814096283142511582094597391631911607966603792178759232576879062831929508737071954239509640535777966387619397011973020685533038235282499616693359375725077923427477655255927466273506029213802245383643086043507268417581720470042691701085294089343833479458527786369583765318814726108727674563431385747752232223625612635372656033553161808165319921299848463824053699961623270748037859107729244207269759034890776143259785380146606013588832702663447285330950976988523851392510849044067585935213039616270080047950826815330409434036375440495026928859051086737

鍵

公開鍵

$n,e$ を公開鍵とします。

ユーザー: 知っている
サーバー: 知っている

秘密鍵

$d$ を秘密鍵とします。

ユーザー: 知らない
サーバー: 知っている

暗号文生成

インターネットのユーザーが、送りたいメッセージの暗号化を行います。

送りたいメッセージ $m$ は数値である必要があります。

送りたいメッセージの文字列がくぁwせdrftgyふじこlpであれば、以下で得られる93590581839664002503925501023619874147572956003341946001938410608を $m$ として扱います。

int.from_bytes("くぁwせdrftgyふじこlp".encode('utf-8')) # -> 93590581839664002503925501023619874147572956003341946001938410608

$0 \leq m < n$ を満たすメッセージ $m$ から暗号文 $C$ を作成します。

ユーザーは、公開鍵 $n,e$ とメッセージ $m$ から、暗号文 $C$ を計算します。

C=m^e \mod{n}

計算結果 $C$ をサーバーに送信します。

暗号文からメッセージに変換

サーバーは、受け取った暗号文 $C$ と、秘密鍵 $d$ 、公開鍵の $n$ から、メッセージ $m$ を計算します。

m=C^d \mod{n}

$m$ を数値から文字列に変換することで、ユーザーが送信したメッセージくぁwせdrftgyふじこlpを取得します。

m_int = 93590581839664002503925501023619874147572956003341946001938410608
m = m_int.to_bytes((m_int.bit_length() + 7) // 8).decode("utf-8") # -> くぁwせdrftgyふじこlp

正当性

$ed=1 \mod{\phi(n)}$ は、整数 $k \ge 0$ を用いて $ed=1+k\phi(n)$ と表せます。

よって、

\begin{align*} C^d &= (m^e)^d \mod{n}\\ &=m^{ed} \mod{n}\\ &=m^{1+k\phi(n)} \mod{n}\\ &=m \cdot m^{k\phi(n)} \mod{n}\\ \end{align*}

ここで、 $m^{k\phi(n)} \mod{n}$ の値について 2 つのケースを考える必要があります。

このケースでは、 $m$ が $p$ または $q$ の倍数であることを意味します。

もし $m$ が $p$ の倍数なら、 $m=p \cdot s$ （ $s$ は整数）と表せます。

このとき、 $m = 0 \mod{p}$ かつ $m^{k\phi(n)} = 0 \mod{p}$

よって、
$\begin{align*} C^d &= m \cdot m^{k\phi(n)} \mod{p}\\ &= 0 \mod{p}\\ &= m \mod{p} \end{align*}$
$m$ が $q$ の倍数の場合も同様に、 $C^d = m \mod{q}$

中国剰余定理により、 $C^d = m \mod{p}$ かつ $C^d = m \mod{q}$ であれば、 $C^d = m \mod{n}$ が成り立ちます。

したがって、すべての有効なメッセージ $m$ （ $0 \leq m < n$ ）に対して、

C^d = (m^e)^d \mod{n} = m \mod{n}

が成り立つことから、RSA 暗号の正当性を確認できます。

コード

pip install sympy

from sympy import randprime

message = "これは送信したいメッセージです。"
message_bytes = message.encode("utf-8")
m = int.from_bytes(message_bytes, byteorder="big")
p = randprime(2**1000, 2**1024)
q = randprime(2**1000, 2**1024)
n = p * q
phi_n = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi_n)

print(f"メッセージ: {message}")
print(f"m = {m}")
print(f"p = {p}")
print(f"q = {q}")
print(f"n = {n}")
print(f"φ(n) = {phi_n}")
print(f"e = {e}")
print(f"d = {d}")

if m < n:
    C = pow(m, e, n)
    print(f"C = {C}")
else:
    print(
        "メッセージが長すぎます。短いメッセージを使用するか、より大きな素数を生成してください。"
    )
    exit(1)

decrypted_int = pow(C, d, n)
decrypted_bytes = decrypted_int.to_bytes(
    (decrypted_int.bit_length() + 7) // 8, byteorder="big"
)
decrypted_message = decrypted_bytes.decode("utf-8")

print(f"復号されたメッセージ: {decrypted_message}")

おまけ

RSA 暗号の安全性は、素因数分解の困難性を根拠にしています。ただし、量子コンピュータによって効率よく素因数分解できるようになる可能性があるため、近年はポスト量子暗号（PQC）に移行する動きがあります。

量子コンピュータが実現した後は、従来のコンピュータと量子コンピュータの両方にとって解決するのが難しい問題に基づいている必要があります。PQC には、格子問題の困難性、符号復号問題の困難性、多変数代数方程式の求解困難性、同種写像上の計算問題の困難性、ハッシュ関数の衝突発見困難性に基づいた暗号などが存在します。

参考図書

IPUSIRON, 暗号技術のすべて. 翔泳社, 2017. [Online]. Available: https://www.shoeisha.co.jp/book/detail/9784798148816
黒澤馨, 現代暗号への招待. サイエンス社, 2010. [Online]. Available: https://www.saiensu.co.jp/search/?isbn=978-4-7819-1262-2&y=2010
萩田真理子, 暗号のための代数入門. サイエンス社, 2010. [Online]. Available: https://www.saiensu.co.jp/search/?isbn=978-4-7819-1268-4&y=2010