For reasons, that will become clear, the version of RSA encryption covered in the lecture is called "naive RSA" in $[$Sma$16].$ In practice, it is recommended that RSA be used with some sort of message padding. A standard way is using optimal asymmetric encryption padding $($OAEP$),$ In this

question, we will cover a simpler version, which at least makes the scheme semantically secure under chosen plaintext attacks. The CEO of the organization XYZ decides to hold a vote to decide whether employees should be allowed to work from home $($WFH$)$ either one, two or three days a week. All $4$ employees of XYZ $($excluding the CEO$),$need to vote either $"$WFH one", $"$WFH two" or $"$WFH three". To ensure privacy, the CEO asks employees to send their votes by emailing them to the CEO. Furthermore, the CEO tells them to encrypt their votes using her RSA public key $e.$ The messages are encoded as:

$WFH$ one $|100,$

$WFH$ two $|200.$

$WFH$ three $|300.$

The CEO recieves the sequence of ciphertexts:

$c_1,c_2,c_3,c_4$

where $c_i$ is the ciphertext from employee $i.$ For completeness, assume the employees are in the order:

Alice, Bob, Charlie, Dave

So$,$ e$.$g$.,$ Bob's ciphertext is $c_2.$

$($a$)$ How many possible sequences of votes are there and why?

$($b$)$ Assume you, the eavesdropper, gets the sequence:After observing this, how many possible sequences of votes are there and why?

$($c$)$ Suppose the CEO's RSA public key is $(N,e)=(311119,11).$ What is Dave's vote? How did you come to this conclusion? Your answer should not involve any decryption. The issue raised above is that naive RSA is deterministic. We would want different ciphertexts, even if the same plaintext is encrypted twice. To do this, instead of letting $m$ be from the set $\{0,1,$dots,$N-1\}=Z_N,$we will restrict it to a smaller set, and then use the remaining bits for a random number $r.$ We will then encrypt $r||m$ instead of $m.$ Let rin$\{0,1{\}}^l.$ Let $|N|$ be the number of bits in the binary representation of $N.$Then, encryption of the message $m$ in this "padded" version of RSA is:

Chocse a random rin$\{0,1{\}}^l.$

Encrypt as $(r||m{)}^e(modN).$

Decryption after receiving $c$ is:

Decrypt as $(c{)}^d(modN).$

Retrieve the last $|N|-l$ bits as the message $m.$

In practice, we will first convert both $r$ and $m$ into their integer representations, and then encrypt $r||m.$

$($d$)$ Suppose $l=3,$ so $r$ can be from the set $\{0,1,2,$dots,$7\}.$ Assume you, the eavesdropper, gets the sequence:

$104376,291308,173608,175767$

encrypted via the padded RSA scheme using $(N,e)=(311119,11).$ Without decrypting, find the sequence of votes.

Hint: You can use the following observation in your for loop in PARI to output encryptions. If min

$\{100,200,300\}$ then $r||m=1000+m.$

$($e$)$ Suppose now that $l=100,$ so $r$ can be from the set $\{0,1{\}}^{100}.$ What is the time complexity of your attack from part $($d$)?$ Is the attack feasible? If you were an employee, would you recommend this encryption scheme to the CEO?A real$-$world account of a similar form of data release using $($deterministically$)$ encrypted IDs can be found here $[$CRT$17]$