Along with an encrypted message (c), you are given a special function that you can call - a parity oracle. This function will accept any integer value that you send to it and decrypt it with the private key corresponding to the public key that was used to encrypt the given cipher (c). The return value of the function will indicate whether this decrypted value is even (true) or odd (false). Armed with this function and a little modular arithmetic, it is possible to crack the encrypted message. Your goal is to write the code necessary to decrypt the original message (m) from the given cipher (c).

from typing import Callable

# You may find these helpful
import math
from decimal import *

def rsa_parity_oracle_attack(c: int, N: int, e: int, oracle: Callable[[int], bool]) -> str:

# TODO: Write the necessary code to get the plaintext message from the cipher (c) using
# the public key (N, e) and an oracle function - oracle(chosen_c) that will give you
# the parity of the decrypted value of a chosen cipher (chosen_c) value using the hidden private key (d)

m_int = 42

# Transform the integer value of the message into a human readable form
message = bytes.fromhex(hex(int(m_int)).rstrip('L')[2:]).decode('utf-8')

Answer rating: 100% (QA)

Answer To decrypt the original message m from the given cipher c using the provided parity oracle fu... View the full answer