密码学：古典密码.代替密码.仿射密码加密与解密 (广义欧几里得除法)

乘法密码和加法密码结合构成仿射密码，放射密码函数为

                                                   f(ai)=bi=aj (i,j为下角标)

                                                   j=i*k1+k0 mod n   只对大写英文加密n为26

其中：要求  (k1，n)=1, 0<=k0<n,且不允许同时有k1=1和k0=0

代码解释：

在输入时密文为字符串，通过ASCII码进行加减A对应的ASCII码把英文字母对应为0~25

在找k1时用广义欧几里得除法得到1~25之内与26互素的数字放在p数组里面，用于密钥k1的选择

代码：

#include <stdio.h>
#include <string.h>
int Findp(int p[],int n)
{int top=0,flag=1;if (n%2)flag=0;     //如果n为偶数，偶数必然不和n互素{for (int i=1;i<n;)//利用广义欧几里得除法找1~n之内与n互素的数{int j1=n,j0=i,r=i;while(r!=0){do{j1-=j0;r=j1;}while(r>=j0);j1=j0;j0=r;}if(j1==1)p[top++]=i;if(!flag)i+=2;elsei++;}}return top;
}int main()
{char M[9999],C[9999];printf("请输入明文字符(大写英文字母,回车结束)\n");fgets(M,9999,stdin);int k1,k0,n=26;printf("请输入密钥k1 k0(中间空格分隔，k1=1和K0=0不能同时)，");int p[26];int num=Findp(p,n);printf("k1可取值为");for (int i=0;i<num;i++)printf("%d ",p[i]);printf("\n");scanf("%d%d",&k1,&k0);printf("密文\n");int end=strlen(M),top=0;for (int i=0;i<end-1;i++){if(M[i]==' ')C[i]=' ';elseC[i]=((M[i]-65)*k1+k0)%n+65;}for (int i=0;i<end-1;i++){printf("%c",C[i]);}printf("\n解密\n");for (int i=0;i<end-1;i++){if (C[i]==' ')printf("%c",C[i]);else{int m=(C[i]-65-k0);//不能用char类型！！！！m超过100多变为负数//while(-25%25)不执行 所以不能小于0while(m%k1 || m<0) //需要先加26 什么时候模K1为0停止m+=26;//因为选K1时互素，所以这里即使后面也有模K1为0的 除k1后再mod26是一样的结果printf("%c",m/k1+65);}}
}