この記事は中国語版をもとにした日本語版です。技術用語は、初出では English term（日本語の専門用語）という形で表記します。説明文は日本語として自然になるように整理し、コード、画像、リンク、記事の構成は原文に対応させています。 RSA 暗号化アルゴリズムの解説
#1. RSA 暗号化アルゴリズムの数学的原理
#1. 鍵ペアの生成
#手順は次のとおりです。
- 二つの大きな素数を選ぶ: \( p \) と \( q \)。
- \( n \) を計算する:
$$
n = p \times q
$$
- Euler’s totient function（オイラーのトーシェント関数、$\varphi(n)$）を計算する:
$$
\varphi (n) = (p-1) \times (q-1)
$$
- public exponent（公開指数、$e$）を選ぶ。$1
- private exponent（秘密指数、\( d \)）を計算する。次の式を満たす値を選びます。
$$
d \times e \equiv 1 \pmod{\varphi (n)}
$$
これは、\( d \) が $\varphi(n)$ を法としたときの \( e \) の乗法逆元であることを意味します。
- key pair（鍵ペア）を生成する:
- public key（公開鍵）: \( (e, n) \)
- private key（秘密鍵）: \( (d, n) \)
2. 暗号化の流れ
#暗号化する plaintext（平文）を \( M \)（\( M < n \)）とします。
$$
C = M^e\;mod\;n \; \text{即} \; M^e \equiv C(mod\;n)
$$
- ここで、\( C \) は ciphertext（暗号文）、\( M \) は平文です。
3. 復号の流れ
#秘密鍵 \( (d, n) \) を使って暗号文 \( C \) を復号します。
$$
M = C^d\;mod\;n\;即\;C^d \equiv M(mod\;n)
$$
- 復号すると元の平文 \( M \) が得られます。
2. RSA アルゴリズムの数学的背景
#RSA の安全性は、次の数学的な難問に基づいています。
- integer factorization problem（素因数分解問題）: \( n = p \times q \) が与えられたとき、\( n \) を分解して \( p \) と \( q \) を求めるのは、特に両方が非常に大きな素数の場合、極めて困難です。
- modular exponentiation（剰余べき乗）とEuler’s theorem（オイラーの定理）:
M^{\varphi (n)} \equiv 1 \pmod{n}
$$
- \( d \) と \( e \) が $d \times e \equiv 1 \pmod{\varphi (n)}$ を満たすように選ぶことで、暗号化と復号が互いに逆の操作になることを保証できます。
条件:
e: $1d: 次の式を満たす。
$d \times e \equiv 1(mod\;\varphi(n))$
$$
\begin{align}
C = M^e\;mod\;n \; \text{即} \; M^e \equiv C(mod\;n) \tag{1}
\end{align}
$$$$
\begin{align}
M = C^d\;mod\;n\;即\;C^d \equiv M(mod\;n)
\end{align} \tag{2}
$$式 (1) の両辺を d 乗すると式 (2) が得られます。
$$
\begin{align}
&M^{de} \equiv C^d\equiv M(\text{mod n}) \text{即} \\
&M^{de}\equiv M(\text{mod n})
\end{align}
$$==なぜ暗号文 C を d 乗すると元の平文を復号できるのかを示します。==
$$
\begin{align}
&M^{\varphi(n)}\equiv 1 \text{(mod n)} \\
&d\times e\equiv 1(\text{mod $\varphi(n)$}) \\
&\text{そのため$\varphi(n)\mid de - 1$} \\
&\text{de - 1 は $\varphi(n)$ の整数倍}\\
&\text{したがって }M^{de-1}\equiv 1(\text{mod n}) \\
\text{証明終わり}
\end{align}
$$3. RSA の実際の利用場面
#- 暗号化通信: 対称鍵を暗号化するために使われます（TLS/SSL の証明書交換における鍵交換など）。
- digital signature（デジタル署名）: メッセージやファイルの完全性と送信元を検証するために使われます（メール署名、ソフトウェア配布の検証など）。
- authentication（認証）: データが正当な送信者から来たことを確認するために使われます（デジタル証明書など）。
RSA と Hash の組み合わせ
#RSA と hash algorithm（ハッシュアルゴリズム）の組み合わせ
#1. デジタル署名
#RSA は hash algorithm（ハッシュアルゴリズム）と組み合わせて**digital signature（デジタル署名）**に使われます。これにより、データの完全性と送信元の真正性を確認できます。流れは次のとおりです。
- 手順 1: メッセージ \( M \) のハッシュを計算し、hash value（ハッシュ値）\( H (M) \) を得る。
- 手順 2: 送信者の秘密鍵 \( d \) でハッシュ値を暗号化し、署名 \( S \) を生成する。
$$
S = H (M)^d \mod n
$$- 手順 3: 署名 \( S \) とメッセージ \( M \) を受信者へ送る。
- 手順 4（検証側）:
- 受信者は送信者の公開鍵 \( e \) で署名を復号する。
$$
H' (M) = S^e \mod n
$$- 受信者はメッセージ \( M \) のハッシュ値 \( H (M) \) を再計算し、復号して得た \( H' (M) \) と比較します。
- \( H (M) = H' (M) \) なら署名は有効で、メッセージは改ざんされていません。
2. なぜ Hash アルゴリズムと組み合わせるのか
#- 性能最適化: RSA は大きなデータの暗号化が遅いため、通常はメッセージ全体ではなくハッシュ値だけに署名します。
- データ完全性: ハッシュアルゴリズムは任意の長さのメッセージを固定長のハッシュ値へ変換し、データの改ざんをすばやく検出できます。
- collision attack（衝突攻撃）の防止: 強力なハッシュアルゴリズムを使うことで、異なるメッセージから同じハッシュ値が生成される可能性を下げ、安全性を高めます。
2.1 性能优化
#
この最適化はメッセージへの署名に関するものであり、大きなファイルそのものを暗号化する最適化ではありません。 例:
- 1 GB のファイルに署名するとします。RSA で直接署名すると 1 GB のデータを処理する必要があり、非常に時間がかかります。
- 先にファイルへ SHA-256 などのハッシュアルゴリズムを適用し、256 ビット（32 バイト）のハッシュ値に変換してから RSA で署名すれば、処理対象は 32 バイトだけです。署名の効率を大幅に高められます。
2.2 データ完全性
#例:
- 送信者がメッセージ \( M \)（たとえば “Hello, World!"）を送る。
- 送信前にハッシュ値 \( H (M) \) を計算し、( H (M) = $\text{0x1a2b3c...}$) を得る。
- 送信者は秘密鍵で \( H (M) \) に RSA 署名を行い、署名とメッセージ \( M \) を一緒に送る。
- 受信者は受信後にメッセージのハッシュ値 \( H' (M) \) を再計算し、署名を検証する。
- \( H (M) = H' (M) \) なら、メッセージは改ざんされていない。
- 一致しなければ、メッセージが変更された可能性がある。
2.3 衝突攻撃の防止
#例:
- Alice が正当なメッセージ ($M_{1}$) に署名し、($S = H (M_{1})^d\text{(mod n)}$) を生成するとします。
- Bob は別のメッセージ ($M_{2}$) を探し、($H(M_{2})=H(M_{1})$) を成立させて Alice の署名を偽装しようとします。
- Alice が SHA-256 などの強力なハッシュアルゴリズムを使っていれば、Bob がそのような ($M_{2}$) を見つけるのはほぼ不可能です。
- したがって、ハッシュアルゴリズムと組み合わせた RSA デジタル署名は、衝突攻撃を効果的に防止できます。
完全な例: RSA と Hash アルゴリズムを組み合わせたデジタル署名の流れ
#Alice が Bob にメッセージを送り、その真正性と完全性を保証するものとします。
Alice がメッセージのハッシュ値を計算する:
- メッセージ \( M \): “Hello, Bob!”
- SHA-256 などのハッシュアルゴリズムを使い、ハッシュ値 ( H (M) ) を得る。
Alice がデジタル署名を生成する:
- Alice は秘密鍵 \( d \) でハッシュ値 \( H (M) \) を RSA 暗号化し、署名 \( S \) を生成する。
$$
S = H (M)^d \mod n
$$- Alice は署名 \( S \) と元のメッセージ \( M \) を Bob に送ります。
- Bob が署名を検証する:
- Bob はメッセージ \( M \) と署名 \( S \) を受け取り、Alice の公開鍵 \( e \) で署名を復号します。
$$
H' (M) = S^e \mod n
$$- Bob は受信したメッセージ ( M ) のハッシュ値 ( H (M) ) を再計算します。
- \( H' (M) = H (M) \) なら署名は有効で、メッセージは改ざんされておらず、Alice から送られたものだと確認できます。
まとめ
#Hash アルゴリズムを組み合わせることで、RSA 暗号化システムの性能と安全性が向上します。
- 性能最適化: メッセージ全体ではなく、固定長のハッシュ値だけに RSA 演算を行います。
- データ完全性: メッセージを改ざんするとハッシュ値が変わるため、改ざんを検出できます。
- 衝突攻撃の防止: 強力なハッシュアルゴリズムによって署名の安全性を保ちます。
そのため、RSA と Hash アルゴリズムの組み合わせは、SSL/TLS、デジタル証明書、メール署名など、現代の安全な通信で重要な役割を果たします。
