科普一下放射密码的原理及其实现方法

放射密码可以说是凯撒密码的升级，在凯撒密码中，明文字母表向前或者向后移动一个固定数值，得到密文，在仿射密码中，给加密函数添加了一个系数。

加密函数有参数（a,b），作为密钥，x表示的就是明文字符。明文字母可以转换为0~25这些数值，p=26.解密函数中，需要求a的逆元，例如a=7，那么a的逆元可以是15（最小的正整数）。

（乘法逆元的求解，可以借助扩展欧几里得算法实现。）

仿射密码的实现过程如下。

#include
#include


//最大公约数
int gcd(int m, int n)
{
  int r;
  while (0 != n)
  {
    r = m % n;
    m = n;
    n = r;
  }
  return m;
}


//扩展欧几里得算法
//m*x+n*y=gcd(m,n)
int exgcd(int a, int p, int *x, int *y)
{
  if (0 == p)    //递归终止条件
  {
    *x = 1;
    *y = 0;
    return a;
  }
  int gcd = exgcd(p, a % p, x, y);    //递归求解最大公约数。
  int temp = *x;
  *x = *y;            //回溯表达式1：x1 = y2;
  *y = temp - a / p * (*y);    //回溯表达式2：y1 = x1 - m/n * y2;
  return gcd;
}


//a*x=1(mod p) 乘法逆元
//a与p互素，a关于模p的乘法逆元有解
int inv(int a, int p, int *x, int *y)
{
  int gcd = exgcd(a, p, x, y);
  if (1 != gcd)    //说明乘法逆元不存在
  {
    return -1;
  }
  else
  {
    return (*x + p) % p;    //为了使余数一定为正数
  }
}




//加密算法
void encrypt(char data[], int a, int b, int p){
  int i = 0;
  while(data[i]){
    if(data[i] >= 'A' && data[i] <= 'Z'){
      data[i] = (a * (data[i] - 'A') + b) % p + 'A';
    }
    else if(data[i] >= 'a' && data[i] <= 'z'){
      data[i] = (a * (data[i] - 'a') + b) % p + 'a';
    }
    else{
      data[i] = data[i];
    }
    i ++;
  }
}


//解密算法
void decrypt(char data[], int a, int b, int p){
  int i = 0;
  int x = 0, y = 0;
  int invA = inv(a, p, &x, &y);
  while(data[i]){
    if(data[i] >= 'A' && data[i] <= 'Z'){
      data[i] = (invA * (data[i] - b - 'A') % p + p) % p + 'A';
    }
    else if(data[i] >= 'a' && data[i] <= 'z'){
      data[i] = (invA * (data[i] - b - 'a') % p + p) % p + 'a';
    }
    else{
      data[i] = data[i];
    }
    i ++;
  }    
}






int main(){


  int a = 7, b = 3, p = 26, x = 0, y = 0;
  printf("%d\\n", exgcd(a, p, &x, &y));
  printf("%d,%d\\n", x, y);
  printf("%d\\n", inv(a, p, &x, &y));


  char data[] = "hot";
  char result[20]={0};


  encrypt(data, a, b, p);
  printf("%s\\n", data);


  decrypt(data, a, b, p);
  printf("%s\\n", data);


  return 0;
}

审核编辑：刘清