# writeup at http://mslc.ctf.su/wp/gctf2017quals-insanity-check/ | |
from sage.all import * | |
Y = 4675975961034321318962575265110114310875697301524971406479091223605006115642041321079605682629390144148862285125353335575850114862081357772478008490889403608973023515499959473374820321940514939155187478991555363073408293339373770407404120884229693036839637631846964085605936966005664594330150750220123106270473482589454510979171010750141467635389981140248292523060541588378749922037870081811431605806877184957731660006793364727129226828277168254826229733536459158767652636094988369367622055662565355698632032334469812735980006733267919815359221578068741143213061033728991446898051375393719722707555958912382769606279 | |
P = 32163437489387646882545837937802838313337646833974044466731567532754579958012875893665844191303548189492604123505522382770478442837553069890471993483164949504735527438665048438808440494922021062011062567528480025060283867381823427214512155583444236623145440836252289902783715682554658231606320310129833109191138313801289027627739243726679212643242494506530838323607821437997048235272405577079630284307474612832155381483129670050964475785090109743586694668757059662450206919471125303517989042945192886030308203029077484932328302318567286732217365609075794327329327141979774234522455646843538377559711464098301949684161 | |
Q = 81090202316656819994650163122592145880088893063907447574390172288558447451623 | |
H = 88030618649759997479497646248126770071813905558516408828543254210959719582166 | |
R = 34644971883866574753209424578777685962679178432833890467656897732184789528635 | |
S = 19288448359668464692653054736434794709227686774726460500150496018082350808676 | |
G = pow(2, int(P//Q), P) | |
A = (-R) * inverse_mod(S, Q) % Q | |
B = (-H) * inverse_mod(S, Q) % Q | |
while 1: | |
XB = 125 | |
KB = 125-16 | |
X = 2**XB | |
K = 2**KB | |
khigh = randint(0, 2**16) | |
Bnew = B + khigh * 2**KB | |
m = matrix(ZZ, 3, 3, [ | |
Q, 0, 0, | |
0, Q * X, 0, | |
Bnew, A * X, K | |
]).LLL() | |
mat = [] | |
target = [] | |
for row in m[:2]: | |
const, cx, ck = row | |
assert cx % X == 0 and ck % K == 0 | |
mat.append([cx / X, ck / K]) | |
target.append(-const) | |
mat = matrix(ZZ, mat) | |
try: | |
x0, k0 = mat.solve_right(vector(ZZ, target)) | |
if int(x0) != x0 or int(k0) != k0: | |
continue | |
except ValueError: | |
continue | |
x0, k0 = int(x0), int(k0) | |
assert (A * x0 + k0 + Bnew) % Q == 0 | |
k0 += khigh * 2**KB | |
assert (A * x0 + k0 + B) % Q == 0 | |
print "SOLUTION", x0, k0 | |
print "SIZE %.02f %.02f" % (RR(log(abs(x0), 2)), RR(log(abs(k0), 2))) | |
break | |
BOUND1 = 10**7 | |
BOUND2 = 10**7 | |
MZ = matrix(ZZ, 2, 2, [ | |
[1, -A], | |
[0, Q], | |
]).LLL() | |
DX1 = abs(MZ[0][0]) | |
DX2 = abs(MZ[1][0]) | |
print "STEP1" | |
table = {} | |
step = pow(G, DX2, P) | |
curg = Y * inverse_mod( int(pow(step, BOUND1, P)), P ) % P | |
cure = -BOUND1 | |
for i in xrange(-BOUND1, BOUND1): | |
if i % 100000 == 0: | |
print i / 100000, "/", BOUND1 / 100000 | |
assert curg not in table | |
table[curg] = cure | |
curg = (curg * step) % P | |
cure += 1 | |
print "STEP2" | |
step = pow(G, DX1, P) | |
curg = pow(G, x0 - DX1 * BOUND2, P) | |
cure = -BOUND2 | |
for i in xrange(-BOUND2, BOUND2): | |
if i % 100000 == 0: | |
print i / 100000, "/", BOUND2 / 100000 | |
if curg in table: | |
print "Solved!", cure, table[curg] | |
ans = x0 + cure * DX1 - table[curg] * DX2 | |
print "Flag: CTF{%d}" % ans | |
break | |
curg = (curg * step) % P | |
cure += 1 |
/** | |
* Print a Flag. | |
* @author Daniel Bleichenbacher | |
*/ | |
package blt; | |
import java.math.BigInteger; | |
import java.security.MessageDigest; | |
import java.security.SecureRandom; | |
import java.security.GeneralSecurityException; | |
public class Flag { | |
// Generate a random integer in the range 1 .. q-1. | |
private static BigInteger generateSecret(BigInteger q) { | |
// Get the number of bits of q. | |
int qBits = q.bitCount(); | |
SecureRandom rand = new SecureRandom(); | |
while (true) { | |
BigInteger x = new BigInteger(qBits, rand); | |
if (x.compareTo(BigInteger.ZERO) == 1 && x.compareTo(q) == -1) { | |
return x; | |
} | |
} | |
} | |
private static BigInteger hashMessage(byte[] message) throws Exception { | |
byte[] digest = MessageDigest.getInstance("SHA-256").digest(message); | |
return new BigInteger(1, digest); | |
} | |
private static BigInteger[] sign( | |
byte[] message, | |
BigInteger p, | |
BigInteger q, | |
BigInteger g, | |
BigInteger x) throws Exception { | |
while (true) { | |
BigInteger h = hashMessage(message); | |
BigInteger k = generateSecret(q); | |
BigInteger r = g.modPow(k, p).mod(q); | |
BigInteger s = k.modInverse(q).multiply(h.add(x.multiply(r))).mod(q); | |
if (r.equals(BigInteger.ZERO) || s.equals(BigInteger.ZERO)) continue; | |
return new BigInteger[]{r,s}; | |
} | |
} | |
/** | |
* This code generates a flag. | |
*/ | |
public static void main(String[] args) throws Exception { | |
// p is a 2048 bit prime number. | |
BigInteger p = new BigInteger(args[0]); | |
// q is a 256-bit prime number that divides p-1. | |
BigInteger q = new BigInteger(args[1]); | |
// g is a generator of order q. (I.e. 1 = g**q mod p) | |
BigInteger g = new BigInteger("2").modPow(p.divide(q), p); | |
// generate the private key | |
BigInteger x = generateSecret(q); | |
BigInteger y = g.modPow(x, p); | |
System.out.println("Y:" + y.toString()); | |
System.out.println("P:" + p.toString()); | |
System.out.println("Q:" + q.toString()); | |
byte[] message = ("CTF{" + x.toString() + "}").getBytes(); | |
System.err.println("Flag: " + new String(message)); | |
System.out.println("H:" + hashMessage(message).toString()); | |
BigInteger[] sig = sign(message, p, q, g, x); | |
System.out.println("R:" + sig[0].toString()); | |
System.out.println("S:" + sig[1].toString()); | |
} | |
} |
Y:4675975961034321318962575265110114310875697301524971406479091223605006115642041321079605682629390144148862285125353335575850114862081357772478008490889403608973023515499959473374820321940514939155187478991555363073408293339373770407404120884229693036839637631846964085605936966005664594330150750220123106270473482589454510979171010750141467635389981140248292523060541588378749922037870081811431605806877184957731660006793364727129226828277168254826229733536459158767652636094988369367622055662565355698632032334469812735980006733267919815359221578068741143213061033728991446898051375393719722707555958912382769606279 | |
P:32163437489387646882545837937802838313337646833974044466731567532754579958012875893665844191303548189492604123505522382770478442837553069890471993483164949504735527438665048438808440494922021062011062567528480025060283867381823427214512155583444236623145440836252289902783715682554658231606320310129833109191138313801289027627739243726679212643242494506530838323607821437997048235272405577079630284307474612832155381483129670050964475785090109743586694668757059662450206919471125303517989042945192886030308203029077484932328302318567286732217365609075794327329327141979774234522455646843538377559711464098301949684161 | |
Q:81090202316656819994650163122592145880088893063907447574390172288558447451623 | |
H:88030618649759997479497646248126770071813905558516408828543254210959719582166 | |
R:34644971883866574753209424578777685962679178432833890467656897732184789528635 | |
S:19288448359668464692653054736434794709227686774726460500150496018082350808676 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment