moreRSA·

普通的RSA，但是用了8个256位素数，并leak了其中2个，flag是HSCTF{uuid}，漏洞点是明文在加密时没有做padding。分析可得明文m的长度是uuid长度加7的bytes，即344bits，而泄露的素数（令其是 $p_i$ 和 $p_j$ ）共512bits，也即 $m=(m \pmod {p_ip_j})$ ，模操作不起作用，在模 $p_ip_j$ 下算出的 $m$ 就已经是明文了。而根据RSA的解密， $m = c^d \pmod {p_ip_j}$ ，其中 $d \equiv e^{-1} \pmod {(p_i-1)(p_j-1)}$ ，由于 $p_i$ 和 $p_j$ 已经由leak泄露，所以可以顺利解密。其实即使没有以上的分析，用普通的RSA解密的方法试一次也就做出来了- -

参考Exp：

from gmpy2 import invert
import libnum

e = 65537
n = 3063722943480635862237015121950954512389855637222268279562142439360092373772638451727868853897228017188009287997989686822326505963816355743751045839981623734324951907542470061214870877938345667445428799274729216487665512902821543660613371140582739693355049374075307925203465730389601758746721615119229450562856054135401000282972656280293087549115821475699821904403440347659526284524592016601374708799146492504125710267386604717353932221245458920934882010076768813518374136671178494756111675383329034142669899980752066580733483539249703449665382965798843404111880773840981973306922123554638583903318808646026150963883
c = 1893702332556285129715833178249948766640820056173780570677007145213596445254630012889699236155736800324933502446415186407909632789140125992824692017179103681425092386418797479952219681568195754688160375191024050569491383397224060174045371797275768530223432221460252759120509591464865791926840862114611672208438902892488878704864967513751405522118062827732160235469035655531992185997149368209429010016762576960972248958240651878560285806841878701901945221744091902653947560364942283301077395608980620408351811670796185806288241449971239536612761250415236225399223716711639959529979754889578964925028155331459750296227
p, q = [110884348586107266365898657364101883003745785631500488033253423256376926890429, 61166808060513244456035439636854096139839114052373310103599210439771425454931]

phi = (p-1)*(q-1)
d = invert(e, phi)
m = pow(c, d, p*q)
flag = libnum.n2s(int(m))
print(flag)

linco2n·

这题是2019 Xp0int新生赛的lincoln的魔改，咋看上去只是把参数换了和times改大了，但其实解题的方法有很大差别，毕竟 $2^{100}$ 是不能枚举的，也就不能用暴力计算的方法做了，而题目给了运算后的结果，就是说是存在高效算法计算LCG的，先说结果，其实这个LCG是存在通项公式的。

首先根据rand函数，有递推关系：

$\rm{State}_{i+1} = a·\rm{State}_i +b \pmod {n}$

令seed是初始状态 $\rm{State}_0$ ，不妨先推出前几项找规律：

$\begin{aligned} \rm{State}_1 &= a·\rm{State}_0 +b &\pmod {n} \\ \rm{State}_2 &= a·\rm{State}_1 +b &\pmod {n} \\ &= a^2·\rm{State}_0 + b(a+1) &\pmod {n} \\ \rm{State}_3 &= a^3·\rm{State}_0 + b(a^2+a+1) &\pmod {n} \\ \rm{State}_4 &= a^4·\rm{State}_0 + b(a^3+a^2+a+1) &\pmod {n} \\ ...\ ... \end{aligned}$

明显每次迭代 $\rm{State}_0$ 前面的 $a$ 次数加1（加到 $a^i$ ）， $b(·)$ 括号里增加一项 $a^{i-1}$ ，然后推出通项公式：

$\rm{State}_i = a^i·\rm{State}_0 + b·\sum_{k=0}^{i-1}a^k \pmod{n}$

到这似乎还不算高效，因为需要从 $0$ 到 $i-1$ 的求和，但是观察会发现这其实是个数列的求和，即有求和公式 $\sum_{k=0}^{i-1}a^k = \frac{a^i-1}{a-1}$ ，而且在模 $n$ 下也适用（证明略），只是需要 $a-1$ 在模 $n$ 下有逆，简单check一下是有的。所以进一步化简：

$\rm{State}_i = a^i·\rm{State}_0 + b·(a^i-1)·(a-1)^{-1} \pmod{n}$

现在知道的是 $\rm{State}_{2^{100}+1}$ （注意__str__里做了一次rand），需要求 $\rm{State}_0$ ，即整理下上式：

$\rm{State}_0 = a^{-i} · (\rm{State}_{2^{100}+1} - b·(a^i-1)·(a-1)^{-1})$

参考Exp：

from gmpy2 import invert
import libnum

a = 0x7d62d58188f9ab4ebd1a55620bd5152960eacc0016b2ae6241136979da8b59d3
b = 0xb6e6d2e6c34d71878e596b5ef97ce76ec63a09e279ff961ea86c845951063074
n = 0x5105b78d4fbfe202ee2e4c02aba41d59f435143897286ec801dfb307da928aa636b4b8524625a5117dea790a518e39f7e4cf240f414e6b61871ee56cd0d7cc17


times = 2 ** 100
x = times + 1
c = 0x9746d7770d1296870dbd8eaf03658d3e3ca2ceb5e28988ecc0557bdd0d44d811cacda444c91cafde598bf26ff108bfe36ca6e71f088f1eb2d648d59b3d96ab7
seed = (c - b*(pow(a, x, n)-1)*invert(a-1, n)) * pow(invert(a, n), x, n) % n
flag = libnum.n2s(int(seed))
print(flag)

另外在验题的时候，@M0D1提供了一种线性代数解法的思路，其实就是类似Fibonacci通项的求法：

$\begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \rm{State}_{i} \\ 1 \end{bmatrix} = \begin{bmatrix} a·\rm{State}_{i}+b \\ 0·\rm{State}_{i}+1 \end{bmatrix} = \begin{bmatrix} \rm{State}_{i+1} \\ 1 \end{bmatrix}$

从初始项开始即：

$\begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix}^i \begin{bmatrix} \rm{State}_{0} \\ 1 \end{bmatrix} = \begin{bmatrix} \rm{State}_{i} \\ 1 \end{bmatrix}$

所以：

$\begin{bmatrix} \rm{State}_{0} \\ 1 \end{bmatrix} = \begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix}^{-(2^{100}+1)} \begin{bmatrix} \rm{State}_{2^{100}+1} \\ 1 \end{bmatrix} = \begin{bmatrix} \rm{lcg} \\ 1 \end{bmatrix}$