杂题

(Updated: )

0xGame2024

Number-Theory-CRT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from Crypto.Util.number import bytes_to_long, getPrime
from hashlib import md5
from random import randint
from gmpy2 import invert,gcd

#Hash Function:
def MD5(m):return md5(str(m).encode()).hexdigest()

#RSA AlgorithmParameter Generation Function:
def KeyGen():
	Factor_BitLength = 30
	q = getPrime(Factor_BitLength)
	p = getPrime(Factor_BitLength)
	N = p * q
	#Euler's totient function:
	phi = (p-1) * (q-1)

	#Generate Keys:
	e = randint(1,phi)

	#Generate Result:
	Pub_Key = (N,e)
	return Pub_Key

Pub = KeyGen()

N = Pub[0]
e = Pub[1]

#RSA Encrypt:
m = randint(1,N)
c = pow(m,e,N)

print(f'Pub_Key = {Pub}')
print(f'Encrypt_msg = {c}')

'''
Pub_Key = (1022053332886345327, 294200073186305890)
Encrypt_msg = 107033510346108389
'''

flag = '0xGame{'+ MD5(m) +'}'

p和q都很小，分解n拿到了phi，直接求逆发现不对，求一下e和phi的公约数发现为2，在me2下求的到了d，然后得到了m，发现依旧不对，然后发现p (mod  4) = 3, q (mod  4) = 1，有限域开方即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Pub_Key = (1022053332886345327, 294200073186305890)
Encrypt_msg = 107033510346108389
from Crypto.Util.number import *
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()

n=Pub_Key[0]
e=Pub_Key[1]
c=Encrypt_msg
p = 970868179
q = 1052721013
phi = (p-1) * (q-1)
# print(GCD(e,phi))
d = inverse(e//2, phi)
m2 = pow(c,d,n)
P.<x> = PolynomialRing(Zmod(n))
f = x^2 - m2
res = f.roots(multiplicities=False)
list = []
for i in res:
    list.append(MD5(int(i)))
print(list)

御网杯

easy-crypto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/bin/env python3.9
# -*- coding: utf-8 -*-
import gmpy2
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from secret import FLAG, E1, E2, P, Q1, Q2


def next_prime(num: int) -> int:
    num = num + 2 if num % 2 else num + 1
    while not isPrime(num):
        num += 2
    return num


p = getPrime(1024)
q = next_prime(getPrime(16) * p + 38219)
n = p * q
c = pow(E1, 65537, n)
print(f'n = {n}')
print(f'c = {c}')
# n = 1605247600724752598798254639224215706171506359654961357324428027985787942008103766562745464838961569081446916113769517713344420113584254259000172572811154232107339480903672251992191997458469905064423618888336088652352540882576826988355783159237971043770132628344798937353150930071309347972804118952814447576207066147031238749098842662046825743988208813903138796789940911515825517078554074496474819128789835309636804325132602557092847746454786387067599510769382078521691609970320528531270474091713477040343897269903489441410062592732302402854035415438078656688806905350495825334584533345448091335565792091890185673190424063
# c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861

assert E2.bit_length() == 69
ns = [getPrime(1024) * getPrime(1024) for _ in range(3)]
cs = [pow(E2, 89, n) for n in ns]
print(f'ns = {ns}')
print(f'cs = {cs}')
# ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
# cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]

qq = getPrime(1024)
nn = P * qq
qqq = qq >> 460 << 460
print(f'nn = {nn}')
print(f'qqq = {qqq}')
# nn = 16851735797771199659625936797279158526379741298692339786049494329385618191510929735113284926125682522862667382938603116481087115598324232020838136618518964343752653000145611092980612556947954728339508416646035295651852840099205127587606898235203114875942637900167644300657599966420459187131027117268004042708998239798434578246497419547543598779697909298102358128788120332794123690714647499091326245022977970510468925837363300545900657420134894815246189043375619879915523611890538142257042753868665844692029124229028056547096764320547579965641276151760507921199827910445919017775913411823263307923216323527883262438117
# qqq = 121042531930820997492656296084544616958724191434895945419858099204426898711413526806300854553993738803031497438495403291406481997877273916883918253302909196533823945327277312672931819555344139777992801106437643790498379469530787985051569590331291422592393540391481519004782904598710037907420679190942964514816

assert len(FLAG) == 42
n1 = P * Q1
n2 = P * Q2
c1 = pow(bytes_to_long(FLAG), E1, n1)
c2 = pow(bytes_to_long(FLAG), E2, n2)
print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
# n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549
# n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309
# c1 = 2615722342860373905833491925692465899705229373785773622118746270300793647098821993550686581418882518204094299812033719020077509270290007615866572202192731169538843513634106977827187688709725198643481375562114294032637211892276591506759075653224150064709644522873824736707734614347484224826380423111005274801291329132431269949575630918992520949095837680436317128676927389692790957195674310219740918585437793016218702207192925330821165126647260859644876583452851011163136097317885847756944279214149072452930036614703451352331567857453770020626414948005358547089607480508274005888648569717750523094342973767148059329557
# c2 = 6769301750070285366235237940904276375318319174100507184855293529277737253672792851212185236735819718282816927603167670154115730023644681563602020732801002035524276894497009910595468459369997765552682404281557968383413458466181053253824257764740656801662020120125474240770889092605770532420770257017137747744565202144183642972714927894809373657977142884508230107940618969817885214454558667008383628769508472963039551067432579488899853537410634175220583489733111861415444811663313479382343954977022383996370428051605169520337142916079300674356082855978456798812661535740008277913769809112114364617214398154457094899399

part1

第一部分，关键代码在于

1
2
3
4
5
6
7
8
def next_prime(num: int) -> int:
    num = num + 2 if num % 2 else num + 1
    while not isPrime(num):
        num += 2
    return num

p = getPrime(1024)
q = next_prime(getPrime(16) * p + 38219)

这里的q是以随机生成的16位数*p后得到的下一位素数

非预期，应该是后面有人上传数据到网站了

直接用factordb网站分解得到的p和q

1
2
3
4
5
6
7
8
9
10
p=177359303792117851328526489433782316926858242790726462423584756658506652493962331976066825721288147144092598144008155700700416740981834713759967821006180523633487466539144055902260971865727010440583137981567069386304376263892672567446542211464028866604828433212841873836196572182719995666975250521334739091549
q=9050822631815566071146035282295345415094502987853562103937953717040252983419391763070666183383055436910189375886880193562442966709044007277884917873766398301540498904959060316748279655279915069793398114337349117852498625122706973789364495593220857091710999775284533663734947275056384098881414009354233070580875787
c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861
e=65537
n = p * q
phi =(p - 1)*(q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(m)
#377312346502536339265

预期解

因为16位数的范围并不大，自己用生成函数测试了一下，到65536前后差不多，并且p是一个1024位的素数，所以我们可以通过爆破的方式寻找到正确的p和q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
import gmpy2
import tqdm
 
########################################################## part 1
 
n = 1605247600724752598798254639224215706171506359654961357324428027985787942008103766562745464838961569081446916113769517713344420113584254259000172572811154232107339480903672251992191997458469905064423618888336088652352540882576826988355783159237971043770132628344798937353150930071309347972804118952814447576207066147031238749098842662046825743988208813903138796789940911515825517078554074496474819128789835309636804325132602557092847746454786387067599510769382078521691609970320528531270474091713477040343897269903489441410062592732302402854035415438078656688806905350495825334584533345448091335565792091890185673190424063
c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861
 
for i in tqdm.tqdm(range(2 ** 15, 2 ** 16)):
    if isPrime(i):
        q = gmpy2.next_prime(i * gmpy2.iroot(n // i, 2)[0] + 38219)
        if n % q == 0:
            print(q)
            break
 
p = n // q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(65537, phi)
E1 = pow(c, d, n)
print(E1)
# 377312346502536339265

part2

1
2
3
4
ns = [getPrime(1024) * getPrime(1024) for _ in range(3)]
cs = [pow(E2, 89, n) for n in ns]
print(f'ns = {ns}')
print(f'cs = {cs}')

小指数公钥，并且多个n和c，中国剩余定理广播攻击

常规解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
e= 89
n1= 15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117
n2= 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183
n3= 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261
c1= 3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924
c2= 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942
c3= 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854

import libnum

m1=libnum.solve_crt([c1,c2,c3],[n1,n2,n3])
m=libnum.nroot(m1,e)
print(m)
flag=libnum.n2s(m)
print(flag)
#561236991551738188085

更简洁的方法2

1
2
3
4
5
6
7
8
9
from sympy.ntheory.modular import crt
 
ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]
 
m = crt(ns, cs)[0]
E2 = gmpy2.iroot(m,89)[0]
print(E2)
# 561236991551738188085

part3

1
2
3
4
5
6
7
8
9
10
11
qq = getPrime(1024)
nn = P * qq
qqq = qq >> 460 << 460
print(f'nn = {nn}')
print(f'qqq = {qqq}')

assert len(FLAG) == 42
n1 = P * Q1
n2 = P * Q2
c1 = pow(bytes_to_long(FLAG), E1, n1)
c2 = pow(bytes_to_long(FLAG), E2, n2)

预期解应该是高位p的泄露攻击（但是没打出来） 但是后续发现n1和n2存在共素数p，所以用个gcd就可以得到p了 后续尝试正常rsa解密发现e和phi不互素，然后求了个gcd得到是35，所以我们可以得到m的35次方，后面是重新学习了一些当e和phi不互素的解决方法

e和phi不互素

对于 gcd(e, φ(n)) ≠ 1，e 与 φ(n) 不互素，

。计算 的模逆 d′，

则 md′ ≡ mgcd(e, φ(n)) (mod  n)。

当 gcd(e, φ(n)) 较小时，可以直接对 c 开根，有两种情况：

  • me < n，这种情况直接对 c 开 e 次方即可；
  • me > n，这种情况需要在有限域下对 c 开方。一般先计算 cp = c (mod  p), cq = c (mod  q)，分别求出 cp, cq 在 c 下的 e 次根（可能有多个），然后使用 CRT 遍历所有组合，分别 check 得出明文。

当 gcd(e, φ(n)) 较大时，求 p, q 的 e 次根步骤需要替换为一个有限域开根的高效算法（如 AMM 算法等）进行计算。

也可以：

假设 gcd(e, φ(n)) = k，计算 。

我们这里正好满足的是me > n，所以需要在有限域下进行开方解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#sage
import gmpy2
from Crypto.Util.number import *
n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549
n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309
c1 = 2615722342860373905833491925692465899705229373785773622118746270300793647098821993550686581418882518204094299812033719020077509270290007615866572202192731169538843513634106977827187688709725198643481375562114294032637211892276591506759075653224150064709644522873824736707734614347484224826380423111005274801291329132431269949575630918992520949095837680436317128676927389692790957195674310219740918585437793016218702207192925330821165126647260859644876583452851011163136097317885847756944279214149072452930036614703451352331567857453770020626414948005358547089607480508274005888648569717750523094342973767148059329557
c2 = 6769301750070285366235237940904276375318319174100507184855293529277737253672792851212185236735819718282816927603167670154115730023644681563602020732801002035524276894497009910595468459369997765552682404281557968383413458466181053253824257764740656801662020120125474240770889092605770532420770257017137747744565202144183642972714927894809373657977142884508230107940618969817885214454558667008383628769508472963039551067432579488899853537410634175220583489733111861415444811663313479382343954977022383996370428051605169520337142916079300674356082855978456798812661535740008277913769809112114364617214398154457094899399
E1 = 377312346502536339265
E2 = 561236991551738188085
 
s1, s2, s3 = gmpy2.gcdext(E1, E2) 
# print(s1, s2, s3 )
 
p = gmpy2.gcd(int(n1), int(n2))
q = n1 // p
 
phi = (p - 1) * (q - 1)
t = gmpy2.gcd(int(E1), int(phi))
print(t)
d = gmpy2.invert(int(E1) // int(t), int(phi))
# m1 = m ^ e
m1 = pow(c1,d,n1)
 
for mp in GF(p)(m1).nth_root(e, all=True):
    for mq in GF(q)(m1).nth_root(e, all=True):
        m = crt([ZZ(mp), ZZ(mq)], [p, q])
        flag = long_to_bytes(m)
        # print(flag)
        if b'flag' in flag:
            print(flag)
# flag{27dab675-9e9b-4c1f-99ab-dd9fe49c190a}

MINLCTF2025

rsasign

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from Crypto.Util.number import bytes_to_long, getPrime, inverse
from secret import flag

def genKeys(nbits):
    e = 0x10001
    p = getPrime(nbits // 2)
    q = getPrime(nbits // 2)
    n = p * q
    phi = n - (p + q) + 1
    d = inverse(e, phi)
    pubkey = (n, e)
    prikey = (d, p, q)    
    return pubkey, prikey

def encrypt(msg, pubkey):
    m = bytes_to_long(msg)
    n, e = pubkey
    c = pow(m, e, n)
    return c

def get_gift(prikey):
    a = bytes_to_long(b'miniL')
    b = bytes_to_long(b'mini7')
    p, q = prikey[1:]
    phi = (p - 1)*(q - 1)
    giftp = p + a
    giftq = q + b
    gift = pow((giftp + giftq + a*b), 2, phi)
    return gift >> 740

if __name__ == "__main__":
    nbits = 1024
    pubkey, prikey = genKeys(nbits)
    c = encrypt(flag, pubkey)
    gift = get_gift(prikey)
    with open('output.txt', 'a') as f:
        f.write('pubkey = ' + str(pubkey) + '\n')
        f.write('c = ' + str(c) + '\n')
        f.write('gift = ' + str(gift) + '\n')
1
2
3
pubkey = (65537,103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399)
c = 50810871938251627005285090837280618434273429940089654925377752488011128518767341675465435906094867261596016363149398900195250354993172711611856393548098646094748785774924511077105061611095328649875874203921275281780733446616807977350320544877201182003521199057295967111877565671671198186635360508565083698058
gift = 2391232579794490071131297275577300947901582900418236846514147804369797358429972790212

已知我们有gift = (giftp + giftq + ab)2 (mod  ϕ) 这里测一下a和b的长度，发现他们相较于p和q极短基本上可以忽略 所以我们近似有gift = (p + q)2 (mod  ϕ) 然后自己生成数据测一下

1
2
3
4
5
6
p=getPrime(512)
q=getPrime(512)
n=p*q
k=(p+q)**2//n
print(k)
#4

我们就拿到了这个式子的关系 并且这里的gift被模掉了低740位，所以我们就可以通过构造方程组拿到p的高位

1
2
3
4
import gmpy2
a = int(gmpy2.iroot(gift << 740, 2)[0])  # p-q
b = int(gmpy2.iroot((gift << 740) + 4*n, 2)[0])  # p+q
p_high= (a + b)//2

然后就是打一元copper攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pubkey = 
c = 
gift = 
n = pubkey[1]
e = pubkey[0]
import gmpy2
a = int(gmpy2.iroot(gift << 740, 2)[0])  # p-q
b = int(gmpy2.iroot((gift << 740) + 4*n, 2)[0])  # p+q
p_high= (a + b)//2
from Crypto.Util.number import *
bits=235
p_h=p_high>> 235 << 235
R.<x>=PolynomialRing(Zmod(n))
f=p_h+x
f=f.monic()
res=f.small_roots(X=2^235,beta=0.4,epsilon=0.01)
if res !=[]:
    p=int(p_h+res[0])
    q=n//p
    phi=(p-1)*(q-1)
    d=inverse(e,phi)
    m=pow(c,d,n)
    print(long_to_bytes(m))

SHCTF2024

lattice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
n = getPrime(1024)
x = getPrime(200)
hint = (x*gmpy2.invert(m,n)) % n
print(f'n = {n}')
print(f'hint = {hint}')
'''
n = 152796022093657008425867826412538793747318986175375760689024975035557838288031741295797649967106130503020117198116769417053850437691492596957416004140550460845551832242126438382622266235726472732569131412860613461542374064825092420723662225110595499077191092820532300002967577653764096759617778091966382904887
hint = 25569143938114268788879827411215745731043262260402779816783733470240028677096410812831399463104121396578625276232462330280604442741242933324330482649175337887274983300003486206478499962082352088597247874234904049860695433433317263563126535527334018280497271436453330693435700311283203594541269296512072155622
'''

我们有 hint ≡ m−1 ⋅ x (mod  n) hint ⋅ m ≡ x (mod  n) hint ⋅ m − k ⋅ n = x 构造格 不需要配平

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
n = 152796022093657008425867826412538793747318986175375760689024975035557838288031741295797649967106130503020117198116769417053850437691492596957416004140550460845551832242126438382622266235726472732569131412860613461542374064825092420723662225110595499077191092820532300002967577653764096759617778091966382904887
hint = 25569143938114268788879827411215745731043262260402779816783733470240028677096410812831399463104121396578625276232462330280604442741242933324330482649175337887274983300003486206478499962082352088597247874234904049860695433433317263563126535527334018280497271436453330693435700311283203594541269296512072155622

L = matrix([[1,hint],[0,n]])
f,g = L.LLL()[0]
f=abs(f)
print(long_to_bytes(f))

pading

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import gmpy2
flag = b'SHCTF{********}'
assert len(flag) == 39
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x3
pad = b'a_easy_problem'
c = pow(bytes_to_long(flag + pad),e,n)
print(f'n = {n}')
print(f'c = {c}')
'''
n = 109737787794968305949598228868674114597018371251979806854788490929456243836953515564749753768100090653929585848710439841326812805404713071846229799341611201345422899839869346846129523704866785092954139080698928767741795106166833882185183866759036319543323061345190111744365702185492443072749347906785496112489
c = 42085883893512048106829975452905289009909421998654249003993514427526589868716834021359088868423245181021979484900636815785724277904618157061827644640976245079056625254053678897529638103361780570361086580770984509290912588699825058783934765458424022883210844472467747148206830472515332804214348856325586329938
'''

测一测数据，pad 的长度为111左右，flag的二进制长度约311位，并且e很小，在e方下的明文也比n小（想用低加密指数攻击没开方成功，明文太大了）所以相对于n来说flag就是个小根，用copper攻击。

1
2
3
4
5
6
7
8
9
10
11
12
n = 101194231761192803646875794770841105131876105333404505987513576849142365482512109876401629071314564545841743473668262668053559550015874646299248232349238400201145583346187330958825878235324968882794481192056169683711007095999439320830763275487477094590502701333963154552470777678553556993349171608134555815527
c = 54067443511581567434123971345564905390315631873898717856316286990552318113901362505672245448553258416669456882532743580961176229271906817289588426185966004215569829572814038485471312399063659287164712291139771809733004385057875146223151700601326161190474536508680332925332614914475852998934930375151571163346
e = 0x3
pad = b'a_easy_problem'

from Crypto.Util.number import *
PR.<x> = PolynomialRing(Zmod(n))
f = (x *256 ** len(pad) + bytes_to_long(pad)) ** e - c

f = f.monic()
root = f.small_roots(X=2**312,beta=0.9,epsilon=0.03)
print(long_to_bytes(int(root[0])))

原来小e攻击在大明文下也能用copper攻击说是

ezECC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from flag import flag
 
assert flag.startswith(b'SHCTF{')
 
m = next_prime(bytes_to_long(flag))
p = getPrime(512)
a,b = getPrime(128),getPrime(128)
E = EllipticCurve(Zmod(p),[a,b])
k = getPrime(256)
A1 = E.random_point()
A2 = A1*k
M = E.lift_x(m)
C = M+A2
 
print('p = ',p)
print('k = ',k)
print('A1 = ',A1)
print('C = ',C)

复习一下基础的ecc推导以及获取 x13 + ax1 + b ≡ y12 (mod  p)

x23 + ax2 + b ≡ y22 (mod  p)

y12 − y22 = x13 − x23 + a(x1 − x2) (mod  p)

a = ((y12 − y22) − (x13 − x23)) * (x1 − x2)−1 (mod  p)

b = y12 − (x13 + ax1) (mod  p)

官方exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *

p =  9799485259524549113003780400336995829253375211044694607315372450399356814285244762186468904824132005209991983177601498069896166228214442123763065076327679
k =  73771953838487511457389800773038323262861649769228176071578897500004883270121
A1 =  (5945412329827707694132352090606154232045921322662767755331097180167148601629747751274580872108985870208681845078153424348847330421799769770041805208089791,4113102573821904570542216004200810877456931033522276527318388416329888348077285857968081007666714313806776668203284797556825595791189566621228705928598709)
C = (2336301464307188733995312208152021176388718095735565422234047912672553316288080052957448196669174030921526180747767251838308335308474037066343018337141276,6868888273736103386336636953449998615833854869329393895956720058438723636197866928342387693671211918574357564701700555086194574821628053750572619551290025)

a = inverse(A1[0]-C[0],p)*((A1[1]**2-A1[0]**3)-(C[1]**2-C[0]**3))% p
b = (C[1]**2-C[0]**3-a*C[0])%p

E = EllipticCurve(Zmod(p),[a,b])#在有限域模P下以a，b为参数生成曲线
A1 = E(A1)
C = E(C)
M = C-k*A1

mm = (M.xy())[0]#获取M的仿射坐标（x，y）中第一个点
for i in range(292):
    m = long_to_bytes(int(mm-i))
    if m.endswith(b'}'):#判断结尾
        print(m)

babyLCG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from enc import flag

seed = bytes_to_long(flag)

a = getPrime(400)
b = getPrime(400)
p = getPrime(400)
c = []
for i in range(3):
    seed = (seed*a+b)%p
    c.append(seed>>80)
print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')
print(f'c = {c}')

'''
a = 2226195477738639469520314871241317996692000453980590059051655917244193431061796494084520115208972884910304639094257195331
b = 1819366699498013196825162828978957434212721200408011692822966187294576933971468888455937630017411789071339806414083368521
p = 2468226688875800583640242996971128907087199220172878918872664572373129611780447612341599434033067093631443731567292789387
c = [1458638764476576620497667312334744692692838533272664001794698423698634900864733383502067184618014, 1929877825753930927256723772056768775233426313865848693767475766366579127755530427079541769349812, 646691106155016146430045567492598040316128576565509395612683821702033873891600466055472183189754]
'''
'''

LCG | DexterJie’Blog（后面再来学习一下推导）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from Crypto.Cipher import AES
from Crypto.Util.number import *

a = 2226195477738639469520314871241317996692000453980590059051655917244193431061796494084520115208972884910304639094257195331
b = 1819366699498013196825162828978957434212721200408011692822966187294576933971468888455937630017411789071339806414083368521
m = 2468226688875800583640242996971128907087199220172878918872664572373129611780447612341599434033067093631443731567292789387
c = [1458638764476576620497667312334744692692838533272664001794698423698634900864733383502067184618014, 1929877825753930927256723772056768775233426313865848693767475766366579127755530427079541769349812, 646691106155016146430045567492598040316128576565509395612683821702033873891600466055472183189754]

h = [0] + c

length = len(h)
for i in range(length):
    h[i] <<= 80

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:]



Ge = Matrix(ZZ,length,length)

for i in range(len(A)):
    Ge[i,i] = m
    Ge[-2,i] = A[i]
    Ge[-1,i] = B[i]

K = 2**80
Ge[-2,-2] = 1
Ge[-1,-1] = K

for line in Ge.LLL():
    if abs(line[-1]) == K:
        L1 = line[-2]
        seed1 = h[1] + L1
        seed = (seed1 - b) * inverse(a,m) % m
        print(f"seed = {seed}")
        print(long_to_bytes(seed))

大学×高中√

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
assert len(flag)==47
leak = cos(m).n(1000)
print(leak)
# -0.531659424314510605474310465691627447018962841799592816094864089691364538229482189727389328879665722000498924085922309530705082058318143911592913356306771218326907498748543471792402846678395378914458319779159891679235865648174792237841148560400444502487744616191775450001945896249393139352114465002808

已知我们有 构造格（二维格的界卡的很死，LLL出不来，所以需要三维格） 配平一下，在中间的1放入2375，在最后一列放入2750（避免在同一个位置加入太大向量导致无法配平，并且尽量不动m） 

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
leak = -0.531659424314510605474310465691627447018962841799592816094864089691364538229482189727389328879665722000498924085922309530705082058318143911592913356306771218326907498748543471792402846678395378914458319779159891679235865648174792237841148560400444502487744616191775450001945896249393139352114465002808
A = arccos(leak)#sage自带的求反函数
phi = RealField(1000)#用realfield计算精度
pi =phi(pi)
G = Matrix(QQ,[[1,0,2^750],[0,2^375,2^750*A],[0,0,2^750*2*pi]])#在实数域下计算
m = abs(G.LLL()[0][0])
print(long_to_bytes(int(m)))

worde很大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = getPrime(200)
d = gmpy2.invert(e,(p-1)*(q-1))
dp = d % (p-1)
c = pow(m,e,n)

print(f"n = {n}")
print(f"c = {c}")
print(f"e = {e}")
print(f"dp = {dp}")
'''
n = 80556471644505011891756231019311882225730165614863719395328309929825293641259274802719238521989722995475141775057817527464270040837552738905604676076146734989560693872114609281119098735209206723559622585697792579892238311917420010818437212211772833281743513007880423036718561435487430398906194020190782727533
c = 54148254421535490527493285183290511426930400302852195437953474915111379369271888877325441784156399780311852702053946823116096097645853719820288433712191436292215603420410887291711072280776432888651650824598073666456855448900533585686638180147222205725403586385675699949105000801347816441718934719453686534738
e = 1313707923168496810525667511687571667930728866593473823130269
dp = 5632614301315357701870642600570871749745208913790376158690650513220923850000171918022929749228070629033357006229715995644578804260941756683958425128792761
'''

e很大的dp泄露

欧拉降幂

ab (mod  c) = ab (mod  φ(c)) + φ(c) (mod  c)

adpe − a ≡ 0 (mod  p)

所以有(adpe − a)|p

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from gmpy2 import *
n = 80556471644505011891756231019311882225730165614863719395328309929825293641259274802719238521989722995475141775057817527464270040837552738905604676076146734989560693872114609281119098735209206723559622585697792579892238311917420010818437212211772833281743513007880423036718561435487430398906194020190782727533
c = 54148254421535490527493285183290511426930400302852195437953474915111379369271888877325441784156399780311852702053946823116096097645853719820288433712191436292215603420410887291711072280776432888651650824598073666456855448900533585686638180147222205725403586385675699949105000801347816441718934719453686534738
e = 1313707923168496810525667511687571667930728866593473823130269
dp = 5632614301315357701870642600570871749745208913790376158690650513220923850000171918022929749228070629033357006229715995644578804260941756683958425128792761
a = 2
p = GCD(pow(a, e*dp, n) - a, n)
q = n // p
d = inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))