2
$\begingroup$

I am attempting to solve the following problem:

I know the following:
3 messages are being sent between Alice and Bob, all messages are encrypted with the known public key $(d,N)$:

  1. Alice sends Bob: $m_1=E(R_1);$ $R_1$ is a 28-bit number.
  2. Bob sends Alice: $m_2=E(R_2,R_1);$ $R_2$ is a 28-bit number and $R_1$ follows (i.e, $p_2 = (2^{28} * R_2 + R_1)$ if i am not mistaken)

  3. Alice sends Bob: $m_3=E(R_2,R_1,R_3);$ $R_3$ is a 156-bit number known in advance.

The goal is to alter $R_3$'s value which is about to be sent to Bob to a new value (first 7 bits only).

The best I could come up with is to precompute all possible 28-bit number encryptions which will allow me to know $R_1$'s value when sent by Alice -> then easily figure out $R_2$'s value -> send my desired $R_3$ value to Bob.

Is there a neater (and more feasible) way to do so?

$\endgroup$
2
  • $\begingroup$ Hint: RSA is multiplicative, you can multiply and divide $\endgroup$
    – kelalaka
    Mar 27, 2019 at 21:30
  • $\begingroup$ I forgot to state that i have been asked not to use the RSA's multiplicative nature $\endgroup$ Mar 28, 2019 at 6:28

1 Answer 1

1
$\begingroup$

I see four ways how to attack this scheme

1) RSA malleability
Suggested in comments

2) If $e=3$ then
Trivial attack exists. Hint: What is the minimal possible size of $N$?

3) If the attack is active(MiTM)
Cheaper attack exists. Hint: Treat the task as a set of Oracles:

  • $Oracle0: n \mapsto E(n)$ - If you know $(e,N)$, you can encrypt any $n$.
  • $Oracle1: \epsilon \mapsto E(R_1)$
  • $Oracle2: E(n) \mapsto E(R_2*2^{28}+n)$
  • $Oracle3: E(n) \mapsto E(n*2^{156}+R_3)$ - Are you sure?

4) You treat it as a blackbox
Your solution

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