江苏省领航杯2023

RSA2

题面：

from Crypto.Util.number import*
import random
from gmpy2 import gcd ,invert
import os,random
from functools import reduce
flag = 'flag{*****}'
nbit = 2048
pbit = 658
qbit = nbit-pbit

def GCRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c / d * invert(curm / d, m / d)
        cura += curm * K
        curm = curm * m / d
    return (cura % curm, curm)

def genkey():
    p = getPrime(pbit)
    q = getPrime(qbit)
    assert(gcd(p-1,(q-1)//2) != 1 and q >= int(pow(p*q,qbit//nbit)))
    n = p*q
    while 1:
        dp,dq = random.getrandbits(50), getPrime(50)
        d = GCRT([p-1,q-1],[dp,dq])[0]
        if(gcd(d, (p-1)*(q-1)) == 1):
            break
    e = invert(d,(p-1) * (q-1))
    return n,e

n,e= genkey()

flag = flag + os.urandom(40)

flag = bytes_to_long(flag)
assert(flag<n)
print n
#24520888125100345615044288264230762903878924272518571342713995342063192899124989891699091460914318368533612522321639660343147487234147817765379565866063142022911783047710228071012334390251457138278189863078398353697056081286846816500611712981402958876560909958985941278622099006464269427107124576069124593580390423932176305639686809675964840679026457045269910781753881177055233058940084858058581167930068081780478893848660425039669034700316924547379360271738374641525963541506226468912132334624110432284070298157810487695608530792082901545749959813831607311669250447276755584806773237811351439714525063949561215550447
print e
#11548167381567878954504039302995879760887384446160403678508673015926195316468675715911159300590761428446214638046840120602736300464514722774979925843178572277878822181099753174300465194145931556418080206026501299370963578262848611390583954955739032904548821443452579845787053497638128869038124506082956880448426261524733275521093477566421849134936014202472024600125629690903426235360356780817248587939756911284609010060687156927329496321413981116298392504514093379768896049697560475240887866765045884356249775891064190431436570827123388038801414013274666867432944085999838452709199063561463786334483612953109675470299
print pow(flag,e,n)
#7903942109284616971177039757063852086984176476936099228234294937286044560458869922921692962367056335407203285911162833729143727236259599183118544731181209893499971239166798975272362502847869401536913310597050934868114362409772188138668288760287305966467890063175096408668396691058313701210130473560756912616590509776003076415730640467731466851294845080825312579944440742910769345079740436037310725065646739277834041891837233390010487460412084089630786396822488869754420904734966722826157548254882580507819654527378643632759059506306290252851428488883937359516531613654502801727220504711666666550673928496325962262842

分析：

3-540-45708-9_16.pdf

此处参考了la佬的：给定N，e，c，其中dp过小

题目给定的q_bit=658,n_bit=2048
$$
q_{bit}=658,N_{bit}=2048\
则\frac{q_{bit}}{N_{bit}}=0.32<0.38
$$

$$
参数\beta=\frac{q_{bit}}{N_{bit}},\delta=\frac{dp_{bit}}{N_{bit}}\
满足3\beta<1+\beta^2+2\delta,可以确定 \beta和\delta的值\
$$

$$
构造格的维度为n，格中的模数N的最大次幂为m，应满足关系： \
\frac{m(m+1)}{2}+\frac{n(n-1)(2\delta+\beta)}{2}-(1-\beta)nm<0
$$

$$
确定\beta和\delta之后，可枚举确定n和m的取值(最小值)，m=(1-\beta)n是一个较优的取值
$$

先给出求格维度的脚本：

from Crypto.Util.number import *

qbit = 658
nbit = 2048
dpbit = 50

beta = qbit/nbit
delta = dpbit/nbit
print(beta,delta)
n = round((1-2*beta-2*delta)/((1-beta)**2-2*delta-beta),6)
print(n)

得到了维度n=3.408695，但是测试发现大于5之后才能得到想要的结果

然后用la佬的脚本：

#sage
N=24520888125100345615044288264230762903878924272518571342713995342063192899124989891699091460914318368533612522321639660343147487234147817765379565866063142022911783047710228071012334390251457138278189863078398353697056081286846816500611712981402958876560909958985941278622099006464269427107124576069124593580390423932176305639686809675964840679026457045269910781753881177055233058940084858058581167930068081780478893848660425039669034700316924547379360271738374641525963541506226468912132334624110432284070298157810487695608530792082901545749959813831607311669250447276755584806773237811351439714525063949561215550447
e=11548167381567878954504039302995879760887384446160403678508673015926195316468675715911159300590761428446214638046840120602736300464514722774979925843178572277878822181099753174300465194145931556418080206026501299370963578262848611390583954955739032904548821443452579845787053497638128869038124506082956880448426261524733275521093477566421849134936014202472024600125629690903426235360356780817248587939756911284609010060687156927329496321413981116298392504514093379768896049697560475240887866765045884356249775891064190431436570827123388038801414013274666867432944085999838452709199063561463786334483612953109675470299

n = 5			    # 或n=5+
beta = 0.32			# beta = 0.3212890625
delta = 0.02		# delta = 0.0244140625

X = int(N ** delta*(n+1)/2)
Y = int(N ** (delta + beta)*(n+1)/2)

def C(a,b):
    ret=1
    for i in range(b):
        ret*=(a-i)
        ret/=(b-i)
    return ret
def get_Matrix(n,m):
    MM=[[0 for __ in range(n)] for _ in range(n)]
    for j in range(n): 
        pN=max(0,m-j)
        for i in range(j+1):
            MM[j][i]=pow(N,pN)*pow(X,n-i-1)*pow(Y,i)*pow(e,j-i)*C(j,i)*pow(-1,i)
    MM=Matrix(ZZ,MM)
    return MM

M=get_Matrix(n,n//2+1)
L=M.LLL()[0]

x,y = var('x'),var('y')
f=0
for i in range(n):
    f+=x**(n-i-1) * y**i * (L[i] // pow(X,n-i-1) // pow(Y,i))#将x,y参数化

print(f.factor())

从后往前是dp , k-1

603601239605461619719962824215850028370828276194986402520006784945171666555162381560306067089554862768237542295127706223128204911327713581268000464342787657534895446276895456449104343518846054862311913534953258511*x + 1115967702502739*y

用下面的式子求p

题解：

from Crypto.Util.number import *
from gmpy2 import *
dp = 1115967702502739
k = 603601239605461619719962824215850028370828276194986402520006784945171666555162381560306067089554862768237542295127706223128204911327713581268000464342787657534895446276895456449104343518846054862311913534953258511
n = 24520888125100345615044288264230762903878924272518571342713995342063192899124989891699091460914318368533612522321639660343147487234147817765379565866063142022911783047710228071012334390251457138278189863078398353697056081286846816500611712981402958876560909958985941278622099006464269427107124576069124593580390423932176305639686809675964840679026457045269910781753881177055233058940084858058581167930068081780478893848660425039669034700316924547379360271738374641525963541506226468912132334624110432284070298157810487695608530792082901545749959813831607311669250447276755584806773237811351439714525063949561215550447
e=11548167381567878954504039302995879760887384446160403678508673015926195316468675715911159300590761428446214638046840120602736300464514722774979925843178572277878822181099753174300465194145931556418080206026501299370963578262848611390583954955739032904548821443452579845787053497638128869038124506082956880448426261524733275521093477566421849134936014202472024600125629690903426235360356780817248587939756911284609010060687156927329496321413981116298392504514093379768896049697560475240887866765045884356249775891064190431436570827123388038801414013274666867432944085999838452709199063561463786334483612953109675470299
c = 7903942109284616971177039757063852086984176476936099228234294937286044560458869922921692962367056335407203285911162833729143727236259599183118544731181209893499971239166798975272362502847869401536913310597050934868114362409772188138668288760287305966467890063175096408668396691058313701210130473560756912616590509776003076415730640467731466851294845080825312579944440742910769345079740436037310725065646739277834041891837233390010487460412084089630786396822488869754420904734966722826157548254882580507819654527378643632759059506306290252851428488883937359516531613654502801727220504711666666550673928496325962262842

RSA3

题面：

from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p1, q1 = getPrime(512), getPrime(512)
n1 = p1*q1
e = 65537

p2, q2 = getPrime(512), getPrime(512)
n2 = p2*q2

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {pow(m,e,n2)}')
print(f'c2 = {pow(n1-m,e,n2)}')

# n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
# n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
# c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
# c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

分析：

很明显是Franklin-Reiter相关信息攻击，但是此处的e比较大，所以考虑用Half-GCD解

pgcd(f1,f2)返回的是ax-bM，a,b代表任意数字

用monic()使得上式变为x-M，再提取出M

题解：

from Crypto.Util.number import *
import sys

def pdivmod(u, v):
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    x = u.parent().gen()
    if u.degree() < v.degree():
        u, v = v, u
    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])
    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)
    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)
    g0 = e // x^(m//2)
    g1 = f // x^(m//2)
    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    if u.degree() < v.degree():
        u, v = v, u
    if v == 0:
        return u
    if u % v == 0:
        return v
    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u
    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1
    return pgcd(b1, r)

sys.setrecursionlimit(500000)

e = 65537
n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

PR.<x> = PolynomialRing(Zmod(n2))
f1 = x^e - c1
f2 = (n1-x)^e - c2

res = pgcd(f1, f2)

m = -res.monic().coefficients()[0]
print(long_to_bytes(int(m)))

RSA4

题面：

from Crypto.Util.number import *
from os import *
from secret import flag

assert len(flag) <= 35

m = bytes_to_long(flag)
t = getPrime(32)
p = getPrime(512)
q = getPrime(512)
n = p * q
hint = ((t+q)**4+(t+q)**3+(t+q)**2+(t+q)+2023) % n

r = 11779674470989201650533406519886591289516202072957618550910646323186300227953911

c = pow(t,m,r)

print(c)
print(n)
print(hint)

# 6580860405834148836110773014414875358234621644983930335529135801623195480368832
# 139415227833650606627481949032630333904915784502498383402775795770352459104117035911044614539656661779065034631025979910419387363425628162982061251276669112098757186870838748231794731153245273066810769109396532311364451556967782895742561287251234088360088678874714586399626016737310602036235187097500522638791
# 43691909620514553907337084747877613125770180914725560231672822190047048268654323014909857087117101555550872581680976037673609645072816688179430921113411189775681186282652913102207473404267361338845128228750191128828347979058211793191911795538917687509092140331114867217314732225741963090158157118956958361667

分析：

$$
hint = ((t+q)^4+(t+q)^3+(t+q)^2+(t+q)+2023) % n
$$
直接二项式展开得到：
$$
hint = t^4+t^3+t^2+t+2023+Poly(p)\ mod\ n
$$
在Coppersmith下，由于在模n的行为下，p是n的素因子，那么就会把含p的多项式都模掉
$$
Poly(p)\ =0\ mod\ n
$$

$$
hint=(t^4+t^3+t^2+t+2023)\ mod\ n
$$

对于：
$$
c≡t^m\ mod\ r
$$
这里注意题目条件：
$$
len(flag)\leq35,\therefore m\leq2^{280}\
但是r.bit_length()只有257\
c≡t^m\ mod\ r \ \ ->\ \ c≡(c×1)\ mod\ r\ \ ->c≡t^{m’} × t^{k\phi®}\ mod\ r\
所以m=m’+k×\phi®
$$
不过发现一直爆破不出来

猜测：
$$
因为\phi®=r-1 有很多因子，\phi ®可能不是t模r的阶，遍历所有因子，发现存在使得t^a≡1\ mod\ r\
发现因子有2,17,则a=\frac{r-1}{2}和a=\frac{r-1}{17}\
所以t模r的阶为\frac{r-1}{34}, 记为\phi’®\
这个满足t^{\phi’®}≡1\ mod\ r\
尝试m=m’+k×\phi’®,k的大小在(280-257)=23,那就大约22bit左右
$$

题解：

from Crypto.Util.number import *

c = 6580860405834148836110773014414875358234621644983930335529135801623195480368832
n = 139415227833650606627481949032630333904915784502498383402775795770352459104117035911044614539656661779065034631025979910419387363425628162982061251276669112098757186870838748231794731153245273066810769109396532311364451556967782895742561287251234088360088678874714586399626016737310602036235187097500522638791
hint = 43691909620514553907337084747877613125770180914725560231672822190047048268654323014909857087117101555550872581680976037673609645072816688179430921113411189775681186282652913102207473404267361338845128228750191128828347979058211793191911795538917687509092140331114867217314732225741963090158157118956958361667

r = 11779674470989201650533406519886591289516202072957618550910646323186300227953911

R.<x> = PolynomialRing(Zmod(n))
f = x^4+x^3+x^2+x+2023-hint
t  = f.small_roots(X = 2^32,beta = 0.4)[0]
#print(t)
t = 4000655279

m = discrete_log(mod(c,r),mod(t,r))
print(int(m).bit_length())

order = []
for i in factor(r-1):
    if pow(t,(r-1)//i[0],r) == 1:
        order.append(i[0])
print(order)
    
phi = (r-1)//reduce(lambda x,y: x*y,order)
for k in range(2^23):
    temp = m + k*phi
    flag = long_to_bytes(temp)
    try:
        if len(flag.decode()) <= 35:
            print(flag.decode())
            break
    except:
        continue