« ヒル暗号完成 | トップページ | エラトステネスの篩 »

2008/01/31

ヒル暗号プログラム解説

昨日は眠くてできなかったヒル暗号プログラムの解説をしたいと思います。前回に引き続きプログラムを表示します。

void hill(int u[2], int key[4], int hkey[4])
{
  int i, det_a, t, angou[2];
  det_a = (key[0]*key[3] - key[1]*key[2] + 28) % 28;
  if(det_a < 0) det_a += 28;
  t = add_gcd(det_a, 28);
  if(t == 0){
   fprintf(stderr, "This keys are incorrect!\n");
   exit(1);
  }
  angou[0] = ((key[0]*u[0] + key[1]*u[1])+28) % 28;
  angou[1] = ((key[2]*u[0] + key[3]*u[1])+28) % 28;
  for(i=0 ; i<2 ; i++){
    if(angou[i] < 0) angou[i] += 28;
  }
  //---Hukugou Kagi---
  hkey[0] = (t*key[3]+28) % 28;
  hkey[1] = (t*key[1]*(-1)+28) % 28;
  hkey[2] = (t*key[2]*(-1)+28) % 28;
  hkey[3] = (t*key[0]+28) % 28;
  for(i=0 ; i<4 ; i++){
    if(hkey[i] < 0) hkey[i] += 28;
  }
  u[0] = angou[0];
  u[1] = angou[1];
}

このヒル暗号プログラムはブロック長2で暗号化を行います。(平文から2文字ずつ読み込むということ)

このvoid関数hillの引数は(数値化した2文字、4つの暗号鍵、4つの復号鍵)となっていて、この関数に2文字と暗号鍵を渡し、暗号化された2文字と復号鍵を取り出すようにしました。(復号鍵を取り出すのはプログラム実行時に復号鍵を表示するためですが、この関数内で表示するようにすれば取り出す必要はないです)

この関数の処理は基本的にはヒル暗号のロジックどおりに行っています。

1.暗号鍵A=(a&b c&d)の行列式を計算し、GCD(detA、28)=1であることを確認(このときプログラム内では拡張ユークリッドを用いて、GCD(detA、28)=1であればdetAの逆元を、そうでなければ0を変数tに代入している)

2.暗号化する

3.復号鍵を求める

4.暗号化した文字を取り出すために変数を入れ替え

このプログラムで頻繁に行っている

(var + 28) % 28;
if(var < 0) var += 28;

という操作はmod 28を守るために行っています。つまり、0~27までの数字のみ使用できる。29なら1、-3なら25と同じになります。そのため、1行目ではのようにvarの値を変換します。では何故2行目が必要かというと、varに入っている値が-28より小さい場合には1行目で変換しても、-1~-27になってしまうので、2行目のようにしてmod 28に収めてやる必要があります。(varの値の絶対値をとってから1行目の計算をすれば2行目は必要ないかな?)

|

« ヒル暗号完成 | トップページ | エラトステネスの篩 »

Algorithm」カテゴリの記事

C」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/222903/17913149

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

« ヒル暗号完成 | トップページ | エラトステネスの篩 »