格约束习题

[CISCN 2021华南]small

import random, hashlib
from Crypto.Util.number import getPrime
from secret import x, y, flag

BITS = 70

assert(2**BITS < x < 2**(BITS+1))
assert(2**BITS < y < 2**(BITS+1))

m = str(x) + str(y)
h = hashlib.sha256()
h.update(m.encode())
assert(flag == "flag{" + h.hexdigest() + "}")


p = getPrime(512)
a = getPrime(510)
b = getPrime(510)
c = (1 + a * x * y ** 2 + b * x ** 2 * y) % p
print("p = " + str(p))
print("a = " + str(a))
print("b = " + str(b))
print("c = " + str(c))

'''
p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881
'''

自法格

题目可用二维copper，在学格所以想用格来进行解答，首先列出等式

$$c\equiv axy^2+bx^2y+1\mod p\\ c-1\equiv axy^2+bx^2y\mod p\\ axy^2+bx^2y-kp-(c-1)=0$$

那么构造格如下

$$\begin{matrix}[k &-xy^2&-x^2y&1]\end{matrix} \left[\begin{matrix}p&0&0&0\\a&1&0&0\\b&0&1&0\\c-1&0&0&1 \end{matrix}\right]=\begin{matrix}[0 &-xy^2&-x^2y&1]\end{matrix}$$

算下大概的位数，$det\approx\frac{512}{4}\approx128$，$\omega\approx maxbit(xy^2,x^2y)\approx 210$，那么需要在矩阵里凑系数使得两者接近，那么构造

$$D=2^{210}\\ \left[\begin{matrix}Dp&0&0&0\\Da&1&0&0\\Db&0&1&0\\D(c-1)&0&0&D \end{matrix}\right]$$

这样用LLL约束出来正好第一个是0最后一个是D，中间正好可以取gcd

p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881
D = 2**210
L = matrix([[D*p, 0, 0, 0], [D*a, 1, 0, 0], [D*b, 0, 1, 0], [D*(c-1), 0, 0, D]])
tmp = L.LLL()[0]
xy = GCD(tmp[1], tmp[2])
x = abs(tmp[2]) // xy
y = abs(tmp[1]) // xy

题解格

$$c-1\equiv axy^2+bx^2y\mod p\\ a^{-1}(c-1)\equiv xy^2+a^{-1}bx^2y\mod p\\ a^{-1}(c-1)-a^{-1}bx^2y-kp=xy^2$$

然后构造格

$$\begin{matrix}[1&x^2y&-k]\end{matrix} \left[\begin{matrix}1&0&a^{-1}(c-1)\\0&1&-a^{-1}b\\0&0&p \end{matrix}\right]=\begin{matrix}[1&x^2y&xy^2]\end{matrix}$$

算位数，$det\approx\frac{512}{3}\approx170$，$\omega\approx 210$，那么需要在左边配平系数

$$D=2^{210}\\ \left[\begin{matrix}D&0&a^{-1}(c-1)\\0&1&-a^{-1}b\\0&0&p \end{matrix}\right]$$

p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881
D = 2**210
t = inverse(a, p)
L = matrix([[D, 0, t*(c-1)], [0, 1, -t*b], [0, 0, p]])
tmp = L.LLL()[0]
xy = GCD(tmp[1], tmp[2])
x = abs(tmp[2]) // xy
y = abs(tmp[1]) // xy

[2024春秋杯夏季赛]happy2024部分

not2022but2024.py

from Crypto.Util.number import *

CBC_key = b''

p,q = getPrime(512),getPrime(512)
n = p * q
N = n**2 + 2024
hint = (pow(3, 2022, N) * p**2 + pow(5, 2022, N) * q**2) % N
c = pow(bytes_to_long(CBC_key), 65537, n)

print('n =', n)
print('h =', hint)
print('c =', c)

'''
n = 104765768221225848380273603921218042896496091723683489832860494733817042387427987244507704052637674086899990536096984680534816330245712225302233334574349506189442333792630084535988347790345154447062755551340749218034086168589615547612330724516560147636445207363257849894676399157463355106007051823518400959497
h = 7203581190271819534576999256270240265858103390821370416379729376339409213191307296184376071456158994788217095325108037303267364174843305521536186849697944281211331950784736288318928189952361923036335642517461830877284034872063160219932835448208223363251605926402262620849157639653619475171619832019229733872640947057355464330411604345531944267500361035919621717525840267577958327357608976854255222991975382510311241178822169596614192650544883130279553265361702184320269130307457859444687753108345652674084307125199795884106515943296997989031669214605935426245922567625294388093837315021593478776527614942368270286385
c = 86362463246536854074326339688321361763048758911466531912202673672708237653371439192187048224837915338789792530365728395528053853409289475258767985600884209642922711705487919620655525967504514849941809227844374505134264182900183853244590113062802667305254224702526621210482746686566770681208335492189720633162
'''

$$h\equiv 3^{2022}p^2+5^{2022}q^2\mod N\\ 5^{-2022}h\equiv 3^{2022}*5^{-2022}p^2+q^2\mod N\\$$

$$D=2^{1024}\\ \left[\begin{matrix}-k&p^2&q^2&1\end{matrix}\right] \left[\begin{matrix} DN&0&0&0\\D3^{2022}&1&0&0\\D5^{2022}&0&1&0\\Dh&0&0&D \end{matrix}\right]= \left[\begin{matrix}0&p^2&q^2&D\end{matrix}\right]$$

格约化后如下，鸡块师傅说要爆线性组合，将有用的一、二、四向量通过线性关系组合在一起，使得向量满足右侧的$0,p^2,q^2,D$，第四组向量最后一个值就是$D$，那么将一、二向量线性后与四相加即可，发现当取0,-1,1组合时，刚好第二个值与n取gcd不是1，那么就能得到p,q

$$\begin{matrix}[p^2&-1&-k]\end{matrix} \left[\begin{matrix}1&0&3^{2022}5^{-2022}\\0&1&5^{-2022}h\\0&0&N \end{matrix}\right]=\begin{matrix}[p^2&-1&q^2]\end{matrix}$$

$det\approx\frac{2048}{3}\approx 683$，$\omega\approx 1024$，接着就是配平，就结果而言与上题无异，也需要进行线性组合，因为右侧有个$D$，可以判断第三个向量只要相加一次

$$D=2^{1024}\\ \left[\begin{matrix}1&0&3^{2022}5^{-2022}\\0&D&5^{-2022}h\\0&0&N \end{matrix}\right]$$

from Crypto.Util.number import *
from gmpy2 import iroot
n = 10476576822122584838027360392121804289649609172368348983286049473381704238742798724450770405263767408689999053
609698468053481633024571222530223333457434950618944233379263008453598834779034515444706275555134074921803408616858
9615547612330724516560147636445207363257849894676399157463355106007051823518400959497
h = 72035811902718195345769992562702402658581033908213704163797293763394092131913072961843760714561589947882170953
251080373032673641748433055215361868496979442812113319507847362883189281899523619230363356425174618308772840348720
631602199328354482082233632516059264022626208491576396536194751716198320192297338726409470573554643304116043455319
442675003610359196217175258402675779583273576089768542552229919753825103112411788221695966141926505448831302795532
653617021843202691303074578594446877531083456526740843071251997958841065159432969979890316692146059354262459225676
25294388093837315021593478776527614942368270286385
N = n**2+2024
a = int(pow(3, 2022, N))
b = int(pow(5, 2022, N))
t = inverse(b, N)
D = 2**1024
L = matrix([[1, 0, a*t], [0, D, t*h], [0, 0, N]])

tmp = L.LLL()

for i in range(-100, 100):
    for j in range(-100, 100):
        t = i*tmp[0]+j*tmp[1]+tmp[2]
        if iroot(abs(t[0]), 2)[1]:
            print(t[0])
            break