# Crew CTF 2022

![](/files/EevtMonY7dipcxboJp3F)

### ez-x0r

```
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}

### The HUGE e

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 = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613
```

solve

```
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))
```

### Malleable Metal

```
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 = }')
```

![](/files/mVrlGNjlb456UuQBSvr3)

### toydl

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")
```

### Delta

```
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 :heart: !

Contact:

* <img src="/files/A6pMYo8ds6Z4t9ocwsvc" alt="" data-size="line">[<mark style="color:blue;">facebook</mark> ](https://www.facebook.com/rong.truong.372)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://giongfnef.gitbook.io/giongfnef/writeup-ctf/crypto/crew-ctf-2022.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.