1. Implement the textbook RSA algorithm.

The textbook RSA is essentially RSA without any padding. Here we give a brief definition:

Choose two large primes $p$ and $q$. Let $n = p \cdot q$. Choose $e$ such that $gcd(e, \varphi(n)) = 1$, where $\varphi(n) = (p−1) \cdot (q−1)$. Find $d$ such that $e \cdot d ≡ 1 \bmod \varphi(n)$. In other words, $d$ is the modular inverse of $e$, i.e., $d ≡ e^{−1} \bmod \varphi(n)$.

$(e, n)$ is the public key, $(d, n)$ the private one.

To encrypt a plaintext $m$, compute $c \equiv m^e \bmod n$.
To decrypt a ciphertext $c$, compute $m \equiv c^d \bmod n$.

In this part, you should achieve following goals:

• Generate a random RSA key pair with a given key size (e.g., 1024bit).

• Encrypt a plaintext with the public key.

• Decrypt a ciphertext with the private key.

2. Perform a CCA2 attack on textbook RSA.

Textbook RSA is elegant, but has no semantic security. Therefore it is not secure against chosen plaintext attacks or ciphertext attacks. A real-world case can be found here: When Textbook RSA is Used to Protect the Privacy of Hundreds of Millions of Users. In section 4.1, the authors explore the CCA2 attack on QQ browser. In this part, we aim to verify this type of attack on the textbook RSA you have built in the last part:

• Firstly you should clarify the attack scenario. There are two roles: server and client. Initially, Server generates a RSA key pair and Client acquires the RSA public key. Then Server and Client will communicate following the steps detailed in section 2.

• Since QQ browser has fixed this problem, you need to simulate the attack locally. In a basic version, you should present the attack process to obtain the AES key (and further decrypt the encrypted request) from a history message. The history message can be generated by yourself in advance, it should includes a RSA-encrypted AES key and an AES-encrypted request.

• Your core goal is to show the CCA2 attack process. Feel free to design your own WUP request format, server-client communication model, etc. A nice design will bring you a bonus. AES encryption and decryption can be achieved with the help of third-party library. Here is an example for AES-ECB python implementation:

  from Crypto.Cipher import AES
  
  key = "0000111122223333"
  
  cipher = AES.new(key, AES.MODE_ECB)
  msg = cipher.encrypt("network-security")
  print(msg.encode("hex"))
  
  decipher = AES.new(key, AES.MODE_ECB)
  print(decipher.decrypt(msg))
  

3. Implement a RSA-OAEP algorithm and discuss why RSA-OAEP can thwart such kind of attacks.

Since textbook RSA is vulnerable to attacks, in this paper, the authors give a solution: using OAEP key padding algorithm. In this part, you need implement the RSA-OAEP algorithm and discuss its effectiveness:

• You can achieve it by adding the OAEP padding module to the textbook RSA implementation.
• You should give a discussion on the advantages of RSA-OAEP compared to the textbook RSA.
• As a bonus, you can further try to present that RSA-OAEP can thwart the CCA2 attack you have implemented in part 2.

Note: feel free to choose your preferred programming language to work on this project.