# Rabin: how discover P and Q?

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

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.

• 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? Mar 11, 2018 at 9:28
• 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? Mar 11, 2018 at 10:28
• 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. Mar 11, 2018 at 10:55
• 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. Mar 11, 2018 at 12:26
• 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. Mar 11, 2018 at 16:35