Cryptohack

The challenge has the most code in it so far, but should not take too long to realize the task we had to do. This follows the same idea as the prequel challenge Let’s Decrypt - that is to find an appropriate N, e such that the pow(sig, e, N) is equal to the value of the PKCS1 padded messages. However, in this challenge, we had a twist - we can only use one non-prime modulus N but has to generate three es such that pow(sig, e_n, N) = m_n with e_n being the public exponent correlated to the nth message m_n....

First, the modulus is big (2048 bits) and the public exponent e is small (3), hence we may use a small number and the arithmetic operation under the modulo N is the same as in $\mathcal Z$ Pedro is not exactly careful with the padding, indeed: 1 2 3 4 5 6 7 8 vote = int(your_input['vote'], 16) verified_vote = long_to_bytes(pow(vote, ALICE_E, ALICE_N)) # remove padding vote = verified_vote.split(b'\00')[-1] if vote == b'VOTE FOR PEDRO': return {"flag": FLAG} Anything in the verified_vote variable before the null byte is discarded, hence a message of the form <SOME RANDOM STUFF>\x00VOTE FOR PEDRO is still valid....

RSA signing with malleability, we can sign anything but the admin token to retrieve the flag. My approach is to get the signature of the hex string b'\x02', in numeric value is $2^d$, with $d$ being the private key. Then we request for the message that is twice the value of the admin token, then we get the value of $(2m)^d$. Then retrieving the value of $m^d$ should be trivial....

This is a example of Franklin-Reiter attack on RSA. We can obtain two ciphertexts that correspond to the same plaintext encrypted with the same modulus, but padded differently. Denote the plaintext as $m$, the modulus $N$, the public exponent $e$, the ciphertexts $c_1$ and $c_2$, and the padding variables be $a_1, a_2, b_1, b_2$. We thus have the two polynomials with the common root of $m$: $$p_1(x) = (a_1 x + b_1) ^ e - c_1 \mod N$$ $$p_2(x) = (a_2 x + b_2) ^ e - c_2 \mod N$$ Hence, if both polynomials have the root $m$, then they are both divisible by $(x - m)$....

The flag is padded with \x00 at the end to make the length of the flag overall becomes 100 bytes long. For each null byte appended, the value of the flag is multiplied by 256. Hence, we can retrieve the flag using Coppersmith, however there is a twist. Even if the polynomial theoretically should output some result, none is returned by the small_roots function. The solution that works seems to reduce the x that is calculated to be the smallest x possible such that the result makes sense....

Long challenge name, but short story. We are given an article at this link, outlining the difficulties in generating RSA keys such that there are no two public keys using the same prime. Because if that’s the case, one can very efficiently recover the factorisation by doing Euclid’s Algorithm, which runs in polynomial time (and thus much faster compared to factorising), to obtain one of the two primes used in the modulus....

I hate recursion depths. Sage on Windows sucks at configuring anything related to this. The challenge gives a peculiar way of generating primes 1 2 3 4 5 6 7 def get_complex_prime(): D = 427 while True: s = random.randint(2 ** 1020, 2 ** 1021 - 1) tmp = D * s ** 2 + 1 if tmp % 4 == 0 and isPrime((tmp // 4)): return tmp // 4 And given the name of the challenge, we are pretty sure that this leads to a vulnerability....

We are given N, e, d of the sender and N, e of his friends. The flag is encrypted using the friend’s public keys e1, e2, ..., e5 under the same modulo N. As seen in this link, we can factorise N given e, d using the given algorithm. From that, decrypting the plaintext should be trivial. Sage Implementation (slight modification and this can work on Python too) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 from Crypto....

We are given multiple messages, but from the hint, some of the messages are repeated. Hence, it is likely some (if not all) of the messages will be the same. That is, there is a message $m$, moduli $n_i$, and ciphertext $c_i$ such that: $$\forall i, c_i \equiv m ^ 3 \mod n_i$$ Hence, we can employ Chinese Remainder Theorem in this case. This is also a simplified form of Hastad’s broadcast attack....

RSA, except we are given a huge public exponent e that has the same number of bits as the modulus N. We can attack this using Wiener’s Attack. The condition for Wiener’s attack is $$d \le \frac{1}{3} \sqrt[^4]{N}.$$ We can refer to the way that the attack works in the Cryptohack Book. Sage Implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 from Crypto....