« RSA暗号の公開鍵と秘密鍵を生成する | トップページ | 1-Click Award »

2008/02/09

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

|

« RSA暗号の公開鍵と秘密鍵を生成する | トップページ | 1-Click Award »

C」カテゴリの記事

Algorithm」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: RSA暗号プログラム:

« RSA暗号の公開鍵と秘密鍵を生成する | トップページ | 1-Click Award »