之前结合一道DSA的题略有了解过，今天找些题目练练，加深下理解。
题一
from Crypto.Util.number import *
flag = b'Spirit{*****************}'
plaintext = bytes_to_long(flag)
length = plaintext.bit_length()
a = getPrime(length)
b = getPrime(length)
n = getPrime(length)
seed = plaintext
output = []
for i in range(10):
seed = (seed*a+b)%n
output.append(seed>>64)
print("a = ",a)
print("b = ",b)
print("n = ",n)
print("output = ",output)
# a = 731111971045863129770849213414583830513204814328949766909151
# b = 456671883153709362919394459405008275757410555181682705944711
# n = 666147691257100304060287710111266554526660232037647662561651
# output = [16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]
结合了LCG问题，a、b、n都有，还有每一轮得到的数进行右移64位的结果。
生成过程：$s_{i+1} = a\cdot s_{i} + b \space (mod \space n)$
将每个$s_{i}$拆成高位部分$h_i$(已知)和低位部分$l_i$，则有：
$h_{2} + l_{2} = a\cdot (h_1 + l_1) + b \space (mod \space n)$
$l_{2} = a\cdot l_1 + a\cdot h_1 + b - h_{2} \space (mod \space n)$
记$A_1 = a,B_1 = a\cdot h_1 + b - h_{2}$
$l_{2} = A_1\cdot l_1 + B_1 \space (mod \space n)$
同理：
$l_{3} = a\cdot l_2 + a\cdot h_2 + b - h_{3} \space (mod \space n)$
带入$l_2$：
$l_{3} = a\cdot A_1 \cdot l_1 +a\cdot B_1+ a\cdot h_2 + b - h_{3} \space (mod \space n)$
记$A_2 = a\cdot A_1,B_2 = a\cdot B_1+ a\cdot h_2 + b - h_{3}$
$l_{3} = A_2\cdot l_1 + B_2 \space (mod \space n)$
以此类推，可得最终表达式：
$l_{i+1} = A_i \cdot l_1 + B_i \space (mod \space n)$
关系转换过后求新的A和B：
a = ...
b = ...
m = ...
h = [0,16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]
for i in range(len(h)):
h[i] <<= 64
A = [1]
B = [0]
for i in range(1, len(h)-1):
A.append(a*A[i-1] % m)
B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)
A = A[1:]
B = B[1:]
print(A)
print(B)
接着需要构造格：
关键就在如何造格。
对于形如下面的关系式组：
$\left{
\begin{matrix}
A_1\cdot x + B_1 = k_1 \pmod n\
… \
A_i\cdot x + B_i = k_i \pmod n \
\end{matrix}
\right.$
已知A、B，bit_length(k) < bit_length(p)，可构造矩阵：
$M = \begin{bmatrix}
n&&&&&& \
&.&&&&& \
&&.&&&& \
&&&.&&& \
&&&&n&& \
A_1 & . & . & . & A_i & K/q & \
B_1 & . & . & . & B_i & & K
\end{bmatrix}$
K表示上界，一般根据所求量的位数所定
此时存在向量$v = \begin{bmatrix} l_1 & . & . & . & l_i& x & 1 \end{bmatrix}$
满足$v \cdot M = \begin{bmatrix} k_1 & . & . & . & k_i& {K\cdot x}/q & K \end{bmatrix}$
在上面，我们求出关系，$l_{i+1} = A_i \cdot l_1 + B_i \space (mod \space n)$
化为$l_{i+1} = A_i \cdot l_1 + B_i \space + k \cdot n$
$l_i最大64bit，$那么可以造出下面的矩阵
$$
M = \begin{bmatrix}
n&&&&&&&&&& \
&n&&&&&&&&& \
&&n&&&&&&&& \
&&&n&&&&&&& \
&&&&n&&&&&& \
&&&&&n&&&&& \
&&&&&&n&&&& \
&&&&&&&n&&& \
&&&&&&&&n&& \
A_1 & A_2 & A_3 & A_4 & A_5 & A_6 & A_7 & A_8 & A_9 & 1 & \
B_1 & B_2 & B_3 & B_4 & B_5 & B_6 & B_7 & B_8 & B_9 & 0 & 2^{64}
\end{bmatrix}
$$
此时会存在向量$v = \begin{bmatrix} k_1 & k_2 & k_3 & k_4 & k_5 & k_6 & k_7 & k_8 & k_9 & l_1 & 1 \end{bmatrix}$ 使得
$vM = \begin{bmatrix} l_2 & l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & l_{10} & l_1 & 2^{64} \end{bmatrix}$
对此格运用LLL算法即可得到$v$，进而得到$l_1$，完整代码如下：
a = 731111971045863129770849213414583830513204814328949766909151
b = 456671883153709362919394459405008275757410555181682705944711
n = 666147691257100304060287710111266554526660232037647662561651
h = [0,16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]
for i in range(len(h)):
h[i] <<= 64
A = [1]
B = [0]
for i in range(1, len(h)-1):
A.append(a*A[i-1] % n)
B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % n)
A = A[1:]
B = B[1:]
print(A)
print(B)
M = matrix(ZZ, 11, 11)
for i in range(9):
M[i, i] = n
M[9, i] = A[i]
M[10, i] = B[i]
M[i, 9] = M[i, 10] = 0
M[9, 9] = 1
M[10, 10] = 2^64
M[9, 10]= 0
vl = M.LLL()[0]
l1 = vl[-2]
h1 = h[1]
s1 = l1+h1
#s1 = a*seed+b %n
m = ((s1 - b)*inverse_mod(a,n))%n
print(long_to_bytes(m))
#b'Spirit{King__of__LCG_qWq}'
题二
from Crypto.Util.number import *
from secret import flag3
qBits = 2048
pBits = 512
num = 2
q = getPrime(qBits)
p = [getPrime(pBits) for _ in range(num)]
r = [getRandomRange(1, 2**(pBits * 2))]
a = getRandomRange(1, 2**pBits)
b = getRandomRange(1, 2**pBits)
gift = (p[0] * a - p[1]) * inverse(b, p[0] * p[1]**2) % (p[0] * p[1]**2)
r.append(a * r[0] % p[1]**2)
n = [p[i] * q + r[i] for i in range(num)]
e = 0x10001
c = pow(bytes_to_long(flag3), e, q)
output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')
$gift = (p[0]\cdot a - p[1]) \cdot b^{-1} \pmod {p[0]\cdot p[1]^2}$
$n[0] = p[0]\cdot q + r[0]$
$n[1] = p[1]\cdot q + r[1]$
$q2048bit，p[0]、p[1]512bit，r[0]、r[1]1024bit，a、b512bit，$数据均未知。
先求$p[0]、p[1]$
$\frac{n_0}{n_1} = \frac{p[0] + \frac{r[0]}{q}}{p[1] + \frac{r[1]}{q}} \approx \frac{p[0]}{p[1]}$
连分数解出p[0]、p[1]：
n = [..., ...]
c = continued_fraction(Integer(n[0]) / Integer(n[1]))
alist = c.convergents()
for i in alist:
a = str(i).split('/')
if len(a) > 1 and gcd(int(a[0]), int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(
a[0]).bit_length() == 512 and int(a[1]).bit_length() == 512:
print(a)
#['10946837640113493291358837873345799060524211396318128031616119937230375611461398026242887066008841733944238658233988256373284494642790134423412452126096931', '8870637512403646759604184989075036324872077413980854140857074514347730644595095752344958376649371893483720976713973475270507678333288479309954238685161531']
然后化简gift表达式：
$a\cdot p[0] \cdot gift^{-1} - p[1]\cdot gift^{-1} = b\pmod {p[0]\cdot p[1]^2}$
记$p[0] \cdot gift^{-1} = A，p[1]\cdot gift^{-1} = B，p[0]\cdot p[1]^2 = n$。
$a\cdot A - B = b\pmod {p[0]\cdot p[1]^2}$
$a\cdot A - B = b + k\cdot n$
这样就满足了上面提到的关系式，构造矩阵：
$M = \begin{bmatrix}
n & & \
A & 1 & \
B & & 2^{512}
\end{bmatrix}$
存在向量$v = \begin{bmatrix} k & a & -1\end{bmatrix} $
满足$v\cdot M = \begin{bmatrix} b & a & -2^{512}\end{bmatrix}$
解出b、a：
n = [..., ...]
p = [...,...]
c = ...
gift = ...
new_n = p[0]*p[1]**2
A = p[0]*inverse(gift,new_n)
B = p[1]*inverse(gift,new_n)
M = [[new_n,0,0],[A,1,0],[B,0,-2^512]]
M = matrix(M)
M.LLL()
后面求q的部分就不提了，不是本文的重点，相关推导网上都有。
参考：
lattice的HNP问题学习_无趣的浅的博客-CSDN博客
题三
from Crypto.Util.number import *
from random import randrange
from secret import flag
def pr(msg):
print(msg)
pr(br"""...
""".decode())
def gen_prime(bit):
while 1:
P = getPrime(bit)
if len(bin(P)) - 2 == bit:
return P
pq_bit = 512
offset = 16
P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)
inpP = int(input())
if inpP != P:
pr(b"you lose!")
exit()
secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]
results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1) for ri in results]
pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
pr(flag)
这次WMCTF2023的一题：
先求P，之前的DAS里做过类似的，只不过这里把gift的高16位去掉了，直接爆破就行。
N = ...
gift = ...
for h_gift in tqdm(range(2**15,2**16-1)):
new_gift = int('0b' + bin(h_gift)[2:] + bin(gift)[2:],2)
pp = bin(new_gift)[2:][:16]
b = 512 - 16
new_gift = bin(new_gift)[2:][16:]
x = 5
for i in range((512 - 16) // x):
PP = int(pp + '0' * b, 2)
Qb = bin(N // PP)[2:][i * x:x * i + x]
gb = new_gift[i * x:i * x + x]
pb = bin(int(gb, 2) ^ int(Qb, 2))[2:].zfill(x)
pp += pb
b -= x
for i in range(3):
px = int(pp + bin(i)[2:], 2)
if N % px == 0:
p = N // px
print(p)
break
然后得到bs、rs，有下面的关系：
$\left{
\begin{matrix}
r_1 \equiv b_1\cdot s \pmod P \pmod {2^{16}}\
… \
r_i \equiv b_i\cdot s \pmod P \pmod {2^{16}} \
\end{matrix}
\right.$
$r_i = b_i\cdot s + k_i\cdot P + l_i\cdot 2^{16}$
$l_i = b_i\cdot s \cdot 2^{-16} - r_i\cdot 2^{-16} + k\cdot P\cdot 2^{-16} $
构造矩阵：
$M = \begin{bmatrix} P & & & &\ & … & & &\& & P & & \b1 & … & b_i & 2^{496}/P &\r1 & … & r_i & &2^{496} \end{bmatrix}$
存在向量$v = \begin{bmatrix} k_1&…&k_i&s & -1\end{bmatrix} $
满足$v\cdot M = \begin{bmatrix} l_1&…l_i&s\cdot 2^{496}/P & -2^{496}\end{bmatrix}$
N = 113085832762387460050909194454508188601839710145973259641841807633696910787521074664125163801098932042163263286640599073505827773617076027949457538588755266924775200379309174584352650184447965594090134058339408319123707191256078941278985793277250010359176168981371817558405046625233760118570087281158691300073
gift = 199985050803827994838443360278631790183485240671381276821869390008297094798604101650230040396960238438051744439652797351494950588189018492967049362060
q = 10334663466575336288964927237243368361745320455964266082084671022955601133491185885718414444900346920541534679690409827410640180875013525283769020248183103
p = 10942381735809094293984549887380781220213608527074866007277748738032866547099740515940771233311296703171442205884575041273590066445574456139400342395115991
bs = [...]
rs = [...]
M = matrix(QQ, 40, 40)
for i in range(38):
M[i,i] = p
M[38,i] = bs[i]*inverse_mod(2^16,p)%p
M[39,i] = rs[i]*inverse_mod(2^16,p)%p
M[38,38] = 2^496 / p
M[39,39] = 2^496
M.LLL()
L = M.LLL()
secret = L[1][-2].numerator() / 2^496#获取分子部分s*2^496，再除2^496得s
print(secret)
总结
感觉对格又有了新的认识，反正不陌生了，下次遇到类似的应该能解了吧(doge)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com