[Crypto] primegame - k1rit0

xp0int Posted on Jun 6 2021

一看到还以为是小数的背包问题, 仔细想想并不是, 来看一下式子就能懂了, 先看得到密文$ct$的式子
$$
ct = 2^{256}(k_0m_0 + k_1m_1 + k_2m_2 + \cdots k_{23}m_{23}) - e
$$
这里多了个$-e$ 就是把取整直接看成减去一个小数$e$了

$k_n$是已知的, 而且是小数, 不能直接造格子, 但我们把$2^{256}$分配给每一项就不一样了, 对于其中一项 
$$
2^{256}km = 2^{256}\ln p \cdot m = (\lfloor 2^{256} \ln p \rceil - e')\cdot m
$$
记$\lfloor 2^{256} \ln p_i \rceil = A_i$每一项都这么干, 那么整个$ct$就会变成
$$
\begin{align}
ct &= A_0m_0 + A_1m_1 + \cdots + A_{23}m_{23} -(m_0e_0'+m_1e_1'+\cdots+m_{23}e_{23}' + e'') \\\\
& = A_0m_0 + A_1m_1 + \cdots + A_{23}m_{23} -E
\end{align}
$$
其中系数$A$都是特别大的数, 而$m,E$都非常小, 这时我们就可以用背包问题的解法求出$m$

构造格子
$$
\begin{pmatrix}
1 & 0 & 0 & \cdots & 0 & A_0 \\
0 & 1 & 0 & \cdots & 0 & A_1 \\
0 & 0 & 1 & \cdots & 0 & A_2 \\
\vdots &\vdots &\vdots &\ddots&\vdots&\vdots \\
0 & 0 & 0 & \cdots & 1 & A_{23} \\
0 & 0 & 0 & \cdots & 0 & -ct 
\end{pmatrix}
$$
规约这个格子就能得到$(m_0,m_1,\cdots,m_{23},E)$了

## exp
```python
from decimal import *
import math
primes = [2]
for i in range(3, 90):
    f = True
    for j in primes:
        if i * i < j:
            break
        if i % j == 0:
            f = False
            break
    if f:
        primes.append(i)
getcontext().prec = 100
keys = []
for i in range(24):
    keys.append(math.floor(Decimal(primes[i]).ln()*2**256))
c1 = 597952043660446249020184773232983974017780255881942379044454676980646417087515453
c2 = 425985475047781336789963300910446852783032712598571885345660550546372063410589918

L = matrix([[0 for _ in range(25)] for _ in range (25)])
for i in range(24):
    L[i,-1] = keys[i]
    L[i,i] = 1
L[-1,-1] = -c1

for i in L.LLL()[0][:-1]:
    print(chr(i),end='')
L[-1,-1] = -c2
for i in L.LLL()[0][:-1]:
    print(chr(i),end='')
```
其实是有原题的https://www.secmem.org/blog/2020/09/20/poka-science-war-hacking/
不过这题自己做会比找原题快一点

打赏还是打残，这是个问题