Man-in-the-middle attack on text-book RSA PKE

Question

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?

Answer 1

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