Crew CTF 2022

Note : A JOURNEY TO GAIN KNOWLEDGE

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

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 ❤️ !

Contact:

facebook

PreviousdvCTF 2022 NextångstromCTF 2022

Last updated 3 years ago

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