RSA方式による暗号/復号化の例 1.平文 暗号/復号化の対象とする平文は「あおもり」とする。 先ずこれをJISコードで符号化し二進数で表わす。 (ひらがな) あ お も り (JISコード) 2422 242A 2462 246A (二進数) 00100010 00101010 01100010 01101010 但し、JISコード中のひらがなを表わす上位1バイト「24」は省略した。 2.暗号文 暗号/復号化の計算を簡単にするため鍵長を3ビットとする。 そうすると、暗号化対象の平文は次のような11ブロックに分割される。 <平文> 001┴000┴100┴010┴101┴001┴100┴010 ┴ 011┴010┴10△┴ (1) (0) (4) (2) (5) (1) (4) (2) (3) (2) (4) → (M) ここで、△はブロック長を一定にするために挿入したスペースである。 鍵長3ビットの場合、各ブロックの数値は0〜7でありこれを一義的に表示するためには 8(2の3乗)進数以上を使用しなければならない。 従って、公開鍵 Nは8(mod8)以上でなければならない。 二つの素数 p,qを任意に p=3,q=5 とする。 N=pq=3x5=15>8 次に或数 eを適当に定め e=3とする。 オイラー関数 φ(N)=(p-1)(q-1)=2x4=8 となるから、mod8において eの逆数 d, d=3 ∵ed=3x3=8+1=1 (mod8)を求める。 上記結果から公開される数は N=15, e=3 及び鍵長 3ビット となる。 ここで、暗号文は modN(N=15) の数値0〜14で表示されるので、そのプロック長は 4ビットになる。 e 暗号化計算式 C=M (modN) により上記平文 Mの暗号化を行う。 これは、各ブロックの値 Mを三乗し次のようになる。 (1)→1(mod15)=1, (0)→0(mod15)=0, (4)→64(mod15)=4, (2)→8(mod15)=8, (5)→125(mod15)=5, (1)→1(mod15)=1, (4)→64(mod15)=4, (2)→8(mod15)=8, (3)→27(mod15)=12, (2)→8(mod15)=8, (4)→64(mod15)=4, <暗号文> 0001┴0000┴0100┴1000┴0101┴0001┴0100┴1000┴1100┴1000┴0100┴ (1) (0) (4) (8) (5) (1) (4) (8) (12) (8) (4) → (C) 3.復号文 d 復号化計算式 M=C (modN) により上記暗号文 Cの復号化を行う。 これは、各ブロックの値 Mを三乗し次のようになる。 (1)→1(mod15)=1, (0)→0(mod15)=0, (4)→64(mod15)=4, (8)→512(mod15)=2, (5)→125(mod15)=5, (1)→1(mod15)=1, (4)→64(mod15)=4, (8)→512(mod15)=2, (12)→1728(mod15)=3, (8)→512(mod15)=2, (4)→64(mod15)=4, <復号文> 001┴000┴100┴010┴101┴001┴100┴010┴011┴010┴100┴ (1) (0) (4) (2) (5) (1) (4) (2) (3) (2) (4) → (M) 本復号文と2.項の平文を比較すれば、復号化が正しく行われたことが分かる。 4.結果の検討 (1)RSA方式による暗号/復号化の例を上記の如く示した。 ここでは、計算を簡単にし暗号/復号化の手順を分かり易くするため鍵長を極端に 短く3ビットにした。実際には、鍵長が長い程解読が難しくなるが、反面処理時間 を要するため用途に適した鍵長が選択されている。例えば、MS社のInternet Explorer 4.xでは 512-768-1024 ビットが使用されている。 (数学的にはNの素因数分解(p,q)が困難な値、10進数でN>160桁が用いられる) (2)本例では公開される数は N=15, e=3 及び鍵長 3ビット である。 しかし、その他にもN進数を表現できる最小ビット数を暗号文のブロック長とする、 或いは最終ブロックに余白が生じた場合の処置方法、平文の使用コード等、別途取 り決めが必要である。 (3)復号化計算式における検算例 3 3x3 8+1 M=12 =(3) =3 (mod8)=3 ;検算終り これは、一般的に次式で表わせる。 d ed M=C =(M) =M ∵ ed=1 at modφ(N) 5.参考 (1) RSA;発明者三人、Rivest,Shamir,Adlemanの頭文字を連ねたもの。 (2) 参考文献 辻井重男著:暗号、ポストモダンの情報セキュリティ;講談社選書メチエ73,'99.4,P201〜209 菅野他3著:ネットワークセキュリティと暗号化;カットシステム,'98.11,P54〜79 (3)m0d N;N進数のこと。16進数の例では0から15までの数しかなく、16は0に戻る 整数の世界である。詳しくは前記参考文献等を参照のこと。 以上