RSA暗号化ステップバイステップシミュレーター

RSA暗号とは？

RSA (Rivest-Shamir-Adleman) は、1977年にロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンによって発表された、最初の公開鍵暗号系の一つです。同じ鍵で暗号化と復号を行う共通鍵暗号とは異なり、RSAは鍵ペアを使用します。誰でもデータの暗号化に使用できる「公開鍵」と、所有者だけが復号に使用できる「秘密鍵」です。

RSAの数学的安全性は整数因数分解問題に基づいています。2つの大きな素数を掛け合わせるのは簡単ですが、その積を元の素数に分解することは、十分に大きな数では計算上不可能です。

RSA鍵生成の仕組み

RSA鍵生成プロセスには、5つの基本的なステップがあります：

• ステップ 1 – 素数の選択： 2つの異なる大きな素数 p と q を選択します。これらの素数が大きいほど、鍵の安全性は高まります。
• ステップ 2 – モジュラスの計算： n = p × q を計算します。n のビット長が鍵のサイズを決定します（例：2048ビット）。
• ステップ 3 – オイラーのトーシェント： φ(n) = (p−1)(q−1) を計算します。この値は e の選択と d の計算に不可欠です。
• ステップ 4 – 公開指数： 1 < e < φ(n) かつ gcd(e, φ(n)) = 1 となる e を選択します。標準的な選択肢は 65537 です。
• ステップ 5 – 秘密指数： 拡張ユークリッド互除法を使用して、d × e ≡ 1 (mod φ(n)) となる d を計算します。

拡張ユークリッド互除法

秘密指数 d を計算するには、φ(n) を法とする e のモジュロ逆数を見つける必要があります。拡張ユークリッド互除法は、標準的な最大公約数（GCD）アルゴリズムを拡張して、a·x + b·y = gcd(a, b) となる係数 x と y も見つけることで、これを効率的に解決します。

gcd(e, φ(n)) = 1 のとき、このアルゴリズムは e·x ≡ 1 (mod φ(n)) となる x を算出し、d = x mod φ(n) が得られます。

RSAのセキュリティに関する考慮事項

• 鍵サイズ： 現代のRSAでは2048ビットまたは4096ビットの鍵を使用します。この電卓で使用されているような小さな素数は教育目的のみであり、即座に因数分解可能です。
• パディングスキーム： 実際のRSA実装では、生のRSAに対する数学的攻撃を防ぐためにパディング（OAEP、PKCS#1）を使用します。
• パフォーマンス： RSAは共通鍵暗号よりもはるかに低速です。実用的には、RSAでランダムな共通鍵を暗号化し、その共通鍵で実際のデータを暗号化します（ハイブリッド暗号）。
• 量子脅威： 十分に強力な量子コンピュータ上でのショアのアルゴリズムは、大きな数を効率的に因数分解し、RSAを脅かす可能性があります。対抗策として耐量子計算機暗号が開発されています。

RSAの具体的な応用例

• TLS/SSL (HTTPS)： ハンドシェイク中に共通セッション鍵を安全に交換するためにRSAが使用されます。
• 電子署名： 秘密鍵でハッシュを暗号化することで文書に署名し、公開鍵で検証可能にします。
• メール暗号化： PGPやS/MIMEは、メール通信の暗号化にRSAを使用します。
• SSH認証： RSA鍵ペアは、リモートサーバーアクセスのためのパスワードレス認証を提供します。
• コード署名： ソフトウェアパブリッシャーは、真正性と完全性を証明するために実行ファイルにRSAで署名します。

よくある質問