密码学系列之流密码RSAECC等

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

因为：c1∈{0,1} ，c2∈{0,1}，所以一共有4种情况，对应4 个反馈函数。

编号(c1,c2,c3)反馈函数周期
1(0,0,1)a3很短
2(0,1,1)a2⊕a3较短
3(1,0,1)a1⊕a3可能最大
4(1,1,1)a1⊕a2⊕a3最大周期7（m序列）

状态更新原则：

(a1,a2,a3)→(a2,a3,f)

每一轮输出值：

输出值为a1

def lfsr_step(state, c1, c2):
a1, a2, a3 = state
f = (c1 & a1) ^ (c2 & a2) ^ a3
return (a2, a3, f)
def generate_sequence(init_state, c1, c2):
state = init_state
seen = []
output = []
while state not in seen:
seen.append(state)
output.append(state[0])
state = lfsr_step(state, c1, c2)
return output, len(seen)
def bits_to_bytes(bits):
res = []
for i in range(0, len(bits), 8):
byte = 0
for j in range(8):
if i + j < len(bits):
byte = (byte << 1) | bits[i + j]
res.append(byte)
return res
def encrypt(hex_str, keystream_bits):
data = bytes.fromhex(hex_str[2:])
ks = bits_to_bytes(keystream_bits)
return bytes([d ^ ks[i] for i, d in enumerate(data)]).hex()
def decrypt(cipher_hex, keystream_bits):
data = bytes.fromhex(cipher_hex)
ks = bits_to_bytes(keystream_bits)
return bytes([d ^ ks[i] for i, d in enumerate(data)]).hex()
# ==========================
# 主程序
# ==========================
init_state = (1, 0, 1)
plaintext = "0x0123456789ABCDEF"
configs = [
(0, 0),
(0, 1),
(1, 0),
(1, 1)
]
for c1, c2 in configs:
print("=" * 40)
print(f"反馈函数: f = {c1}*a1 ⊕ {c2}*a2 ⊕ a3")
seq, period = generate_sequence(init_state, c1, c2)
print("输出序列:", seq)
print("周期:", period)
# 生成64bit密钥流
keystream = (seq * (64 // len(seq) + 1))[:64]
print("密钥流(bit):", keystream)
# 加密
cipher = encrypt(plaintext, keystream)
print("密文:", cipher)
# 解密
plain = decrypt(cipher, keystream)
print("解密:", plain)

回到顶部

NFLSR

题目：设n=4,f(a1,a2,a3,a4)=a1* a4^(a2 * a3),初始状态为(a1,a2,a3,a4)=(1,1,0,1),求此非线性反馈移位寄存器的输出序列及周期,输出他的密钥流,并利用生成的密钥流对明文'0x0123456789ABCDEF'进行加密,输出加密后的结果,再对密文进行解密,输出解密后的结果。
流密码原理 1）生成密钥流（keystream）；2）明文 XOR 密钥流 → 密文 3）密文 XOR 密钥流 → 明文。
加密：cipher = plaintext XOR keystream 解密：decrypt(cipher) == plaintext

  • 寄存器长度：n=4
  • 状态：(a1,a2,a3,a4)
  • 反馈函数：

f(a1,a2,a3,a4)=a1⋅a4⊕(a2⋅a3)

状态更新原则：

(a1,a2,a3,a4)→(a2,a3,a4,f)

输出序列一般取：

输出=a1(最左边)

def nlfsr_step(state):
a1, a2, a3, a4 = state
# 非线性反馈函数
f = (a1 & a4) ^ (a2 & a3)
# 移位
return (a2, a3, a4, f)
def generate_sequence(init_state):
state = init_state
seen = []
output_seq = []
while state not in seen:
seen.append(state)
output_seq.append(state[0]) # 输出 a1
state = nlfsr_step(state)
period = len(seen)
return output_seq, period
def bits_to_bytes(bits):
res = []
for i in range(0, len(bits), 8):
byte = 0
for j in range(8):
if i + j < len(bits):
byte = (byte << 1) | bits[i + j]
res.append(byte)
return res
def encrypt(plaintext_hex, keystream_bits):
plaintext = bytes.fromhex(plaintext_hex[2:])
keystream_bytes = bits_to_bytes(keystream_bits)
cipher = bytes([p ^ keystream_bytes[i] for i, p in enumerate(plaintext)])
return cipher.hex()
def decrypt(cipher_hex, keystream_bits):
cipher = bytes.fromhex(cipher_hex)
keystream_bytes = bits_to_bytes(keystream_bits)
plain = bytes([c ^ keystream_bytes[i] for i, c in enumerate(cipher)])
return plain.hex()
# ==========================
# 主流程
# ==========================
init_state = (1, 1, 0, 1)
# 生成序列
seq, period = generate_sequence(init_state)
print("输出序列:", seq)
print("周期:", period)
# 生成足够长的密钥流（明文8字节=64bit）
keystream_bits = (seq * (64 // len(seq) + 1))[:64]
print("密钥流(bit):\n", keystream_bits)
# 明文
plaintext = "0x0123456789ABCDEF"
# 加密
cipher = encrypt(plaintext, keystream_bits)
print("密文:", cipher)
# 解密
decrypted = decrypt(cipher, keystream_bits)
print("解密结果:", decrypted)

回到顶部

ECC

题目：已知椭圆曲线E11(1,6)，编程求其上所有的点。

这个问题本质是在有限域 F11 上求椭圆曲线

E:y2≡x3+x+6(mod11)

的所有点。

思路：

  1. 枚举 x∈[0,10]
  2. 计算右边

    rhs=x3+x+6(mod11)

  3. 枚举 y∈[0,10]，找满足以下 条件的解

    y2≡rhs(mod11)

  4. 加上无穷远点 O
#include <stdio.h>
#define p 11
#define a 1
#define b 6
typedef struct {
int x;
int y;
} Point;
int isOnCurve(Point point) {
int left = (point.y * point.y) % p;
int right = (point.x * point.x * point.x + a * point.x + b) % p;
return left == right;
}
int main() {
int count = 0;
for (int x = 0; x < p; x++) {
for (int y = 0; y < p; y++) {
Point point = {x, y};
if (isOnCurve(point)) {
printf("(%d, %d)\n", point.x, point.y);
count++;
}
}
}
printf("Point at infinity: O\n"); //注意，必须添加无穷远点。
printf("Total points (including O): %d\n", count + 1);
return 0;
}

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

回到顶部

背包

题目：编程实现背包密码的加密和解密，假设选取的私钥为超递增背包向量 A=[1, 3, 5, 11, 21, 44, 87, 175, 349, 701]，选取模数k = 1590和乘数t = 43，计算新的背包向量B == t * A (mod k)作为公钥。利用上述密码算法对明文“SAUNA AND HEALTH”进行加密，输出密文，并对密文进行解密。

实现一个公钥加密系统：

  • 私钥：超递增序列 A
  • 公钥：B = t·A mod k
  • 加密：用 B 做“子集和”
  • 解密：用 A 做“贪心恢复”
加解密原理：
超递增序列（私钥）。A = [1, 3, 5, 11, 21, 44, 87, 175, 349, 701] 。 满足每个元素 > 前面所有元素之和
保证子集和可唯一反推（贪心）。
↓
公钥生成 Bi​=(t⋅Ai​)mod k ， k = 1590，t = 43（i是下标）
↓
加密。把字符 → 二进制（10 bit，对应 A 长度） C=∑bi​⋅Bi​
↓
解密。1. 求逆元：t^-1 modk
2. 还原：C′=C⋅t^−1 modk
3. 用 A 贪心恢复 bit
# 私钥
A = [1, 3, 5, 11, 21, 44, 87, 175, 349, 701]
# 参数
k = 1590
t = 43
# 求逆元（扩展欧几里得）
def modinv(a, m):
def egcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = egcd(b, a % b)
return g, y1, x1 - (a // b) * y1
g, x, _ = egcd(a, m)
if g != 1:
raise Exception("无逆元")
return x % m
# 生成公钥
B = [(t * ai) % k for ai in A]
print("公钥 B:", B)
# 字符转10bit
def char_to_bits(c):
val = ord(c)
return [(val >> i) & 1 for i in reversed(range(10))]
# bits转字符
def bits_to_char(bits):
val = 0
for b in bits:
val = (val << 1) | b
return chr(val)
# 加密
def encrypt(plaintext):
ciphertext = []
for ch in plaintext:
bits = char_to_bits(ch)
c = sum(b * bi for b, bi in zip(bits, B))
ciphertext.append(c)
return ciphertext
# 解密
def decrypt(ciphertext):
inv_t = modinv(t, k)
plaintext = ""
for c in ciphertext:
c_prime = (c * inv_t) % k
# 贪心恢复
bits = [0] * len(A)
for i in reversed(range(len(A))):
if c_prime >= A[i]:
bits[i] = 1
c_prime -= A[i]
plaintext += bits_to_char(bits)
return plaintext
# ==========================
# 主程序
# ==========================
plaintext = "SAUNA AND HEALTH"
print("明文:", plaintext)
cipher = encrypt(plaintext)
print("密文:", cipher)
decrypted = decrypt(cipher)
print("解密:", decrypted)