Science Break: Encryption part two – the digital era

I admit that splitting this article into two parts was partly borne out of trepidation. By delaying part two I was able to put off the daunting task of writing about an extremely dry and complex topic – not as exciting as WWII spy stuff! Part one ( March 2013) ended with WWII and the Enigma Machine, but in the 70+ years since then, with the advent of the digital era and the Internet, the field of encryption has developed considerably more complexity. I will do my best to provide a basic understanding of the mathematics behind modern key-based encryption methods.

Encryption turns easily understood information – plaintext – into something completely unintelligible – ciphertext. At the receiving end, the ciphertext needs to be decrypted, and this requires a decryption key. The relationship between the encryption and decryption keys separates encryption systems into two categories, symmetric-key (or private-key) encryption and asymmetric-key (or public-key) encryption.

The former term, which includes all the systems discussed in part one of this article, refers to encryption schemes where the encryption and decryption keys are the same. They require both the sender and the receiver to be in possession of the (hopefully) secret key. Public-key schemes on the other hand employ encryption and decryption keys that are different. Public-key encryption is so named because it usually involves a publically available encryption key, along with a secret decryption key. It is a recently developed methodology, but most encryption methods now used fall into this category.

Today’s reality is that our confidential information is glaringly exposed to the rest of the world, because of the pervasiveness of the Internet and other digital networks and access points. As if this wasn’t bad enough, computers are so powerful that they can solve inadequate forms of encryption through brute force alone. An early symmetric-key encryption from the 1970’s called DES (digital encryption standard) used 56-bit encryption, but the 716 possible combinations that it provides are considered inadequate given today’s compute power.

There has been an evolution of symmetric-key encryption methods, and as you will see, these are still very much in use. The Blowfish cipher was introduced as an open source improvement on DES, and although still in use, it has largely been eclipsed by AES (advanced encryption standard), which offers 128, 192, and 256-bit encryption. To give an idea of its ability to withstand cracking efforts, 128-bit encryption translates to 30035 possible combinations. But even with these large bit encryption systems, the Achilles’ heel is still there – the sender must give the recipient the secret key, and if it is intercepted then security is compromised. I do this on a fairly regular basis and laugh at myself. For example, I’ll email someone a confidential spreadsheet as an attachment and include the password in the email body text – duh. That’s like putting a sticky note with your password on the side of your desktop monitor! To get around this weakness, public-key systems were invented.

Here is an everyday example to illustrate public-key encryption in use. You’ll see that it actually combines symmetric and public-key encryption – most or all of today’s encryption methods involve different combinations of public and private keys. Let’s say I want to pay for a CSEG luncheon ticket online. Figure 1 outlines the steps taken.

As soon as I get to the secure PayPal page, its address will begin with “https” rather than “http”, indicating that I am entering a secure process, probably an SSL (secure socket layer) or TSL (transport layer security) protocol. In step 1, my browser basically says “hello”, and sends stuff like its SSL version number, cipher settings, session-specific data, and other information that the PayPal server needs to communicate with me.

In step 2, the two key pieces of information PayPal sends back are its public encryption key, and its SSL certificate number. Step 3, my browser checks with the SSL certificate authority (there are a number of these businesses that get paid to essentially be a trustworthy middleman to ensure a party is who it says it is) whether the PayPal browser is legitimate. But the key step is 4, where my browser sends back my symmetric key to PayPal, encoded with PayPal’s public-key. The reason this is done is that symmetric-key encoding and decoding is a lot faster than asymmetric, and so the asymmetric key system is only used once to send my symmetric key to PayPal. Once PayPal receives my encoded symmetrickey, it uses its private key to decode it. After that all information exchanged is encrypted using my symmetric-key.

Variations of this type of process are used for many of the digital information exchanges we use, including email, voiceover- IP, texting, etc. They are all based on the use of keys, and this means key management, usually behind the scenes, is a critical component of our networked age. The loss of keys can render data meaningless, so this is a critical area. I should note that a large piece of digital security involves authentication and hash algorithms, and this topic could be further extended into the area of digital rights management, but this article has more than enough to handle with pure encryption.

The relationship between the public and secret keys is worth looking into in more detail, and will get you math boffins into a lather (of excitement). Explanations that I’ve found helpful seem to start off with simple analogies, so that’s what I’ll do too. From a conceptual point of view, I could send you a message in a box with a padlock that only I have the key to. You then add your own padlock to the box and send it back to me. I unlock my lock and take it off, then send the box to you a second time, but now it has only your lock on it, so you can unlock it upon receipt. Bottom line – I’ve been able to securely send you a message, without either of us having to exchange our keys and thus expose them to theft or copying.

Now take it a bit further. I plan to send you the message, so I ask you to send me your lock, but unlocked, and then I put the message in the box, lock it with your lock and send it off. Take it even further and make it a bit more abstract, and we’re getting close to public-key encryption – you send me instructions on how to build a lock, but in building it I have no way to deduce how to construct the key to open it. I build the lock, lock my message with it and send the box off to you, and you having the key, are able to open it. Substitute the term public-key for the instructions, and private-key for your key, and instead of a physical lock think mathematical algorithms, and you’ve got publickey (or asymmetric-key) encryption!

So what are these mathematical relationships? This is the part I find really tricky, but I think I can blunder my way through an example. Generally the relationships have to be asymmetric in that the encryption is easy and the decryption is hard, and by easy/hard I mean from a computational perspective. In mathematical terms, these are trapdoor functions. Given a certain function, in most cases figuring out its inverse function is relatively easy. Let’s say we have a function,

F(x) = (x * 81) - 13

Its inverse function is obviously

G(x) = (x + 13) / 81

It is a trivial exercise to construct G(x) knowing F(x) – you simply reverse the order of the operations. But with trapdoor functions it is extremely difficult to deduce what the inverse function G(x) is even when the function F(x) is known.

An example might be that multiplying two integers is relatively easy, but deriving all the resultant answer’s prime factors is relatively hard. This indeed is the very relationship that RSA encryption is based on. RSA comes from the first letters of the names of the people at MIT who developed the method in 1977: Ron Rivest, Adi Shamir and Leonard Adleman. Their algorithm and methodology provide a good example as most other modern encryption methods are very similar. One notable one is PGP (pretty good privacy).

Using the RSA method we’re going to derive values for P, Q, and R where P & R will make up the public-key, and Q & R the private-key.

R is chosen first as the product of two large prime numbers, but for our example let’s use two smaller primes, 3 and 13.

R = 3 * 13 = 39

To proceed further, a little side explanation is required here. Euler’s totient function j(N) gives the number of numbers that are relatively prime to N, that is the number of integers between 1 and N-1 that do not have any factors in common with N.

E.g. φ(8) = 4 (there are 4 relative primes to 8: 1,3,5,7)

Now there is a handy formula that states that when a number R is a product of two prime numbers U and V, then,

φ(R) = (U-1)*(V-1)

So for our example,

φ(39) = (3-1) * (13-1) = 24

Now back to the main thread – we’re going to choose P and Q such that,

P * Q = 1 (mod φ(R)) = 1 (mod 24)

I don’t know if I ever studied modulus mathematics – if I did it is long forgotten – but trust me when I say that what the above equation means is that under a modulus of 24, (P*Q) and 1 are considered to be the same number. You can think of the modulus as the number of points along a circle, and 1 (in this case) is the remainder, or partial circle left when P*Q is wrapped around the circle. So here P*Q can be 25, 49, 73,... and so on to infinity because each one of those numbers leaves a remainder of 1 on the modulus “circle”. Sometimes modulus math is called clock face math, because a clock is modulus 12 (or 24 in some parts of the world), and every 12 hours times repeat themselves. There are all kinds of tricks possible using modulus math, mainly related to reducing numbers to their remainders before doing the number crunching – this property has been exploited within computers to shorten calculation times for operations involving extremely large numbers, such as, not coincidentally, with encryption.

In choosing P and Q there are additional conditions besides those imposed by the last equation: P and Q must be whole numbers, both must be relatively prime to 24, and preferably to each other. Each of them can also not be congruent to mod 24 (24, 48, 96, ...) because then the asymmetric trapdoor keys will become symmetric keys.

Let’s arbitrarily choose P to be equal to 5, then we can easily calculate all the possible Q’s by,

5 * Q = (K * 24) + 1, where K can be any number. We don’t get a suitable solution for K = 1, 2, 3, 4, 5, but when K = 6 the right side is 145 and is divisible by 5, giving a Q of 29.

Alright, so we’ve now got,

P=5
Q=29
R=39

I bolded them because if you’re like me you’ll refer back to them many, many times in trying to figure out what follows. The way we’re going to use them to encrypt our message exploits a certain property of modulus math, so I’ll briefly explain that before actually doing a sample encryption.

After a whole bunch of mathematical gymnastics, it can be shown that,

T^(S+1) = T (mod R),

or in other words, if we raise a number T to the power of S+1 using modulus math, it gives us T again. If we choose two numbers P and Q such that their product equals S + 1, then that gives us the equation mentioned above, P * Q = 1 (mod j(R)). This is the crux of it, as you will see. Substituting in P*Q gives us:

T^{(P * Q)} = T (mod R),

which is equivalent to:

(T^P)^Q = T (mod R)

Importantly, this can then be expressed as a combination of two separate steps:

T^P = X (mod R), and then X^Q = T (mod R).

And there you have it – two steps, the first using the public keys P & R, and the second the private keys Q & R, with X being the encrypted data value!

To encrypt something we use T integers that are all the relatively prime numbers to R, except for 1 and R-1. The following chart maps out the T values relative to the alphabet:

For simplicity’s sake let’s encode a simple word that doesn’t need letters beyond V because that’s all we’ve got; obviously in a real case our R number would be huge, giving us lots of numbers to work with. The message we’ll encode is “OIL”. We take the number corresponding to the letter, and then raise it to the power of P modulo R:

O: 25⁵ mod(39) = 9765625 mod(39) = 5
I: 16⁵ mod(39) = 1048576 mod(39) = 22
L: 20⁵ mod(39) = 3200000 mod(39) = 11

The code numbers 5, 22, 11 translate to C, M, G in the chart, and that is the encrypted message sent to the recipient, who to decode the message just needs to follow the same procedure using Q instead of P:

C: 5²⁹ mod(39) = 186264514923095703125 mod(39) = 5
M : 22²⁹ mod(39) = 851643319086537701956194499721106030592 mod(39) = 16
G: 11²⁹mod(39) = 1586309297171491574414436704891 mod(39) = 20

The decryption has delivered back the original code numbers 5, 16, 20 which of course represent the originally encoded word OIL. Of course the real test of RSA encryption’s effectiveness is to see how difficult it is to figure out the secret key (Q), given the public key P & R. Let’s say my example message of CMG, P=5, and R=39 is intercepted by evil forces; how easy is it for them to figure out Q, and then decode the message?

Reworking an earlier equation gives,

Q = (K * φ(R) + 1) / P

Different values for K can be systematically plugged in one after the other, and each time a possible value is found, the message can be decoded and checked to see if it makes sense. In our example we know that the right answer for Q will be found to be 29 when K=6, so that will be quite easy and quick. If it’s not at K=6 then every 7th number after that needs to be checked, until we find it. So that all seems very easy for a computer to do, but the challenge is that φ(R) needs to be known, and that is very time consuming, even for a computer, when R is big.

My head already hurts from all this math, so I’ll cut out a lot of the details. When selecting P and Q, which have to both be primes, there are quick tests to determine whether they are primes or not, for example a form of Fermat's Little Theorem. That means we can use a computer to randomly generate massive prime numbers for P and Q. Their product creates an even bigger composite number (a positive integer that can be divided by at least one positive integer other than itself, in other words any number greater than 1 that is not a prime). There are no known ways to efficiently calculate the prime factors for a composite number – the only way to do it is to keep dividing in primes until one works. For massive, massive numbers, even this is computationally prohibitive for computers.

So the prime factor based encryption techniques like RSA all boil down to that computational inequity – faster to encrypt than decrypt. If mathematical solutions are found for solving prime factors, then these current encryption techniques will be rendered obsolete overnight. Given the millions of hours mathematicians have spent pondering the intricacies of prime numbers, this seems unlikely, but you never know. Just recently a paper published by an unknown mathematician gave a theorem apparently proving a well-known (to mathematicians) conjecture regarding pairs of primes, stunning the math world (Ellenberg, 2013). Some apparently obscure advance like that may provide the key to cracking encryption codes, which would turn the digital security world upside down!

I wish readers a fantastic summer. I hope to write up a few articles during the break, and am already working on a fragrant topic for September.

Key search terms: Encryption, decryption, public key, asymmetric key, SSL, Diffie- Hellman, Blowfish cipher, AES, PGP

References

Calculatorpro. (2013). Modulo Calculator. Retrieved May 27, 2013, from Calculatorpro: www.calculatorpro.com/calculator/modulo-calculator/

Defuse . (2013, May 19). Online Big Number Calculator. Retrieved May 27, 2013, from Defuse Computer Security R&D: https://defuse.ca/big-number-calculator.htm

Ellenberg, J. (2013, May 22). The Beauty of Bounded Gaps. Retrieved May 27, 2013, from The Slate Group, a Division of the Washington Post Company: www.slate.com/articles/health_and_science/do_the_math/2013/05/yitang_zhang_twin_primes_conjecture_a_huge_discovery_about_prime_numbers.html

IBM. (2012, November 1). An overview of the SSL handshake. Retrieved May 27, 2013, from IBM: http://publib.boulder.ibm.com/infocenter/wmqv6/v6r0/index.jsp? topic=%2Fcom.ibm.mq.csqzas.doc%2 Fsy10660_.htm.

Raiter (aka Organic Worker Drone BR903), B. (1994). Prime Number Hide-and-Seek: How the RSA Cipher Works. Retrieved May 27, 2013, from Muppetlabs, Inc.: www.muppetlabs.com/~breadbox/txt/rsa.html.

Tyson, J. (n.d.). How Encryption Works. Retrieved May 26, 2013, from How Stuff Works: www.howstuffworks.com/encryption.htm.

Wikimedia Foundation, Inc. (2013, May 23). Encryption. Retrieved May 27, 2013, from Wikipedia: http://en.wikipedia.org/wiki/Encryption.