It’s been a while since I looked at how public-key encryption actually works. I thought I need to refresh my knowledge, so here’s a quick summary of the RSA algorithm.
The idea is that there are two keys, one public and one private. If I wanted to send you an encrypted message, I would encrypt it with your public key. But using the same public key, I could no longer decrypt it.
Only you can do it, with the private key which, of course, is private and only in your posession.
The public and the private key are just very (very very) big numbers.
It’s impossible (or rather completely, totally unlikely) to calculate the private key from the public key.
Encryption is, basically, just raising a number (=message) to an exponent (public) modulo some value (public).
Decryption is, basically, just raising a number (=encrypted message) to an exponent (private) modulo some value (public).
It just works with numbers, but any data is bascially a number. If you took this blog post, it would be just one veeeeery long number that, given the encoding (= meaning), represents this post.
So for encryption we have
And for decryption it’s
and the sign = in the above two equasions is actually not “equals to” but “congruent to”, since we are doing modular arithmetic.
The only difficulty is in calculating the keys. the random numbers p * q that make up the product n have to be very large for the cipher ot be secure. And calculating the secret exponent d is a matter of finding the multiplicative inverse for e “under” modulo(phi(n)).
That sounds weird, but it’s very similar to the reciprocal that everyone knows, namely the one, where multiplying the number and its inverse yields 1. For example 5, where the multiplicative inverse is 1/5, because 5 * 1/5 = 1. Same here, except we’re doing modular arithmetic, and we’re dealing with large numbers.
Here’s some ruby code that generates keys and uses them to encrypt and decrypt a message.
Note that this only demonstrates the principle. It is probably not entirely secure and definitely not very useful. (See discussion below)
But it runs and you can try it out. :)
So the above code implements RSA. However, there are some downsides to this implementation.
- The message cannot be longer than the key.
- The cipher can probably be broken.
Actually, both problems are addressed with the same solution. (And please, take this with a grain of salt, I am a total amateur just scratching the surface here.)
What is missing here is a formatting or padding scheme. If we want to encrypt long messages (arbitrary length) we need to be able to split them up so they are in chunks that can be encrypted.
Also, we need to harden the algorithm against attacks. One such hardening measure is adding random noise to each block, which is used as padding. The result is that the ciphertext will be completely different each time, but the receiver, since he knows how to apply (or un-apply) the padding, will be able to remove it again.
These things are complicated, but the core algorithm is easy. However, they are necesary to avoid certain weaknesses. That’s why, generally, just because a software encrypts data, it does not necessarily mean they do it right. You have to know what you do and/or use well known and well tested libraries. (OpenSSL comes to mind.)
As you can see there’s also some “trickery” involved. And I just mean that you need to use special algorithms, because you can’t just tell the computer to take a number with 500 digits and raise it to the power of another number of 500 digits. It would typically fail or be very slow. Same thing with checking if such a large number is prime. Thus the “good enough” algorithm above.
I don’t know. I just wanted to write this down. Just so you can see that it’s not very difficult. Even if the proofs why it’s secure, why it works in the first place, may be not.
Btw. this whole code is based on this great Github repository. This guy also has implementations of other algorithms and some great explanation docs.
P.S.: You can follow me on Twitter.