仿射密码是一种古典移位密码,其算法设计时用到的数学基础是模运算和同余方程。它是一个字母对一个字母的加密密码。定义明文空间
P
=
Z
26
P={\rm Z}_{26}
P=Z26? ,密文空间
C
=
Z
26
C={\rm Z}_{26}
C=Z26? ,秘钥空间为
K
=
{
(
a
,
b
)
∈
Z
26
?
Z
26
:
g
c
d
(
a
,
26
)
=
1
}
K=\lbrace (a,b)\in {\rm Z}_{26} \cdot {\rm Z}_{26}:gcd(a,26)=1 \rbrace
K={(a,b)∈Z26??Z26?:gcd(a,26)=1} 对于
x
∈
P
,
y
∈
C
,
k
=
(
a
,
b
)
∈
K
x\in P, y\in C,k=(a,b)\in K
x∈P,y∈C,k=(a,b)∈K 定义加密函数
e
k
(
x
)
=
a
x
+
b
m
o
d
??
?
26
{\rm e}_k(x)=ax+b\mod \ 26
ek?(x)=ax+bmod?26 ,定义解密函数
d
k
(
x
)
=
a
?
1
(
y
?
b
)
m
o
d
??
?
26
)
{\rm d}_k(x)=a^{-1}(y-b)\mod \ 26)
dk?(x)=a?1(y?b)mod?26) ,其中是a在群的乘法逆元(求a在群的乘法逆元)。当a=1时,仿射密码,弱化为凯撒密码。
1.加密过程: text为要加密的明文,password为加密后的密文
char* encode(char* text,int addkey,int mulkey)
{
char* password=NULL;
password=(char*)malloc(10*sizeof(char));
for(int i=0;i<strlen(text);i++)
{
int code=text[i]-'a';
password[i]=(code*mulkey+addkey)%26+'a';
}
return password;
}
2.求逆过程: 拓展欧几里得算法
int extendedeuclid(int m,int b)
{
int a1,a2,a3;
int b1,b2,b3;
int t1,t2,t3;
a1=1;a2=0;a3=m;
b1=0;b2=1;b3=b;
while(1)
{
if(b3==0) return 0;
if(b3==1)
{
if(b2<0) b2=m+b2;
return b2;
}
int q=a3/b3;
t1=a1-q*b1;t2=a2-q*b2;t3=a3-q*b3;
a1=b1;a2=b2;a3=b3;
b1=t1;b2=t2;b3=t3;
}
return 0;
}
3.解密过程: password是要解密的密文,text是得到的解密后的明文。
char* decode(char* password,int addkey,int mulkey)
{
char* text=NULL;
text=(char*)malloc(10*sizeof(char));
for(int i=0;i<strlen(password);i++)
{
int code=password[i]-'a';
text[i]=( (code-addkey+ 26) * extendedeuclid(26,mulkey) )% 26 + 'a';
}
return text;
}
4.完整代码:
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int extendedeuclid(int m,int b)
{
int a1,a2,a3;
int b1,b2,b3;
int t1,t2,t3;
a1=1;a2=0;a3=m;
b1=0;b2=1;b3=b;
while(1)
{
if(b3==0) return 0;
if(b3==1)
{
if(b2<0) b2=m+b2;
return b2;
}
int q=a3/b3;
t1=a1-q*b1;t2=a2-q*b2;t3=a3-q*b3;
a1=b1;a2=b2;a3=b3;
b1=t1;b2=t2;b3=t3;
}
return 0;
}
char* encode(char* text,int addkey,int mulkey)
{
char* password=NULL;
password=(char*)malloc(10*sizeof(char));
for(int i=0;i<strlen(text);i++)
{
int code=text[i]-'a';
password[i]=(code*mulkey+addkey)%26+'a';
}
return password;
}
char* decode(char* password,int addkey,int mulkey)
{
char* text=NULL;
text=(char*)malloc(10*sizeof(char));
for(int i=0;i<strlen(password);i++)
{
int code=password[i]-'a';
text[i]=( (code-addkey+ 26) * extendedeuclid(26,mulkey) )% 26 + 'a';
}
return text;
}
int main()
{
char text[200];
printf("请输入明文:");
scanf("%s",text);
int k,b;
printf("请输入k,b的值:");
scanf("%d%d",&k,&b);
char *p=NULL;
char *q=NULL;
p=q=(char*)malloc(10*sizeof(char));
p=encode(text,k,b);
q=decode(p,k,b);
printf("加密后的密文:%s\n",p);
printf("解密后的明文:%s",q);
free(p);free(q);
return 0;
}
Cmd Markdown 公式指导手册 复习了一下C语言的指针,学的时候感觉难,现在看还是难。
|