Instantly share code, notes, and snippets.

# elliptic-shiho/ed25519.py

Created April 18, 2016 00:11
Show Gist options
• Save elliptic-shiho/f41fd75cc30646a61d7ad63043fdd56e to your computer and use it in GitHub Desktop.
sCTF 2016 Q1: Ed25519 Writeup
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import hashlib b = 256 q = 2**255 - 19 l = 2**252 + 27742317777372353535851937790883648493 def H(m): return hashlib.sha512(m).digest() def expmod(b,e,m): return pow(b, e, m) def inv(x): return expmod(x,q-2,q) d = -121665 * inv(121666) I = expmod(2,(q-1)/4,q) def xrecover(y): xx = (y*y-1) * inv(d*y*y+1) x = expmod(xx,(q+3)/8,q) if (x*x - xx) % q != 0: x = (x*I) % q if x % 2 != 0: x = q-x return x By = 4 * inv(5) Bx = xrecover(By) B = [Bx % q,By % q] def edwards(P,Q): x1 = P[0] y1 = P[1] x2 = Q[0] y2 = Q[1] x3 = (x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2) y3 = (y1*y2+x1*x2) * inv(1-d*x1*x2*y1*y2) return [x3 % q,y3 % q] def scalarmult(P,e): if e == 0: return [0, 1] bits = map(int, bin(e)[2:])[::-1] x = P if bits[0]: res = x else: res = [0, 1] for cur in bits[1:]: x = edwards(x, x) if cur: res = edwards(res, x) return res def encodeint(y): bits = [(y >> i) & 1 for i in range(b)] return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)]) def encodepoint(P): x = P[0] y = P[1] bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1] return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)]) def bit(h,i): return (ord(h[i/8]) >> (i%8)) & 1 def publickey(sk): h = H(sk) a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) A = scalarmult(B,a) return encodepoint(A) def Hint(m): h = H(m) return sum(2**i * bit(h,i) for i in range(2*b)) def signature(m,sk,pk): h = H(sk) a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) r = Hint(''.join([h[i] for i in range(b/8,b/4)]) + m) R = scalarmult(B,r) S = (r + Hint(encodepoint(R) + pk + m) * a) % l return encodepoint(R) + encodeint(S) def isoncurve(P): x = P[0] y = P[1] return (-x*x + y*y - 1 - d*x*x*y*y) % q == 0 def decodeint(s): return sum(2**i * bit(s,i) for i in range(0,b)) def decodepoint(s): y = sum(2**i * bit(s,i) for i in range(0,b-1)) x = xrecover(y) if x & 1 != bit(s,b-1): x = q-x P = [x,y] if not isoncurve(P): raise Exception("decoding point that is not on curve") return P def checkvalid(s,m,pk): if len(s) != b/4: raise Exception("signature length is wrong") if len(pk) != b/8: raise Exception("public-key length is wrong") R = decodepoint(s[0:b/8]) A = decodepoint(pk) S = decodeint(s[b/8:b/4]) h = Hint(encodepoint(R) + pk + m) if scalarmult(B,S) != edwards(R,scalarmult(A,h)): raise Exception("signature does not pass verification")
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import ed25519 import gmpy def modinv_p(a, p): assert gmpy.is_prime(p) return pow(a, p-2, p) pk = "5bfcb1cd3938f3f6f3092da5f7d7a1bdb1d694a725d0585a99208787554e110d".decode("hex") s1 = "68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de8e2224855125b1acbeab1468bf4860c1eeb05b6d2375e2214c55bdfe808a6c106".decode("hex") m1 = "sctf.io" s2 = "68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de825ad01a05a0cce69258d41d42ed046956e7d4586eb21ff031bf8ac03243d5e04".decode("hex") m2 = "2016 Q1" # check ed25519.checkvalid(s1, m1, pk) ed25519.checkvalid(s2, m2, pk) P = ed25519.decodepoint(pk) a = 0 R1 = ed25519.decodepoint(s1[:ed25519.b/8]) S1 = ed25519.decodeint(s1[ed25519.b/8:ed25519.b/4]) h1 = ed25519.Hint(ed25519.encodepoint(R1) + pk + m1) R2 = ed25519.decodepoint(s2[:ed25519.b/8]) S2 = ed25519.decodeint(s2[ed25519.b/8:ed25519.b/4]) h2 = ed25519.Hint(ed25519.encodepoint(R2) + pk + m2) print R1, S1, h1 print R2, S2, h2 a = ((S1 - S2) * modinv_p(h1 - h2, ed25519.l)) % ed25519.l r1 = (S1 - h1 * a) % ed25519.l r2 = (S2 - h2 * a) % ed25519.l print r1, r2 f = "the flag" r = r1 R = ed25519.scalarmult(ed25519.B, r) S = (r + ed25519.Hint(ed25519.encodepoint(R) + pk + f) * a) % ed25519.l print "Flag is sctf{%s}" % ((ed25519.encodepoint(R) + ed25519.encodeint(S)).encode("base64").replace("\n", ""))

### elliptic-shiho commented Apr 18, 2016 • edited

Writeup: Breaking Ed25519 with same random key.

Trivial algebraic practice.

``````Mon Apr 18 09:11:09 JST 2016 ~/ctf/sctf-2016-q1/crypto40/ed25519 Battery 0: Full, 100%
> time python solve.py
[28104680254895858602950095340273610962152604410683289209133586156927824858805L, 47318893950578276168317079672385112889584626339324959120861701577279184447848L] 3056024505099303091264038272914434090600937271399321803322554667848809587426 13397442584040240938586667532063254484324168699882605334802284616584255557111053955417396865311479649066713941214800499812450892230427570948701676049481822
[28104680254895858602950095340273610962152604410683289209133586156927824858805L, 47318893950578276168317079672385112889584626339324959120861701577279184447848L] 1975756995894560183473395863515241874506266339720132698812345799672898628901 7960866852339352189900001165174010281146836611057896297646402284319532015956538563906002724988794309980855750528647709587915541142579171768379987340263132
117 117
Flag is sctf{aCmaUba1kuLbg8Jso1lL3YG9u58RxZeh3rgj2nyLneh12Mf7NAvaREdBikQrkpWSa3UT15wUmunsrceSa3CUCQ==}

real    0m0.910s
user    0m0.901s
sys     0m0.008s
``````