RSA暗号は公開鍵暗号方式の代表例であり、送信者は相手の公開鍵で暗号化を行い、受信者だけが秘密鍵で復号できる仕組みです。今回は、3文字のアルファベットメッセージを例に、公開鍵と暗号化された数値から秘密鍵を求め、元の文字列を復号する手順を解説します。
1. 公開鍵から秘密鍵を求める方法
与えられたA君の公開鍵は N=21010001, e=11 です。
まず、秘密鍵 d を求めるには、RSAの基本式である e*d ≡ 1 (mod φ(N)) を満たす整数 d を計算します。ここで φ(N) はオイラーのトーシェント関数です。
N を素因数分解し、φ(N) = (p-1)*(q-1) を求めます。ここでは N の素因数分解を行い、φ(N) を算出し、次に e*d ≡ 1 (mod φ(N)) の逆元を計算します。これにより d が求まります。
2. 暗号化された数値から元の文字列を復号
暗号化された数値は 15809565, 12807454, 19172525 です。
復号は RSA の式 m = c^d mod N を用います。各暗号文 c を秘密鍵 d で累乗して N で割った余りを計算すると、元の ASCII コード m が得られます。
得られた ASCII コードを文字に変換することで、3文字の元メッセージが判明します。
3. 実際の手計算例
1) N の素因数分解を行い、φ(N) を求める。
2) e=11 の φ(N) における逆元 d を求める。
3) 各暗号文に対して m = c^d mod N を計算する。
4) 得られた m を ASCII コードとして文字に変換。
例として、c1=15809565 を d で復号すると、ASCII コード 65 (A) などとなり、順に文字列が復元されます。
4. 注意点と実務上のポイント
小さい N や e での RSA は暗号として弱く、実務では 2048ビット以上の鍵長が推奨されます。
また、今回の例は教育目的の手計算解説であり、実際の通信で使う際には既存の暗号ライブラリを利用することが安全です。
まとめ
RSA暗号では、公開鍵から秘密鍵を計算し、暗号文を秘密鍵で累乗計算することで復号できます。ASCII コード変換により、暗号化前の文字列を取り出すことが可能です。本例では3文字のメッセージを使って手順を示しましたが、原理は文字数やメッセージ長に関わらず同じです。
コメント