Preventing attack in RSA modified version 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 &lt; m &lt; 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


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?
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?
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.