{"id":140,"date":"2008-07-16T05:44:16","date_gmt":"2008-07-16T05:44:16","guid":{"rendered":"http:\/\/www.blueraja.com\/blog2\/?p=140"},"modified":"2012-03-09T19:04:51","modified_gmt":"2012-03-10T00:04:51","slug":"rsa-encryption-part-3","status":"publish","type":"post","link":"https:\/\/www.blueraja.com\/blog\/140\/rsa-encryption-part-3","title":{"rendered":"RSA Encryption, Part 3"},"content":{"rendered":"

Finally, we get to the point: how RSA encryption works. You may want to review parts 1<\/a> and 2<\/a> to make sure all that modular arithmetic stuff is fresh in your mind.<\/p>\n

3. RSA Encryption<\/span>
\nFor those of you who are unaware, the term encryption<\/em> is used to describe any method that changes a message so that only its intended recipient can read it. RSA encryption (named after its creators) belongs to a special class of encryption called public key encryption<\/em>. In public key encyption, separate keys are used to encrypt and decrypt the message: the public key is known to everyone, and can be used to encrypt a message, while the private key is known only to the recipient, and is required to decode the message. This is opposed to symmetric-key encryption<\/em>, in which the same key must be known to both the sender and receiver.
\nThus, if you want to send me a message, all you have to do is encode your message with my public key, and only I will be able to read it (since only I have the corresponding private key). If I then want to send you a message in response, I would simply encrypt my response using your public key.
\nThink safes: public key encryption would be akin to a safe with a slot on top for inserting messages. Anyone with access to the safe (that is, who has the public key) can drop messages into the safe through the slot, but only the person who has the key to the safe (the private key) can read them.<\/p>\n

As a quick refresher, remember what we finished with last time. For all cases important to us, if we want to determine ak<\/sup> (mod n)<\/span>, then
\nak<\/sup> ≡ ak mod Φ(n)<\/sup> (mod n)<\/span>.<\/p>\n

First of all, we need some convention for mapping letters to numbers and vice versa. Let’s use the convention that A=0, B=1, C=2, …, Y=24, Z=25.†<\/sup><\/p>\n

Next, we begin the encryption process by choosing any two prime numbers; for convenience, let’s choose 3 and 11. The product of these will be our n: thus, n = 3*11 = 33<\/span>. Also, since n is the product of two primes, Φ(n) = (3-1)(11-1) = 20<\/span> (as was discussed last time).
\nWe also choose some number less than (and relatively prime to) Φ(n) and compute its inverse (mod Φ(n)) – we will see why in a minute. Let’s choose e=3<\/span> and d = e-1<\/sup> = 7<\/span> (since 3*7 ≡ 21 ≡ 1 (mod Φ(n))<\/span>). Keep in mind that, since we defined e and d to be inverses, their product ed ≡ 1 (mod Φ(n))<\/span>.
\nWe’ll call the pair of numbers (d,n)=(7,33)<\/span> our Private Key<\/em>, and the pair of numbers (e,n)=(3,33)<\/span> our Public Key<\/em>.<\/p>\n

Now we have everything we need – this is where it gets cool. Let’s try to encrypt the message “HELLO” using the public key. We will do this by encoding the message into numbers using our convention and then taking each number in turn to the power of e<\/span> (mod n). We can then decrypt by taking each number to the power d<\/span> (mod n). Let’s go over the example, and then I’ll explain why it works.<\/p>\n

Under our encoding, the message “HELLO” is given by the numbers “7 4 11 11 14”. Since e=3<\/span>, we raise 7 to the 3rd power to get 73<\/sup> ≡ 13 (mod n)<\/span>; so the first number in our encrypted message is 13. Likewise, 43<\/sup> ≡ 31 (mod n)<\/span>. After a bit of calculation, we get an encrypted message of “13 31 11 11 5”. We can now transmit this message down the line without having to worry about somebody reading it without the private key.
\nNow let’s decrypt the message: taking each of the numbers “13 31 11 11 5” and raising them in turn by the power d=7<\/span>, we get “7 4 11 11 14”, which decodes to the message “HELLO”. Great!<\/p>\n

So how did this all work? The reasoning is simple, actually. If you’ll remember back to last time, we concluded with the formula
\nak<\/sup> ≡ ak (mod Φ(n))<\/sup> (mod n)<\/span>
\nIn this case, a is our message, and k is e, our public key exponent. Thus, for each digit a<\/span>, what we’re transmitting is ae<\/sup> (mod n)<\/span>. When the message is received, we take it to the exponent d; thus, the new value is
\n(ae<\/sup>)d<\/sup> ≡ aed<\/sup> ≡ aed mod Φ(n)<\/sup> (mod n)<\/span>
\nby the above formula. However, if you’ll remember, ed ≡ 1 (mod Φ(n))<\/span>. Thus, after decryption we’re left with simply a (mod n)<\/span>, the original message!††<\/sup><\/p>\n

Yep – it’s just that simple. So simple, in fact, it might seem too simple. Why, you may be asking, can’t someone who’s given e (part of the public key) just calculate its inverse to get d (the unknown half of the private key)? Keep in mind that d<\/span> is the inverse of e (mod Φ(n))<\/span> – and in order to calculate Φ(n)<\/span>, we need to know p and q, the two primes which make up n. And here’s the point – integers, as every computer scientist knows, are hard to factor into primes. Very hard‡<\/sup>. This means that if n is very large (usually along the order or tens or hundreds of decimal digits), it will be nearly impossible for even the fastest super computers to determine p and q, meaning an attacker is very unlikely to be able to determine Φ(n) and thus determine d. It is this inability to "reverse" our choice of n that gives RSA its security.<\/p>\n

\n

†<\/sup> For those of you more familiar with computers, mappings based on strings of several ASCII or Unicode characters are most common.
\n ††<\/sup> The astute reader will have noticed that this only holds true if the encoded message is relatively prime to n. As it turns out, however, for RSA it just happens to hold true even when the message is not relatively prime to n; a proof of this can be found on wikipedia<\/a>.
\n ‡<\/sup> Probably. That is, it’s believed<\/em> to be very hard, but nobody knows for sure.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Finally, we get to the point: how RSA encryption works. You may want to review parts 1 and 2 to make sure all that modular arithmetic stuff is fresh in your mind. 3. RSA Encryption For those of you who are unaware, the term encryption is used to describe any method that changes a message […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts\/140"}],"collection":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/comments?post=140"}],"version-history":[{"count":4,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts\/140\/revisions"}],"predecessor-version":[{"id":348,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts\/140\/revisions\/348"}],"wp:attachment":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/media?parent=140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/categories?post=140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/tags?post=140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}