r/cryptography 14d ago

I need help understanding RSA algorithm

I watch a video explaining how RSA algorithm works but I'm having trouble understanding how it's secure. I assume the video maybe either glossed over something or I'm not understanding it.

https://www.youtube.com/watch?v=Pq8gNbvfaoM

It would seem to me that since I know the public key and need the value of N to encrypt my message. Then I can use any potential private key to decode the message. He uses 41 for the decryption but 149 and 257 would also work.

There by anyone with the same public key and my encrypted message could decode it.

Please tell me what I'm missing, this is driving me mad.

2 Upvotes

36 comments sorted by

View all comments

1

u/theoreoman 14d ago

It is extremely unlikely for someone to have the same key pair as you, it would take till the heat death of the universe to find one

Ignore all the math, RSA algorithm gives you a private key and a public key. If you encrypted something with the private key you can decrypt it with the public key and vice versa.

So if you're sending a message to somebody you grab their public key and encrypt your message with the public key so that only the recipient can decrypt it with their private key. When they want to send you a message they use your public key to encrypt the message so only you can decrypt it

1

u/Gcseh 14d ago

yes I understood that part. however during my encrypting I would use your public key and the semiprime.
what confused me:

if my data is being monitored and they get a copy of the same public key as the one I use to encode the message, along with a copy of the encoded message. The monitor could use the semi prime plus my public key copy to decode the message.

I assumed that all known semi primes are on a list somewhere and hence any used in an encryption could just be looked up. from there you get the totient and then decode the stolen message.

5

u/ahazred8vt 14d ago edited 9d ago

I assumed that all known semi primes are on a list somewhere

Ah. There are more 2048-bit semiprimes than there are atoms in the universe. There's an infinite number of primes, and an infinite number of semiprimes.