# Eavesdropping attack on text-book RSA encryption with public nonce

Consider the following scenario: Alice has a secret key and public key pair for text-book RSA (denoted $$\text{sk}$$ and $$\text{pk}$$ respectively). Bob has an authentic copy of $$\text{pk}$$. The adversary has an authentic copy of $$\text{pk}$$.

Now, Bob wants to send his $$\text{PIN}$$ to Alice which is a four digit number. He encrypts as follows: First he chooses a nonce $$N_0$$ (a number chosen randomly from a very large domain). He then sends the encryption: $$c = N_0 \mathbin\| \operatorname{RSA}(\text{pk}, [\text{PIN}\mathbin\| N_0]) = N_0 \mathbin\| [\text{PIN} \mathbin\| N_0]^e \bmod N$$ where $$(e,N)$$ is the RSA public key.

Otherwise said, he constructs the new message $$“\text{PIN} \mathbin\| N_0”$$ (you may assume that he is able to embed $$[\text{PIN}\mathbin\|N_0]$$ as a number in $$\{1, 2, … , N-1\}$$) and encrypts that using text-book RSA. He also sends the number $$N_0$$ to Alice “in the clear”.

Show an attack which allows the adversary to learn the $$\text{PIN}$$ using only an eavesdropping attack.

I'm just not sure how to even start with this problem. I understand that textbook rsa creates the ciphertext with $$\operatorname{Enc}(e, m) = m^e\bmod N$$, but I don't know how I would get the $$\text{PIN}$$ if I can't tamper with messages. Any help would be appreciated.

I tried to work some things out and I've come to a different problem. Since the PIN has a relatively small number of possibilities, could I just use a brute force attack? Since the adversary knows the ciphertext, e, N0, and has access to the public key I could just keep trying different PINS correct?

• Hint: suppose you had a guess to the PIN - how would you verify that guess? Nov 23, 2021 at 19:33
• While editing the question, I took the liberty to replace the ambiguous occurrences of $a=b\pmod N$ with $a=b\bmod N$, which is the desired meaning in an RSA context. Recall $a\equiv b\pmod N$ means $b-a$ is a multiple of $N$, and $a=b\bmod N$ additionally means $0\le a<N$. If $a=b\pmod N$ is used and assigned one of the two meanings, that's best explicitly stated.
– fgrieu
Nov 23, 2021 at 20:37
• Yes you found the attack. Now your best options are writing an answer to your own question (you'll be able to accept it in a few days), or delete the question.
– fgrieu
Nov 24, 2021 at 10:45

Since the adversary knows both $$N_0$$ and $$E_{pk}(PIN || N_0)$$, the adversary can guess a PIN $$PIN_{guess}$$ and verify their guess by computing $$E_{pk}(PIN_{guess} || N_0)$$ and checking if it equals $$E_{pk}(PIN || N_0)$$.