0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Hint: suppose you had a guess to the PIN - how would you verify that guess? $\endgroup$
    – poncho
    Nov 23, 2021 at 19:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Nov 23, 2021 at 20:37
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Nov 24, 2021 at 10:45

1 Answer 1

Reset to default
1
$\begingroup$

RSA is deterministic. This means that if you encrypt the same message twice using the same public key, the two ciphertexts are exactly the same.

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)$.

Since the PIN is a 4 digit number, the adversary can check all of the PINs.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.