Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
yud121212
GitHub Repository: yud121212/Coppersmith-s-Short-Pad-Attack-Franklin-Reiter-Related-Message-Attack
 Path: blob/master/coppersmiths_short_pad_attack.sage
117 views
1
# source code http://inaz2.hatenablog.com/entry/2016/01/20/022936

2


3


4
def short_pad_attack(c1, c2, e, n):

5


6
    PRxy.<x,y> = PolynomialRing(Zmod(n))

7


8
    PRx.<xn> = PolynomialRing(Zmod(n))

9


10
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

11


12


13
    g1 = x^e - c1

14


15
    g2 = (x+y)^e - c2

16


17


18
    q1 = g1.change_ring(PRZZ)

19


20
    q2 = g2.change_ring(PRZZ)

21


22


23
    h = q2.resultant(q1)

24


25
    h = h.univariate_polynomial()

26


27
    h = h.change_ring(PRx).subs(y=xn)

28


29
    h = h.monic()

30


31


32
    kbits = n.nbits()//(2*e*e)

33


34
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

35


36


37
    return diff

38


39


40
def related_message_attack(c1, c2, diff, e, n):

41


42
    PRx.<x> = PolynomialRing(Zmod(n))

43


44
    g1 = x^e - c1

45


46
    g2 = (x+diff)^e - c2

47


48


49
    def gcd(g1, g2):

50


51
        while g2:

52


53
            g1, g2 = g2, g1 % g2

54


55
        return g1.monic()

56


57


58
    return -gcd(g1, g2)[0]

59


60


61


62
if __name__ == '__main__':

63


64
    n = 103812409689464886276475047044770609297885893720146571798654593885477457188425375786047017735691464865799751262776976174291152757506033948402223696021505470811665108707476725788296289255777914656800454451779117367605227364391483323666809650532860469176398816220707851639905500304208833022438234033264200398959

65


66
    e = 3

67


68


69
    C1 = 9317106922634505445328279149755295612464875825943780841886193649700131610057100771444165757592479299555845021862440454968502065319770337331674061960123779876709748994547507057835826773522733671492329400557540100987018908395372213360970889608191940631081957498661950679566048064234326337242245437800870328713

70


71
    C2 = 9314352234311777268152500810432217195086739647228997430466360767070638972017377674642639833356580951663634114522574738957708645348438979256455824440476178459296267056062724307782801856615506577790281367843133061096735566462588088807072141910079117362448136849082448630141871675817981866725491776400151339928

72


73
    C3 = 102298788718908831383454512674839558060033746080468660252243145800572734468521296602058538109452538907204027081338987796558296639830757629468491322438048912956916198524821066676689795698612028521062296901313097979278633376983280108123961097977187251599033620058543603046291262367128490175209233898073639549204

74


75


76
    nbits = n.nbits()

77


78
    kbits = nbits//(2*e*e)

79


80
    print "padding lenght %d bytes " % (kbits/8)

81


82
    print "upper %d bits (of %d bits) is same" % (nbits-kbits, nbits)

83


84


85
 

86


87
    diff = short_pad_attack(C1, C2, e, n)

88


89
   #print "difference of two messages C1 and C2 is %d" % diff

90


91
    m = related_message_attack(C1, C2, diff, e, n)

92


93
    M1 = hex(int(m))[2:-1].decode('hex')

94


95
    M2 = hex(int(m+diff))[2:-1].decode('hex')

96


97
    print "Message of C1 is ", M1

98


99
    print "Message of C2 is ", M2

100


101


102


103
    diff = short_pad_attack(C1, C3, e, n)

104


105
    #print "difference of two messages C1 and C3 is ", diff

106


107
    M3 = hex(int(m+diff))[2:-1].decode('hex')

108


109
    print "Message of C3 is ", M3

110


111


112
    print "Flag: ", M1[-6:] + M2[-6:] +M3[-6:]

113


114