Reminder: Class on Monday, September 21st is on Zoom. The link is in Canvas.

Relevant Textbook Sections:

2.12 (ElGamal Encryption), 3.6 (RSA Encryption), 3.6.1 (RSA Example).

To Do:

1. Suppose Oscar (a “man-in-the-middle”) intercepts and can modify a ciphertext on its way from Alice to Bob in El Gamal. Suppose he replaces the ciphertext $(K,c)$ with $(K,sc)$ for some $s$ of his choosing. (Oscar doesn’t know any of the secrets, like the message or private keys, but he can modify things.) What message will Bob decrypt? This exercise shows that Oscar can manipulate the message in a predictable way, without knowing what the message is. This is called “malleability”. This is an “active” attack, meaning that Oscar interacts with the protocol (changes things which are being sent during the protocol). Can you think of a way to fight malleability? How could you modify El Gamal to prevent this attack?
2. An RSA ciphertext chain!
   1. If you need a review of RSA, check the textbook (Section 3.6, with an explicit example in 3.6.1). For what follows, the Sage Sandbox page should be useful, as may be the RSA Tools page. These pages show how to do operations like modular inverse, exponentiation, and euler phi function in Sage. You can use basic number theory functions in Sage to do all your computations.
   2. First, set up your public and private key.
      1. Choose two 8-decimal-digit primes and form their product $n$. You can get primes out of Sage using the next_prime() function. So pick a number in the ballpark you want (maybe using randint()) and use next_prime() to get the next smallest integer which is prime.
      2. Compute $\varphi(n)$. Note that euler_phi() will do this for you in Sage, but it’s better to use the formula (p-1)*(q-1) because at cryptographic size, Sage would not return an answer, since euler_phi(n) would try to factor n.
      3. Choose an encryption exponent $e$ that is positive and less than $\varphi(n)$.
      4. Compute your decryption exponent $d$. It’s possible this will fail (e.g., if $e$ is not invertible!). If this error gets annoying (depends on your $\varphi(n)$), you could try using next_prime() to get a likely invertible $e$. (Concept check: why is a prime $e$ more likely to work?)
      5. Keep $d$ safe (along with $p$ and $q$, $n$ and $\varphi(n)$, just in case) in a file on your computer. The $d$ is your private key information; be sure also to keep $p,q, \varphi(n)$ away from prying eyes.
      6. Reveal your public key $n$ and $e$ on the discord #public-keys channel (“My RSA Public Key Is (n,e)=(…,…)”).
   3. Create a secret message which is at most 6 letters long. It should answer “What’s something awesome?” Please don’t make it longer or this exercise won’t work.
   4. Turn it into an integer using the Text to Integer tool. (There’s an Integer-to-Text tool on the same page to undo this process.)
   5. Now find someone else who has posted their public key (the most recent one before yours), and encrypt your message to that person. Post it on the #ciphertexts channel for them (use @theirname to alert them). Note: this should be one residue modulo their public $n$.
   6. When someone posts a message for you, decrypt it and announce the result using discord’s “spoiler” feature.
   7. You can turn in on canvas a screenshot of your discord result(s).

Added Sept 23: solutions to this daily post (El Gamal malleability and the RSA ciphertext chain worked end to end) are now posted: Solutions to Daily Due Sep 21.