【春秋云实企安殿】Classical - Crypto - 300 pt
题目描述题目分析
题目给出了生成脚本
enc给出了：956576997571830839619219661891070912231751993511506911202000405564746186955706649863934091672487787498081924933879394165075076706512215856854965975765348320274158673706628857968616084896877423278655939177482064298058099263751625304436920987759782349778415208126371993933473051046236906772779806230925293741699798906569
key.pub给出了：
本质上就是Merkle–Hellman 背包加密的一个变种
私钥 sk：超递增序列sk > sum(sk)
公钥 pkpk = sk * mask mod N
其中：
[*]mask 与 N 互素
[*]N > sk[-1]
加密cipher = Σ msg * pk
低密度背包问题
c=i=0∑n−1mi⋅pki,mi∈{0,1}
由于：
[*]原始 sk 是超递增
[*]公钥 pk 是线性变换
[*]明文是比特串
⇒ 可转化为格上的最短向量问题（SVP）
c=956576997571830839619219661891070912231751993511506911202000405564746186955706649863934091672487787498081924933879394165075076706512215856854965975765348320274158673706628857968616084896877423278655939177482064298058099263751625304436920987759782349778415208126371993933473051046236906772779806230925293741699798906569
pubkey=
from Crypto.Util.number import long_to_bytes as l2b
def create_matrix(pub, c):
n = len(pub)
i = matrix.identity(n) * 2
last_col = [-1] * n
first_row = []
for p in pub:
first_row.append(int(p))
first_row.append(-c)
m = matrix(ZZ, 1, n+1, first_row)
bottom = i.augment(matrix(ZZ, n, 1, last_col))
m = m.stack(bottom)
return m
def is_target_value(V):
for v in V:
if v!=-1 and v!=1:
return False
return True
def find_shortest_vector(matrix):
for col in matrix.columns():
if col == 0 and is_target_value(col):
return col
else:
continue
pub = pubkey
c = c
m = create_matrix(pub, c)
lllm = m.transpose().LLL().transpose()
shortest_vector = find_shortest_vector(lllm)
print(shortest_vector)
x = ""
for v in shortest_vector:
if v == 1:
x += "1"
elif v == -1:
x += "0"
print(x)
# 先转成 int，再转 hex
hex_string = hex(int(x, 2))# 去掉 '0x' 前缀
# 如果长度是奇数，需要补零
if len(hex_string) % 2 != 0:
hex_string = "0" + hex_string
# 转成 bytes
result = bytes.fromhex(hex_string)
print(result) # bytes 类型
print(result.decode())# 转成字符串
https://sierting.feishu.cn/space/api/box/stream/download/asynccode/?code=OWMzMmEzMTEyYjIyOWRjYjE4MjE2OTAyYTYwYjkyYjlfaWo1TUxKT3JwU1FUUzVyVTRhWnNOUGgwQ1NCbnlOSnBfVG9rZW46VmVuNWIwSUZOb1dvRDZ4eEJON2N2YmVBbkZnXzE3NjgyNzU2Mjc6MTc2ODI3OTIyN19WNA
页:
[1]