Cryptography: Old vs New

There are things that we want to tell somebody else, but not everybody, so you write the message in a special way that only the intended recipients can know its actual meaning. For example, in primary school you might have tried to pass a secret note to your best friend in class, of which the content could only be understood by you two (at least that’s what you thought).

Transforming a message (plaintext) into something that looks like “nonsense rubbish” (ciphertext) is called Encryption, while transforming it back to meaningful message is call Decryption. Cryptography is the study of encryption methods.

We have been encrypting messages for thousands of years. Probably the most well-known ancient encryption method is the Caesar cipher, the encryption method invented by Julius Caesar to communicate with its army against spies from the enemy.

 

Caesar cipher is simple: substitute every alphabet with the one 3 places next. i.e. A->D, B->E, C->F,…, W->Z, X->A, Y->B, Z->C.

For example, the message “HELLO WORLD” is transformed into “KHOOR ZRUOG”. To convert it back, simply substitute every alphabet with the one 3 places before.

There are variations to the method. For example, you may decide how many places the alphabets should be shifted. You may even decide to shift alphabets in different words by a different number of places. As long as your recipient knows how you shift the alphabets, he/she can decrypt the ciphertext.

It is not hard to imagine how quickly this method can be broken. For example, by counting the number of times each alphabet appears in the ciphertext, then try matching the most frequent one with “E”, “T”, “A”,…(most frequent alphabets in the English words). This is known as frequency analysis. It is also very quick to experiment with different shifts until meaningful words are obtained.

 

Encryption with Caesar cipher is unreliable. Therefore, people have devised other more complicated, secure methods. Machines have been developed to apply those methods efficiently. The Enigma machine is a famous example.

Invented by Germans, the Enigma machine was mainly used by Nazi Germany for encrypting military messages. It looks like a typewriter with three wheels. When a key is pressed, some circuit within the machine is completed, and a lamp shows up, indicating the ciphertext.

The Enigma code was very difficult to crack, mainly because there are quintillions ways to set the machine to generate a different ciphertext. Nonetheless, three Polish mathematicians eventually found a way to solve it. (Who said theoretical maths has no application?) How they solved it deserves a separate blog post. Some people estimated that the successful breaking of the code helped the Allies to end the European was by two years.

Both the very insecure Caesar method and the secure Enigma machine belong to the same broad class of cryptography – Private-key cryptography (or better known as symmetric key cryptography)

 

Private-key cryptography

Suppose two people, Ada and Mandy, want to send secret messages to each other. For fear that their messages may be read by spies, they have to encrypt the messages before sending it out.

The first thing they have to do is to meet up and discuss how they should encrypt the message, also how the message can be decrypted. Then, when Ada needs to send a message, she first encrypts it, send out the encrypted message, Mandy receives it and decrypts it back to the original message.

The method is called “symmetric” because once you know how the encryption is done, you know how to reverse it, just like a two-way road.

Is it necessary for them to meet up first? They cannot just send an email to reach other about what encryption method to be used, since a spy may be able to intercept the email and then know how to break their code.

Also, for secrecy, you need a different encryption method for each of your recipients. Suppose Ada also wants to send secret messages to Dennis, she will need to discuss with him another encryption method. The more recipients she has, the more troublesome it gets.

In modern days we often need to send private information to people or companies, from personal emails to bank account information. The requirement that both parties need to possess the key (decryption method) significantly limits its use.

Then, in the 1970s’, the concept of Public-key cryptography emerged and became popularized.

 

Public-key cryptography

Back to the example of Ada and Mandy. Now, instead of discussing a way to encrypt the messages, they set up their own mailboxes in the postoffice, and lock them up with their own locks. When Ada wants to send a secret message to Mandy, she simply puts the letter into Mandy’s mailbox.

Since only Mandy has the key of her own mailbox, no one else can open it to read the messages inside. They two need not meet up beforehand. Sending secret messages to a stranger becomes possible. All you have to do is to find out his/her mailbox and put the letter in.

Public-key cryptography system solves the problems we have with the private-key system, as it removes the requirement of “both parties need to possess the key”. Now, only the recipient needs the key.

In real life, public-key cryptography requires everyone to publish his/her own encryption method. When you want to send a secret message, you look for the encryption method of the recipient, encrypt the message and send it out.

But a new problem arises. If you know how the message is encrypted, doesn’t it imply that you also know how to decrypt it? The core problem is similar to building a transparent lock which everyone can see its interior structure clearly, yet you are the only person who can create a key for it. How is this even possible?

 

Asymmetric-key algorithm – analogy

Remember phonebooks? The thick yellow books that were best used as cutting mats? Back in the days when computers were not yet common household appliances, not to mention internet and websites, phonebooks were useful for people to look up for the phone numbers of people and companies.

In a phonebook, the names are arranged in alphabetical order, and the phone numbers are listed next to the names. It is very easy to search for a phone number given the name.

However, searching the name given a phone number is extremely difficult and tedious.

There is simply not a clear pattern for the order of phone numbers, and it is impossible to guess where the next number is located. For example, even if you know the name of the recipient of 24567111 (which I am sure many of you do. If not, try calling), you still have no idea who is going to answer the call to 24567112.

This is known as an asymmetric algorithm, also known as trap-door function, where working in one way is simple, but working in the other way is immensely difficult, if not impractical.

The encryption method is basically a function that is easy to compute but very hard to solve. When you construct the function, you adjust some parameters so that there is a “special trick” to solve it. The special trick is called the private key, and you should never disclose it to anybody else. It is just like a phonebook sorted by phone numbers instead of names. Meanwhile, you publish the function that you have created, and ask people to encrypt the messages with it.

The security of the method relies on whether people can find out the parameters just by looking at the function itself. If they can, then they can construct the private key from the parameters and the encryption method is broken.

This still sounds more like fantasy, doesn’t it? Thanks to Number Theory, three mathematicians developed the first practicable public-key system, the RSA algorithm in 1977, which will be introduced next time. Who said Number Theory is just for curiosity?