University of Silesia in Katowice

Cryptology Day – 25 January

| Prof. Jerzy Dajka |

Origins of cryptography reach back to the 19th century BCE, however, the term ‘cryptology’ was first used in 1844 when – borrowing from Greek kryptós and logos – the art of searching for the hidden received its name.

Until the middle of the 20th century, cryptography was primarily used by the military and diplomatic service. The protocols used were based on sharing a secret key that was used by the parties to ‘translate’ messages into ciphertext and ciphertext into messages. Many of the tools used at the time are of rather historical interest today, e.g. the Spartan scytale, the so-called Caesar cypher, or the Vigenere cypher. It was not until mathematicians and cryptologists played a decisive role in deciphering the German Enigma and the impact of this event on the course of World War II that cryptology began to be widely perceived as an effective and dangerous tool of war.

Key to knowledge and secrets

Cryptology involves building and analysing protocols that will not allow unauthorised people and systems to decrypt messages. The primary goal is to guarantee fundamental safety functions: confidentiality, message integrity, making authentication possible, and guarantee non-repudiation. In other words, the protocol should guarantee that the message that we are sending won’t be read (and understood) by unauthorised people, that someone won’t add or delete anything from it, that it will be undersigned, and that we won’t be able to deny sending the message even if we really wanted to.

As modern mathematics entered the field of cryptology, i.e. numbers theory, probability, information theory, and modern algebra, symmetric protocols, using a secret key, started becoming increasingly subtle. However, there was still the problem of generating a secret key and transferring it to someone without the risk of exposure. During the Cold War in the 1960s, solving this problem was a priority. However, the solution and a true breakthrough came in the 1970s with the Diffie–Hellman protocol and the RSA cryptosystem laying the foundations for public key cryptography. These protocols not only allowed to generate a secret key for quick symmetric protocols but also were the basis for completely new solutions, e.g. today’s digital signature.

Thanks to Ron Rivest, as well as Adi Shamir and Leonard Adleman – creators of RSA, modern cryptology brought also a new family onto the scene: the inseparable Alice and Bob. Ever since then, many cryptology works begin with the words: ‘Alice wants to send a message to Bob’. Alice and Bob engage in confidential and undeniably authenticated (using hash functions, passwords, identification) transmission of information, exchange a key between them, share common secrets, flip a coin at a distance (bit commitment) and even boast about their achievements without displaying them openly (zero-knowledge proof). Alice and Bob are eavesdropped on by Eve and attacked by Mallory or Charlie, which makes the ‘crypto-family’ complete, even if a little dysfunctional.

To break the cipher

Although, the mathematics concepts used for the RSA protocols were not novel at the time of its creation and were based on the discoveries made several centuries back, achieving a satisfying level of security necessitates the utilisation of large numbers, which are difficult to calculate the way our ancestors did – by hand, without using computers. This and the obvious interest in confidentiality by the military caused secret-key cryptography to have no real alternative for quite a long time. Meanwhile, the progress in cryptology theory along with the development of computing methods became a blessing and a curse for the safety of cryptosystems.

When Martin Gardner used RSA to leave an encrypted text in Scientific American in 1977 (Scientific American 237 (2): 120–124) and was convinced that deciphering it would take ‘millions of years’, he certainly did not expect that just after 17 years the world will find out that ‘the magic words are squeamish ossifrage’ thanks to a brute force attack, internet, and distributed computing.

Along with the developments made in cryptography and the appearance of various cryptosystems, different attack methods have also emerged, depending on the tools and knowledge that has become available. If the hypothetical Eva has a cyphertext, she can, being a good linguist, she can, being a good linguist, attempt to reconstruct the plaintext by way of letter or word frequency analysis. If she has the plaintext and the respective cyphertext, she can attempt to understand the encryption mechanism. Historic cyphers were vulnerable to such attacks. If Even can encrypt a given plaintext all on her own, then she is also on a path to success: this kind of attack was executed by mathematicians and cryptologists when they were reconstructing Enigma’s encryption process. If Eve has the cypher at her disposal, she can attempt to modify it slightly and check whether the deciphered message will turn into gibberish: in this case ‘Eve’ can be a server modifying the encrypted message and observing the reaction of the recipient.

Attacks can be carried out ‘by brute force’, using increasing and available computing power, based on the physical characteristics of cryptosystem implementations (the use of copies of Enigma is a historical example), and very often by seemingly non-cryptology methods of ‘social engineering’. Among the possible attack methods, analytical attacks that take advantage of the weaknesses of the encryption methods themselves are the most beautiful. It is worth pointing out here that the modern standard is the 19th-century Kerckhoff’s principle, according to which the method of encryption must not be required to be secret and the acquisition of the method must not cause problems.

Information security

The set of contemporary threats to the confidentiality of encrypted messages is now being expanded to include risks associated with the development of quantum computers. A very important group of cryptosystems bases its security on the difficulty (in terms of computational complexity) of today’s known solutions to the problem of decomposing numbers into prime factors or the discrete logarithm. To put it simply – we do not know how to solve these problems, and therefore break the cryptosystems based on them, in a reasonably short time. Access to a quantum computer that enables an efficient implementation of Shor’s algorithm will change this situation, as the computation time required to break a large group of cryptosystems will go from being ludicrously exponential to pleasantly polynomial. The response to this threat is, on the one hand, the thriving development of post-quantum cryptography, which, although classical in essence, is resistant to attack using Shor’s algorithm, and, on the other hand, the increasing use of quantum cryptography whose security is guaranteed by Mother Nature herself, provided it is implemented correctly.

Together with the ‘era of information’ came the common and frequent use of cryptological solutions. While people still painstakingly scratch out passwords on the backs of their credit cards, modern and secure methods of ensuring the security of data transmission have emerged using widely accepted security standards verified by subtle certification methods. Alice and Bob are increasingly often non-human entities, i.e. servers, smart cars, and even smarter fridges. We want to believe that our communication is safe and confidential and that no unauthorised person can eavesdrop and forge our messages, even in the name of the ‘common good’.

Nowadays, an area where cryptology plays a crucial role (or at least should) is online election voting systems. Electronic and remote voting is becoming an increasingly common form of casting a vote. Even this year’s elections at the University of Silesia are done online. Modern cryptology provides us now with a range of reliable tools that should constitute the foundation for true democracy. It is worth bearing in mind that non-compliance with security standards can (and even should) be a basis to contest election results. Voting must be carried out correctly: only those entitled to vote can cast a vote and they do so only once, votes may not be swapped or the results altered in any way, and voters must be guaranteed verifiability and privacy. In addition, the above-mentioned Kerckhoff principle about the open knowledge of the method used should apply here too. If, due to various reasons, we are not certain that we can comply with the strict security standards of electronic voting, employing some other, more secure but less modern method, should be considered.

Today, wrapped up in the social web and the Internet of Things (IoT), we forget that our security is guarded by algorithms, the fruits of the labour of generations of mathematicians and cryptologists, and they do so to a far greater extent than was the case in the wartime days of Enigma. Even though cryptology might not seem like a tool of war, we should remember the wise words of ancient people – si vis pacem, para bellum – and bear in mind that cryptology has earned its own day.

The article was written for the Scientific Information Agency of the University of Silesia in Katowice.