密码学系列之流密码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)
的所有点。
思路：
- 枚举 x∈[0,10]
- 计算右边
rhs=x3+x+6(mod11)
- 枚举 y∈[0,10]，找满足以下 条件的解
y2≡rhs(mod11)
- 加上无穷远点 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) |