标签 LLL格基规约 下的文章


[CISCN 2022 东北赛区]math

题干
​

import gmpy2
from Crypto.Util.number import *
from flag import flag
assert flag.startswith(b"flag{")
assert flag.endswith(b"}")
message=bytes_to_long(flag)
def keygen(nbit, dbit):
if 2*dbit < nbit:
while True:
a1 = getRandomNBitInteger(dbit)
b1 = getRandomNBitInteger(nbit//2-dbit)

n1 = a1*b1+1

if isPrime(n1):
break
while True:
a2 = getRandomNBitInteger(dbit)
b2 = getRandomNBitInteger(nbit//2-dbit)

n2=a2*b2+1

n3=a1*b2+1
if isPrime(n2) and isPrime(n3):
break
while True:
a3=getRandomNBitInteger(dbit)
if gmpy2.gcd(a3,a1*b1*a2*b2)==1:
v1=(n1-1)*(n2-1)
k=(a3*inverse(a3,v1)-1)//v1
v2=k*b1+1
if isPrime(v2):
return a3,n1*n2,n3*v2
def encrypt(msg, pubkey):
return pow(msg, pubkey[0], pubkey[1])

分析
分析题干，发现取近似值后有N1约等于 a1*b1*a2*b2 ，N2约等于 a1*b2*k*b1 ，两者结构相似，且有N1/N2约等于a2/k，因此理论上可以尝试采用连分数展开来求解a2和k参数的值。
首先进行可行性分析，计算是否满足收敛的验证条件，经过验证，误差大致在 2^-511 到 2^-512 之间，满足 2^-513 的临界条件，因此满足条件，理论上可以通过连分数展开来求解。
补充：连分数展开前提条件，即确定p/q是否一定是x的某个收敛子的判断依据。要求既约分数p/q满足

QianJianTec1768191074497.png


除了连分数展开以外，此处还可以采用LLL格基规约来求解，原理是近似的，会在后续进行展开说明
对N1/N2进行常规展开之后得到多个候选解，此时可以选用a2与k均为256bit数量级的条件进行约束，经过筛选共有两组候选解
通过上述步骤得到a2与k的值之后，下一步可以采用多种方式求解，其中我认为最易于理解的思路是构造同余关系，进行CRT约束求解。
首先根据已有的式子 phi(N1)=a1*b1*a2*b2 以及 ed-1=k*phi(N1) 即 k*phi(N1)≡-1(mod e) 分别可以构造出 phi(N1)≡0 mod a2 与 k*phi(N1)≡-1(mod e) 两个同余式，随后对其进行CRT求解可以得到 phi(N1)≡_phi(mod a2*e)

需要注意的是构造同余式的过程当中其中的第二个式子需要满足一定的前提条件即 gcd(a2, e) 必须为1，否则得到的将不是模a2*e的解而是模 lcm(a2, e) 即a2*e/gcd(a2, e) 的解。在本题当中，由于 gcd(a2, e)=1 ，可以继续进行
随后是利用已知的N1与上述CRT求出的同余关系进行N1的分解。由RSA基础公式可知 phi(N1)=N1-(n1+n2)+1 ，由于n1与n2数量级均为512bit，因而 phi(N1)-N1 的量大约为512-513bit，而 a2*e 的数量级也在512bit左右，N1为已知量，因而可以通过小范围爆破来求解n1与n2的实际值
设n1n2分别为pq，则有 p+q=N-phi(N)+1 ，验证条件此处可以设为 x^2-(p+q)*x+N=0 的判别式为完全平方数，爆破完成后即可得到pq的值，随后常规RSA解密即可

exp1
​

from math import gcd
from gmpy2 import isqrt
from Crypto.Util.number import *
from sympy.ntheory.modular import crt

e = 86905291018330218127760596324522274547253465551209634052618098249596388694529
N1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
N2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067
c1 = 71281698683006229705169274763783817580572445422844810406739630520060179171191882439102256990860101502686218994669784245358102850927955191225903171777969259480990566718683951421349181856119965365618782630111357309280954558872160237158905739584091706635219142133906953305905313538806862536551652537126291478865

class ContinuedFraction():
def __init__(self, numerator, denumerator):
self.numberlist = []
self.fractionlist = []
self.GenerateNumberList(numerator, denumerator)
self.GenerateFractionList()

def GenerateNumberList(self, numerator, denumerator):
while numerator != 1:
quotient = numerator // denumerator
remainder = numerator % denumerator
self.numberlist.append(quotient)
numerator = denumerator
denumerator = remainder

def GenerateFractionList(self):
self.fractionlist.append([self.numberlist[0], 1])
for i in range(1, len(self.numberlist)):
numerator = self.numberlist[i]
denumerator = 1
for j in range(i):
temp = numerator
numerator = denumerator + numerator * self.numberlist[i - j - 1]
denumerator = temp
self.fractionlist.append([numerator, denumerator])

a = ContinuedFraction(N1, N2)
for (_, solve) in enumerate(a.fractionlist):
if solve[0].bit_length() == 256 and solve[1].bit_length() == 256:
a2, k = solve
if gcd(a2, k) == 1:
inve = inverse(k, e)
_phi = int(crt([a2, e], [0, -inve%e])[0])
M = a2*e
for i in range(-10,10):
phi = (N1//M)*M+i*M+_phi
s = N1-phi+1
delta = s*s-4*N1
if delta > 0:
t = isqrt(delta)
if t*t == delta:
p = (s+t)//2
q = (s-t)//2
d = inverse(e, (p-1)*(q-1))
m = pow(c1, d, N1)
print(long_to_bytes(m).decode())

接下来是一些其他的思路，得到a2与k的值之后，可以直接尝试直接恢复d，而不是先恢复phi(N1)再分解N1并求解d
已知有 e*d-1=k*phi(N1) ，由于 phi(N1)=a1*a2*b1*b2≡0(mod a2) ，因此 k*phi(N1)≡0(mod k*a2) ，所以有 e*d-1≡0(mod k*a2) 。 gcd(e, a2*k)=1 ，因此可以求解e关于k*a2的逆元inva2k，此时有 d%(a2*k)=inva2k ，注意与后文d的近似值_d做好区分
另外的，与上个思路相似的，有phi(N1)与N1的大小相近，有 d=(k*phi(N1)+1)/e ，根据 phi(N1)=N1-(n1+n2)+1 ，尝试通过N1+1来近似phi(N1)，此时估算的_d与实际的d值有误差x为

QianJianTec1768191034522.png


估算误差x大小，ek位数同为256bit，因而d的估计误差x的位数大致在512-513bit左右，关于x有式子 x=_d-d=_d-inva2k-k1*(a2*k)≡_d-inva2k(mod a2*k)

因此满足式子 x=(_d-inva2k)%(a2*k)+t*a2*k ，其中x的位数与a2*k的位数相近，均为512bit左右，因而搜索空间t很小，可以快速爆破t求解x。随后根据预估值_d得到d的值，随后常规RSA求解

exp2

本题中非必要的，但可以作为拓展知识进行补充，在上述的方案中，最后一步枚举t求d的过程当中如果面临搜索空间过大的问题，可以尝试用BSGS算法将时间复杂度由o(B)降到o(sqrt(B))
即在求解inva2k之后，可以通过BSGS算法来求解x，本题中，对任意底数g，有

QianJianTec1768190944164.png
将同余式左侧设为G^t，右侧设为H，成功将问题转化为一个离散对数问题，即求解t，使得 G^t≡H(mod N1)

由于涉及到离散对数求解，此处实现用python可能相对麻烦，因此可能需要切换到sagemath，其中有内置的连分数展开、求解离散对数问题、求解模逆的函数，求解的思路实现起来很方便，具体的参考pcspcs大佬的wp就够了

要注意的是这里选用的不能是常规的bsgs算法实现，而应该是特定的针对指定区间的，类似于bounded bsgs的算法，与常规的算法实现有着些许的差异，具体表现在未知数x的范围，常规的应该在ord(g)-1内，一旦超过一定的量级，就难以求解出结果，而本题中因为知道x的上界，所以不需要群阶信息，也不需要做全范围的离散对数，只用在这个由数量级推算出来的确定的小范围里搜索就可以了。具体细节不难实现，这里就不多赘述了。
对于已知a2和k求解flag的另一种思路是利用爆破高位+coppersmith来求解，此时需要判断未知量是否满足在小根阈值之内，经过验证，当前恰好卡在边界条件上，很可能不稳定甚至求不出解，可以通过爆破少量高位来增强该攻击方案的鲁棒性。
爆破少量高位的具体流程是先枚举一个高位前缀（规模很小， 2^8 到 2^12 级别就够用），然后对每个前缀，把 q=a2*b2+1 改写成已知近似值+小偏移的形式，用格方法去抓这个小量。
最后，第一步求解a2和k并非必须借助连分数展开，也有其他原理相似的办法来求解。连分数本质是在进行有理数逼近。既然要找256bit的a2和k使得 N1/N2≈a2/k ，那么理论上就可以把它写成一个整数线性组合尽量小的问题，然后用LLL直接把这组小关系挖出来。将差值视为小量，利用格基规约进行求解。
本题中的小量即为 N1*k-N2*a2 ，相对于主量级这是一个极小的数，不过这里由于不同维度的数量级不一样，需要先进行缩放，把不同维度的量级拉到同一数量级上。
相对于连分数逼近而言，利用LLL算法来求解的容错性与泛用性更高，例如对于不确定是否符合理论阈值的时候，LLL往往还能给出可用的候选，但是运算量这方面而言比连分数展开的方法要重不少。

总结
复盘了一下CISCN 2022 东北赛区 math题目，并把这题里能走通的几条路线放在同一条脉络下统一整理了一遍。主线部分强调的是先把关键参数落地，再用最稳的方式收尾：前半段通过比值逼近筛出 a2 和 k 的候选，后半段用CRT把 phi(N1) 的同余信息拼起来，再借助 phi(N1) 与 N1 的接近性在很小的范围内定位出正确的 p+q，用判别式验平方完成分解并解密。拓展部分则是把收尾拆成可替换的模块：可以不显式恢复 phi(N1)，而是直接从 d mod (a2*k) 与近似值 _d 把误差压缩到很小的搜索区间里求出 d；当枚举空间变大时再用bounded BSGS把线性枚举换成开方级复杂度；同时也说明了第一步并不一定非要用连分数，LLL同样可以在结构相似带来的小量关系里挖出候选，而爆破少量高位配合格方法属于可行但不如主线稳的备选。整体来看，这题最有价值的地方在于可以把“结构信息→可求参数→多种收尾工具”的链条串得很清楚，后续遇到类似的结构化RSA题，基本都能沿着同样的节奏把问题拆开、把不确定性压到可控范围内解决。

​