Ouchie Revenge

Overview

Same Paillier-like cryptosystem as Ouchie, over n = p**2 * q with 384-bit primes. The difference is in option 3 (Get Flag): the challenge value is now encrypted before being printed, so we can no longer just echo it back.

elif choice == 3 :
    challenge = randint(p >> 10, p - 1)
    print(f"Challenge: {encrypt(challenge)}")
    response = int(input("Plaintext: "))
    if challenge == response :
        print("Congrats!")
        print(FLAG)
        exit()
    else :
        print("Wrong!")
        exit()

The Encrypt and Decrypt menu options remain available, giving us both an encryption oracle and a decryption oracle.

Analysis

Key structure: n = p² · q, with p being 384 bits. Look closely at the decryption routine:

L = lambda x : (x - 1) // p
def decrypt(c):
    a = pow(c, p - 1, p**2)
    b = pow(g, p - 1, p**2)
    a = L(a)
    b = L(b)
    m = (a * pow(b, -1, p)) % p
    return m

Both a and b are reduced modulo p, so decrypt(c) returns m' = m mod p. If we ask the oracle to encrypt a plaintext m that is much larger than p (for example m = 2^385), then decrypting that ciphertext gives us m' = m mod p. The difference m − m' is therefore an exact multiple of p.

By collecting several such differences mᵢ − mᵢ' and taking their GCD, the common factor p falls out:

gcd(m₁ − m₁', m₂ − m₂', …) = p   (with high probability)

Once we know p, the challenge ciphertext from option 3 decrypts deterministically with the same formula the server uses, and we submit the recovered plaintext to get the flag.

Exploitation

from pwn import *
from Crypto.Util.number import GCD

def get_p(io):
    m_list = [2**385, 2**385 + 1, 2**386, 2**386 + 1]
    diffs = []

    for m in m_list:
        io.sendlineafter(b">> ", b"1")
        io.sendlineafter(b"Enter Your Plaintext: ", str(m).encode())
        io.recvuntil(b"Encrypted: ")
        c = int(io.recvline().strip())

        io.sendlineafter(b">> ", b"2")
        io.sendlineafter(b"Enter Your Ciphertext: ", str(c).encode())
        io.recvuntil(b"Decrypted: ")
        m_prime = int(io.recvline().strip())
        diffs.append(m - m_prime)

    p = GCD(diffs[0], diffs[1])
    for d in diffs[2:]:
        p = GCD(p, d)
    return p

def main():
    io = remote("20.198.224.34", 8666)

    # Read g from the banner
    io.recvuntil(b"g = ")
    g = int(io.recvline().strip())

    # Recover p via the decryption oracle
    p = get_p(io)

    # Grab the encrypted challenge
    io.sendlineafter(b">> ", b"3")
    io.recvuntil(b"Challenge: ")
    c = int(io.recvline().strip())

    # Decrypt the challenge using p
    a = pow(c, p-1, p**2)
    b = pow(g, p-1, p**2)
    a = (a - 1) // p
    b = (b - 1) // p
    m = (a * pow(b, -1, p)) % p

    # Submit the plaintext
    io.sendlineafter(b"Plaintext: ", str(m).encode())
    io.interactive()

if __name__ == "__main__":
    main()

Recovering p from the GCD of the decryption differences lets us replicate the server's decryption and answer the encrypted challenge, yielding the flag.