# Really Secure Algorithm

## Problem

I like my e's like I like my trucks: big and obnoxious

Author: trashcanna

## Solution

Recall that *e* is chosen such that

$$
ed=1\pmod{\text{lcm}(p-1, q-1)}
$$

In this case, *e* is really large (only one order of magnitude smaller than *n*). This suggests that *d* might be small. When *d* is small, Wiener's attack would work.

![](/files/-M_EIv2_2wUuPolxu__w)

```python
"""
MxRy - 2016 - Wiener's attack 
useful link : http://math.unice.fr/~walter/L1_Arith/cours2.pdf
"""
import math

def DevContinuedFraction(num, denum) :
    partialQuotients = []
    divisionRests = []
    for i in range(int(math.log(denum, 2)/1)) :
        divisionRests = num % denum
        partialQuotients.append(num / denum)
        num = denum
        denum = divisionRests
        if denum == 0 :
            break
    return partialQuotients

""" (cf. useful link p.2) Theorem :
p_-2 = 0 p_-1 = 1   p_n = a_n.p_n-1 + p_n-2
q_-2 = 1 q_-1 = 0   q_n = a_n.q_n-1 + q_n-2 
"""
def DivergentsComputation(partialQuotients) :
    (p1, p2, q1, q2) = (1, 0, 0, 1)
    convergentsList = []
    for q in partialQuotients :
        pn = q * p1 + p2
        qn = q * q1 + q2
        convergentsList.append([pn, qn])
        p2 = p1
        q2 = q1
        p1 = pn
        q1 = qn
    return convergentsList    

"""  
https://dzone.com/articles/cryptographic-functions-python
Be careful to physical attacks see sections below
"""
def SquareAndMultiply(base,exponent,modulus):
    binaryExponent = []
    while exponent != 0:
        binaryExponent.append(exponent%2)
        exponent = exponent/2
    result = 1
    binaryExponent.reverse()
    for i in binaryExponent:
        if i == 0:
            result = (result*result) % modulus
        else:
            result = (result*result*base) % modulus
    return result

def WienerAttack(e, N, C) :
    testStr = 42 
    C = SquareAndMultiply(testStr, e, N)
    for c in DivergentsComputation(DevContinuedFraction(e, N)) :
        if SquareAndMultiply(C, c[1], N) == testStr :
            FullReverse(N, e, c)
            return c[1]
    return -1

"""
Credit for int2Text : 
https://jhafranco.com/2012/01/29/rsa-implementation-in-python/
"""
def GetTheFlag(C, N, d) :
    p = pow(C, d, N)
    print p
    size = len("{:02x}".format(p)) // 2
    print "Flag = "+"".join([chr((p >> j) & 0xff) for j in reversed(range(0, size << 3, 8))])

"""
http://stackoverflow.com/questions/356090/how-to-compute-the-nth-root-of-a-very-big-integer
"""
def find_invpow(x,n):
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

"""
On reprend la demo on cherche (p, q), avec la recherche des racines du P
de scd degre : x^2 - (N - phi(N) + 1)x + N
"""
def FullReverse(N, e, c) :
    phi = (e*c[1]-1)//c[0]
    a = 1
    b = -(N-phi+1)
    c = N
    delta =b*b - 4*a*c
    if delta > 0 :
        x1 = (-b + find_invpow((b*b - 4*a*c), 2))/(2*a)
        x2 = (-b - find_invpow((b*b - 4*a*c), 2))/(2*a)
        if x1*x2 == N :
            print "p = "+str(x1)
            print "q = "+str(x2)
        else :
            print "** Error **"
    else :
        print "** ERROR : (p, q)**"

"""
Si N, e, C en hex ::> int("0x0123456789ABCDEF".strip("0x"), 16)
"""
if __name__ == "__main__":
    C = 329889278578044016824313741527705229624826354380113199851837764563746872233807021113693371778072747023303193661391256917654673579748983619101229337776995574989101525295578632981918777232038222679949264372167418981038519164359046193397794833575692294838270919137212503594644756884879905102382013616716795766055806380675079122193261937202152727372307035197702671407008933906723580158843896939160889881874945976423829414877735269690727711347872615864084627631956403177338185780100778564548976884299086453421725163428017908949325966904530291069025584097022695816511626589485257615664532774194555809017763622197728156453680059300808277471558450818004384751746190317910501772671219117514746584045928056487904112720801176609889740173288130073788687010544220250814378467249611243953690831406523455960639957029937819775398561228599467536715020954136970283137688613486109370883547218314163119613810764259334933209435078926856747403933578685724271075988136268967520808025339001863614193092075106995811355116213778057037256625729238040020810096266917394213617319914026291093309897483557317625696133298013326746629673265558468135602690674704939910172338556035967840157228859997765219241095551758253889312610691956445984657535082546460420349808372702307807697037778668585720318640246334216650054353036505301550387620089144331383076791604944171531121861009872807022569971425034887955393207445086587528972631782104261610625226982484798915695532492666822649105680868782554501246818156815043534857204078057748607289822387462529373683511672270708474273078574153649263666927268413520984191265086647728912692418609093325194826161869428270138209430215739290181617579745939639392608498596400274014103435747462262045586624613109970954762445247628187031774393639286689201449970646288560996969456145518290732375783779950601901268751888374247634804346090070762202809312421725537938059723148831745384765961875359917754708570262909323774973728101735046489385116839098154905761289565030660932858839402457684704605894701939226586411257561719440368089980555960049063794123068432799043630558103308335378100690170353973384441557259766075780510887009923794374174414344793891145106172614982174022423725641446878993111773629101974963001417653742183922637679467704643683488299451383820099923197374567580088833681469257525555566554059017269673597621231456370183587051700138951722854738823417346171701112221512801669470086625272428387110466009926633732340715338158014022960380535876415340423270463298180055 
    e = 322080206518256091443899533297838582806903462189212623492459529527398362853578807723331748892091281476489691674322396825893568981731186597175657851460964692083587224231830304595753200276915353388440323973696723177120007866661510911934423352216586106031397002127519163858107192766128665700540985814443511274004469695128927172454976219787146706562954392698315026949257322529441349029783228167181158744356828575460114272675952388130344874175195393881248661753342888300368969470477541152888408256683251028110005741172636776279619483668723660512026112365800539035538500635904281702733475127339140385714006560153071610279780303018848372325359598739283968138816333125764253403325773002607652913882484078902775827169048401031393263955166695217841400017855979724317225872294531492451624247032809524082714281043873127461832051383511298796820369453358960824162684362741938604084210435623099328622028419710290325683380378726085007158903982932912214314158223921219724759717266136246703830446993309980595073110001804483058339461412460693911416430728558495048873597685942089531373734578638349738930086910038003088294940942692030998047041393152747526278088574238755027474019265539054527491401757165011505470582647900401492273402847703170162847259159161319094910753659832147964969052296859561769298825881593753592121708897035728873795159475926749806998737812501868665513946666352941497086651818553871606417281352599234688183547212675353626023151426982640664474136377374110023532481101565870359846621748326349516467938614155834462639061592390266451169971250010491497379073868786106821570448253182042906240682833067783409574735400739329311810053094530811477002973464432651755811246151509011287858077298295987954915889199100328695730233096226912526329144478198121096489396083876129542516602969866961376423685647767885680559757094208574124411496017291060228388949556065235333802142865557844913535276572535282671404020237763405558477020152910105019008364237315330047605257380696367871417207254833979064342650664181309067142909106945469319731754805506564282047041605728503555870882010025649797753726253285119740979484849951129514070748168270413416940958393138417596025358589062839735425553556206423183484639265605269615685651949641759227283257819425264608389110223455267792764547470141745830149226062457331548317230637497633273069300415564503833751637575125936072041989787691982221885384446295804003751739608564016981200019839941768866474797817202494560129096305497153712068566001154013937
    N = 1063494238636905330671898279123020701722241177838742822812173978727720269828464796177466331816675300997219760473399150899338190503499441304612339501295713174906319744094945565844664372365921409430229356934682156557249826723147031652843433859344718768493183522524995480377138743798310313783408725321419870843554822150601536373735923419276343616677440442774544203945706641152517137477442684440329779076981535293867470891276594740058202983415251883426242386508849130959905432961654910957147313116759921173654729071152981682554792584462863534617943384988632032130835087976957452863581161399454295389753849954195624356779281196493728732643445649356033158461867533398892265000228558146288424480232820613034689816560319929705959290376265550914058448343308161173100473161643834475548888676356572581129193395124610558172636505697071928778350452726229098387020587814634712035171712313035012109421792643188405752849278190287414108308734638519593282032082768153331276317440224645157072560878195004847185217741752846484430459047014205368551175641186962966731731946128786111994668528579102737764964521437485037695161775036622411218739549286577109028626220150452705854596994751235894610227300222070678106023292138580496517177268042770934391185798181598618563332872419401223903806812404310665174941843727792999745655534108889130325189241267039092501129173520194489329592776789648244263220437261594447066833175026748830694496235756029688061559449109400248449366143822446893851310444152168531390880512280359096438303124398155397910138799660941243464476642041104225318910175143988510614445494598098558426300612294667831401095538851181871031466580808942102239297182977785401087460226345045290147371931284725756179151791539310603340196586480494033673522637677423221202352493653286430691931273676649062037570851083535722738207802574643773975006788646467981693396925922930573766914743566111012462215653872417726475122775377641591778444141816733462035690735543990556767891443301312941168828619850007793197693295002346977318117653857994731382292035666024397790972920502626243999541832942059274728220802530163223188484361653845185336386588669397688474323385816925410493569923865462650449548121898936835205060632513390578074550881170405889665319159308800795056447244869407145217360018494614236328487464266591617854909647808315406639117270321158016494893469025866752746911948790708005075752364953010067274475470453957941422189404716860354111166203043679764568407375052809648827400302926099178569

    print "e : "+str(e)
    print "N : "+str(N)
    print "C : "+str(C)
    d = WienerAttack(e, N, C)
    if d != -1 :
        print "d = "+str(d)
        GetTheFlag(C, N, d)
    else :
        print "** ERROR : Wiener's attack Impossible**"
```


---

# 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://ctf.zeyu2001.com/2021/dawgctf-2021/really-secure-algorithm.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.