2023江苏省领航杯(部分CRYPTO题目复现)

发布时间 2023-10-26 15:50:25作者: Kicky_Mu

?决赛

回文

1、题目信息

=QfzEDO4YDNlBzN4gzN0YGM1QzYyUGZ3QDZzgDM7V2Sn52bI52Q=

2、解题方法

base64解码,两种思路:

要么是去掉前面=号解码

QfzEDO4YDNlBzN4gzN0YGM1QzYyUGZ3QDZzgDM7V2Sn52bI52Q=

要么去掉后面=号再翻转一下解码

Q25Ib25nS2V7MDgzZDQ3ZGUyYzQ1MGY0Nzg4NzBlNDY4ODEzfQ=

显然试过后发现第二种是对的

CnHongKe{083d47de2c450f478870e468813}

RSA2

1、题目信息

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

2、解题方法

这个题还是很难的,从大佬那里学到的方法。。。。

首先观察d的产生方式,而且发现p,q相差很大,因此想到Cryptanalysis of Unbalanced RSA with Small CRT-Exponent

这里讲了公私钥的产生方式,有个疑惑的点是论文里说了p-1和(q-1)/2must be coprime(互素),但是题目附件中

不是这样的。why?

然后网上搜索一番后找到了lazzzaro大神的脚本:https://lazzzaro.github.io/2020/05/06/crypto-RSA/index.html

#sage
N=
e=

n = 12			    # 或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())

参数beta

参数delta

参数n:n为格子的维度,大佬用下面的式子计算出n,对于本题来说,求得的n=3.408695

但是实际用脚本的过程中,发现n=4并不能得到想要的结果,n=5可能是一个最低值

beta = 
delta = 
n = round((1-2*beta-2*delta)/((1-beta)^2-2*delta-beta),6)
m = (1-beta)*n
print(m,n)

结果得到:

...(603601239605461619719962824215850028370828276194986402520006784945171666555162381560306067089554862768237542295127706223128204911327713581268000464342787657534895446276895456449104343518846054862311913534953258511*x + 1115967702502739*y)

从后往前, 第一个是dp,第二个是k

然后利用这两个式子求p

exp:

from Crypto.Util.number import *
import gmpy2

k = 603601239605461619719962824215850028370828276194986402520006784945171666555162381560306067089554862768237542295127706223128204911327713581268000464342787657534895446276895456449104343518846054862311913534953258511
dp = 1115967702502739
n = 24520888125100345615044288264230762903878924272518571342713995342063192899124989891699091460914318368533612522321639660343147487234147817765379565866063142022911783047710228071012334390251457138278189863078398353697056081286846816500611712981402958876560909958985941278622099006464269427107124576069124593580390423932176305639686809675964840679026457045269910781753881177055233058940084858058581167930068081780478893848660425039669034700316924547379360271738374641525963541506226468912132334624110432284070298157810487695608530792082901545749959813831607311669250447276755584806773237811351439714525063949561215550447
e = 11548167381567878954504039302995879760887384446160403678508673015926195316468675715911159300590761428446214638046840120602736300464514722774979925843178572277878822181099753174300465194145931556418080206026501299370963578262848611390583954955739032904548821443452579845787053497638128869038124506082956880448426261524733275521093477566421849134936014202472024600125629690903426235360356780817248587939756911284609010060687156927329496321413981116298392504514093379768896049697560475240887866765045884356249775891064190431436570827123388038801414013274666867432944085999838452709199063561463786334483612953109675470299
c = 7903942109284616971177039757063852086984176476936099228234294937286044560458869922921692962367056335407203285911162833729143727236259599183118544731181209893499971239166798975272362502847869401536913310597050934868114362409772188138668288760287305966467890063175096408668396691058313701210130473560756912616590509776003076415730640467731466851294845080825312579944440742910769345079740436037310725065646739277834041891837233390010487460412084089630786396822488869754420904734966722826157548254882580507819654527378643632759059506306290252851428488883937359516531613654502801727220504711666666550673928496325962262842

k = k + 1
p = (e * dp - 1) // k + 1
print(int(p).bit_length())
q = n // p
print(int(q).bit_length())
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))
#CnHongKe{1b35037a-a472-4e9c-bdba-768f7e84dd0e}

根据

但是,这题不知道为什么k要加上1

总之,理解不太透彻,只能存下脚本了。。。

RSA3

1、题目信息

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

2、解题方法

e太大了,对于Franklin攻击来说要跑很久,看到大佬WP后了解需要用到 half-gcd

参考文章:

HALF-GCD算法的阐述

多项式 gcd 的正确姿势:Half-GCD 算法

脚本来源:

https://github.com/rkm0959/rkm0959_implements/blob/main/Half_GCD/code.sage

exp:

from Crypto.Util.number import *
import sys

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)

e = 65537
n1 = 
n2 = 
c1 = 
c2 = 
R.<x> = PolynomialRing(Zmod(n2))
f = x^e - c1
g = (n1 - x)^e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)
#CnHongKe{Fr4nkl1n_R31ter_4nd_gcD}

GCD(f,g)返回ax-bM,a,b代表任意数字

monic()使得上式变为x-M,再提取 M

RSA4

1、题目信息

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

2、解题方法

展开后发现

在Coppersmith下模n,会把q全部模完,所以可以直接求出t

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

发现m一直出不来

接着就是爆破k

exp:

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
res = f.small_roots(X=2^32,beta=0.4)
# print(res)
t = res[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)
# [2, 17]
phi = (r - 1) // 34
for k in range(2^22):
    temp = m + k*phi
    flag = long_to_bytes(temp)
    try:
        if len(flag.decode()) <= 35:
            print(flag)
            break
    except:
        continue
# CnHongKe{cp_smith_with_pollard_p-1}

?复赛

asr

1、题目信息

from Crypto.Util.number import *              
from secret import flag              
           
def genprime():              
    while True:              
        r = getRandomNBitInteger(64)              
        p = r**6 + 8*r**4 - 41*r**3 + 14*r**2 - 116*r + 31387              
        q = r**5 - 9*r**4 + 17*r**3 - 311*r**2 - 16*r + 14029              
        if isPrime(p) and isPrime(q):              
            return p, q              
def enc(flag, n):              
    m = bytes_to_long(flag)              
    return pow(m, 31387, n)              



p, q = genprime()              
n = p * q              
c = enc(flag, n)              
print(n)              
print(c)

2、解题方法

把n开11次方,得到的r'会略大于或者略小于r

爆破一下

exp:

from Crypto.Util.number import *
import gmpy2 

n = 73553176031506251642448229714220151174734540964434813056145000616720019024269982417494553771890010861489245572362590935764438928110836109730139595790550323300572059713433794357690270439325805603980903813396260703                
c = 6035303231100318215656164353047198868742763055193754611914191674005776329646395050293747516587004104241717689072827492745628156828285466831779549229513115371571798719567117034735830671759951028004405762435531685                
e = 31387          

r = gmpy2.iroot(n,11)[0]                
for i in range(100000):                
    p = r**6 + 8*r**4 - 41*r**3 + 14*r**2 - 116*r + 31387                
    q = r**5 - 9*r**4 + 17*r**3 - 311*r**2 - 16*r + 14029                
    r = r+1          
    if isPrime(p) and isPrime(q) and n==p*q:                
        print(p)
        q = n // p
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))   
        break                          
# b'CnHongKe{m0re_fuN_RSA!!!}'

结果发现,只需要r+1就行了

脚本来源:2023 江苏领航杯

ezrsa

1、题目信息

from Crypto.Util.number import *              
from gmpy2 import invert              
#from secret import flag,e              
e=11299              
flag="CnHongKe{xxxxx}"              
           
def enc(key, p):              
    e, n = key              
    cipher = [pow(ord(char), e, n) for char in p]              
    return cipher              
def dec(pk, c):              
    key, n = pk              
    plain = [chr(pow(char, key, n)) for char in c]              
    return ''.join(plain)              
p = getPrime(512)              
q = getPrime(512)              
n = p*q              
pubkey = (e,n)              

assert(e < 20000)              
print("Public key:")              
print(pubkey[1])              
cipher = (enc(pubkey, flag))              
           
print("Encrypted flag:")              
print(cipher)

"""
n = 72247494519029483967034760366376786853061601103300157813759661775953565912596351092287547406601293830981872918918938736057259213906558022493243888210973589378711150746378675386713286364059548872717761789465830532496818860955952848759604076974545518597370294034234115061042965941759696027120414108241913315823 
c = [23086568633766027889700149282556028601873588133389538577048220777519629053893020835596785887647597774272630671514043075789089166339490664485821551265008072526985961605709337174865785620861795518368806256695564549352791382917399957127324333828822855864895189216581775972150143373812919138450624070271563605781, 61424780590998716668669522879005833894226611068988736111090847848564952203683192799647992306556603909310758923465682857752771528865725336620979965796403804180726836508128298963907214867637490978049881021200499605597084724400813056262536028860369819412653602159130062278358850923752212354694875260742761085298, 48972347185727309580275811398968322398732292284718613286033964656750569533816676490768122129969818200823106363038086076716848785261859085349544695714346759435389253954398744742706972731080540025437559712419376172012608552755595256980994587437212314607911439680754158685958213442852345610886117149808132016667, 61900034054386621130587335874165191153789670659043111868368913383427388843553828977951515166753531254554889530123861241679942156133394477844988559568261609121966239636746106844585498882352452796587012169345091313195906669668187972481122815780919799898784783071380231308771760678158462462371463688337980966056, 61424780590998716668669522879005833894226611068988736111090847848564952203683192799647992306556603909310758923465682857752771528865725336620979965796403804180726836508128298963907214867637490978049881021200499605597084724400813056262536028860369819412653602159130062278358850923752212354694875260742761085298, 9450415868171579852265098054119152648200942770623210086786809222084784959844945630371248180007508011953947300816820109987312423346559505226253550792399518771112488858163511513111841198409634670818742944088825363946933893952656072580401498319136121912520261916028145167846733858193149171599064970439268199783, 10035734578627344969947375235594072983851319696847209997368331158831147669149961069031833471519627366504594153020437204571060611428623914456969214997923532068856482468179965518854707629794312716955250557912419773434419097161023559262564458848063915219346903480654597328232422644596377103117825829328614075690, 5651041338136387965270707005514495599960051787842260459297309665876049923224924292148523058126335232362070965833156272480917510429785778533039914573874120321092901286353688478193761623313802721160582545556066963078690764669931722358118104123077318311422846797054759255064946480668759913078778113387444436772, 14271259146328702790695772784067429851163342737347538777950741762508946650827944617931146968866218980425939274541815935964077603794848153188731356254177631333208035026728310408767228380734867744475231330055609453484352384922899766458129175972076865172633564831188088602907146780176603278159798710852150155253, 62406194652765011605245085350409728452067228284594736543030951188813141827047471129688563874017873401654027493958313799538667190622125421268982329762449606129199279688989354341511243792985075002044026442461088633434402762089223231979549393979184803396697173744411798858018768084174805247172995100258785744206, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 565104133813638796527070700551449559996005178784226045,                
9297309665876049923224924292148523058126335232362070965833156272480917510429785778533039914573874120321092901286353688478193761623313802721160582545556066963078690764669931722358118104123077318311422846797054759255064946480668759913078778113387444436772, 3956140276099962408524811644378665260926195324627931125735919417604617330787900581903522720016806707086965650313838135840992580442876605474811383818108244966337270671303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 26352444581944643830963227423429946980811236174292159142870560906116668786800921081108266494217634934060542948019867625299869944900083383044563948756655507024025376518773098977036898176798319228360435941463124583821154981070698271384027340432620539761424919238056654209894138660851835259359180413998571510866, 40143952866342512113851528831224840428508359508863486720333430314639020044892359484055175960350878532212164045297142804890441825145732613460997839927190176844605217276182528040788352071676527553305037569493706223713078036314819975031692707790811142576347096406283580538840499698900522007082050790381461432333, 3956140276099962408524811644378665260926195324627931125735919417604617330787900581903522720016806707086965650313838135840992580442876605474811383818108244966337270671303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 48888685774691755361314428123012470903274435407919121739086146641066936108772671897622273617773466901370666579985825990735116909193505734002962914749300893402294987407241465624548368394059300582991374404299605248595530416820237532082552535859877438232561386581747696852665114096889765422722443550622873560905, 48888685774691755361314428123012470903274435407919121739086146641066936108772671897622273617773466901370666579985825990735116909193505734002962914749300893402294987407241465624548368394059300582991374404299605248595530416820237532082552535859877438232561386581747696852665114096889765422722443550622873560905, 38583572018907364214647900005166742548285199585572254326541125387795789224923544225334386246655335740938100752554849888600258201438026409196139322439518308323982209353504064739859448757230608480631399883893401220790226127149746215151900805996489931009866529965548635227695192170717058032494324346363053930619, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 39561402760999624085248116443786652609261953246279311257359194176046173307879005819035227200168067070869656503,                
13838135840992580442876605474811383818108244966337270671303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 5651041338136387965270707005514495599960051787842260459297309665876049923224924292148523058126335232362070965833156272480917510429785778533039914573874120321092901286353688478193761623313802721160582545556066963078690764669931722358118104123077318311422846797054759255064946480668759913078778113387444436772, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 21643731734484252696109953515687478013118937715056061520976924340371395968660338303624558633862679263768843575243426341986847599097591917653435606042602095144570247241757302533523905744626606836773661026140082883368820615972739914083417816255913686820936373857254933361629603081613492930030281179652207492149, 48888685774691755361314428123012470903274435407919121739086146641066936108772671897622273617773466901370666579985825990735116909193505734002962914749300893402294987407241465624548368394059300582991374404299605248595530416820237532082552535859877438232561386581747696852665114096889765422722443550622873560905, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 40143952866342512113851528831224840428508359508863486720333430314639020044892359484055175960350878532212164045297142804890441825145732613460997839927190176844605217276182528040788352071676527553305037569493706223713078036314819975031692707790811142576347096406283580538840499698900522007082050790381461432333, 40143952866342512113851528831224840428508359508863486720333430314639020044892359484055175960350878532212164045297142804890441825145732613460997839927190176844605217276182528040788352071676527553305037569493706223713078036314819975031692707790811142576347096406283580538840499698900522007082050790381461432333, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 395614027609996240852481164437866526092619532462793112573591941760461733078790058190352272001680670708696565031383813584099258044287660547481138381810824496633727067,                
1303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 20593313344992264722474643208232460904729585942331327945281307002575544045487870568637031063784433406096326172788745559326479291854636106027597680333110098010128235038952685620360851399518780967171732233524825381055879695801401425059095441692301391956163400460584139637380367489591078077440142620116997434358] 
"""

2、解题方法

直接爆破

exp:

e = 11299
n =  
c = [...]
flag = ''
for j in range(len(c)):
    for i in range(32,128):
        if pow(i,e,n) == c[j]:
            flag += chr(i)
            print(flag)
#CnHongKe{a8cc755d375811f55cec82153388c}

prng

1、题目信息

from Crypto.Util.number import *              
from secret import flag              
import random              
              
def base(n, l):              
    bb = []              
    while n > 0:              
        n, r = divmod(n, l)              
        bb.append(r)              
    return ''.join(str(d) for d in bb[::-1])              
              
def prng(secret):                
    seed = base(secret, 5)              
    seed = [int(i) for i in list(seed)]              
    length = len(seed)              
    R = [[ random.randint(0,4) for _ in range(length)] for _ in range(length*2)]              
    S = []              
    for r in R:              
        s = 0              
        for index in range(length):              
            s += (r[index] * seed[index]) % 5              
        s %= 5              
        S.append(s)              
    return R, S              
        
m = bytes_to_long(flag)              
R, S = prng(m)              

with open('output.txt', 'w') as f:              
    f.write(f'R = {R}\nS = {S}')

2、解题方法

divmod(n,l)返回(n // l,n % l)

base(n,l)就是把n,写成l进制

分析代码知道

上面代码自己生成数据

GF(5)下解这个矩阵方程

exp:

#sage
from Crypto.Util.number import *

R = [[] , ... , []]
S = []

r = Matrix(GF(5),R)
s = vector(GF(5),S)
seed = r.solve_right(s)
m = list(seed)
flag = ""
# flag="".join(map(str,m))

for i in m:
    flag += str(i)
    
flag = long_to_bytes(int(flag,5))
print(flag)
# CnHongKe{l1ne4r_prng_1s_d4ngr0s~~!d9uxdj9223}

bd

1、题目信息

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

p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(299)
e = inverse(d,(p-1)*(q-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
hint1 = p >> (512-70)
hint2 = q >> (512-70)


print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")

"""
n = 73337798113265277242402875272164983073482378701520700321577706460042584510776095519204866950129951930143711572581533177043149866218358557626070702546982947219557280493881836314492046745063916644418320245218549690820002504737756133747743286301499039227014032044403571945455215839074583290324966069724343874361
e = 42681919079074901709680276679968298324860328305878264036188155781983964226653746568102282190906458519960811259171162918944726137301701132135900454469634110653076655027353831375989861927565774719655974876907429954299669710134188543166679161864800926130527741511760447090995444554722545165685959110788876766283
c = 35616516401097721876690503261383371143934066789806504179229622323608172352486702183654617788750099596415052166506074598646146147151595929618406796332682042252530491640781065608144381326123387506000855818316664510273026302748073274714692374375426255513608075674924804166600192903250052744024508330641045908599
hint1 = 740477612377832718425
hint2 = 767891335159501447918
"""

2、解题方法

根据大佬师傅WP,需要利用上高位的boneh_durfee攻击

参考论文:https://eprint.iacr.org/2023/367.pdf

他们实验时的脚本:https://pastebin.com/zpUkrfDh

论文中提到:

对于1024bit的模,当m = 7, t = 3的时候,至少需要27位p的高位,才能成功

exp:

import time
time.clock = time.time
 
debug = True
 
strict = False
 
helpful_only = True
dimension_min = 7 # 如果晶格达到该尺寸,则停止移除
# 显示有用矢量的统计数据
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1
 
	print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# 显示带有 0 和 X 的矩阵
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60: 
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        #print (a)

# 尝试删除无用的向量
# 从当前 = n-1(最后一个向量)开始
def remove_unhelpful(BB, monomials, bound, current):
    # 我们从当前 = n-1(最后一个向量)开始
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB
 
    # 开始从后面检查
    for ii in range(current, -1, -1):
        #  如果它没有用
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
             # 让我们检查它是否影响其他向量
            for jj in range(ii + 1, BB.dimensions()[0]):
                # 如果另一个向量受到影响:
                # 我们增加计数
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj
 
            # 等级:0
            # 如果没有其他载体最终受到影响
            # 我们删除它
            if affected_vectors == 0:
                #print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB
 
           # 等级:1
            #如果只有一个受到影响,我们会检查
            # 如果它正在影响别的向量
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # 如果它影响哪怕一个向量
                    # 我们放弃这个
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # 如果没有其他向量受到影响,则将其删除,并且
                # 这个有用的向量不够有用
                #与我们无用的相比
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    #print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB
 
""" 
Returns:
* 0,0   if it fails
* -1,-1 如果 "strict=true",并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
 
 在以下情况下找到解决方案:
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 delta < 1 - sqrt(2)/2 ~ 0.292
    """
 
    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)   #多项式环
    Q = PR.quotient(x*y + 1 - u)        #  u = xy + 1
    polZ = Q(pol).lift()
 
    UU = XX*YY + 1
 
    # x-移位
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()
 
    # 单项式 x 移位列表
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式():
            if monomial not in monomials:  # 如果单项不在单项中
                monomials.append(monomial)
    monomials.sort()
 
    # y-移位
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
 
    # 单项式 y 移位列表
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)
 
    # 构造格 B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
 
    #约化格的原型
    if helpful_only:
        #  #自动删除
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # 重置维度
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0
 
    # 检查向量是否有帮助
    if debug:
        helpful_vectors(BB, modulus^mm)
 
    # 检查行列式是否正确界定
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print ("We do not have det < bound. Solutions might not be found.")
        print ("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
 
    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)
 
    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")
 
    #BB = BB.BKZ(block_size=25)
    BB = BB.LLL()
 
    if debug:
        print ("LLL is done!")
 
    # 替换向量 i 和 j ->多项式 1 和 2
    if debug:
        print ("在格中寻找线性无关向量")
    found_polynomials = False
 
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
 
            # 对于i and j, 构造两个多项式
 
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
 
            # 结果
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
 
 
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print ("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
 
    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
 
    rr = rr(q, q)
 
    # solutions
    soly = rr.roots()
 
    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0
 
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
    return solx, soly
 
def example():
    ############################################
    # 随机生成数据
    ##########################################
    #start_time =time.perf_counter
    start =time.clock()
    size=512
    length_N = 2*size;
    ss=0
    s=70;
    M=1   # the number of experiments
    delta = 299/1024
    # p =  random_prime(2^512,2^511)
    for i in range(M):
#         p =  random_prime(2^size,None,2^(size-1))
#         q =  random_prime(2^size,None,2^(size-1))
#         if(p<q):
#             temp=p
#             p=q
#             q=temp
        N = 
        e = 
        c = 
        hint1 =   # p高位
        hint2 =   # q高位
#         print ("p真实高",s,"比特:", int(p/2^(512-s)))
#         print ("q真实高",s,"比特:", int(q/2^(512-s)))
 
#         N = p*q;
 
 
    # 解密指数d的指数( 最大0.292)
 
 
 
        m = 7   # 格大小(越大越好/越慢)
        t = round(((1-2*delta) * m))  # 来自 Herrmann 和 May 的优化
        X = floor(N^delta)  # 
        Y = floor(N^(1/2)/2^s)    # 如果 p、 q 大小相同,则正确
        for l in range(int(hint1),int(hint1)+1):
            print('\n\n\n l=',l)
            pM=l;
            p0=pM*2^(size-s)+2^(size-s)-1;
            q0=N/p0;
            qM=int(q0/2^(size-s))
            A = N + 1-pM*2^(size-s)-qM*2^(size-s);
        #A = N+1
            P.<x,y> = PolynomialRing(ZZ)
            pol = 1 + x * (A + y)  #构建的方程
 
            # Checking bounds
            #if debug:
                #print ("=== 核对数据 ===")
                #print ("* delta:", delta)
                #print ("* delta < 0.292", delta < 0.292)
                #print ("* size of e:", ceil(log(e)/log(2)))  # e的bit数
                # print ("* size of N:", len(bin(N)))          # N的bit数
                #print ("* size of N:", ceil(log(N)/log(2)))  # N的bit数
                #print ("* m:", m, ", t:", t)
 
            # boneh_durfee
            if debug:
                ##print ("=== running algorithm ===")
                start_time = time.time()
 
 
            solx, soly = boneh_durfee(pol, e, m, t, X, Y)
 
 
            if solx > 0:
                #print ("=== solution found ===")
                if False:
                    print ("x:", solx)
                    print ("y:", soly)
 
                d_sol = int(pol(solx, soly) / e)
                ss=ss+1

                print ("=== solution found ===")
                print ("p的高比特为:",l)
                print ("q的高比特为:",qM)
                print ("d=",d_sol) 
 
            if debug:
                print("=== %s seconds ===" % (time.time() - start_time))
            #break
        print("ss=",ss)
                            #end=time.process_time
        end=time.clock()
        print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
    example()  

题目给出了p的高70位,所以exp中把s由27改为了70,得出:

d=783087701705468761679148299766995936398557044101882919430819055852416479930185217204358163

from Crypto.Util.number import *

n = 
d = 
c = 

m = pow(c,d,n)
print(long_to_bytes(m))
#CnHongKe{Y0u_m4d3_n3w_rec0rd!!!1113dsd2et}

另外一种解法参考:2023 江苏领航杯 misc密码wp