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

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?

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

I see four ways how to attack this scheme

1) RSA malleability

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