Lets say I have the following modified RSA scheme

  1. We choose two large primes P, Q, with additional restriction that these are relatively prime to (p-1) and (q-1)

  2. We choose N = PQ as public key

  3. We calculate $P'$ such that $P'P \bmod (Q-1) = 1$ and $Q'$ such that $Q'Q \bmod (P-1) = 1$

  4. Encryption is $C = M^N \bmod N$

  5. To decrypt, we find M such that $M = C^{P'} \bmod Q$ and $M = C^{Q'} \bmod P$

which can be shown to be correct using similar proof as RSA.

Is this scheme more secure or less secure than the normal RSA? Better or worse? My gut feeling is that it is less secure because it depends on primes that satisfy condition 1 which reduces the search space. However, more computation is required to check for this in the first place so I can't be sure.

Also this encryption scheme will only result in one public key N compared to (N, e) in the RSA and no private key which seems to suggest less security on the surface

  • $\begingroup$ Sorry, we don't do "here's something I came up with; please analyse it for me." $\endgroup$ – fkraiem Dec 17 '19 at 6:25
  • $\begingroup$ (It could also be homework; no better.) $\endgroup$ – fkraiem Dec 17 '19 at 6:26
  • $\begingroup$ @fkraiem hi, thanks for the comment. How would you prefer I phrase this question? I've managed to verify the decryption process but Im not too sure how to judge the security of this modification. I have tried to give my take on it though albeit a bit simplified since I'm not too sure how to go about it. And yes, this was an suggested modification in a textbook Im studying and I'm trying to gain a better understanding of it. If you haven't noticed its mid-december and most courses are finished, its not homework. Any pointers would also be greatly appreciated! $\endgroup$ – ackbar03 Dec 17 '19 at 6:40
  • $\begingroup$ could you also, link or write the textbook name and number of the page/example etc? $\endgroup$ – kelalaka Dec 17 '19 at 6:49

This system was invented in 1973 by Clifford Christopher Cocks of the GCHQ and described in his document (then secret) A note on Non-Secret Encryption, before RSA was published. See this question for more context.

Is this scheme more secure or less secure than the normal RSA? Better or worse?

On security, we know no difference with RSA. The restriction that $p$ and $q$ are relatively prime to $p-1$ and $q-1$ does not sizably reduce the keyspace, in fact this restriction is always met when $p/2<q<2p$, which is customary in RSA as practiced. And, by using $N$ as the public exponent, nothing more than their product is revealed about the factors. From this standpoint, RSA with small exponent reveals more: with $e=3$, about half the primes are ruled out, and this is not known to make factoring sizably easier. But, like in RSA, factorization is only one of the security threats: we know no reduction to factorization for either scheme.

On practicality, RSA is superior because it can use a small $e$, which greatly speeds-up encryption (and signature verification), with no known drawback if proper padding and leakage protection is used, or $e$ is comfortably above the bit size of $N$. Small $e$ was not in Ronald L. Rivest, Adi Shamir, and Leonard Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in Communications of the ACM, Feb. 1978. But that quickly was added by Rivest's MIT group: it's in the challenge they made for Martin Gardner's A new kind of cipher that would take millions of years to break (in the Mathematical Games column of Scientific American, Aug. 1977).

Cock's paper clearly suggests using the Chinese Remainder Theorem for decryption, which from the standpoint of speed is superior to RSA as initially described. As far as I know, that improvement was not published before Jean-Jacques Quisquater and Chantal Couvreur's Fast decipherement algorithm for RSA public-key cyptosystem, in Electronics Letters, Oct. 1982. It is now standard practice in RSA, because it speeds up things by a factor up to about 4 compared to computing $x^d\bmod N$ by performing all the arithmetic modulo $N$.

| improve this answer | |
  • $\begingroup$ Thanks very much for this answer! The history behind this is interesting. This scheme is also essentially quite similar to the RSA with e = N it seems, as also mentioned here cryptome.org/jya/ellisdoc.htm in case it helps anyone else $\endgroup$ – ackbar03 Dec 21 '19 at 9:33

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.