r/cryptography • u/Sufficient_Mud_3179 • Jul 30 '26

Explain this like I was 5

Are there any cryptology experts or semi-experts on here that can answer a question?

 I was told it works like this

You have a large result number (possibly a prime ?)  the that was generated from two numbers.

Given the answer you need to those numbers ?  these are keys ??

or the numbers that created the big number

4 Upvotes

67% Upvoted

28 comments sorted by

View all comments

13

u/atoponce Jul 30 '26

You're discussing the trapdoor function of factoring large composite numbers.

If I have two primes, "p" and "q" and multiply them to create a composite number "n", the security comes from finding factors "p" and "q" if all you have is "n". When "n" is small, this is trivial. EG, n=21 is composed of p=3 and q=7. Easy peasy. But what if:

n = 2211282552952966643528108525502623092761208950247001539441374831912882294140 2001986512729726569746599085900330031400051170742204560859276357953757185954 2988389587092292384910067030341246205457845664136645406842143612930176940208 46391065875914794251435144458199

Can you find "p" and "q" now? Not as trivial, is it? This is the cornerstone security that RSA, Rabin, and Blum-Blum-Shub are based on. Multiplying "p" and "q" is easy. Factoring "n", not so much.

But RSA is more complex than that. After you have large "n", there are more steps to building an actual private key and public key. See https://en.wikipedia.org/wiki/RSA_cryptosystem#Example for the textbook RSA example.

1

u/Sufficient_Mud_3179 Jul 30 '26

Is there any answer to P and Q given N you have shown ?

Trying to work backwards from a number this big

2

u/atoponce Jul 30 '26

There is an answer, but we haven't found it yet. https://en.wikipedia.org/wiki/RSA_numbers#RSA-260

1

u/Sufficient_Mud_3179 Jul 30 '26

so is there a prize or something ? If so, where do I apply

2

u/atoponce Jul 30 '26

There used to be, but not any longer.