本丸の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のページにはコードもあるので参考になります)と呼ばれる手法を用います。
最近のコメント