DesignSpark Electrical Logolinkedin
Menu Search
Ask a Question

7 May 2020, 13:02

Industrial Security Part 2: About Asymmetric Keys

Part 1 refresh: Keys and Encryption

Symmetric versus Asymmetric Keys

We need to talk about an extraordinary concept in cryptography. This concept uses different keys for encrypting and decrypting messages. Therefore it is called asymmetric cryptography. It solves the following problem. It’s a love story:

Pete loves Helen, and she loves him. But Helen lives 300 km away from Pete. So she is sending him love letters. She will not bother if anyone else read her messages because there is nothing wrong with loving Pete. But she would not like Susan to send Pete letters and pretend to be Helen. Susan loves Pete too. But she has no chance as long as Pete shares his love with Helen. So Susan plans to send Pete a letter pretending to be Helen and saying that she would break up with Pete. Pete wants to be sure that messages from Helen do come from Helen and that no one could manipulate them.

Susan has sent Pete a key to decrypt the letters she has encrypted. This key is a copy of her own. The two keys are identical and therefore called “symmetrical” (I mark them sKpriv = symmetric private key). So Pete could be sure that if his key does decrypt the message, it must be encrypted with this key. But as the digital key is not a hardware but a number. And Susan does keep an eye on the mail traffic between Helen and Pete. So Susan might have opened the letter with the key and copied that number when it was on its way from Susan to Pete. Now she can read all the encrypted messages (which does not bother Helen or Pete), but what is more relevant, she can also write letters and encrypt them with Susan’s and Pete’s secret key. Poor Helen, poor Pete…

But here comes the asymmetric key: Helen generates two keys which are not identical. With the first one, she can encrypt the message, and with the second one, someone else might decrypt it. This also works vice versa. Helen sends the second key to Pete. As anyone could spy out the letter with this key, such a key is called “public key” (aKpub). She keeps the other key private and secret (aKpriv). Therefore this key is called “private key”. Now let’s assume Susan copies the public key. She did it again? Well, not really. The only thing she can do now is reading Helen’s messages to Pete because her copied key is only suitable for this process. If she tries to encrypt a letter with this key, Pete would not be able to decrypt this letter with his copy of the public key.

Mathematically asymmetric cryptography is done with “one-way functions”.  This type of functions are easy to solve in one direction, but the inverse function is a “very difficult” mathematical task.

Before I can give you an example, I need to explain modular arithmetic. Those of you who are programming 8-bit CPUs using C language will know what happens when you add 200 + 100 in byte arithmetic. You will not get 300 because an eight-bit byte can only count up to 255. Some systems will raise an error, but normally you simply get what you call “wrap-around”: after adding 56 the byte is set to zero again, and the result is what is left from 100, namely 44. You can express this wrap-around with the “modulus” function (the onboard Windows 10 calculator does provide this function in scientific mode):

300 mod 255 = 44

Let me explain

32 mod 14 = 4

In a different way for those of you who are not programming bits and bytes operations:

Think of a clock with 14 ticks (instead of the typical 12). You start circling from the tick 1 for altogether 32 marks. At the end of this procedure, you will arrive at tick number 4. If you like, you could also define the X = A mod B is calculated by taking the remainder of the division A/B.

Back to our one-way functions. Let’s take a simple example of such functions:

X = YA

can be inverted straightforward to

Y = X1/A

Any pocket calculator can compute the result of this equation. So this would not be one-way.

But you will have a challenging task to reverse the function

X = YA mod B

If your non-coded message Y is, e.g. 2 and your coding key A is 5, while you chose B to be 14 you get a coded message

X = 32 mod 14 = 4

Now try to find out what value of Y was used (non-coded message) if you only know the result X, A and B (4, 5, 14). Not only that this is a difficult task, but you will also end up by finding more than one solution (in our example, e.g. not only 2 would work as Y, but 16 would also result in X=4.

There is a mathematical way to get Y from X, which I will describe in detail. With this procedure, you need to find a third key parameter C which corresponds to A and B in such a way that you will get the result with this equation:

Y = XC mod B

In our example, C would need to be 11: 

411 mod 14 = 4,194,304 mod 14 = 2

This is how (one type of) asymmetrical keys work. In our example, you generate the private key A and public key C (which only work in conjunction with a public known B). You can code your message (according to the equation above) with key C. Someone else can decode it only with key A. If you code the message with key A the receiver can only decode it with his key C. Please take the key generation as a black box function provided by many libraries. 

AES and RSA

You may have heard of AES (“Advanced Encryption Standard”) which is a symmetric cryptographic algorithm. There are many more and if you want to get deep into the maths of such algorithms and learn about their security level, please go ahead and follow the links on the Wikipedia article on “Symmetric-key algorithm”. For now, you can take the algorithm as a black box and just need to know that the longer the key is (i.e. the more bits it has), the more secure the encryption is. AES.256, e.g. uses 256-bit keys, and it is known to be (currently) very confident. A modern supercomputer would need more time to hack a 256-bit key encrypted message than our universe’s age. It would require about 2254 (that’s about a 3 with 76 zeros behind) steps to find the right key.

The most commonly used asymmetrical key algorithm is called “RSA” (the letters stand for the three inventors’ names). Asymmetric keying uses much bigger keys and needs much more computing power compared with symmetric algorithms.

RSA is often combined with something called “OAEP” to make it more robust against attacks.  OAEP adds a random factor to RSA. Thus it changes the algorithms from being deterministic to be probabilistic.

Because such random factors will also be part of the practical work later in this series, I would like to explain its need a little more:

We continue with the above example. This time Pete is using his public key now to send Helen a secret message. And this time he does not want Helen or anyone else to read it. That’s possible because he can encrypt the message with his public key. Only the possessor of the private key (Helen) can decrypt this message. Please note that this is typical for asymmetric keying: Because the public key is exchanged "publically" the sender cannot send secret messages (anyone could read them because decryption is done with the publically known key). The receiver can only be sure about the authenticity of the message he gets. But any possessor of the public key can send secret messages to the owner of the private key which only he can decrypt. Once we get to certificates and signatures, you will understand the necessity of both cases.

Susan has made new plans: She has detected that whenever Helen asks Pete "Do you love me?" Pete is sending one of three different answers. So Susan builts a library of encoded possible and expected messages, all done by using the public key. Let's assume Pete is one of these short worded males. Susan could expect one of possibly 1,000 messages. She is now spying the answers of Pete to Helen's repeating question and compares them to her library. When she gets a match, she knows the original content (called “plaintext”) of the message. This is called a “chosen-plaintext attack”. It is especially efficient with short messages and a limited variety of content. Imagine Pete would add a delimiter at the end of his message and then add a random number. This way, he would never send two identical messages. Helen would be able to separate the real content from the random content because she knows the delimiter. Still, Susan would never get a match with her library (the random part is too long to generate all possible combinations).

We will simply take the asymmetric algorithm as black boxes also. Again, if you love maths, please go ahead and study one of the excellent books on cryptographic algorithms. To give you an impression of what you will read I’m just citing the introduction of the OAEP article in Wikipedia:

“The OAEP algorithm is a form of Feistel network which uses a pair of random oracles G and H to process the plaintext prior to asymmetric encryption. When combined with any secure trapdoor one-way permutation f {\displaystyle f} f, this processing is proved in the random oracle model to result in a combined scheme which is semantically secure under chosen plaintext attack (IND-CPA). When implemented with certain trapdoor permutations (e.g., RSA), OAEP is also proved secure against chosen ciphertext attack. OAEP can be used to build an all-or-nothing transform. “

Believe me, that stuff is gibberish to me. When it comes to “random oracles” I prefer to take this miracle as a black box which is working perfectly for me. (I know, those nerds will find possibilities to make it look “bad” on their conferences because it no longer takes billion of years to hack the keys but only millions). So don’t feel ashamed when you do not deeply understand the algorithms behind these concepts.

Later in this series, we will become more practical. It is not a big business to integrate AES or RSA into your program code as there are many libraries out there helping you to do the heavy maths. “Open SSL” is one of them and the most commonly used.

Part 3: Covers Hash and Signatures

Volker de Haas started electronics and computing with a KIM1 and machine language in the 70s. Then FORTRAN, PASCAL, BASIC, C, MUMPS. Developed complex digital circuits and precise analogue electronics for neuroscience labs (and his MD grade). Later database engineering, C++, C#, hard- and software developer for industry (transport, automotive, automation). Ended up designing and constructing the open source PLC / IPC "Revolution Pi". Today engaged in advanced development as a service.

7 May 2020, 13:02