Frozen like there is no sun, yet, we know the Meltdown will be arriving soon!
Files given:
d = 32
def keygen(params, l, d):
p, r = params
s = getRandomRange(1, p)
U = [pow(r, c + 1, p) * s % p for c in range(0,l)]
V = [int(bin(u)[2:][:-d] + '0' * d, 2) for u in U]
S = [int(bin(u)[2:][-d:], 2) for u in U]
privkey, pubkey = S, V
return pubkey, privkey
def sign(msg, privkey, d):
msg = msg.encode('utf-8')
l = len(msg) // 4
M = [bytes_to_long(msg[4*i:4*(i+1)]) for i in range(l)]
q = int(next_prime(max(M)))
sign = [M[i]*privkey[i] % q for i in range(l)]
return sign
This challenge gives a server with \(4\) options:
| Options:
| [S]how the params - gives p,r
| [P]rint pubkey - gives pubkey
| [E]xample signature - gives signature of random 20 char string
| [F]orge the signature - asks signature of random 20 char string
| [Q]uit
Looking at the signing function, we can easily recover privkey[i] % q given the message and since \(256^4=2^{32}\), this almost recovers the entire privkey[i], so we only need to add a small multiple of \(q\). Seeing the keygen function, we know that after adding the private and public key together, we should get a geometric series. This will tell us when we are done adding multiples of \(q\). From here the brute force is quite simple.
Solution at solve.py
Flag:
CCTF{Lattice_bA5eD_T3cHn1QuE_70_Br34K_LCG!!}