N1CTF 2019 - Part3-BabyRSA
RSA encrypted flag but each flag bit is encrypted at a time with random padding. The padding is a square thus using computing the Jacobi symbol for each bit encryption reveals the flag.
Description
The plaintext space in TokyoWesterns CTF real-baby-rsa challenge is too small, so I decide to add some random padding to the plaintext to prevent bruteforce attack. Hope this padding can prevent the hackers. XD
attachment:https://share.weiyun.com/5DMLSFC password:hujqnt
or
https://drive.google.com/file/d/1FNPT90x-rGhUwAKR5b18jnwMvHG91vgW/view?usp=sharing
Details
Points: 227
Category: Crypto
Solution
We were given a script which was used to encrypt the flag and the encrypted flag file. Each flag bit is padded with a random number and then encrypted. At a first view the challenge does not seem solvable since the function which return the least significant bit of the RSA plaintext is a hard-core predicate i.e it is a function as hard as preforming the full decryption without the private key. But looking at how the padding is computed :
|
|
We noticed that the padding is a square and is is shifted by two (or multiply by two) before be added to the plaintext bit. Thus if a the plaintext bit is 0 the corresponding ciphertext will be:
$$ c = (2 {P}^2) ^ e = 2^e ({P}^e)^2$$
with $P$ the random number from the padding. If the plaintext bit is 1 we have the corresponding ciphertext is
$$ c = (2 {P}^2 + 1) ^ e $$
We can divide by $2^e$ each ciphertexts and test with the Jacobi symbol if the number is a square modulo $N$ or not. The Jacobi symbol $\left(\frac{a}{p}\right)$ for a prime number $p$ is defined to be 1 if $a$ is a square and -1 if not. For our case $\left(\frac{a}{N}\right) = \left(\frac{a}{p}\right) \left(\frac{a}{q}\right)$. Thus if $\left(\frac{c}{N}\right) = -1$ we know that the plaintext bit was 1. Thus we can write a script to reveal the plaintext:
|
|
It outputs the flag:
|
|