English [Sharif University CTF 2016] [Crypto 100 – Universal re-encryption] Write Up


Universal Re-Encryption
Let p be a prime, and g be an element of ℤ/pℤ of prime order q.
Let x ∈ ℤ/qℤ be the private key, and h = g^x (mod p) be the public key.

To encrypt a message m ∈ ℤ/pℤ, pick two random values r, s ∈ ℤ/qℤ, and compute the ciphertext as follows:
(a, b, c, d) = (g^r, h^r, g^s, mh^s).

Download a valid ciphertext σ = (a, b, c, d) below, and compute another valid ciphertext σ′ = (a′, b′, c′, d′) such that:
σ and σ′ decrypt to the same message;
a ≠ a′ and b ≠ b′ and c ≠ c′ and d ≠ d′.


This challenge was based on an application of the property of an hypothetic homeomorphic encryption which is that we can operate on the cipher as we would do on the clear text (without decoding it before).
So basically we must re-encrypt the ciphertext in order to make decryption giving the same result on both ciphers.

We found a very useful link which explains this ciphering method : https://crypto.stanford.edu/~pgolle/papers/univrenc.pdf.

Then we applied what is described at page 6 with this python code :

p = int('0x8000048d1d71b57838b7d90ebc63b8c853f3af1af87ce2db5593f3386ae5139d040d3844e31db723d39cdd7717c8cffc26f6f877b5c85ca8e595ca687c07c773',16)

a = int('0x21068b690f5438360063bb80799a95af7bbb83fa399376af9ad21e0cef3d5233aa313fe1960ccfd87e8a4b1dba0e053d89bfebd4bc57170147462fafef44c9c7',16)
b = int('0x436c161645052a76c1f7c976da63f61987f5f9bf7cb810a0e6fb1ea593aa9397c7b7cb0488f0f14cf93c79eef967a4b2a39388da1a357077d30a6f8b2a2c97e7',16)
c = int('0x7dd53b07c05ea2aca88bcbdd58601fa344918848107431ae7710542ea625abb335c27352c1bd2ef01359adb19b1bee77edc07ab0b41b9766392fc154f7891268',16)
d = int('0x1a50308011b409460d504cc7cddd61cdff1bda0774d1329b59606df274bce81a7e4b15830ddd4e684e3f2422d36bd52220134881db560be0a34c76a9c5bbb6be',16)

r = 5
s = 7

print hex((pow(a,s,p))%p)
print hex((pow(b,s,p))%p)
print hex((c*pow(a,r,p))%p)
print hex((d*pow(b,r,p))%p)

Flag was : “SharifCTF{d03de378ab0f370b0a27e7e366ba6f2e}“.


Leave a Reply

Your email address will not be published. Required fields are marked *