暗码学系列之流暗码

注意本篇大多数的题解都是直接在VsCode点击按钮运行的，假如控制台终端输入python ABC.py(ABC.py为你写的脚本的名称)很大概会报一些小错误。这里我也不知道为什么，真的想不懂。
LSFR

标题：3级线性反馈移位寄存器在c3=1时有4种线性反馈函数,设其初始状态为(a1,a2,a3)=(1,0,1),求各线性反馈函数的输出序列及周期,输出他们的密钥流,并利用天生的密钥流对明文'0x0123456789ABCDEF'举行加密,输出加密后的效果,再对密文举行解密,输出解密后的效果。
已知：

• 寄存器长度：n = 3
  
• 状态：(a1, a2, a3)
  
• 初始状态：(1, 0, 1)
  
• 条件：c3 = 1
  

LFSR 的反馈函数是：f=c1a1⊕c2a2⊕c3a3。由于：c3=1，以是：f=c1a1⊕c2a2⊕a3
由于：\(c_1 \in \{0,1\}\)  ，\(c_2 \in \{0,1\}\)，以是一共有4种情况，对应4 个反馈函数。
编号\((c_1,c_2,c_3)\)反馈函数周期1\((0,0,1)\)\(a_3\)很短2\((0,1,1)\)\(a_2 \oplus a_3\)较短3\((1,0,1)\)\(a_1 \oplus a_3\)大概最大4\((1,1,1)\)\(a_1 \oplus a_2 \oplus a_3\)最大周期7（m序列）状态更新原则：

\[(a_1, a_2, a_3) \rightarrow (a_2, a_3, f)\]
每一轮输出值：

\[\text{输出值} 为 a_1\]

1. def lfsr_step(state, c1, c2):
2.     a1, a2, a3 = state
3.     f = (c1 & a1) ^ (c2 & a2) ^ a3
4.     return (a2, a3, f)
6. def generate_sequence(init_state, c1, c2):
7.     state = init_state
8.     seen = []
9.     output = []
11.     while state not in seen:
12.         seen.append(state)
13.         output.append(state[0])
14.         state = lfsr_step(state, c1, c2)
16.     return output, len(seen)
18. def bits_to_bytes(bits):
19.     res = []
20.     for i in range(0, len(bits), 8):
21.         byte = 0
22.         for j in range(8):
23.             if i + j < len(bits):
24.                 byte = (byte << 1) | bits[i + j]
25.         res.append(byte)
26.     return res
28. def encrypt(hex_str, keystream_bits):
29.     data = bytes.fromhex(hex_str[2:])
30.     ks = bits_to_bytes(keystream_bits)
31.     return bytes([d ^ ks[i] for i, d in enumerate(data)]).hex()
33. def decrypt(cipher_hex, keystream_bits):
34.     data = bytes.fromhex(cipher_hex)
35.     ks = bits_to_bytes(keystream_bits)
36.     return bytes([d ^ ks[i] for i, d in enumerate(data)]).hex()
38. # ==========================
39. # 主程序
40. # ==========================
41. init_state = (1, 0, 1)
42. plaintext = "0x0123456789ABCDEF"
44. configs = [
45.     (0, 0),
46.     (0, 1),
47.     (1, 0),
48.     (1, 1)
49. ]
51. for c1, c2 in configs:
52.     print("=" * 40)
53.     print(f"反馈函数: f = {c1}*a1 ⊕ {c2}*a2 ⊕ a3")
55.     seq, period = generate_sequence(init_state, c1, c2)
57.     print("输出序列:", seq)
58.     print("周期:", period)
60.     # 生成64bit密钥流
61.     keystream = (seq * (64 // len(seq) + 1))[:64]
62.     print("密钥流(bit):", keystream)
64.     # 加密
65.     cipher = encrypt(plaintext, keystream)
66.     print("密文:", cipher)
68.     # 解密
69.     plain = decrypt(cipher, keystream)
70.     print("解密:", plain)

复制代码

ElGamal

标题：编程实现ElGamal的加密息争密，假设用户A选择素数p=11和本原根g=2，而且选择私钥α=5，输出A的公钥；若用户B向用户A发送消息m=6，随机数k=7，输出对该消息加密后的密文，以及对密文举行解密的明文。
已知：

• 素数：p=11
  
• 本原根：g=2
  
• A 的私钥：α=5
  

1. def nlfsr_step(state):
2.     a1, a2, a3, a4 = state
3.     # 非线性反馈函数
4.     f = (a1 & a4) ^ (a2 & a3)
5.     # 移位
6.     return (a2, a3, a4, f)
8. def generate_sequence(init_state):
9.     state = init_state
10.     seen = []
11.     output_seq = []
13.     while state not in seen:
14.         seen.append(state)
15.         output_seq.append(state[0])  # 输出 a1
16.         state = nlfsr_step(state)
18.     period = len(seen)
19.     return output_seq, period
21. def bits_to_bytes(bits):
22.     res = []
23.     for i in range(0, len(bits), 8):
24.         byte = 0
25.         for j in range(8):
26.             if i + j < len(bits):
27.                 byte = (byte << 1) | bits[i + j]
28.         res.append(byte)
29.     return res
31. def encrypt(plaintext_hex, keystream_bits):
32.     plaintext = bytes.fromhex(plaintext_hex[2:])
33.     keystream_bytes = bits_to_bytes(keystream_bits)
35.     cipher = bytes([p ^ keystream_bytes[i] for i, p in enumerate(plaintext)])
36.     return cipher.hex()
38. def decrypt(cipher_hex, keystream_bits):
39.     cipher = bytes.fromhex(cipher_hex)
40.     keystream_bytes = bits_to_bytes(keystream_bits)
42.     plain = bytes([c ^ keystream_bytes[i] for i, c in enumerate(cipher)])
43.     return plain.hex()
45. # ==========================
46. # 主流程
47. # ==========================
48. init_state = (1, 1, 0, 1)
50. # 生成序列
51. seq, period = generate_sequence(init_state)
53. print("输出序列:", seq)
54. print("周期:", period)
56. # 生成足够长的密钥流（明文8字节=64bit）
57. keystream_bits = (seq * (64 // len(seq) + 1))[:64]
59. print("密钥流(bit):\n", keystream_bits)
61. # 明文
62. plaintext = "0x0123456789ABCDEF"
64. # 加密
65. cipher = encrypt(plaintext, keystream_bits)
66. print("密文:", cipher)
68. # 解密
69. decrypted = decrypt(cipher, keystream_bits)
70. print("解密结果:", decrypted)

复制代码

1. #include <stdio.h>
3. #define p 11
4. #define a 1
5. #define b 6
7. typedef struct {
8.     int x;
9.     int y;
10. } Point;
12. int isOnCurve(Point point) {
13.     int left = (point.y * point.y) % p;
14.     int right = (point.x * point.x * point.x + a * point.x + b) % p;
15.     return left == right;  
16. }
18. int main() {
19.     int count = 0;
21.     for (int x = 0; x < p; x++) {
22.         for (int y = 0; y < p; y++) {
23.             Point point = {x, y};
24.             if (isOnCurve(point)) {
25.                 printf("(%d, %d)\n", point.x, point.y);
26.                 count++;
27.             }
28.         }
29.     }
31.     printf("Point at infinity: O\n"); //注意，必须添加无穷远点。
32.     printf("Total points (including O): %d\n", count + 1);
34.     return 0;
35. }

复制代码

RSA

标题：编程实现RSA的加密息争密，选择参数p=71593，q=77041，e=1757316971，输出公钥和私钥，并对消息“I need your best time”举行加密，输出密文。末了对密文举行解密，输出明文。
已知：

• 两个大素数 p=71593,q=77041
  
• 公钥指数 e=1757316971
  

1. p = 11
2. a = 1
3. b = 6
5. points = []
7. for x in range(p):
8.     rhs = (x**3 + a*x + b) % p
9.     for y in range(p):
10.         if (y*y) % p == rhs:
11.             points.append((x, y))
13. # 加上无穷远点
14. points.append("O")
16. print("椭圆曲线上的点：")
17. for pt in points:
18.     print(pt)
20. print("\n点的总数：", len(points))

复制代码

1. 加解密原理：
2. 超递增序列（私钥）。A = [1, 3, 5, 11, 21, 44, 87, 175, 349, 701] 。 满足每个元素 > 前面所有元素之和
3. 保证子集和可唯一反推（贪心）。
4. ↓
5. 公钥生成 Bi​=(t⋅Ai​)mod k ， k = 1590，t = 43（i是下标）
6. ↓
7. 加密。把字符 → 二进制（10 bit，对应 A 长度） C=∑bi​⋅Bi​
8. ↓
9. 解密。1. 求逆元：t^-1 modk
10.      2. 还原：C′=C⋅t^−1 modk
11.      3. 用 A 贪心恢复 bit

复制代码

DH

标题：编程盘算25的全部本原根。

• 本原根界说
  

对于整数 \(n\) 和 \(g\)（模 \(n\)），假如 \(g\) 的阶便是欧拉函数 \(\phi(n)\)，则称 \(g\) 是 \(n\) 的本原根：

\[g^1, g^2, ..., g^{\phi(n)} \mod n\]
会天生模 \(n\) 的全部互质剩余类（即整数 1 到 \(n-1\) 与 \(n\) 互质的整数）。

• 盘算步调
  

• \(n = 25\)
  
• 盘算 \(\phi(25) = 25 \cdot (1 - 1/5) = 20\)
  
• 查抄每个 \(g \in [1, 24]\)，若：
  

\[g^{20/p} \neq 1 \pmod{25} \quad \forall p \text{ 是 } 20 \text{ 的质因子}\]
则 \(g\) 是本原根。

• 20 的质因子：2, 5。
  

1. # 私钥
2. A = [1, 3, 5, 11, 21, 44, 87, 175, 349, 701]
4. # 参数
5. k = 1590
6. t = 43
8. # 求逆元（扩展欧几里得）
9. def modinv(a, m):
10.     def egcd(a, b):
11.         if b == 0:
12.             return a, 1, 0
13.         g, x1, y1 = egcd(b, a % b)
14.         return g, y1, x1 - (a // b) * y1
16.     g, x, _ = egcd(a, m)
17.     if g != 1:
18.         raise Exception("无逆元")
19.     return x % m
21. # 生成公钥
22. B = [(t * ai) % k for ai in A]
23. print("公钥 B:", B)
25. # 字符转10bit
26. def char_to_bits(c):
27.     val = ord(c)
28.     return [(val >> i) & 1 for i in reversed(range(10))]
30. # bits转字符
31. def bits_to_char(bits):
32.     val = 0
33.     for b in bits:
34.         val = (val << 1) | b
35.     return chr(val)
37. # 加密
38. def encrypt(plaintext):
39.     ciphertext = []
40.     for ch in plaintext:
41.         bits = char_to_bits(ch)
42.         c = sum(b * bi for b, bi in zip(bits, B))
43.         ciphertext.append(c)
44.     return ciphertext
46. # 解密
47. def decrypt(ciphertext):
48.     inv_t = modinv(t, k)
49.     plaintext = ""
51.     for c in ciphertext:
52.         c_prime = (c * inv_t) % k
54.         # 贪心恢复
55.         bits = [0] * len(A)
56.         for i in reversed(range(len(A))):
57.             if c_prime >= A[i]:
58.                 bits[i] = 1
59.                 c_prime -= A[i]
61.         plaintext += bits_to_char(bits)
63.     return plaintext
65. # ==========================
66. # 主程序
67. # ==========================
68. plaintext = "SAUNA AND HEALTH"
70. print("明文:", plaintext)
72. cipher = encrypt(plaintext)
73. print("密文:", cipher)
75. decrypted = decrypt(cipher)
76. print("解密:", decrypted)

复制代码

标题：编程实现Diffie-Hellman密钥交换协议，假设共享素数p=19，它的一个本原元g =3，A选机密的随机数x=5，B选机密的随机数y=7，输出A和B共享的密钥。

• 素数：p=19
  
• 本原元：g=3
  
• A 的私钥：x=5
  
• B 的私钥：y=7
  

A盘算并发送15

\[A = g^x \mod p = 3^5 \mod 19 = 15\]
B盘算并发送2

\[B = g^y\mod p = 3^7 \mod 19 =2\]
盘算共享密钥
A盘算

\[K = B^x \mod p = 2^5 \mod 19  = 13\]
B盘算

\[K = A^y \mod p = 15^7 \mod 19  = 13\]
以是终极的共享密钥就是K=13
[code]生成公钥。β=g^α modp,计算β=2^5 mod 11= 32 mod 11= 10,所以A的公钥为(p, g, β) = (11, 2, 10)
↓
加密（B → A）。给定，明文：m = 6，随机数：k = 7。计算 c1​=g^k mod p= 2^7 mod 11= 7,c2​=m⋅β^k mod p=6*10^7 mod 11=5。所以密文为(c1, c2) = (7, 5)
↓