I'm really lost.

I'm creating a classroom lesson about Rabin encryption and I had understood the encryption process, the creation of public-key (N = p*q) and the steps I need to find the 4 values that can be the solution.

BUT, every sample I find consider the true P and Q to demonstrate the decryption process (Extended Euclidean or Euclidean) and most of them using p=7, q=11, N = 77!

I mean, how they have P and Q?

For instance: this and this and some other as in Applied Cryptography (section 8.12) and so forth.

Is the factoring of N the first step to calculate the secret-key?
Or the solution of trying random values to put into Chinese Remainder Theorem? I can't believe in this because doing so, I would be considering Bob like Eve (have to try a lot of values to get P and Q)!

Can you light my way? I appreciate in advance.


1 Answer 1


The intended users know, in fact choose $p,q.$ The attackers aren't supposed to know. Once you know $p,q,$ you use the Chinese Remainder Theorem for efficient computations.

  • $\begingroup$ But I understood Rabin as an asymmetric schema to exchange keys and if Alice and Bob know P, Q and N, what is really the advantage of Rabin? $\endgroup$
    – David BS
    Commented Mar 11, 2018 at 9:28
  • $\begingroup$ In another supposition, let's imagine a N with 400 digits: how can I suppose Bob will know/remeber P and Q? And at last, if I need to change my key to another and Bob is offshore, how can I inform him about the new P and Q securely? $\endgroup$
    – David BS
    Commented Mar 11, 2018 at 10:28
  • 1
    $\begingroup$ Modern cryptography is machine/computer based, of course no one can remember such large numbers. More importantly you seem to have missed the basic point of asymmetric systems. The public key is public without making the private key insecure. That is the whole point. You have P,Q, N and so does any other party you communicate with, they have their own. $\endgroup$
    – kodlu
    Commented Mar 11, 2018 at 10:55
  • $\begingroup$ thank you, I understand it, BUT, if I must provide P and Q to Bob, I wouldn't need to calculate N and make it public; isn't it? I came to the initial point: if Bob must know P and Q, N is discardable. And, if I just have to send N (what I understand as the right thing to do), how exactly obtain P and Q if all samples I see mention the original P/Q values to calculate the square-roots. $\endgroup$
    – David BS
    Commented Mar 11, 2018 at 12:26
  • $\begingroup$ Hmmm.... I guess I understood now your point of view. Alice and Bon will not share a key. Each one will have his own key and each N is enough to allow them to share secrets. Thank you @kodlu. $\endgroup$
    – David BS
    Commented Mar 11, 2018 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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