Really Secure Algorithm

Wiener's attack on RSA

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.

"""
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**"