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?

$\endgroup$
3
  • 2
    $\begingroup$ Hint: suppose you had a guess to the PIN - how would you verify that guess? $\endgroup$
    – poncho
    Nov 23 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 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 at 10:45
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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