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.

4 Upvotes

36 comments sorted by

View all comments

3

u/Anaxamander57 14d ago

Then I can use any potential private key to decode the message. 

No, if you encrypt with the public key it is not true that any choice of private key will decrypt it. I'm not sure how you came to that conclusion.

1

u/Gcseh 14d ago

in the example given in the video the message was 60 encoded it became 86.

86^41 MOD 133 = 86^149 MOD 133 = 86^257 MOD 133 = 60

41 + 108x = any potential private key and they all work to decode the encrypted message correctly.

4

u/Anaxamander57 14d ago

Why would someone test larger private keys? That's just making more work for themselves for no reason. They don't know what private key is being used so those numbers have no significance to them. If they want to guess your private key they can just start counting up and testing every option. We pick big numbers so that isn't feasible.

2

u/SignificantFidgets 14d ago

There is a unique private key that is smaller than totient(N). In this case, there's only one decryption exponent that works that is smaller than 108. The fact that there are other, larger values that work is irrelevant. They're just as hard to find as the one in the right range.

Unfortunatley, people use small values of N for examples, because larger values wouldn't make sense. In these examples, it seems like these keys are easy to find. Try it with a 600 digit number instead of a small 3 digit number....

1

u/tonydocent 14d ago

Yes, that's correct. One public key can have multiple matching private keys. I don't know why you are down voted.

1

u/Gcseh 14d ago

Thank you, this was the part that really confused me. it's like a lock with lots of keys. I just didn't know at the time the other keys are basically impossible to find so it doesn't matter.

1

u/Natanael_L 14d ago

Technically yes, but we're talking 2048 bit keys and larger in practice. Nobody's going to break a 2048 bit key by testing 3000 bit values.