Non Zero Knowledge Proof - ECSC
Challenge:
https://hack.cert.pl/challenge/nzkp
import itertools
import sys
import random
import string
from Crypto.Util.number import getPrime, bytes_to_long
from functools import reduce
################ BOILERPLATE, YOU CAN IGNORE THIS ################
def multiply(values):
"""
Multiply values on the list
:param values: list of values
:return: a*b*c*d...
"""
import functools
return functools.reduce(lambda x, y: x * y, values, 1)
def solve_crt(residue_and_moduli):
"""
Solve CRT for given modular residues and modulus values, eg:
x = 1 mod 3
x = 2 mod 4
x = 3 mod 5
x = 58
residue_and_moduli = [(1,3), (2,4), (3,5)]
:param residue_and_moduli: list of pairs with (modular residue mod n, n)
:return: x
"""
residues, moduli = zip(*residue_and_moduli)
N = multiply(moduli)
Nxs = [N // n for n in moduli]
ds = [modinv(N // n, n) for n in moduli]
mults = [r * Nx * d for r, Nx, d in zip(residues, Nxs, ds)]
return reduce(lambda x, y: x + y, mults) % N
def extended_gcd(a, b):
"""
Calculate extended greatest common divisor of numbers a,b
:param a: first number
:param b: second number
:return: gcd(a,b) and remainders
"""
def copysign(a, b):
return a * (1 if b >= 0 else -1)
lastrem, rem = abs(a), abs(b)
x, lastx, y, lasty = 0, 1, 1, 0
while rem:
lastrem, (quotient, rem) = rem, divmod(lastrem, rem)
x, lastx = lastx - quotient * x, x
y, lasty = lasty - quotient * y, y
return lastrem, copysign(lastx, a), copysign(lasty, b)
def gcd(a, b):
"""
Return simple greatest common divisor of a and b
:param a:
:param b:
:return: gcd(a,b)
"""
return extended_gcd(a, b)[0]
def modinv(x, y):
"""
Return modular multiplicative inverse of x mod y.
It is a value d such that x*d = 1 mod y
:param x: number for which we want inverse
:param y: modulus
:return: modinv if it exists
"""
return extended_gcd(x, y)[1] % y
def modular_sqrt_composite(c, factors):
"""
Calculates modular square root of composite value for given all modulus factors
For a = b^2 mod p*q*r*m... calculates b
:param c: residue
:param factors: list of modulus prime factors
:return: all potential root values
"""
n = multiply(factors)
roots = [[(modular_sqrt(c, x), x), (x - modular_sqrt(c, x), x)] for x in factors]
solutions = []
for x in itertools.product(*roots):
solution = solve_crt(list(x))
solutions.append(solution)
assert solution ** 2 % n == c
return solutions
def modular_sqrt(a, p):
"""
Calculates modular square root with prime modulus.
For a = b^2 mod p calculates b
:param a: residue
:param p: modulus
:return: root value
"""
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return p
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1
n = 2
while legendre_symbol(n, p) != -1:
n += 1
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
def legendre_symbol(a, p):
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
def pad(flag, nbits):
missing = nbits // 8 - len(flag)
return flag + ''.join(random.choices(string.ascii_letters, k=missing)).encode()
################ END OF BOILERPLATE ################
def main():
bits = 1024
p = getPrime(bits)
q = getPrime(bits)
n = p * q
print(
"Interactive ZKP based on Rabin cryptosystem. Provide encrypted challenge value (r^2 mod n such that r%10 == 0) and I will decrypt it to prove I have the private key.")
print(n)
sys.stdout.flush()
for i in range(32):
try:
c = int(input("challenge>\n"))
roots = modular_sqrt_composite(c, [p, q])
valid_decryption = [r for r in roots if r % 10 == 0]
print(valid_decryption[0])
sys.stdout.flush()
except:
print("Please provide only challenges ending with 0, so I can distinguish the real root!")
sys.stdout.flush()
return
print(pow(bytes_to_long(pad(open("flag.txt", "rb").read(), bits)), 2, n))
sys.stdout.flush()
main()
Solve:
https://crypto.stackexchange.com/questions/96060/rabin-cryptosystem-chosen-ciphertext-attack
from os import environ
environ['TERM'] = 'konsole'
from Crypto.Util.number import *
from pwn import *
from tqdm import trange
while True:
while True:
io = remote('nzkp.ecsc22.hack.cert.pl', 18665)
io.recvline()
n = int(io.recvline())
io.recvline()
r = randint(0, n)
c = pow(r, 2, n)
io.sendline(str(c).encode())
recv = io.recvline()
print(recv)
if b'Please provide only' in recv:
io.close()
continue
break
t = int(recv)
p = gcd(r-t, n)
print(f'{p = }')
if 1<p<n:
break
print('retrying......')
q = n//p
for _ in trange(31):
io.recvline()
io.sendline(str(c).encode())
io.recvline()
flagenc = int(io.recvline())
pari.addprimes([p, q])
for flag in Zmod(n)(flagenc).sqrt(all=True):
flag = long_to_bytes(int(flag))
if b'ecsc' in flag:
print(flag)
# ecsc{H3y_R4bbi_Wh4tch4_D0in_l3ak1ng_fl4gs}