[关闭]
@ArrowLLL 2019-05-25T04:29:09.000000Z 字数 24525 阅读 1828

密码学习题


班级: 09061401
学号: 2014302358
姓名: 林维


传统密码

加法密码

[1]

若加法密码中密钥K=7,试求明文good night的密文。

  1. const int alplen(26);
  2. // ptx表示明文(plaintext), key表示密钥, ctx表示密文(ciphertext)
  3. void additive_cipher(char *ptx, int key, char *ctx)
  4. {
  5. int i;
  6. for(i = 0; ptx[i]; i++) {
  7. if(ptx[i] > 'z' || ptx[i] < 'a') {
  8. ctx[i] = ptx[i];
  9. }
  10. else {
  11. int c = ((ptx[i] - 'a') + key) % alplen;
  12. ctx[i] = 'a' + c;
  13. }
  14. }
  15. ctx[i] = '\0';
  16. }

解得密文为 : nvvk upnoa

乘法密码

[2]

若乘法密码中密钥K=5,试对明文network的加密。

  1. const int alplen(26);
  2. // ptx表示明文(plaintext), key表示密钥, ctx表示密文(ciphertext)
  3. void multiplication_cipher(char *ptx, int key, char *ctx)
  4. {
  5. int i;
  6. for(i = 0; ptx[i]; i++) {
  7. if(ptx[i] < 'a' || ctx[i] > 'z') {
  8. ctx[i] = ptx[i];
  9. }
  10. else {
  11. int c = ptx[i] - 'a';
  12. c = c * key % alplen;
  13. ctx[i] = 'a' + c;
  14. }
  15. }
  16. ctx[i] = '\0';
  17. }

得到密文为 : nurgshy

仿射变换

[3]

已知仿射变换为c=5m+7(mod26),试对明文help me加密

  1. const int alplen(26);
  2. // ptx表示明文(plaintext), key1、key2表示密钥, ctx表示密文(ciphertext)
  3. void affine_transformation(char *ptx, int key1, int key2, char *ctx)
  4. {
  5. int i;
  6. for(i = 0; ptx[i]; i++) {
  7. if(ptx[i] < 'a' || ptx[i] > 'z') {
  8. ctx[i] = ptx[i];
  9. }
  10. else {
  11. int c = ptx[i] - 'a';
  12. c = (c * key1 + key2) % alplen;
  13. ctx[i] = 'a' + c;
  14. }
  15. }
  16. ctx[i] = '\0';
  17. }

得到加密的密文为 : qbke pb

[4]

已知仿射变换为c=5m+7(mod26),试对密文VMWZ解密

  1. const int alplen(26);
  2. // ptx表示ctx表示密文(ciphertext), key1、key2表示密钥, 明文(plaintext)
  3. void re_affine_trans(char *ctx, int key1, int key2, char *ptx)
  4. {
  5. int i, re_key1;
  6. // 求key1在模alplen情况下的逆
  7. for(re_key1 = 0; re_key1 < alplen; re_key1++) {
  8. if(re_key1 * key1 % alplen == 1) {
  9. break;
  10. }
  11. }
  12. for(int i = 0; ctx[i]; i++) {
  13. if(ctx[i] < 'A' || ctx[i] > 'Z') {
  14. ptx[i] = ctx[i];
  15. }
  16. else {
  17. int c = ctx[i] - 'A';
  18. c = (c - key2) * re_key1;
  19. c = (c % alplen + alplen) % alplen;
  20. ptx[i] = 'A' + c;
  21. }
  22. }
  23. ptx[i] = '\0';
  24. }

得到解密的明文为 : IBDO

[5]

已知下列密文是通过单表代替密码加密的结果,试求其明文。

YIF QFMZRW QFYV ECFMD ZPCVMRZW NMD ZVEJB TXCDD UMJN DIFEFMDZ CD MQ ZKCEYFCJMYR NCW JCSZR EXCHZ UNMXZ NZ UCDRJ XYYSMRT M EYIFZW DYVZ VYFZ UMRZ CRW NZ DZJJXZW GCHS MR NMD HNCMF QCHZ JMXJZW IE JYUCFWD JNZ DIR.

这个过程是手算的,结果如下 :

our friend from paris examined his empty glass with surprise as if evaporation had taken place while he wasnt looging i poured some more wine and he settled back in his chair face tilted up towards the sun.

Vignere密码

[6]

已知Vigenere密码的密钥为matrix,试对明文some simple cryptosystem加密

  1. const int alplen(26);
  2. //ptx表示明文(plaintext), key表示密钥, ctx表示密文(ciphertext)
  3. void vignere(char *ptx, char *key, char *ctx)
  4. {
  5. int i, j;
  6. for(i = 0, j = 0; ptx[i]; i++) {
  7. if(ptx[i] < 'a' || ptx[i] > 'z') {
  8. ctx[i] = ptx[i];
  9. }
  10. else {
  11. int c = ptx[i] - 'a' + (key[j++] - 'a');
  12. ctx[i] = 'a' + (c % 26);
  13. if(!key[j]) j = 0;
  14. }
  15. }
  16. ctx[i] = '\0';
  17. }

得到加密的密文为 : eofv afypev kokpmfavetxd

代数密码

[7]

若代数密码中密钥为best,试对明文good加密

  1. const int alplen(26);
  2. // ptx表示明文(plaintext), key1、key2表示密钥, ctx表示密文(ciphertext)
  3. void algebraic_cipher(char *ptx, char *key, char *ctx)
  4. {
  5. int i, j;
  6. for(i = 0, j = 0; ptx[i]; i++) {
  7. if(ptx[i] > 'z' || ptx[i] < 'a') {
  8. ctx[i] = ptx[i];
  9. }
  10. else {
  11. int c = ptx[i] - 'a', k = key[j++] - 'a';
  12. ctx[i] = 'a' + (c ^ k) % alplen;
  13. if(!key[j]) j = 0;
  14. }
  15. }
  16. ctx[i] = '\0';
  17. }

得到加密的密文为 : hkcq

Hill 密码

[8]

假设Hill密码加密使用密钥,试对明文best加密

  1. const int alplen(26), maxn(100);
  2. // ptx表示明文(plaintext), key[maxn][maxn]表示密钥, 密钥的秩为k, ctx表示密文(ciphertext)
  3. // 这里假设矩阵的大小不超过100
  4. void hill_cipher(char *ptx, int key[][maxn], int l, char *ctx)
  5. {
  6. int i = 0, c[maxn];
  7. while(ptx[i]) {
  8. for(int j = 0; j < l; j++) {
  9. c[j] = ptx[i + j] - 'a';
  10. }
  11. for(int j = 0, t; j < l; j++) {
  12. t = 0;
  13. for(int k = 0; k < l; k++) {
  14. t += key[j][k] * c[k];
  15. }
  16. ctx[j + i] = 'a' + t % 26;
  17. }
  18. i += l;
  19. }
  20. ctx[i] = '\0';
  21. }

得到加密的密文 : ofjf

[9]

假设Hill密码加密使用密钥,试对密文UMFL解密。

  1. const int alplen(26), maxn(100);
  2. // ptx表示明文(plaintext), key[2][2]表示密钥, ctx表示密文(ciphertext)
  3. void re_hill_cipher(char *ctx, int key[2][2], char *ptx)
  4. {
  5. int re_key[2][2] = {key[1][1], -key[0][1], -key[1][0], key[0][0]};
  6. int detKey = key[0][0] * key[1][1] - key[0][1] * key[1][0], re_detKey;
  7. for(int i = 0; i < 26; i++) {
  8. if(detKey * i % alplen == 1) {
  9. re_detKey = i;
  10. break;
  11. }
  12. }
  13. for(int i = 0; i < 2; i++) {
  14. for(int j = 0; j < 2; j++) {
  15. re_key[i][j] = re_key[i][j] * re_detKey % alplen;
  16. re_key[i][j] = (re_key[i][j] + alplen) % alplen;
  17. }
  18. }
  19. int i = 0, c[2];
  20. while(ctx[i]) {
  21. for(int j = 0; j < 2; j++) {
  22. c[j] = ctx[j + i] - 'a';
  23. }
  24. for(int j = 0; j < 2; j++) {
  25. int ans = 0;
  26. for(int k = 0; k < 2; k++) {
  27. ans += re_key[j][k] * c[k];
  28. }
  29. ptx[i + j] = 'a' + ans % alplen;
  30. }
  31. i += 2;
  32. }
  33. ptx[i] = '\0';
  34. }

得到相应的明文 : GOOD

[10]

假设明文friday利用的Hill密码加密,得到密文PQCFKU,试求密钥K

  1. void key_hill_cipher(char *ptx, char *ctx, int key[2][2])
  2. {
  3. int p[6], c[6], t = strlen(ptx);
  4. for(int i = 0; i < t; i++) {
  5. p[i] = ptx[i] - 'a', c[i] = ctx[i] - 'a';
  6. }
  7. for(int i = 0; i < alplen; i ++) {
  8. for(int j = 0; j < alplen; j++) {
  9. int sig;
  10. for(sig = 0; sig < t; sig += 2) {
  11. if((p[sig] * i + p[sig + 1] * j) % alplen != c[sig]) {
  12. break;
  13. }
  14. }
  15. if(sig < t) continue;
  16. key[0][0] = i, key[0][1] = j;
  17. for(int k = 0; k < alplen; k++) {
  18. for(int l = 0; l < alplen; l++) {
  19. for(sig = 0; sig < t; sig += 2) {
  20. if((p[sig] * k + p[sig + 1] * l) % alplen != c[sig + 1])
  21. break;
  22. }
  23. if(sig >= t) {
  24. key[1][0] = k, key[1][1] = l;
  25. return ;
  26. }
  27. }
  28. }
  29. }
  30. }
  31. }

解得密钥

分组密码

DES

[1]

设DES数据加密标准中:
明文

m = 0011 1000 1101 0101 1011 1000 0100 0010 1101 0101 0011 1001 1001 0101 1110 0111

密钥

K = 1010 1011 0011 0100 1000 0110 1001 0100 1101 1001 0111 0011 1010 0010 1101 0011

试求L1与R1。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn(70);
  4. void output(bool *t, int l)
  5. {
  6. for(int i = 1, d = 1; i <= l / 4; i++) {
  7. for(int j = 0; j < 4; j++) {
  8. cout<<t[d++];
  9. }
  10. cout<<' ';
  11. }
  12. cout<<endl;
  13. cout<<"--------------"<<endl;
  14. }
  15. void ipTrans(bool m[maxn])
  16. {
  17. bool cm[maxn];
  18. int s[] = {58, 60, 62, 64, 57, 59, 61, 63};
  19. for(int i = 0, l = 1; i < 8; i++) {
  20. for(int j = s[i]; j > 0; j -= 8) {
  21. cm[l++] = m[j];
  22. }
  23. }
  24. for(int i = 1; i <= 64; i++) {
  25. m[i] = cm[i];
  26. }
  27. }
  28. void PC_1(bool k[maxn])
  29. {
  30. bool ck[maxn];
  31. int st[] = {57, 58, 59, 60, 63, 62, 61, 28};
  32. int le[] = {8, 8, 8, 4, 8, 8, 8, 4};
  33. for(int i = 0, l = 1; i < 7; i++) {
  34. for(int j = 0; j < le[i]; j++) {
  35. ck[l++] = k[st[i] - j * 8];
  36. }
  37. }
  38. for(int i = 0; i <= 56; i++) {
  39. k[i] = ck[i];
  40. }
  41. }
  42. int cirMv[] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
  43. void circle_left(bool k[maxn], int t)
  44. {
  45. t = cirMv[t];
  46. bool C[maxn >> 1], D[maxn >> 1];
  47. for(int i = 1; i <= 28; i ++) {
  48. C[i] = k[i], D[i] = k[28 + i];
  49. }
  50. for(int j = 0; j < t; j++) {
  51. for(int i = 0; i < 28; i++) {
  52. C[i] = C[i + 1], D[i] = D[i + 1];
  53. }
  54. C[28] = C[0], D[28] = D[0];
  55. }
  56. for(int i = 1; i <= 28; i++) {
  57. k[i] = C[i], k[28 + i] = D[i];
  58. }
  59. }
  60. void PC_2(bool k[maxn], bool ck[maxn])
  61. {
  62. int transTable[] = {
  63. 14, 17, 11, 24, 1, 5,
  64. 3, 28, 15, 6, 21, 10,
  65. 23, 19, 12, 4, 26, 8,
  66. 16, 7, 27, 20, 13, 2,
  67. 41, 52, 31, 37, 47, 55,
  68. 30, 40, 51, 45, 33, 48,
  69. 44, 49, 39, 56, 34, 53,
  70. 46, 42, 50, 36, 29, 32
  71. };
  72. for(int i = 0; i < 48; i++) {
  73. ck[i + 1] = k[transTable[i]];
  74. }
  75. }
  76. const int selectMatrix[8][4][16] = {
  77. // S1
  78. 14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
  79. 0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
  80. 4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
  81. 15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
  82. //S2
  83. 15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
  84. 3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
  85. 0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
  86. 13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
  87. //S3
  88. 10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
  89. 13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
  90. 13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
  91. 1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
  92. //S4
  93. 7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
  94. 13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
  95. 10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
  96. 3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
  97. //S5
  98. 2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
  99. 14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
  100. 4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
  101. 11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
  102. //S6
  103. 12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
  104. 10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
  105. 9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
  106. 4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
  107. //S7
  108. 4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
  109. 13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
  110. 1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
  111. 6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
  112. //S8
  113. 13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
  114. 1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
  115. 7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
  116. 2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11
  117. };
  118. void encrypt_f(bool R[maxn], bool k[maxn], bool fR[maxn])
  119. {
  120. bool ER[maxn], p[maxn];
  121. int st[] = {0, 4, 8, 12, 16, 20, 24, 28};
  122. for(int i = 0, l = 1; i < 8; i++) {
  123. for(int j = 0; j < 6; j++) {
  124. ER[l++] = R[st[i] + j];
  125. }
  126. }
  127. ER[1] = R[32], ER[48] = R[1];
  128. for(int i = 1; i <= 48; i++) {
  129. ER[i] = ER[i] ^ k[i];
  130. }
  131. for(int i = 0, l = 1; i < 8; i++) {
  132. int locbit[10], row, column;
  133. for(int j = 1; j <= 6; j++) {
  134. locbit[j] = ER[i * 6 + j];
  135. }
  136. row = (locbit[1] << 1) | locbit[6];
  137. column = 0;
  138. for(int j = 2; j <= 5; j++) {
  139. column |= (int)locbit[j] << (5 - j);
  140. }
  141. int res = selectMatrix[i][row][column];
  142. for(int i = 3; i >= 0; i--) {
  143. p[l++] = (res & (1 << i)) ? 1 : 0;
  144. }
  145. }
  146. int p_trans[] = {
  147. 16, 7, 20, 21,
  148. 29, 12, 28, 17,
  149. 1, 15, 23, 26,
  150. 5, 18, 31, 10,
  151. 2, 8, 24, 14,
  152. 32, 27, 3, 9,
  153. 19, 13, 30, 6,
  154. 22, 11, 4, 25
  155. };
  156. for(int i = 0; i < 32; i++) {
  157. fR[i + 1] = p[p_trans[i]];
  158. }
  159. }
  160. void re_ipTrans(bool m[maxn])
  161. {
  162. bool cm[maxn];
  163. int st[] = {40, 8, 48, 16, 56, 24, 64, 32};
  164. for(int i = 0, l = 1; i < 8; i++) {
  165. for(int j = 0; j < 8; j++) {
  166. cm[l++] = m[st[j] - i];
  167. }
  168. }
  169. for(int i = 1; i <= 64; i++) {
  170. m[i] = cm[i];
  171. }
  172. }
  173. int main()
  174. {
  175. bool m[maxn], k[maxn], ck[maxn];
  176. int n = 64;
  177. char in[6];
  178. freopen("data.in", "r", stdin);
  179. for(int i = 0, l = 1; i < 16; i++) {
  180. cin >> in;
  181. for(int j = 0; j < 4; j++) {
  182. m[l++] = in[j] - '0';
  183. }
  184. }
  185. for(int i = 0, l = 1; i < 16; i++) {
  186. cin >> in;
  187. for(int j = 0; j < 4; j++) {
  188. k[l++] = in[j] - '0';
  189. }
  190. }
  191. // 初始置换IP
  192. ipTrans(m);
  193. bool L[maxn >> 1], R[maxn >> 1], cR[maxn >> 1];
  194. for(int i = 1; i <= 32; i++) {
  195. L[i] = m[i], R[i] = m[32 + i];
  196. }
  197. PC_1(k);
  198. for(int i = 0; i < 16; i++) {
  199. // 子密钥生成
  200. circle_left(k, i);
  201. PC_2(k, ck);
  202. // 加密函数f
  203. encrypt_f(R, ck, cR);
  204. //获得新的L和R
  205. for(int j = 1; j <= 32; j++) {
  206. cR[j] ^= L[j];
  207. }
  208. for (int j = 1; j <= 32; j++) {
  209. L[j] = R[j];
  210. R[j] = cR[j];
  211. }
  212. if(i == 0) {
  213. cout << "L = "; output(L, 32);
  214. cout << "R = "; output(R, 32);
  215. }
  216. }
  217. for(int i = 1; i <= n / 2; i++) {
  218. m[i] = R[i], m[i + 32] = L[i];
  219. }
  220. re_ipTrans(m);
  221. output(m, 64);
  222. return 0;
  223. }

求得

L = 1101 0110 1010 0101 0010 0101 1000 1000
R = 1010 0110 0001 0100 0011 1001 1100 0100

IDEA

[2]

已知IDEA密码算中:

明文 m =

01011100 10001101 10101001 11011110
10101101 00110101 00010011 10010011

密钥 K =

00101001 10101100 11011000 11100111
10100101 01010011 10100010 01011001
00101000 01011001 11001010 11100111
10100010 00101010 11010101 00110101

求第一轮的输出与第二轮的输入。

得到第一轮的输出(first iteration's output) :

0111 1111 0111 1001
1001 1001 0101 1101
0110 0000 0110 0011
0010 0101 0001 0100

以及第二轮的输入(second iteration's input) :

m =
0111 1111 0111 1001
1001 1001 0101 1101
0110 0000 0110 0011
0010 0101 0001 0100
z(1 - 6) =
1010 0010 0010 1010
1101 0101 0011 0101
1100 1111 0100 1010
1010 0111 0100 0100
1011 0010 0101 0000
1011 0011 1001 0101

[3]

已知IDEA密码算中:


  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. // 快速幂乘
  5. LL ksPower(LL a, LL n, LL p)
  6. {
  7. LL ans = 1;
  8. while(n) {
  9. if(n & 1) ans = ans * a % p;
  10. a = a * a % p;
  11. n >>= 1;
  12. }
  13. return ans;
  14. }
  15. // 费马小定理求乘法逆元
  16. LL getReverse(LL a, LL p)
  17. {
  18. return ksPower(a, p - 2, p);
  19. }
  20. void output(LL d)
  21. {
  22. for(int i = 15; i >= 0; i--) {
  23. if(d & (1 << i)) cout << '1';
  24. else cout << '0';
  25. }
  26. cout << endl;
  27. }
  28. int main()
  29. {
  30. char z[20];
  31. cin >> z;
  32. LL d = 0, p = (1 << 16) + 1;
  33. for(int i = 0; i < 16; i++) {
  34. if(z[i] == '1') {
  35. d |= 1LL << (15 - i);
  36. }
  37. }
  38. cout << "addition reverse : ";
  39. output(p - 1 - d);
  40. cout << "multiplication reverse : ";
  41. output(getReverse(d, p));
  42. return 0;
  43. }

求得 :

addition reverse : 0111101101100011
multiplication reverse : 1011000000110011

FEAL

[4]

已知FEAL密码中
明文 m=

0011 1010 1101 0111 0010 1010 1100 0010
1101 0111 1011 1000 0101 1101 0100 1000

密钥 K=

1001 0010 1001 0010 1111 1000 0110 0001
1101 0101 0011 1000 0100 1000 1101 1110

求L0与R0。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef unsigned char usch;
  4. const int maxn(10);
  5. void input(usch *s)
  6. {
  7. # define anlsget(g, sig) do{\
  8. usch d = 0, x[5];\
  9. cin >> x;\
  10. for(int j = 0; j < 4; j++) {\
  11. if(x[j] - '0') d |= 1 << (3 - j);\
  12. }\
  13. g |= (sig ? d << 4 : d);\
  14. }while(false)
  15. for(int i = 0; i < 8; i++) {
  16. s[i] = 0;
  17. anlsget(s[i], 1);
  18. anlsget(s[i], 0);
  19. }
  20. }
  21. void output(usch *s, int l)
  22. {
  23. for(int i = 0; i < l; i++) {
  24. for(int j = 0; j < 8; j++) {
  25. cout << ((s[i] & (1 << (7 - j))) ? 1 : 0);
  26. if(((j + 1) & 3) == 0) cout << ' ';
  27. }
  28. }
  29. cout << endl;
  30. puts("----------------------");
  31. }
  32. usch S(usch x1, usch x2, int sigm)
  33. {
  34. usch w = (sigm + x1 + x2) % (1 << 8);
  35. return (w << 2) | (w >> 6);
  36. }
  37. void f_K(usch *a, usch *b, usch *f)
  38. {
  39. usch h1 = a[1] ^ a[0];
  40. usch h2 = a[3] ^ a[2];
  41. f[1] = S(h1, h2 ^ b[0], 1);
  42. f[2] = S(h2, f[1] ^ b[1], 0);
  43. f[0] = S(a[0], f[1] ^ b[2], 0);
  44. f[3] = S(a[3], f[2] ^ b[3], 1);
  45. }
  46. void product_sub_key(usch *key, usch K[][2])
  47. {
  48. usch A[4], B[4];
  49. memcpy(A, key, 4);
  50. memcpy(B, key + 4, 4);
  51. usch D[4], cB[4];
  52. for(int i = 0; i < 6; i++) {
  53. memcpy(D, A, 4);
  54. memcpy(A, B, 4);
  55. for(int j = 0; j < 4; j++) {
  56. cB[i] = B[i] ^ D[i];
  57. }
  58. f_K(D, cB, B);
  59. memcpy(K[i * 2], B, 2);
  60. memcpy(K[i * 2 + 1], B + 2, 2);
  61. }
  62. }
  63. void encrypt_f(usch a[4], usch b[2], usch f[4])
  64. {
  65. usch g1 = a[1] ^ b[0] ^ a[0];
  66. usch g2 = a[2] ^ b[1] ^ a[3];
  67. f[1] = S(g1, g2, 1);
  68. f[2] = S(g2, f[1], 0);
  69. f[3] = S(a[3], f[1], 1);
  70. f[0] = S(a[0], f[1], 0);
  71. }
  72. void initialize_calculate(usch plx[8], usch L[4], usch R[4], usch K[12][2])
  73. {
  74. memcpy(L, plx, 4);
  75. memcpy(R, plx + 4, 4);
  76. for(int i = 0; i < 2; i++) {
  77. L[i] ^= K[4][i];
  78. L[i + 2] ^= K[5][i];
  79. R[i] ^= K[6][i];
  80. R[i + 2] ^= K[7][i];
  81. }
  82. for(int i = 0; i < 4; i++) {
  83. R[i] ^= L[i];
  84. }
  85. }
  86. void iteration(usch L[4], usch R[4], int j, usch K[12][2])
  87. {
  88. usch f[4], cL[4];
  89. memcpy(cL, L, 4);
  90. memcpy(L, R, 4);
  91. encrypt_f(R, K[j], f);
  92. for(int i = 0; i < 4; i++) {
  93. R[i] = cL[i] ^ f[i];
  94. }
  95. }
  96. void tail_calculate(usch L[4], usch R[4], usch ctx[maxn], usch K[12][2])
  97. {
  98. for(int i = 0; i < 4; i++) {
  99. R[i] ^= L[i];
  100. }
  101. for(int i = 0; i < 2; i++) {
  102. R[i] = R[i] ^ K[8][i];
  103. R[i + 2] = R[i + 2] ^ K[9][i];
  104. L[i] = L[i] ^ K[10][i];
  105. L[i + 2] = L[i + 2] ^ K[11][i];
  106. }
  107. for(int i = 0; i < 4; i++) {
  108. ctx[i] = R[i];
  109. ctx[i + 4] = L[i];
  110. }
  111. }
  112. int main()
  113. {
  114. freopen("data.in", "r", stdin);
  115. usch plaintext[maxn], key[maxn], ciphertext[maxn];
  116. input(plaintext);
  117. input(key);
  118. usch sub_key[12][2], L[4], R[4];
  119. product_sub_key(key, sub_key);
  120. initialize_calculate(plaintext, L, R, sub_key);
  121. cout << "L = "; output(L, 4);
  122. cout << "R = "; output(R, 4);
  123. for(int i = 0; i < 4; i++) {
  124. iteration(L, R, i, sub_key);
  125. }
  126. tail_calculate(L, R, ciphertext, sub_key);
  127. output(ciphertext, 8);
  128. return 0;
  129. }

求得 :

L = 1000 1000 0110 0000 1011 0100 0000 1100
R = 0000 1000 0000 0101 0111 0110 0000 1110

[5]

已知 a, b 分别为

a = 10000011 11010111 10100101 00110100
b = 00101011 10011010 00100101 11011100

为FEAL密码的子密钥产生函数,求

  1. usch S(usch x1, usch x2, int sigm)
  2. {
  3. usch w = (sigm + x1 + x2) % (1 << 8);
  4. return (w << 2) | (w >> 6);
  5. }
  6. void f_K(usch a[4], usch b[4], usch f[4])
  7. {
  8. usch h1 = a[1] ^ a[0];
  9. usch h2 = a[3] ^ a[2];
  10. f[1] = S(h1, h2 ^ b[0], 1);
  11. f[2] = S(h2, f[1] ^ b[1], 0);
  12. f[0] = S(a[0], f[1] ^ b[2], 0);
  13. f[3] = S(a[3], f[2] ^ b[3], 1);
  14. }

求得结果为 :

f = 01110010 00111100 11011100 11010100

[6]

已知

α = 00101011 11011101 10000001 01001000
β = 10011101 11100111

为FEAL密码的加密函数,求

  1. usch S(usch x1, usch x2, int sigm)
  2. {
  3. usch w = (sigm + x1 + x2) % (1 << 8);
  4. return (w << 2) | (w >> 6);
  5. }
  6. void encrypt_f(usch a[4], usch b[2], usch f[4])
  7. {
  8. usch g1 = a[1] ^ b[0] ^ a[0];
  9. usch g2 = a[2] ^ b[1] ^ a[3];
  10. f[1] = S(g1, g2, 1);
  11. f[2] = S(g2, f[1], 0);
  12. f[3] = S(a[3], f[1], 1);
  13. f[0] = S(a[0], f[1], 0);
  14. }

求得 :

f = 01010110 01101010 01100010 11001110

欧几里得算法(拓展gcd)

[1]

用欧几里得算法求 的逆元。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void exgcd(int a, int b, int &x, int &y)
  4. {
  5. if(!b) {
  6. x = 1, y = 0;
  7. return ;
  8. }
  9. exgcd(b, a % b, y, x);
  10. y -= x * (a / b);
  11. }
  12. int main()
  13. {
  14. int a, b, x, y;
  15. cin >> a >> b;
  16. exgcd(a, b, x, y);
  17. cout << x << endl;
  18. }

求得逆元为 : 16

线性同余式

[2]

求解下列线性同余式

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void exgcd(int a, int b, int &d, int &x, int &y)
  4. {
  5. if(!b) {
  6. d = a, x = 1, y = 0;
  7. return ;
  8. }
  9. exgcd(b, a % b, d, y, x);
  10. y -= x * (a / b);
  11. }
  12. int main()
  13. {
  14. int a, b, c, x, y, d;
  15. // ax = c (mod b)
  16. cin >> a >> c >> b;
  17. exgcd(a, b, d, x, y);
  18. if(c % d != 0) {
  19. cout <<"no solution";
  20. }
  21. else {
  22. x = (x * (c / d)) % b;
  23. cout << (x + b) % b;
  24. }
  25. cout << endl;
  26. return 0;
  27. }

求得上两式的解分别为 : 16147

[3]

求解下列同余方程组

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // 拓展欧几里得
  4. int exgcd(int a, int b, int &x, int &y)
  5. {
  6. if(!b) {
  7. x = 1, y = 0;
  8. return a;
  9. }
  10. int d = exgcd(b, a % b, y, x);
  11. y -= x * (a / b);
  12. return d;
  13. }
  14. // 中国剩余定理
  15. int china(int *b, int *w, int k)
  16. {
  17. int i, d, x, y, m, a = 0, n = 1;
  18. for(i = 0; i < k; i++) {
  19. n *= w[i];
  20. }
  21. for(i = 0; i < k; i++) {
  22. m = n / w[i];
  23. d = exgcd(w[i], m, x, y);
  24. a = (a + y * m * b[i]) % n;
  25. }
  26. if(a > 0) return a;
  27. else return a + n;
  28. }
  29. int main()
  30. {
  31. const int maxn(5);
  32. int a[maxn], b[maxn], n;
  33. cin >> n;
  34. for(int i = 0; i < n; i++) {
  35. cin >> a[i] >> b[i];
  36. }
  37. cout << china(a, b, n) << endl;
  38. return 0
  39. }

求得两个方程组的解分别为 : 71430

快速幂乘

[4]

  1. // a^n % mod = ans
  2. int quickPower(int a, int n, int mod)
  3. {
  4. int ans = 1;
  5. while(n) {
  6. if(n & 1) {
  7. ans = ans * a % mod;
  8. }
  9. a = a * a % mod;
  10. n >>= 1;
  11. }
  12. return ans;
  13. }

求得结果为 : 33

RSA公钥密码

[5]

已知RSA密码体制的公开钥为 ,试对明文best wisheas加密。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // 快速幂乘
  4. int quicksPower(int a, int n, int mod)
  5. {
  6. int ans = 1;
  7. while(n) {
  8. if(n & 1) {
  9. ans = ans * a % mod;
  10. }
  11. a = a * a % mod;
  12. n >>= 1;
  13. }
  14. return ans;
  15. }
  16. // 加密函数
  17. int encrypt(char a[2], int e, int n)
  18. {
  19. int d = a[0] - 'a';
  20. if(a[1] >= 'a' && a[1] <= 'z') {
  21. d = d * 100 + a[1] - 'a';
  22. }
  23. return quicksPower(d, e, n);
  24. }
  25. int main()
  26. {
  27. freopen("data.in", "r", stdin);
  28. const int maxn(20);
  29. char plaintext[maxn];
  30. gets(plaintext);
  31. for(int i = 0, j = 0; plaintext[i]; i++) {
  32. if(plaintext[i] >= 'a' && plaintext[i] <= 'z') {
  33. plaintext[j++] = plaintext[i];
  34. }
  35. }
  36. int e, n;
  37. scanf("%d%d", &n, &e);
  38. for(int i = 0; plaintext[i]; i += 2) {
  39. int ciphertext = encrypt(plaintext + i, e, n);
  40. printf("%04d ", ciphertext);
  41. }
  42. puts("");
  43. return 0;
  44. }

求得相应的密文为 : 0975 1694 0009 2796 0255

背包公钥

[6]

已知背包公钥系统的超递增序列为 ,乘数 ,模数 ,试对明文 good night 进行加密。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // 获得b序列
  4. void get_bs(int *a, int *b, int n, int w, int m)
  5. {
  6. for(int i = 0; i < n; i++) {
  7. b[i] = a[i] * w % m;
  8. }
  9. }
  10. // 进行单个字符的加密
  11. int encrypt(int *b, char c, int n)
  12. {
  13. int d = c - 'a', ciphertext = 0;
  14. for(int i = 0; i < n; i++) {
  15. int j = 1 << (n - i - 1);
  16. if(d & j) {
  17. ciphertext += b[i];
  18. }
  19. }
  20. return ciphertext;
  21. }
  22. int main()
  23. {
  24. freopen("data.in", "r", stdin);
  25. const int maxn(20);
  26. int a[maxn], b[maxn], w, m, n;
  27. char plaintext[maxn];
  28. gets(plaintext);
  29. scanf("%d", &n);
  30. for(int i = 0; i < n; i++) {
  31. scanf("%d", a + i);
  32. }
  33. scanf("%d%d", &w, &m);
  34. get_bs(a, b, n, w, m);
  35. for(int i = 0; plaintext[i]; i++) {
  36. if(plaintext[i] < 'a' || plaintext[i] > 'z') {
  37. continue;
  38. }
  39. printf("%d ", encrypt(b, plaintext[i], n));
  40. }
  41. puts("");
  42. return 0;
  43. }

求得密文为 : 56 59 59 39 36 3 56 64 96

[7]

已知背包公钥系统的超递增序列为 ,乘数 ,模数 ,试对密文 进行解密。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn(10);
  4. int femat(int w, int n)
  5. {
  6. int m = n - 2, ans = 1;
  7. while(m) {
  8. if(m & 1) ans = ans * w % n;
  9. w = w * w % n;
  10. m >>= 1;
  11. }
  12. return ans;
  13. }
  14. int decode(int rw, int c, int *a, int m, int n)
  15. {
  16. int d = rw * c % m, ans = 0;
  17. for(int i = n - 1; i >= 0; i--) {
  18. if(d >= a[i]) {
  19. ans += (1 << (n - 1 - i));
  20. d -= a[i];
  21. }
  22. }
  23. return ans;
  24. }
  25. int main()
  26. {
  27. int n, a[maxn], w, m;
  28. int ciphertext[maxn];
  29. freopen("data.in", "r", stdin);
  30. scanf("%d", &n);
  31. for(int i = 0; i < n; i++) {
  32. scanf("%d", a + i);
  33. }
  34. scanf("%d%d", &w, &m);
  35. int j = 0;
  36. while(~scanf("%d", ciphertext + j)) {
  37. j++;
  38. }
  39. int rw = femat(w, m);
  40. for(int i = 0; i < j; i++) {
  41. char plaintext = 'a' + decode(rw, ciphertext[i], a, m, n);
  42. cout << plaintext;
  43. }
  44. puts("");
  45. return 0;
  46. }

解得明文为 : besb

香农理论

[1]

设明文空间共含有5个信息 ,并且


  1. #!/usr/bin/env python3
  2. # -*- coding: utf-8 -*-
  3. from math import log
  4. Pm = [1/4, 1/4, 1/8, 3/16, 3/16]
  5. Hm = sum(map(lambda x : -x * log(x, 2), Pm))
  6. print (Hm)

得到结果为 : 2.2806390622295662

[2]

考虑一个密码体制 。假设加密矩阵为

a b c
2 3 4
3 4 1
1 2 3

已知密钥概率分布

明文概率分布为
计算

  1. #!/usr/bin/env python3
  2. # -*- coding: utf-8 -*-
  3. from math import log
  4. def entropy(p) :
  5. return -p * log(p, 2)
  6. '''
  7. Pk = [1/4, 1/4, 1/2]
  8. Pm = [1/3, 1/4, 5/12]
  9. epMatrix = [[2, 3, 4], [3, 4, 1], [1, 2, 3]]
  10. '''
  11. Pk = [1/2, 1/4,1/4]
  12. Pm = [1/4, 3/4]
  13. epMatrix = [[1, 2], [2, 3], [3, 4]]
  14. Hm = sum(map(entropy, Pm))
  15. print ("H(M) =", Hm)
  16. Hk = sum(map(entropy, Pk))
  17. print ("H(K) =", Hk)
  18. cTomk, objNum = {}, 0
  19. for k, row in enumerate(epMatrix) :
  20. for m, code in enumerate(row) :
  21. if code not in cTomk :
  22. cTomk[code] = []
  23. cTomk[code].append((k, m, Pk[k] * Pm[m]))
  24. objNum += 1
  25. Pc = [sum(map(lambda x: x[2], cTomk[cmk])) for cmk in cTomk]
  26. Hc = sum(map(entropy, Pc))
  27. print ("H(C) =", Hc)
  28. Hmc, Hkc = 0, 0
  29. for (p, cmk) in zip(Pc, cTomk) :
  30. Pmc, Pkc = {}, {}
  31. for (k, m, pkm) in cTomk[cmk] :
  32. Pmc[m] = Pmc.setdefault(m, 0) + pkm
  33. Pkc[k] = Pkc.setdefault(k, 0) + pkm
  34. for m in Pmc :
  35. Hmc += p * entropy(Pmc[m] / p)
  36. for k in Pkc :
  37. Hkc += p * entropy(Pkc[k] / p)
  38. print ("H(M/C) =", Hmc)
  39. print ("H(K/C) =", Hkc)
  40. print ("H(K/C) = H(M) + H(K) - H(C) =", Hk + Hm - Hc)

求得 :

H(M) = 1.5545851693377997
H(K) = 1.5
H(C) = 1.9430486343469147
H(M/C) = 1.1115365349908848
H(K/C) = 1.1115365349908848
H(K/C) = H(M) + H(K) - H(C) = 1.111536534990885

[3]

证明:

已知概率关系


之间存在映射关系
映射关系证明如下 :
对于任意的 都有

由上,可以有推导过程 :

因此任意 均可通过上述推导过程由条件
得到

即两式之间存在映射
且现已知

由映射关系可得

[4]

证明一个密码体制完全保密的充要条件为

移位寄存器

[1]

3级线性反馈移位寄存器 时可有4种线性反馈函数,设初态为 , 求各线性反馈函数的输出序列和周期。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int f(int *a, int *c, int n)
  4. {
  5. int g = a[0];
  6. a[n] = 0;
  7. for(int i = 0; i < n; i++) {
  8. a[n] ^= a[i] * c[n - 1 - i];
  9. }
  10. for(int i = 0; i < n; i++) {
  11. a[i] = a[i + 1];
  12. }
  13. return g;
  14. }
  15. bool cmp(int *a, int *b, int n)
  16. {
  17. for(int i = 0; i < n; i++) {
  18. if(a[i] != b[i]) return false;
  19. }
  20. return true;
  21. }
  22. int main()
  23. {
  24. int a[5] = {1, 0, 1, 0, 0};
  25. int c[5] = {0, 0, 1, 0, 0};
  26. int fa[5], t;
  27. memcpy(fa, a, sizeof a);
  28. for(int &i = c[0]; i < 2; i++) {
  29. c[1] = 0;
  30. for(int &j = c[1]; j < 2; j++) {
  31. cout <<"c1 = " << i << ", c2 = " << j << " : " <<endl;
  32. cout << "output sequence : ";
  33. t = 0;
  34. do {
  35. cout << f(a, c, 3);
  36. t++;
  37. }while(!cmp(a, fa, 3));
  38. cout << endl;
  39. cout << "period = " << t << endl << endl;
  40. }
  41. }
  42. return 0;
  43. }

由上述程序可得结果 :

c1 = 0, c2 = 0 :
output sequence : 101
period = 3

c1 = 0, c2 = 1 :
output sequence : 1011100
period = 7

c1 = 1, c2 = 0 :
output sequence : 1010011
period = 7

c1 = 1, c2 = 1 :
output sequence : 10
period = 2

[2]

4级线性反馈移位寄存器在 , 可有8种线性反馈函数,设初态为,确定这些线性反馈函数中哪一个将给出周期为 的密钥流。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int f(int *a, int *c, int n)
  4. {
  5. int g = a[0];
  6. a[n] = 0;
  7. for(int i = 0; i < n; i++) {
  8. a[n] ^= a[i] * c[n - 1 - i];
  9. }
  10. for(int i = 0; i < n; i++) {
  11. a[i] = a[i + 1];
  12. }
  13. return g;
  14. }
  15. bool cmp(int *a, int *b, int n)
  16. {
  17. for(int i = 0; i < n; i++) {
  18. if(a[i] != b[i]) return false;
  19. }
  20. return true;
  21. }
  22. void output(int *a, int n)
  23. {
  24. while(n--) {
  25. cout << a[n];
  26. }
  27. cout << endl;
  28. }
  29. int main()
  30. {
  31. int a[] = {1, 1, 0, 1, 0};
  32. int c[] = {0, 0, 0, 1, 0};
  33. int fa[5], t;
  34. memcpy(fa, a, sizeof a);
  35. for(int &i = c[0]; i < 2; i++) {
  36. c[1] = 0;
  37. for(int &j = c[1]; j < 2; j++) {
  38. c[2] = 0;
  39. for(int &k = c[2]; k < 2; k++) {
  40. int t = (1 << 4) - 1;
  41. do{
  42. f(a, c, 4);
  43. t--;
  44. }while(!cmp(a, fa, 4));
  45. if(!t) {
  46. cout << "c = ";
  47. output(c, 4);
  48. }
  49. }
  50. }
  51. }
  52. return 0;
  53. }

求得两解 :

c = 1100
c = 1001

[3]

[3] 假设破译者得到密文串 和相应的明文串 。假定攻击者也知道密钥流是使用3级线性移位寄存器产生的,试破译该密码系统。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int f(int *a, int *c, int n)
  4. {
  5. int g = a[0];
  6. a[n] = 0;
  7. for(int i = 0; i < n; i++) {
  8. a[n] ^= a[i] * c[n - 1 - i];
  9. }
  10. for(int i = 0; i < n; i++) {
  11. a[i] = a[i + 1];
  12. }
  13. return g;
  14. }
  15. void output(int *a, int n)
  16. {
  17. while(n--) {
  18. cout << a[n];
  19. }
  20. cout << endl;
  21. }
  22. void putIntoArray(int *a, int d, int n)
  23. {
  24. for(int i = 0; i < 3; i++) {
  25. a[i] = (d >> i & 1);
  26. }
  27. }
  28. int main()
  29. {
  30. char plx[20], ctx[20];
  31. int a[5] = {0}, c[5] = {0}, fa[5], key[20], l;
  32. //输入 plx = '0100010001', ctx = '1010110110'
  33. cin >> plx >> ctx;
  34. l = strlen(plx);
  35. for(int i = 0; i < l; i++) {
  36. key[i] = (plx[i] - '0') ^ (ctx[i] - '0');
  37. }
  38. for(int i = 0; i < (1 << 3); i++) {
  39. for(int j = 0; j < (1 << 3); j++) {
  40. putIntoArray(c, j, 3);
  41. putIntoArray(a, i, 3);
  42. int k = 0;
  43. for(k = 0; k < l; k++) {
  44. if(key[k] != f(a, c, 3)) break;
  45. }
  46. if(k >= l) {
  47. cout << "a = "; output(a, 3);
  48. cout << "c = "; output(c, 3);
  49. return 0;
  50. }
  51. }
  52. }
  53. puts("no solution");
  54. return 0;
  55. }

解得 :

a = 010
c = 101

[4]

初态为 ,试求此非线性移位寄存器的输出序列及周期。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int f(int *a)
  4. {
  5. int g = a[1];
  6. a[5] = a[1] ^ a[4] ^ 1 ^ (a[2] * a[3]);
  7. for(int i = 1; i <= 4; i++) {
  8. a[i] = a[i + 1];
  9. }
  10. return g;
  11. }
  12. bool cmp(int *a, int *b)
  13. {
  14. for(int i = 1; i <= 4; i++) {
  15. if(a[i] != b[i]) return false;
  16. }
  17. return true;
  18. }
  19. int main()
  20. {
  21. int a[] = {0, 1, 1, 0, 1, 0}, fa[6];
  22. int t = 0;
  23. memcpy(fa, a, sizeof a);
  24. cout << "sequence = ";
  25. do {
  26. cout << f(a);
  27. t ++;
  28. }while(!cmp(a, fa));
  29. cout << endl;
  30. cout <<"period = " << t << endl;
  31. return 0;
  32. }

解得 :

sequence = 11011
period = 5

[5]

[5] 设J-K触发器中 是3级m序列, 是4级m序列,且


试求J-K触发器的输出序列 及周期。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn(50);
  4. int input(int *d)
  5. {
  6. char cd[maxn];
  7. cin >> cd;
  8. int ld = strlen(cd);
  9. for(int i = 1, j, k; i < ld; i++) {
  10. if(ld % i != 0) continue;
  11. for(j = 0, k; j < i; j++) {
  12. for(k = j; k < ld; k += i) {
  13. if(cd[k] != cd[j]) break;
  14. }
  15. if(k < ld) break;
  16. }
  17. if(j >= i) {
  18. ld = i;
  19. break;
  20. }
  21. }
  22. for(int i = 0; i < ld; i++) {
  23. d[i] = cd[i] - '0';
  24. }
  25. return ld;
  26. }
  27. int main()
  28. {
  29. freopen("data.in", "r", stdin);
  30. int a[maxn], am, b[maxn], bn, u = 0;
  31. am = input(a);
  32. bn = input(b);
  33. for(int i = 0; i < bn; i++) {
  34. b[i] = 1 - b[i];
  35. }
  36. int j = 0, fu = a[0] == b[0] ? -1 : 1;
  37. do {
  38. u = u ? b[j % bn] : a[j % am];
  39. j++;
  40. cout << u;
  41. if(j % 15 == 0) cout <<endl;
  42. }while(j % am != 0 || j % bn != 0);
  43. cout << endl;
  44. cout << "period = " << j << endl;
  45. return 0;
  46. }

得到结果为 :

110010010101111
110100101100011
110001100100111
110010101101111
110101100010111
110100100101111
110101101100111

period = 105

[6]

[6] 设二元域GF(2)上的一个线性移位寄存器的联系多项式为,初始状态为 ,试求其输出序列及其周期。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn(20);
  4. int input(int *a)
  5. {
  6. char s[maxn];
  7. cin >> s;
  8. int i;
  9. for(i = 0; s[i]; i++) {
  10. a[i] = s[i] - '0';
  11. }
  12. return i;
  13. }
  14. int f(int *a, int *c, int n)
  15. {
  16. int g = a[0];
  17. a[n] = 0;
  18. for(int i = 0; i < n; i++) {
  19. a[n] += a[i] * c[i];
  20. }
  21. a[n] &= 1;
  22. for(int i = 0; i < n; i++) {
  23. a[i] = a[i + 1];
  24. }
  25. return g;
  26. }
  27. bool cmp(int *a, int *fa, int n)
  28. {
  29. for(int i = 0; i < n; i++) {
  30. if(a[i] != fa[i]) return false;
  31. }
  32. return true;
  33. }
  34. int main()
  35. {
  36. int n;
  37. int c[maxn], a[maxn], fa[maxn];
  38. cin >> n;
  39. input(c);
  40. input(a);
  41. memcpy(fa, a, sizeof a);
  42. int t = 0;
  43. do {
  44. cout << f(a, c, n);
  45. t++;
  46. }while(!cmp(a, fa, n));
  47. cout << endl;
  48. cout << "period = " << t << endl;
  49. return 0;
  50. }

求得 :

1101000
period = 7

[7]

设二元域GF(2)上的一个线性移位寄存器的联系多项式为 ,初始状态为 ,试求其输出序列及其周期.

[6]的程序可求得 :

0110111110100010010101100001110
period = 31

数字签名

[1]

在DSS数字签名标准中,取 , 的一个本原元,于是 ,若取 ,则 ,假设想签名一个消息 ,且选择 ,计算明文 的签名,然后验证。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int quickPower(int a, int n, int mod)
  4. {
  5. int ans = 1;
  6. while(n) {
  7. if(n & 1) ans = ans * a % mod;
  8. a = a * a % mod;
  9. n >>= 1;
  10. }
  11. return ans;
  12. }
  13. //83 41 23 4 56 57 77
  14. int main()
  15. {
  16. int p, q, k, g, x, m, y;
  17. cout <<"input p, q, k, g, m, x, y :" << endl;
  18. cin >> p >> q >> k >> g >> m >> x >> y;
  19. int r = quickPower(g, k, p) % q;
  20. cout << "r = " << r << endl;
  21. int rk;
  22. for(rk = 1; rk < q; rk++) {
  23. if(rk * k % q == 1) break;
  24. }
  25. int s = (rk * (m + x * r)) % q;
  26. cout << "s = " << s << endl;
  27. cout <<"------------" << endl;
  28. int rs = 0;
  29. while(rs * s % q != 1) rs++;
  30. int w = rs % q;
  31. cout << "w = " << w << endl;
  32. int u1 = (m * w) % q;
  33. cout << "u1 = " << u1 << endl;
  34. int u2 = (r * w) % q;
  35. cout << "u2 = " << u2 << endl;
  36. int v = quickPower(g, u1, p) * quickPower(y, u2, p) % p % q;
  37. cout << "v = " << v << endl;
  38. return 0;
  39. }

由上述程序可得 :


得到密文

验证 :


得到 : v = r, 验证成功

[2]

假设用户A使用了 的DSS数字签名标准,利用随机值 确定关于消息 的用户A签名,且说明产生签名是怎样验证的.

A签名, 由[1]给出的程序计算出 :

然后将 发送给B

B验证, 由[1]给出的程序 :

最后计算出

与r相等, 验证成功,是A的数字签名

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注