Crew CTF 2022
Note : A JOURNEY TO GAIN KNOWLEDGE
Last updated
Note : A JOURNEY TO GAIN KNOWLEDGE
Last updated
BRQDER1VHDkeVhQ5BRQfFhIJGw==Convert to hex than xor with some char?
i brute force xor string with ascii and got flag when i xor with 66
crew{3z_x0r_crypto}
chall
from Crypto.Util.number import getPrime, bytes_to_long, inverse, isPrime
from secret import flag
m = bytes_to_long(flag)
def getSpecialPrime():
a = 2
for i in range(40):
a*=getPrime(20)
while True:
b = getPrime(20)
if isPrime(a*b+1):
return a*b+1
p = getSpecialPrime()
e1 = getPrime(128)
e2 = getPrime(128)
e3 = getPrime(128)
e = pow(e1,pow(e2,e3))
c = pow(m,e,p)
assert pow(c,inverse(e,p-1),p) == m
print(f'p = {p}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
print(f'e3 = {e3}')
print(f'c = {c}')
# p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
# e1 = 219560036291700924162367491740680392841
# e2 = 325829142086458078752836113369745585569
# e3 = 237262361171684477270779152881433264701
# c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613solve
from Crypto.Util.number import long_to_bytes
p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
e1 = 219560036291700924162367491740680392841
e2 = 325829142086458078752836113369745585569
e3 = 237262361171684477270779152881433264701
c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613
phiP = p - 1
phiphiP = 63775594668498404422995279661693309334486076035802944116275814269950078792958445557761589097717204934857369990271713664698474867142217580223510594284968730411939236198524531363514002763605853593498040656788050786948899096447734618521600000000
subE = pow(e2, e3, phiphiP)
e = pow(e1, subE, p - 1)
d = pow(e, -1, p - 1)
pt = pow(c, d, p)
print(long_to_bytes(pt))from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
import random
import binascii
from secret import flag
e = 3
BITSIZE = 8192
key = RSA.generate(BITSIZE)
n = key.n
flag = bytes_to_long(flag)
m = floor(BITSIZE/(e*e)) - 400
assert (m < BITSIZE - len(bin(flag)[2:]))
r1 = random.randint(1,pow(2,m))
r2 = random.randint(r1,pow(2,m))
msg1 = pow(2,m)*flag + r1
msg2 = pow(2,m)*flag + r2
C1 = Integer(pow(msg1,e,n))
C2 = Integer(pow(msg2,e,n))
print(f'{n = }\n{C1 = }\n{C2 = }')chall
== proof-of-work: disabled ==
n: 1616497406380138491133503779690192730817057608639372592252520516975862952615210945574537405760549389168583892593257067120087756082808421681517111766821299898406140165578044670375631111376738910879062957482159564936855771411852877194121566364820768099990998260313903643849753803317252919830952992383066880828005875017
Here is RSA encrypted flag.(e=65537)
1130532517825519479130381004085268339474035118115829225696514522310776730318147700377221603337245401091452518784299726171598333570292109329806114629724566207717052670629170022638782995856892709748078107193105711596936798857638476662400307716137670955272389571708458372033883275664790451293457040269142716857976313491
Let's see a property of numbers... I like small numbers.
pow(2, x, n) = 6
x->54828916555058866342511122652949588153181027525251823266513880028737569174757086472069470761499776719376579212883756027917948138130667412480899243793877791489883668254211206543348496781426212493882946189924622083417727756846933240503067573973939985114987319164236080575398688212404039674423758940307316117062712501
pow(9, x, n) = 6
x->403447800130724601175231354302360739195683626926257673518279460913854183723640618534084125974065844665542055707653182458026653283010409169669161651499443772457104776418145612781095649691282667656550411888571602648560581456064925298128011213551167435698425467717649866969298488689573907817316549002129279947647955041
pow(7, x, n) = 8
x->68189663474432712466688488112616939168690829755454600879624170726100871762773784613238004838124813468160746559406797472939510418837631220281607197500190788909087304480602560528471775926407749080486553817237296720933106091270467616587022515393240481894514003957876983090244823489736106844320191501937524362421477954
pow(5, x, n) = 2
x->332143598303254255984474286445716911550865493777262390951635164725656995062115171041667459124707600273918305610275350893527997427098209837076646139588706129117628127958957234080138783937035599851419465941606102534266402111116010328979208020300591443883262504395454924857841937624447672721739529153831259928254745042
pow(5, x, n) = 6
x->470257225334054674704037727495010723611064690574301271732547359940973354160493991533084833818912523149979170303536330287017193402324208835858592442916663226562391423201228010344341683822411983854997792681972822496788285072997816242279395146766975448893348368585785731771017254844154206642796841090314441830434625268
pow(4, x, n) = 6
x->229476634075046744562943533787748885428722714842547485664822004636351653664279911432851911100818562005761276180599011403969943579416386416430088592749601382820125181102318211569897197496450005293991478406247904972333848957357643903445003466731934297502565059255742341011819618278385198786745403493956381131580256125
pow(3, x, n) = 6
x->402771248666414579567086763682173295687102851692672198973428792583742629293478500674533900507994342038938138266992098136031367545318712918959045361293562570763842858885866008965745401171091537219000813154572017435871192754261496029869083067612406261506708136088051132490356429034781457735566049956653113749198110333
pow(8, x, n) = 3
x->287692539915042703969754337499348651187236610614979373130924712838889681827454186419779391213924823767889508503170763195987275393178292751079818375734842579930205685385020546578746764401457936227360989145022332601972556024194547457758982097651265734965090972619577761157293261633712251824185951678506069469752770666
pow(3, x, n) = 8
x->400065042809174493134508401201423521652779750758330300794026119263296411572830029236332998643708331532522468504347760848050224594551927916118580200470037763990795188756747593704344407090327015468802418218573676585113637947047778956833370483857361564739838809569656194574588190415611657408564053774748448955398731498
pow(5, x, n) = 4
x->664287196606508511968948572891433823101730987554524781903270329451313990124230342083334918249415200547836611220550701787055994854196419674153292279177412258235256255917914468160277567874071199702838931883212205068532804222232020657958416040601182887766525008790909849715683875248895345443479058307662519856509490084
pow(6, x, n) = 9
x->205512574179997488626998905557700634483715481813052990011911853561579774316820488634105298576319770174343834524354610802278872416040586064697094614213808503897600264699865798413966958500958802824302427794957961260592118759732690565438500593718497917391740706793448693655109768109094126251399162695621747806403089029
pow(8, x, n) = 6
x->152984422716697829708629022525165923619148476561698323776548003090901102442853274288567940733879041337174184120399340935979962386277590944286725728499734255213416787401545474379931464997633336862660985604165269981555899304905095935630002311154622865001710039503828227341213078852256799191163602329304254087720170750
pow(6, x, n) = 2
x->99305888707518567078188519682423774110274460173395079025609137841192981918491123879764526431908788558901069311979827988871533302330759677841091663745758235126383214625279709091239469855257497634898791413806613300328925699067832000474219382885715346249201046276899953896565390117636115823833942675991849169847355361
pow(3, x, n) = 4
x->401418145737794536350797582441798408669941301225501249883727455923519520433154264955433449575851336785730303385669929492040796069935320417538812780881800167377319023821306801335044904130709276343901615686572847010492415350654637493351226775734883913123273472828853663532472309725196557572065051865700781352298420915
pow(6, x, n) = 8
x->297917666122555701234565559047271322330823380520185237076827413523578945755473371639293579295726365676703207935939483966614599906992279033523274991237274705379149643875839127273718409565772492904696374241419839900986777097203496001422658148657146038747603138830699861689696170352908347471501828027975547509542066083
pow(6, x, n) = 4
x->198611777415037134156377039364847548220548920346790158051218275682385963836982247759529052863817577117802138623959655977743066604661519355682183327491516470252766429250559418182478939710514995269797582827613226600657851398135664000948438765771430692498402092553799907793130780235272231647667885351983698339694710722
pow(2, x, n) = 3
x->54828916555058866342511122652949588153181027525251823266513880028737569174757086472069470761499776719376579212883756027917948138130667412480899243793877791489883668254211206543348496781426212493882946189924622083417727756846933240503067573973939985114987319164236080575398688212404039674423758940307316117062712500
pow(9, x, n) = 8
x->200032521404587246567254200600711760826389875379165150397013059631648205786415014618166499321854165766261234252173880424025112297275963958059290100235018881995397594378373796852172203545163507734401209109286838292556818973523889478416685241928680782369919404784828097287294095207805828704282026887374224477699365749
pow(9, x, n) = 4
x->402771248666414579567086763682173295687102851692672198973428792583742629293478500674533900507994342038938138266992098136031367545318712918959045361293562570763842858885866008965745401171091537219000813154572017435871192754261496029869083067612406261506708136088051132490356429034781457735566049956653113749198110332
pow(4, x, n) = 8
x->202062175797517311391687972461274091352132201079921574031565064621982869076901368196817175720068673646072986574157133390010969510351052710189638970852662487075183346975212608298222949105736899047050005311285593930624985078934177283193469679744964304945071399673624300724120274172183178949533524023802723073048899876
pow(3, x, n) = 2
x->402771248666414579567086763682173295687102851692672198973428792583742629293478500674533900507994342038938138266992098136031367545318712918959045361293562570763842858885866008965745401171091537219000813154572017435871192754261496029869083067612406261506708136088051132490356429034781457735566049956653113749198110332
pow(9, x, n) = 2
x->201385624333207289783543381841086647843551425846336099486714396291871314646739250337266950253997171019469069133496049068015683772659356459479522680646781285381921429442933004482872700585545768609500406577286008717935596377130748014934541533806203130753354068044025566245178214517390728867783024978326556874599055166
pow(4, x, n) = 9
x->54828916555058866342511122652949588153181027525251823266513880028737569174757086472069470761499776719376579212883756027917948138130667412480899243793877791489883668254211206543348496781426212493882946189924622083417727756846933240503067573973939985114987319164236080575398688212404039674423758940307316117062712500
pow(7, x, n) = 6
x->609351919330338788564728739822629956355456887028721887298974504570568882611692565461123562992956781668119233854345529628370992321630269821927109251308765409363947773150478737986144449647765451611997306740440424376260329986447810528617668618523626355701107679066679097393166524781089216933985070581366246284724787480
pow(2, x, n) = 9
x->109657833110117732685022245305899176306362055050503646533027760057475138349514172944138941522999553438753158425767512055835896276261334824961798487587755582979767336508422413086696993562852424987765892379849244166835455513693866481006135147947879970229974638328472161150797376424808079348847517880614632234125425000
pow(5, x, n) = 9
x->276227254061600837439126882098587624120398393594077761561824390430632718196757640982834749388409845752121729386521958786978391950451997997563892606655914194889526590484541552528405799770752768007156653480733439925043765923763611826600374252932768010020171728380661613826350634439413067842114623872966363804359760452
pow(7, x, n) = 2
x->22729887824810904155562829370872313056230276585151533626541390242033623920924594871079334946041604489386915519802265824313170139612543740093869065833396929636362434826867520176157258642135916360162184605745765573644368697090155872195674171797746827298171334652625661030081607829912035614773397167312508120807159318
pow(7, x, n) = 9
x->364995359820986523251579931058418921189924416567454411218605970169139041073930468392819753213555659773172690372457994048071766322631241322907924487540087011154437288746372002427082585588311474315470223024246941882731982262978600180070110174471901837025587090133609669829688737213621646840289250732896584035639656826
pow(8, x, n) = 9
x->171260728235050785156132730076149119670208819070115598198719296433813625501105636445924430987712300243633043858027259611952611765654480081780358809764360185710044676819615876561047630591442074360621967667473477342695141890520740349131024835812602860040039145891906920866345974923058145749304855309406692793407741583
pow(7, x, n) = 3
x->586622031505527884409165910451757643299226610443570353672433114328535258690767970590044228046915177178732318334543263804057822182017726081833240185475368479727585338323611217809987191005629535251835122134694658802615961289357654656421994446725879528402936344414053436363084916951177181319211673414053738163917628162
pow(7, x, n) = 4
x->45459775649621808311125658741744626112460553170303067253082780484067247841849189742158669892083208978773831039604531648626340279225087480187738131666793859272724869653735040352314517284271832720324369211491531147288737394180311744391348343595493654596342669305251322060163215659824071229546794334625016241614318636
pow(8, x, n) = 4
x->134708117198344874261125314974182727568088134053281049354376709747988579384600912131211450480045782430715324382771422260007313006900701806793092647235108324716788897983475072198815299403824599364700003540857062620416656719289451522128979786496642869963380933115749533816080182781455452633022349349201815382032599917
pow(5, x, n) = 8
x->188182091719693522386670969492054369244067677012100876728645235689039508878740040337733674493848106237462970534197519120540114239890418670471382535355468439052150995976021269047524555388159203366058376579675931880299266017611321854163745341921917111869501914491867571677044716184610302367084491366282887492568635628
pow(5, x, n) = 3
x->138113627030800418719563441049293812060199196797038880780912195215316359098378820491417374694204922876060864693260979393489195975225998998781946303327957097444763295242270776264202899885376384003578326740366719962521882961881805913300187126466384005010085864190330806913175317219706533921057311936483181902179880226
pow(4, x, n) = 3
x->27414458277529433171255561326474794076590513762625911633256940014368784587378543236034735380749888359688289606441878013958974069065333706240449621896938895744941834127105603271674248390713106246941473094962311041708863878423466620251533786986969992557493659582118040287699344106202019837211879470153658058531356250
pow(6, x, n) = 3
x->304818462887516055705187425240124408593989941986448069037520991402772756235311612513869825008228558733244903836334438791150405718371345742538186277959566739023983479325145507505206428356216300459201219208764574560921044458800522565912719976604213263640941753070348647551675158226730242075233105371613596976250444389
I'm bored.
bye.import sys
from Crypto.Util.number import long_to_bytes, inverse, GCD
import gmpy2
from pwn import *
proc = remote('toydl.crewctf-2022.crewc.tf', 1337)
proc.recvline()
n = int(proc.recvline().strip(b'\n').split(b': ')[1])
proc.recvline()
proc.recvline()
e = 65537
encflag = int(proc.recvline().strip(b'\n'))
proc.recvline()
proc.recvline()
proc.recvline()
print(n)
result = {}
while(True):
firstline = proc.recvline().strip(b'\n')
if firstline == b"I'm bored.":
proc.close()
break
base = int(firstline.split(b'pow(')[1].split(b',')[0])
number = int(firstline.split(b' = ')[1])
dl = int(proc.recvline().strip(b'\n').split(b'->')[1])
result[(base, number)] = dl
proc.recvline()
def factor(base, baseorder):
if baseorder == 0:
return False
i = 1
while(baseorder % (2**i) == 0):
cand = pow(base, baseorder//(2**i), n)
if cand != 1:
p = GCD(cand+1, n)
if p > 1 and p < n:
q = n // p
d = inverse(e, (p-1)*(q-1))
print(b'FOUND: ' + long_to_bytes(pow(encflag, d, n)))
return True
i += 1
return False
found = False
# base1**x = a, (a**k)**y = base1**l
for base1 in (2,3,5,6,7):
for number1 in range(2, 10):
for k in range(1, 4):
for l in range(1, 4):
if (base1, number1) in result.keys() and (number1**k, base1**l) in result.keys():
dl1 = result[(base1, number1)]
dl2 = result[(number1**k, base1**l)]
base1order = dl1*dl2*k-l
assert pow(base1, base1order, n) == 1
found = factor(base1, base1order)
if found:
break
if found:
break
if found:
break
if found:
break
if found:
sys.exit(0)
# base1**x = a, (a**k)**y = base1.sqrt**l
for base1 in (4, 9):
base1_sqrt = int(gmpy2.iroot(base1, 2)[0])
for number1 in range(2, 10):
for k in range(1, 4):
for l in range(1, 4):
if (base1, number1) in result.keys() and (number1**k, base1_sqrt**l) in result.keys():
dl1 = result[(base1, number1)]
dl2 = result[(number1**k, base1_sqrt**l)]
base1_sqrtorder = 2*dl1*dl2*k-l
assert pow(base1_sqrt, base1_sqrtorder, n) == 1
found = factor(base1_sqrt, base1_sqrtorder)
if found:
break
if found:
break
if found:
break
if found:
break
if found:
sys.exit(0)
# base1**x = a, (a**k)**y = base1.cubert**l
for base1 in (8,):
base1_cubic = int(gmpy2.iroot(base1, 3)[0])
for number1 in range(2, 10):
for k in range(1, 4):
for l in range(1, 4):
if (base1, number1) in result.keys() and (number1**k, base1_cubic**l) in result.keys():
dl1 = result[(base1, number1)]
dl2 = result[(number1**k, base1_cubic**l)]
base1_cubicorder = 3*dl1*dl2*k-l
assert pow(base1_cubic, base1_cubicorder, n) == 1
found = factor(base1_cubic, base1_cubicorder)
if found:
break
if found:
break
if found:
break
if found:
break
if found:
sys.exit(0)
# (base1.0*base1.1)**x = a, (a**k)**y0 = base1.0**l, (a**k)**y1 = base1.1**l
for number1 in range(2, 10):
for k in range(1, 4):
if (6, number1) in result.keys() and (number1**k, 2) in result.keys() and (number1**k, 3) in result.keys():
dl1 = result[(6, number1)]
dl2 = result[(number1**k, 2)]
dl3 = result[(number1**k, 3)]
six_order = dl1*k*(dl2+dl3)-1
assert pow(6, six_order, n) == 1
found = factor(6, six_order)
if found:
break
if (6, number1) in result.keys() and (number1**k, 4) in result.keys() and (number1**k, 9) in result.keys():
dl1 = result[(6, number1)]
dl2 = result[(number1**k, 4)]
dl3 = result[(number1**k, 9)]
six_order = dl1*k*(dl2+dl3)-2
assert pow(6, six_order, n) == 1
found = factor(6, six_order)
if found:
break
if found:
break
if found:
sys.exit(0)
# base1**x = a, (base1**k)**y = a**l
for base1 in range(2, 10):
for number1 in range(2, 10):
for k in range(1, 4):
for l in range(1, 4):
if (base1, number1) in result.keys() and (base1**k, number1**l) in result.keys():
dl1 = result[(base1, number1)]
dl2 = result[(base1**k, number1**l)]
base1_order = abs(dl1*l - k*dl2)
assert pow(base1, base1_order, n) == 1
found = factor(base1, base1_order)
if found:
break
if found:
break
if found:
break
if found:
break
if found:
sys.exit(0)
print("NOTFOUND")from __future__ import print_function
import time
debug = True
# display matrix picture with 0 and 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'
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print(a)
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
"""
Coppersmith revisited by Howgrave-Graham
finds a solution if:
* b|modulus, b >= modulus^beta , 0 < beta <= 1
* |x| < XX
"""
#
# init
#
dd = pol.degree()
nn = dd * mm + tt
#
# checks
#
if not 0 < beta <= 1:
raise ValueError("beta should belongs in (0, 1]")
if not pol.is_monic():
raise ArithmeticError("Polynomial must be monic.")
#
# calculate bounds and display them
#
"""
* we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
* we know LLL will give us a short vector v such that:
||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
* we will use that vector as a coefficient vector for our g(x)
* so we want to satisfy:
2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
(it's important to use N because we might not know b)
"""
if debug:
# t optimized?
print("\n# Optimized t?\n")
print("we want X^(n-1) < N^(beta*m) so that each vector is helpful")
cond1 = RR(XX^(nn-1))
print("* X^(n-1) = ", cond1)
cond2 = pow(modulus, beta*mm)
print("* N^(beta*m) = ", cond2)
print("* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD")
# bound for X
print("\n# X bound respected?\n")
print("we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M")
print("* X =", XX)
cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
print("* M =", cond2)
print("* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD")
# solution possible?
print("\n# Solutions possible?\n")
detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
print("we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)")
cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
print("* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1)
cond2 = RR(modulus^(beta*mm) / sqrt(nn))
print("* N^(beta*m) / sqrt(n) = ", cond2)
print("* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)")
# warning about X
print("\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n")
#
# Coppersmith revisited algo for univariate
#
# change ring of pol and x
polZ = pol.change_ring(ZZ)
x = polZ.parent().gen()
# compute polynomials
gg = []
for ii in range(mm):
for jj in range(dd):
gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
for ii in range(tt):
gg.append((x * XX)**ii * polZ(x * XX)**mm)
# construct lattice B
BB = Matrix(ZZ, nn)
for ii in range(nn):
for jj in range(ii+1):
BB[ii, jj] = gg[ii][jj]
# display basis matrix
if debug:
matrix_overview(BB, modulus^mm)
# LLL
BB = BB.LLL()
# transform shortest vector in polynomial
new_pol = 0
for ii in range(nn):
new_pol += x**ii * BB[0, ii] / XX**ii
# factor polynomial
potential_roots = new_pol.roots()
print("potential roots:", potential_roots)
# test roots
roots = []
for root in potential_roots:
if root[0].is_integer():
result = polZ(ZZ(root[0]))
if gcd(modulus, result) >= modulus^beta:
roots.append(ZZ(root[0]))
#
return roots
############################################
# Test on Stereotyped Messages
##########################################
print("//////////////////////////////////")
print("// TEST 1")
print("////////////////////////////////")
# RSA gen options (for the demo)
length_N = 1024 # size of the modulus
Kbits = 200 # size of the root
e = 3
# RSA gen (for the demo)
p = next_prime(2^int(round(length_N/2)))
q = next_prime(p)
N = p*q
ZmodN = Zmod(N);
n=141100651008173851466795684636324450409238358207191893767666902216680426313633075955718286598033724188672134934209410772467615432454991738608692590241240654619365943145665145916032591750673763981269787196318669195238077058469850912415480579793270889088523790675069338510272116812307715222344411968301691946663
e=65537
c=115338511096061035992329313881822354869992148130629298132719900320552359391836743522134946102137278033487970965960461840661238010620813848214266530927446505441293867364660302604331637965426760460831021145457230401267539479461666597608930411947331682395413228540621732951917884251567852835625413715394414182100
val=55719322748654060909881801139095138877488925481861026479419112168355471570782990525463281061887475459280827193232049926790759656662867804019857629447612576114575389970078881483945542193937293462467848252776917878957280026606366201486237691429546733291217905881521367369936019292373732925986239707922361248585
# Create problem (for the demo)
K = ZZ.random_element(0, 2^Kbits)
Kdigits = K.digits(2)
M = [0]*Kbits + [1]*(length_N-Kbits);
for i in range(len(Kdigits)):
M[i] = Kdigits[i]
M = ZZ(M, 2)
C = ZmodN(M)^e
# Problem to equation (default)
P.<x> = PolynomialRing(Zmod(n)) #, implementation='NTL')
f = (pow(2,e,n)*(x)**3) + pow(3,e,n)*(x)**2 + pow(5,e,n)*(x) + pow(7,e,n) -val
f=f.monic()
# Coppersmith
start_time = time.time()
roots = coppersmith_howgrave_univariate(f, n, 1, 4, 12, 2^64)
# output
print("we found:", str(roots))from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Hash import SHA256
import random
import binascii
import math
n=141100651008173851466795684636324450409238358207191893767666902216680426313633075955718286598033724188672134934209410772467615432454991738608692590241240654619365943145665145916032591750673763981269787196318669195238077058469850912415480579793270889088523790675069338510272116812307715222344411968301691946663
e=65537
c=115338511096061035992329313881822354869992148130629298132719900320552359391836743522134946102137278033487970965960461840661238010620813848214266530927446505441293867364660302604331637965426760460831021145457230401267539479461666597608930411947331682395413228540621732951917884251567852835625413715394414182100
val=55719322748654060909881801139095138877488925481861026479419112168355471570782990525463281061887475459280827193232049926790759656662867804019857629447612576114575389970078881483945542193937293462467848252776917878957280026606366201486237691429546733291217905881521367369936019292373732925986239707922361248585
delta = 16660334173862742020
m = (pow(2,e)*pow(delta,3) + pow(3,e)*pow(delta,2) + pow(5,e)*delta + pow(7,e)) %n
tmp = (val-m)%n
q=math.gcd(tmp,n)
p=n//q
phi = (p-1)*(q-1)
d= pow(e,-1,phi)
key = RSA.construct((n,e,d,p,q))
cipher = PKCS1_OAEP.new(key=key,hashAlgo=SHA256)
flag = cipher.decrypt(long_to_bytes(c))
print(flag)
#crew{m0dp_3qu4710n_l34d5_u5_f4c70r1n6}Thanks for reading. Have a good day โค๏ธ !
Contact:
