RSA暗号プログラム
本丸のRSA暗号プログラムです。RSA暗号/復号を処理する関数は次のようになります。
//---RSA Encryption & Decryption--- void rsa_angou(int xy[2], int key[2], int stu[3]) { int m, code; (mode == 1) ? (m = bind2(xy)) : (m = bind3(stu)); code = pow_mod(m, key[0], key[1]); (mode == 1) ? (split3(code, stu)) : (split2(code, xy)); }
引数には(2文字を格納した配列、鍵を格納した配列、3文字を格納した配列)を与えます。関数内で使われているmodeという変数はmode == 1のときは暗号モード、mode != 1のときは復号モードで処理するために設定したものです。
また、この関数内にはpow_mod(a, b, c)やbind、splitといった関数が存在していますが、pow_mode(a, b, c)はaのb乗(mod n)を計算するもの(後述)、bindやsplitは次のようになっています。( #define N 28 )
//---{x, y} --> x*N + y--- int bind2(int xy[2]) { return (xy[0]*N + xy[1]); } //---{s, t, u} --> s*N^2 + t*N + u--- int bind3(int stu[3]) { return (stu[0]*N*N + stu[1]*N + stu[2]); } //---m --> {x, y}--- void split2(int m, int xy[2]) { if(m > N*N){ fprintf(stderr, "Error Argument 'm'.\n"); exit(1); } xy[0] = m / N; xy[1] = m - xy[0]*N; } //---m --> {s, t, u}--- void split3(int m, int stu[3]) { if(m > N*N*N){ fprintf(stderr, "Error Argument 'm'.\n"); exit(1); } stu[0] = m / (N*N); stu[1] = (m - stu[0]*N*N) / N; stu[2] = m - stu[0]*N*N - stu[1]*N; }
何故このような関数が必要かというと、今回私がつくったRSA暗号プログラムはブロック長2で暗号化しています。つまり、2文字ずつ読み込んで暗号化しているのですが、RSA暗号で2文字を暗号化すると3文字になって出力されてきます。(←このページの下の方にある例を読むとわかると思います)したがって、
暗号化:2文字をbind2で計算してmする→mを暗号化「m^key1 mod key2」(このとき、(key1, key2) = 公開鍵(e, n)である)→split3でmを3文字に変換して出力
復号化:3文字をbind3で計算してmする→mを復号化「m^key1 mod key2」(このとき、(key1, key2) = 秘密鍵(d, n)である)→split2でmを2文字に変換して出力
このような処理をするためにbindやsplitがあるわけです。
次にpow_modによるaのb乗(mod n)の計算についてですが、普通はa^bを計算した後にnで割った余りを求めればいいわけですが、これは’b’の値が小さいときのみに有効な方法です。RSA暗号では、’b’に該当する’e’や’d’に大きな値(今回は3000までの素数しか使っていませんが、それでも6000くらい)が代入されるので時間がかかります。(単純に言えばb=6000の場合、5999回の乗算を必要とする)
これを高速に計算するにはバイナリ法(このWikipediaのページにはコードもあるので参考になります)と呼ばれる手法を用います。
| 固定リンク
「C」カテゴリの記事
- CG法(2008.12.09)
- NTEmacs + MinGW + MSYSでWindows上にC言語開発環境を構築してみる - その5(2008.10.10)
- NTEmacs + MinGW + MSYSでWindows上にC言語開発環境を構築してみる - その4(2008.10.09)
- NTEmacs + MinGW + MSYSでWindows上にC言語開発環境を構築してみる - その3(2008.10.08)
- NTEmacs + MinGW + MSYSでWindows上にC言語開発環境を構築してみる - その2(2008.10.07)
「Algorithm」カテゴリの記事
- コラッツの問題(2008.02.21)
- フィボナッチ数を求める(2008.02.19)
- べき剰余を求める(2008.02.12)
- RSA暗号プログラム(2008.02.09)
- RSA暗号の公開鍵と秘密鍵を生成する(2008.02.08)
この記事へのコメントは終了しました。
コメント