« シーザー暗号プログラム(その3) | トップページ | xfy Blog Editor »

2007/11/19

アフィン暗号プログラム

昨日のプログラムを応用して早速アフィン暗号プログラムを作ってみました。

/*
  アフィン暗号プログラム
*/

#include <stdio.h>
#include <math.h>
#define  JIS   26
#define  FIRST 'A'

int add_gcd(int a, int b)
{
  int r_pre = a, r = b, r_next;
  int x_pre = 1, x = 0, x_next;
  int y_pre = 0, y = 1, y_next;
  int ans_x, ans_y, ans_gcd;
  int q, k = 1;
  int ans;

  //---拡張ユークリッド---
  while((r_next = r_pre % r) != 0) {
    q      = r_pre / r;
    k++;
    x_next = q * x + x_pre;
    y_next = q * y + y_pre;
    //---変数を更新---
    r_pre = r;
    r     = r_next;
    x_pre = x;
    x     = x_next;
    y_pre = y;
    y     = y_next;
  }
  ans_x = pow(-1, k)   * x;
  ans_y = pow(-1, k+1) * y;
  ans_gcd = (ans_x * a) + (ans_y * b);

  //---一次合同式を解く---
  if(ans_gcd == 1) {
    ans = (ans_x + b) % b;
  } else {
    ans = 0;
  }

  /*最大公約数が1なら逆元を,1でなければ0を返す*/
  return (ans);
}

int main(void)
{
  int  key1, key2;
  int  check, e_k;
  int  input, output;
  FILE *fpi, *fpo;
  char file1[64], file2[64];

  printf("==============================\n");
  printf("平文ファイル:");   scanf("%s", file1);
  printf("暗号ファイル:");   scanf("%s", file2);
  do{
    printf("鍵1を入力   :");   scanf("%d", &key1);
    printf("鍵2を入力   :");   scanf("%d", &key2);
    //---鍵の判定---
    if( (check = add_gcd(key1, JIS)) == 0){
      printf("!!!Input Anothor Key!!!\n");
    } else {
      printf("Key ---> k = (%d, %d)\n", key1, key2);
    }
  }while(check == 0);
  
  //---入力ファイルを暗号化---
  if( (fpi = fopen(file1, "r") ) == NULL){
    printf("Failure.\n");
  } else {
    if( (fpo = fopen(file2, "w") ) == NULL){
      printf("Failure.\n");
    } else {
      while( (input = fgetc(fpi)) != EOF ){
	if(input == ' ' || input == '.' || input == ',' || input == '\n'){
	  fputc(input, fpo);
	} else {
	  //---アフィン暗号の処理---
	  e_k    = ((input - FIRST) * key1 + key2) % JIS;
	  output = FIRST + e_k;
	  fputc(output, fpo);
	}
      }
      fclose(fpo);
    }
    fclose(fpi);
  }
  printf("Encryption Success!!\n");
  printf("==============================\n");
  
  return 0;
}

アフィン暗号は鍵を2つ入力します。例えば鍵k = (a、b)というふうにします。このとき鍵bは任意の整数でかまいませんが、鍵aは使用文字数N(このプログラムの場合は26)と互いに素ではなくてはなりません。(この判定にプログラムでは拡張ユークリッドを使っていますが、別にノーマルのユークリッドでも問題ないです)

この条件を満たしたら次は暗号化関数を作ります。この関数はe_k(x) = (a*x + b) % Nとなります。(引数xは文字コード、つまり文字に割り当てられた数字です)

そして暗号化関数によって得られた値を新しい文字コードとすることで暗号化されるわけです。したがって、アフィン暗号はシーザー暗号のようにシフトした数がどの文字も同じではないので若干複雑な暗号になります。

講義で示された例題は「PAY ME NOW」を鍵k = (7, 3), N = 26で暗号化すると「EDP JF QXB」となるのですが、このプログラムでも同様の結果を得ることができました。

今回のプログラムでは使用文字数と先頭の文字をマクロにしてあるので、使いたい文字を変更することが容易になりました。

|

« シーザー暗号プログラム(その3) | トップページ | xfy Blog Editor »

Algorithm」カテゴリの記事

C」カテゴリの記事

コメント

コメントを書く



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


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



トラックバック

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

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

« シーザー暗号プログラム(その3) | トップページ | xfy Blog Editor »