Category: Crypto
Points: 200
Description:
The flag is encrypted by this code, can you decrypt it after finding the system?
Write-up:
The code is written in python.
#!/usr/bin/python
flag = # censored
from gmpy import next_prime, invert
from random import randint
from hashlib import sha1
def makey():
q = next_prime(randint(1, 2**1024))
x1 = next_prime(randint(1, q-1))
x2 = next_prime(x1)
y1 = next_prime(x2)
y2 = next_prime(y1)
z = next_prime(y2)
g1 = next_prime(z)
g2 = next_prime(g1)
c = divmod(pow(g1, x1, q)*pow(g2, x2, q), q)[1]
d = divmod(pow(g1, y1, q)*pow(g2, y2, q), q)[1]
h = pow(g1, z, q)
pubkey = (q, g1, g2, c, d, h)
privkey = (x1, x2, y1, y2, z)
return (pubkey, privkey)
def encrypt(m, pubkey):
q, g1, g2, c, d, h = pubkey
k = randint(1, q-1)
u1 = pow(g1, k, q)
u2 = pow(g2, k, q)
m = int(m.encode('hex'), 16)
e = divmod(pow(h, k, q)*m, q)[1]
alpha = sha1(str(u1) + str(u2) + str(e)).hexdigest()
v = divmod(pow(c, k, q)*pow(d, int(alpha, 16)*k, q), q)[1]
return (u1, u2, e, v)
pubkey, privkey = makey()
print pubkey
c = encrypt(flag, pubkey)
print c
This cryptosystem is like this:
1. Alice generates public key and private key:
1) choose a big prime q as modulus
2) choose big primes x1, x2, y1, y2, z, g1, g2
3) c = ((g1^x1)(g2^x2)) mod q ; d = ((g1^y1)(g2^y2)) mod q ; h = (g1^z) mod q , with ^ represents “exponent with”
4) public key = (q, g1, g2, c, d, h) ; private key = (x1, x2, y1, y2, z)
5) send public key to Bob2. Bob encrypt message m with public key:
1) choose a random number k
2) u1 = (g1^k) mod q ; u2 = (g2^k) mod q ; e = ((h^k)m) mod q
3) alpha = sha1(u1 || u2 || e) , with || represents joint
4) signature v = ((c^k)(d^(alpha * k))) mod q
5) send (u1, u2, e, v) to Alice3. Alice decrypt ciphertext with private key:
1) v’ = (u1^x1)(u2^x2)(u1^(alpha * y1))(u2^(alpha * y2)) mod q
2) if (v’ != v) verification fail ; if (v’ == v) go on
3) r = (u1^z) , so r == (h^k)
4) it’s easy to find r’ with extended Euclid’s algorithm such that (r * r’) mod q = 1
5) m = (r’ * e) mod q
Now we have the public key(q, g1, g2, c, d, h) and the ciphertext (u1, u2, e, v). We have to decrypt the ciphertext to get the flag message m.
This public-key cryptosystem looks like very safe, in fact, this should be a well-known cryptosystem or its variation. Whatever, we can’t decrypt the ciphertext without knowing the private key. So, we need to focus on how to get the private key.
In real world, many things protected by cryptosystem are cracked not because of a weak cryptosystem but because its key generation step is weak such as RC4 used in WEP.
This cryptosystem also have a very weak key generation step.
x2 = next_prime(x1) y1 = next_prime(x2) y2 = next_prime(y1) z = next_prime(y2) g1 = next_prime(z) g2 = next_prime(g1)
The private key z is just the prime before the public key g1. So we can easily get z if you have a crypto lib which give you a previous_prime() function. But this time, we just use the gmpy.next_prime() to find z.
Obviously, we need to know the gap between g1 and z. Trying it one by one can work, but not very efficient. Our method is that since z, g1, g2 are adjacent primes, the gap between z and g1 must approximately equal to the gap between g1 and g2.
So, we can guess z like this:
temp = next_prime(g1-(g2-g1))
Fortunately, g1 == next_prime(temp), so temp is just what we want (z).
Now we can decrypt the ciphertext as step 3.3, 3.4 and 3.5:
>>> r = pow(u1, z, q)
>>> ir = invert(r, q)
>>> m = divmod(ir*e, q)[1]
>>> hex(m)
'0x415349535f6534653634313762346261656262373438646136376533336636653039316435'
>>> (hex(m)[2:]).decode('hex')
'ASIS_e4e6417b4baebb748da67e33f6e091d5'
P.S: q is a prime, so gcd(q , r) = 1 .
It means there’re two number n1,n2 so that (n1*q + n2*r) = 1, then (n2 * r) mod q = 1.
n2 is called multiplicative inverse of r when mod q, and it’s the r’ we discuss above.
It’s not hard to understand if you have learn something about finite field.
Beagle Harrier 