1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can you give a full description of your scheme? Because, as it is here, there are no restrictions for q other than the size. What if someone says "let's take some 2^n for simplicity"? Broken without even looking at it. $\endgroup$ – deviantfan Nov 3 '16 at 14:06
  • $\begingroup$ About your "attack", I don't see an attack` One can add some redundancy in the message before encryption` Ok, and then? Check what exactly after encryption, before disclosing what? And why? $\endgroup$ – deviantfan Nov 3 '16 at 14:07
  • 1
    $\begingroup$ This distantly related question has a link (currently dead, but I'm working on it) to the article defining RSA for paranoids (RSAP), which seems similar (except for the "not necessarily prime" bit in the present one). $\endgroup$ – fgrieu Nov 3 '16 at 14:26
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ eprint.iacr.org/2008/260.pdf Turned up in Google (no idea if someone found an error in their proofs since then). So, assuming it still holds, both directions are known. $\endgroup$ – deviantfan Nov 3 '16 at 15:00
  • $\begingroup$ The paper is about RSA and factoring in a generic ring model (the only allowed operations are the ring operations and test for equality). That can be useful for upper or lower bounds. However, it does not imply that factoring and RSA are equivalent in general. $\endgroup$ – tylo Nov 3 '16 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.