Preventing attack in RSA modified version

Question

I have the following modified version of RSA apparently proposed by Shamir. To check the original version of RSA check the first scheme in this other question.

The modified version goes as follows: que take $p$ a prime number of $s$ bits and $q$ a random number not necesseraily prime of size $ts$ where $t \simeq 10$ and take $n = pq$. The public key and the encryption function are as in RSA shown in the link.

We can show that the decryption problem is equivalent to find the factor $p$ of $n$. Namely, to show that decrypting would imply finding factor $p$ we do at follows:

Choose a message $p < m < 2p$ and write $m = u + p$ then $m = m^{ed} \, mod \, p = (p+u) \, mod \, p = u$ so that $p = m-u$.

Here we used the fact that decrypting with $m^{ed} \, mod \, p$ is good enough (is injective if we choose $gcd(e,p-1) = 1$.

My question

1. In the previous the deduction we actually chose a convenient message to show that solving decryption problem implies factoring $n$ but in reality we won't get a chosen message $m$ but random ones so that even if we know how to decrypt we might not be able to find out $p$. How is this deduction valid then?

2. The notes I'm following propose a way to thwart this attack.

One can add some redundancy in the message before encryption, and check the redundancy after decryption before disclosing the result.

I don't see very well how this strategy would work. Can you give an example?

Answer 1

Tldr: Your notes are nonsense.

First, normal RSA: There are some big, random, secret (pseudo)-primes p and q, and a nonsecret N with N=p*q. RSA is secure (well, other than the known problems) because an attacker can't extract p and q from N (factorization).

Your version of RSA does not require that q is prime, just big and random. If the random number happens to be a prime, everything is ok.
If, on the other hand, it is something like 2^1024 or anything else with lots of small prime factors, it's trivial to factorize N => broken. In real RSA, the requirement for primes is important.

We can show that the decryption problem is equivalent to find the factor p of n.

Yes, like in normal RSA. If p is found, q=N/p, broken.
But again, if I can factorize N easily, there's no challenge.
Let's take the 2^n - example from above: I do N=N/2 until I have a prime number (or any uneven number), and that's p. ... Other numbers than 2^n are not much harder.

In the previous the deduction we actually chose a convenient message to show that solving decryption problem implies factoring n but in reality we won't get a chosen message m but random ones

The content of the message m does not matter at all. Factoring N => broken, that's all.

One can add some redundancy in the message before encryption, and check the redundancy after decryption before disclosing the result.

That's something to detect tampering (ie. the attacker changes the encrypted data to something else, without knowing the plain content), but it does not prevent factorization.

Answer 2

For starters, in your other question you hard coded: $\phi(N) = (p-1)(q-1)$. This is not true, if $q$ is not prime. This would have to be fixed.

And then, as a rule of thumb the difficulty of the factorization problem is not defined by the largest prime factor in general - different algorithms scale with different properties (e.g. length of $N$ or the size of the prime factors except the largest one).

We can show that the decryption problem is equivalent to find the factor p of n. Namely, to show that decrypting would imply finding factor p we do at follows

This is wrong. It is unknown if the RSA problem is equaivalent to factoring. And then, you can find $p$ indirectly as well, if you can find all other factors of $n$.

Here's a counterexample:

• Choose $p$ prime like you suggest, choose $q = 2^k$ with $k$ matching your length requirement. So you have $n = 2^kp$.
• In binary representation, this is basically $p$ concatenated with $k$ zeros, so we don't even need to do any trial divisions to get $p$. Powers of $2$ can be removed by simply right-shifting, and if we see the remaining number is prime, we're done.

---

Considering your question, there might be a misconception about security in general. You assume "the attacker gets a random message". However, this is hinting towards ciphertext-only attacks. Those are quite irrelevant in terms of modern cryptography. I would suggest reading about attack models, and usually we want resistance against chosen-plaintext attacks or chosen-ciphertext attacks.

Regarding your general deduction: If you want to have an algorithm to find "p", then you can't use "p" in your calculations (or calculate your $u$). It just doesn't work that way.