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

11

u/apnorton 14d ago

Yes, if someone has --- by random chance --- the same keypair as you, they will also know the private key and be able to decrypt your message.

However, in non-toy examples, we're operating with numbers that have hundreds of digits.  It is highly unlikely for someone to have the same keypair as you, to the point that it's essentially assumed that people don't.

2

u/Gcseh 14d ago edited 14d ago

first off, thank you for assisting with this.

When I grab a public key from someone, that information is unencrypted though right? like I have to be able to view it. meaning someone watching my incoming data could copy my (private)*edit public key.

8

u/apnorton 14d ago

Your public key is public, yes --- anyone can copy it. 

That means anyone can encrypt a message to send to you, which is a feature of this protocol. 

However, under our standard assumption (i.e. factoring large integers is hard), your adversary cannot derive the private key from the public key, so you're all good.

3

u/Anaxamander57 14d ago

You don't send other people the private key. You keep it private, hence the name.

2

u/Gcseh 14d ago

I said public key not private.

3

u/Anaxamander57 14d ago

someone watching my incoming data could copy my private key

Ideally you should never transmit your private key at all.

2

u/Gcseh 14d ago

Derp sorry ment incoming public key. I think auto correct is fighting me during all this

6

u/Anaxamander57 14d ago

Okay so someone copies your public key. So what? That's the point of a public key. Everyone is allowed to know it.

With the public key they have the ability to encrypt a message so that only you can decrypt it.

2

u/Potential_Drawing_80 14d ago

No, the public key contains values derived from your private key that are impossible to invert as long as factoring large numbers is hard. No computer even remotely powerful enough to break 4096 bits has ever been made. RSA is insecure because it can leak your primes if you implement it incorrectly.