仿射密码的攻击

加法密码和乘法密码的结合就构成了仿射密码，仿射密码加密的思路为：首先将明文乘以密钥的一部分，然后再加上密钥的剩余部分。

一、仿射密码加密解密算法

假设c , m , a , b ∈Z26

加密：ek(m) ≡c ≡ a⋅m + b mod 26 

解密：dk(c) = m = a-1 ⋅(c-b) mod 26

 

密钥为：k =(a ，b )，且满足限制条件 gcd( a ,26)=1。当a=1时，仿射密码变为加法密码，当b=0时，仿射密码变为乘法密码。
解密可以很容易地从加密函数推导出来：

a ⋅ m  + b≡c mod 26
a ⋅ m≡ (c– b )mod 26
m ≡ a-1⋅ (c– b )mod 26

 

二、C++编程实现仿射密码的攻击

1．问题描述

仿射密码系统用五元组（P，C，K，E，D）表示，设P=C={abcdefghijklmnopqrstuvwxyz}.现在截获了一段密文“ojbkojbk”。请编程分析出明文。

2．C++代码如下:

2. #include <iostream>
3. #include <string>
4. #include <cstdio>
5. #include<stdlib.h>
7. using namespace std;
8. /*
9. 欧几里德算法
10. */
11. int gcd(int a,int b)
12. {
13. int temp;
14. if(a<b)//判断大小
15. {
16. temp=a;
17. a=b;
18. b=temp;
19. }
20. if(b==0) return a;
21. else return gcd(b,a%b);//递归
22. }
23. int main()
24. {
25. string List("abcdefghijklmnopqrstuvwxyz"),c("ojbkojbk"),result;
26. int a,b,m,p;
27. /*
28. 加密：c = Ea,b(m) ≡ a, + b(mod 26)
29. 解密：m = Da,b(c) ≡ a^-1(c - b)(mod 26)
30. a,b是密钥 0<=a,b<=n,gcd(a,m)=1
31. 逆元：a^-1*a≡1mod m
32. */
33. for(a=2;a<26;a++){
34. //a和26互素
35. if(gcd(a,26)==1){
36. //求a的乘法逆元p
37. for(b=2;b<26;b++){
38. if((a*b)%26==1){
39. p=b;break;
40. }
41. }
42. //下面进行解密
43. for(b = 0; b < 28; b++) // k2 = b<q
44. {
45. for(int i=0;i<c.size();i++){
46. for(int k = 0; k < List.size(); k += 1){
47. if(List[k] == c[i]) //得到密文所对应的密文数字
48. {
49. //string中文测试，因为编码和string类的原因，一个中文字符占两个下标
50. // pp=pp+bi1[k] + bi1[k + 1];
51. // cout<<pp<<endl;
52. // printf("k:%d ",k);
53. // printf("\n");
54. m = (p * (k - b)) % 26; //得到密文数字相对应的明文数字
55. //得到明文数字对应的明文
56. if (m >= 0)
57. {
58. result = result + List[m] ;
59. }
60. else
61. {
62. m = m+ 26;
63. result = result + List[m];
64. }
65. }
66. }
67. }
68. printf ("当 a = %02d, b = %02d 时,解密得到的明文是: ", a, b);
69. cout << result << endl;
70. result.clear();
71. }
72. }
73. }
74. return 0;
75. }

复制代码

 

三、运行结果