- category : crypto
- points : 467
Someone was thinking encrypting again and again helps, prove them wrong.
c = 196353764385075548782571270052469419021844481625366305056739966550926484027148967165867708531585849658610359148759560853
File : q1.py
We have :
n = p * q, p, q, c. To encrypt a message
m the script does :
(m ^ 2) % n = c.
The encryption remembers RSA, however in this case we have
e = 2 which is not a possible exponent in RSA because
gcd(2, phi(n)) = 2 and so the inverse of
phi(n) is not possible. This cryptosystem with exponent 2 is the Rabin cryptosystem.
Decrypting a ciphertext
c we get 4 different results. To decrypt we need to:
mp = c ^ (1/4 * (p + 1)) mod p
mq = c ^ (1/4 * (q + 1)) mod q
- Both can be expressed as :
mp = sqrt(c) mod p
mq = sqrt(c) mod q
- Use Tonelli-Shanks algorithm to compute both of them.
- Use Extended Euclidean algorithm to find
yp * p + yq * q = gcd(p, q) = 1
- Use the Chinese remainder theorem to find the fours square roots of
c mod n:
r1 = (yp * p * mq + yq * q * mp) mod n
r2 = n - r1
r3 = (yp * p * mq - yq * q * mq) mod n
r4 = n - r3
During encryption the challenger encrypts the flag
n times, we don’t know how many times (
n) because we don’t know the flag. To solve the problem we can imagine the following graph :
Where recursively during the decryption we create
4 times more nodes at each level. In the level
i there will be
To solve this problem we can implement a BFS. Implementing a DFS is not a valid approach. We don’t have the graph structure and we need to create one on the fly, with a DFS we don’t know where to stop “searching”.