Learning Objectives

In this course, you will learn about

1. the terminology, aims and history of cryptography,
2. the basic principles of symmetric algorithms (those with a single key),
3. the principles of asymmetric algorithms (those with a public and private key),
4. the methods of user authentication, the proof of the identity of a user,
5. the methods of cryptanalysis, the art of deciphering enciphered data without knowledge of the key,
6. the practical considerations of applied cryptography in a corporate environment,
7. its manifold implementations, for example, in Online banking, Blockchain and electronic voting.

The recommended reading will introduce you to the most important authors and articles in cryptology.

1 Basic concepts of cryptology

Study Goals

On completion of this chapter, you will have learned …

• … to distinguish between cryptology, cryptography and cryptanalysis.
• … what cryptography is good for: IT-security for Confidentiality, Integrity and Availability.
• … basic (historic) cryptographic algorithms.
• … its historical impact.
• … a key criterion (by Kerckhoff) for best cryptographical practice.
• … The principal uses of Hash functions.

Introduction

Cryptography serves to protect information by encryption (or enciphering), the shuffling of data (that is, the transformation of intelligible into indecipherable data) that only additional secret information, the key, can feasibly undo it (decryption or deciphering).

encrypt/encipher: to shuffle data so that only additional secret information can feasibly undo it.

key: the additional secret information that is practically indispensable to decrypt.

decrypt/decipher: to invert encryption.

That is, the shuffled (enciphered) data can practically only be recovered (deciphered) by knowledge of the key. Since the original data is in principle still recoverable, it can be thought of as concealment.

Because historically only written messages were encrypted, the source data, though a string of 1s and 0s (the viewpoint adopted in symmetric cryptography) or a number (that adopted in asymmetric cryptography), is called plaintext and the encrypted data the ciphertext.

plaintext respectively ciphertext: the data to be encrypted respectively the encrypted data.

Single and Public-Key Cryptography

Historically, the key to reverse this transformation (of intelligible data into indecipherable data) was both necessary to decipher and to encipher, symmetric encryption. That is, in the past, the key used to encrypt and decrypt was always the same: Symmetric cryptography had been used by the Egyptians almost 2000 years before Christ, and was used, for example,

• during World War II on the Engima machine, and
• nowadays, in the encryption of a wireless network (for example, by the AES algorithm).

symmetric cryptography: cryptography is symmetric when the same key is used to encrypt and decrypt.

In the 70s asymmetric cryptography was invented, in which the key to encipher (the public key) and the key to decipher (the secret or private key) are different.

asymmetric cryptography: cryptography is asymmetric when different keys are used to encrypt and decrypt. The key to encipher is public and the key to decipher is private (or secret).

In fact, only the key to decipher is private, kept secret, while the key to encrypt is public, known to everyone. In comparison with symmetric cryptography, asymmetric encryption avoids the risk of compromising the key to decipher that is involved

• in exchanging the key with the cipherer, and
• in ownership of the cipher key (by the cipherer in addition to the decipherer).

On top, It is useful, that the keys exchange their roles, the private key enciphers, and the public one deciphers, a digital signature: While the encrypted message will no longer be secret, every owner of the public key can check whether the original message was encrypted by the private key.

Nowadays such asymmetric cryptography algorithms are ubiquitous on the Internet: Examples are

• RSA which is based on the difficulty of factoring in prime numbers, or
• ECC which is based on the difficulty of computing points in finite curves,

which protect (financial) transactions on secure sites (those indicated by a padlock in the browser’s address bar).

Data Format

Up to the digital age, cryptography mainly studied the transformation of intelligle text into indecipherable text. Since then, cryptography studies the transformation of processible (digital) data into indecipherable (digital) data. This data is, for example, a digital file (text, image, sound, video, …). It is considered a bit sequence (denoted by a string of 0s and 1s) or byte sequence (denoted by a string of hexadecimal pairs 00, 01, …, FE, FF) or a number (denoted as usual by their decimal expansion 0, 1, 2, 3 …). Let us recall that every $1011...$ bit sequence is a number $n$ via its binary expansion $$n = 1 + 0 \cdot 2 + 1 \cdot 2^2 + 1 \cdot 2^3 + \cdots$$ (and vice versa).

The point of view of a sequence of bits (or, more exactly, of hexadecimal digits whose sixteen symbols 0 – 9 and A – F correspond to a group of four bits) is preferred in symmetric cryptography whose algorithms transform them, for instance, by permutation and substitution of their digits. The point of view of a number is preferred in asymmetric cryptography whose algorithms operate on it by mathematical functions such as raising to a power (raising to a power) and exponentiation.

The key, the additional secret information, can take various form; which form is mainly a question of convenience, most common are:

• that of a number,
• that of a sequence of letters, for example,
  • a password, or
  • a secret phrase (with spaces).

For example, in the ancient Scytale algorithm (see Section 2) that uses a role of parchment wrapped around a stick, the key consists of the circumference (in letters) of the stick, a small number. Nowadays, PIN codes (= Personal Identification Number) or passwords are ubiquitous in day-to-day life; to facilitate memorization the memorization of complete secret sentences (= pass phrases) is encouraged.

Asymmetric encryption depends on larger keys and therefore stores them in files (of 64-letter texts, called ASCII-armor) of a couple of kilobytes. For example (where ... indicates tens of skipped lines):

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: SKS 1.1.6
Comment: Hostname: pgp.mit.edu

mQENBFcFAs8BCACrW3TP/ZiMRQJqWP0SEzXqm2cBZ+fyBUrvcu1fGU890pd4
3JdiWIreHx/sbJdW1wjABeW8xS1bM67nLW9VVHUPLi9QP3VGfmqmXqbWIB7O
...
-----END PGP PUBLIC KEY BLOCK-----

1.1 Terminology

The prefix Crypto-, comes from Greek kryptós, “hidden”.

Cryptography

Cryptography (from the Greek gráphein, “to write”) is the art of hidden writing: shuffling information so that it is indecipherable to all but the intended recipient.

Cryptography: the art of transforming information so that it is indecipherable to all but the intended recipient.

That is, cryptography is the art of transforming information such that it is incomprehensible to all but the intended recipient. Useful, since Antiquity, for example to conceal military messages from the enemy. Since then, (electronic binary) data has replaced text, and what used to be concealing written messages exchanged by messengers or kept secret has become symmetric cryptography: securing data flowing between computers or stored on a computer.

Since the 70s, asymmetric cryptography makes it possible (by digital signatures) to verify the identities of participants and undeniably (non-repudiation) register their transactions in electronic commerce.

Cryptographic methods (or Ciphers) are generically classified

1. according to whether sender and recipient use the same key (symmetric, or single-key) cipher, such as AES, or different keys to encrypt and decrypt (asymmetric, or two-key, or public-key) cipher, such as RSA or ECC.

Among the symmetric ciphers, these are generically classified

2. according to whether they operate on blocks of bits of fixed length, say 128 bits, (block cipher, such as AES or RSA) or single bits (stream ciphers such as RC4): While stream ciphers typically are simpler, faster and predestined for real time transmissions, they tend to be less secure and are therefore less commonly used (for example, a Wi-Fi network is commonly secured by a block cipher such as AES).

Cryptanalysis

Cryptanalysis (from the Greek analýein, “to unravel”) is the art of untying the hidden writing: the breaking of ciphers, that is, recovering or forging enciphered information without knowledge of the key.

Cryptanalysis: the art of deciphering ciphertext without knowledge of the key.

Cryptanalysis (colloquially “code breaking”) is the art of deciphering the enciphered information without knowledge of the secret information, the key, that is normally required to do so; usually by finding a secret key.

Cryptanalysis of public-key algorithms relies on the efficient computation of mathematical functions on the integers. For instance, cryptanalysis of the most famous public-key algorithm, RSA , requires the factorization of a number with $> 500$ decimal digits into its prime factors, which is computationally infeasible (without knowledge of the key).

Cryptanalysis of symmetric ciphers depends on the propagation of patterns in the plaintext to the ciphertext. For example, in a monoalphabetic substitution cipher (in which each letter is replaced by another letter, say A by Z), the numbers of occurrences with which letters occur in the plaintext alphabet and in the ciphertext alphabet are identical (if A occurred ten times, then so does Z). If the most frequent letters of the plaintext can be guessed, so those of the ciphertext.

A powerful technique is Differential cryptanalysis that studies how differences (between two plaintexts) in the input affect those at the output (of the corresponding ciphertexts). In the case of a block cipher, it refers to tracing the (probabilities of) differences through the network of transformations. Differential cryptanalysis attacks are usually Chosen-plaintext attacks, that is, the attacker can obtain the corresponding ciphertexts for some set of plaintexts of her choosing.

Cryptology

Cryptology (from the Greek lógos, “word”, “reason”, “teaching” or “meaning”) is the science of hiding, the science of trusted communication which embraces cryptography and cryptanalysis; according to Webster (1913) it is “the scientific study of cryptography and cryptanalysis”. Though cryptology is often considered a synonym for cryptography and occasionally for cryptanalysis, cryptology is the most general term.

Cryptology: the science of trusted communication, including cryptography and in particular cryptanalysis.

Secrecy, though still important, is no longer the sole purpose of cryptology since the advent of public-key cryptography in the 80s. To replace by electronic devices what had historically been done by paperwork, digital signatures and authentication were introduced.

Adjectives often used synonymously are secret, private, and confidential. They all describe information which is not known about by other people or not meant to be known about. Something is

• secret, from Latin secretus “set apart”, if it is only known by a particular person or group,
• confidential, from from Latin confidere, “to have full trust or reliance”, if it is to be kept secret, that is, not to be told or shared with other people,
• private, from Latin privatus “set apart” (from the state), if it is meant to be secret, especially regarding an individual versus the state.

Frequently confused, and misused, terms in cryptology are code and cipher, often employed as though they were synonymous: A code is a rule for replacing one information symbol by another. A cipher likewise, but the rules governing the replacement (the key) are a secret known only to the transmitter and the legitimate recipient.

Code

A codification or an encoding is a rule for replacing one bit of information (for example, a letter) with another one, usually to prepare it for processing by a computer.

encoding: a rule for replacing one bit of information (for example, a letter) with another one, usually to process it by a computer.

For example,

• Morse Code, that replaces alphanumeric characters with patterns of dots and dashes,
• the American Standard Code for Information Interchange (ASCII code) from 1963 that represents on computers 128 characters (and operations such as backspace and carriage return) by seven-bit numbers, that is, by sequences of seven 1s and 0s. For example, in ASCII a lowercase a is always 1100001, a lowercase b is always 1100010, and so on (whereas an uppercase A is always 1000001, an uppercase B is always 1000010).
• more recently, UTF-8 (8-bit Unicode Transformation Format) is a variable-length character encoding by Ken Thompson and Rob Pike to represent any universal character in the Unicode standard (which possibly has up to $2^2 \approx4$ billion characters, and includes the alphabets of many languages, such as English, Chinese, …, as well as meaningful symbols such as emoticons) by a sequence of between 1 up to 4 bytes, and which is backwards compatible with ASCII , and is becoming the de facto standard.

Ciphers

A cipher, like an encoding, also replaces information (which may be anything from a single bit to an entire sequence of symbols) with another one. However, the replacement is made according to a rule defined by a key so that anyone without its knowledge cannot invert the replacement.

cipher: a rule for replacing information (for example, a text) so that its inverse is only feasible by knowledge of the key.

Information is frequently both encoded and enciphered: For example, a text is encoded, for example, by ASCII, and then encrypted, for example, by the Advanced Encryption Standard (AES).

Self-Check Questions

1. Please distinguish between cryptology, cryptography and cryptanalysis:

   • cryptology is the science of secure storage and communication of information.
   • cryptography is the art of secure storage and communication of information.
   • cryptanalysis is the art of decryption of encrypted information without knowledge of the key.

2. Please distinguish between encoding and encryption:

   While both encoding and encryption transform information into a computer readable format, only for encryption this transformation is not invertible without knowledge of the key.

1.2 IT security: threats and common attacks

A snappy acronym to resume the fundamental aims of information security is the CIA, which stands for: Confidentiality, Integrity and Availability. That is, confidentiality of information, integrity of information and availability of information.

CIA: stands for Confidentiality, Integrity and Availability.

More comprehensive are “the five pillars of Information Assurance”, that add authentication and non-repudiation: Confidentiality, integrity, availability, authentication and non-repudiation of information.

The five pillars of Information Assurance: are formed by Confidentiality, integrity, availability, authentication and non-repudiation of information.

Cryptography helps to achieve all of these to good effect: Good encryption, as achieved by thoroughly tested standard algorithms such as AES or RSA, is practically impossible to break computationally; instead, keys are stolen or plaintext is stolen before encryption or after decryption. While cryptography provides high technical security, human failure, for example, arising out of convenience or undue trust, is the weakest point in information security.

Confidentiality

Information that is confidential is meant to be kept secret, that is, should not be disclosed to other people, for example information that is known only by someone’s doctor or bank. In law, confidential is the relation existing between, for example, a client and her counsel or agent, regarding the trust placed in one by the other. In the information security standard ISO/IEC 27002 the International Organization for Standardization (ISO) defines confidentiality as “ensuring that information is accessible only to those authorized to have access”. In IT, it means ensuring that sensitive information stored on computers is not disclosed to unauthorized persons, programs or devices. For example, avoiding that anyone with access to a network can use common tools to eavesdrop on traffic and intercept valuable private information.

Integrity

Integrity is the state of being whole, the condition of being unified or sound in construction.

(Data) Integrity is about the reliable, complete and error-free, transmission and reception or storage of data: that the original data had not been altered or corrupted; in particular, is valid in accordance with expectations.

When the data has been altered, either through electronic damage by software or physical damage to the disk, the data is unreadable. For example when we download a file we verify its integrity by calculating its hash and comparing with the hash published by source. Without such a check, someone could, for example, package a Trojan horse into an installer on Microsoft Windows (that, as a last resort, hopefully would already be known and detected by an antivirus program such as Microsoft Defender).

Availability

Though unrelated to cryptology, in IT security availability of information against threats such as DoS (Denial of Service) attacks (to deny users of the Website access to a Website by flooding it with requests) or accidents, such as power outages, or natural disasters such as earthquakes. To achieve it, it is best to have a safety margin and include redundancy, in particular, to have

• parallel redundant failover hardware, such as a server or network, which is always kept running so that at any moment, upon detected failure of the primary system, processing can be automatically shifted over.
• prevent intrusion by monitoring network traffic patterns for anomalies and block network traffic when necessary.

Authentication

Authentic (from Greek authentes, real or genuine) means according to Webster (1913)

• not false or copied, genuine, real.
• having the origin supported by unquestionable evidence, verified, or
• entitled to acceptance or belief because of agreement with known facts or experience; reliable; trustworthy.

Authentication thus is the verification of something (or someone) as “authentic”. This might involve confirming the identity of a person or the origins of an object.

In IT, authentication means

• verification of the identity of a user and possibly her permission to access an object; convincing a computer that a person is who she claims to be after identification.
• verification that data is unchanged between two points of time; be it intentionally (altered) or accidentally (corrupted).

To verify her identity, a person proves that she is who she claims to be by showing some evidence. Devices that are used for authentication include passwords, personal identification numbers, smart cards, and biometric identification systems. For example, to login, she enters her user identification and password.

A common attack is that of the “man in the middle”, where the attacker assumes to either correspondent the identity of the other correspondent. To solve this, certificates, digital signatures by third parties, are used. Either,

• as in the web of trust in OpenPGP, by signatures among persons known to each other over ends, or
• as on secure sites in a web browser, by a signature of an, unconditionally trusted, central certification authority, usually companies such as VeriSign.

Non-repudiation

Repudiation is a legal term for disavowal of a legal bind (such as an agreement or obligation); someone who repudiates:

• refuses to accept or be associated with a legal bind,
• refuses to recognize the validity of the legal bind (for example, her signature),
• refuses to fulfill the legal bind.

For example, a forged or forced signature is repudiable.

Non-repudiation is the assurance:

• that a contract cannot later be denied by either of the parties that agreed on it;
• of the identity of the claimed sender or recipient of a given message.

In computing, this means that authentication can hardly be refuted afterwards. This is achieved by a digital signature.

For example,

• an electronic receipt proves that a particular user has sent a message such as an instruction to buy an item in an online auction.
• if the e-mail says it was sent by Bob, then later on Bob can’t claim that it was not originally sent by him.

In today’s global economy, where face-to-face agreements are often impossible, non-repudiation is essential for safe commerce.

Self-Check Questions

1. In practice, is sensitive information obtained by

   • human, or
   • cryptographic

   failure?

2. What does CIA in IT security stand for: Confidentiality, Integrity and Availability.

3. Please list the five pillars of information security: Confidentiality, integrity, availability, authentication and non-repudiation of information.

1.3 Aims of Cryptography in Child’s terms

Alice wants to send Bob a locked box (with a message or a key) without sending the key, so that the box was never left unlocked throughout the process.

A castle

An open lock is the public key and locking its application. The key is the secret key:

1. Alice sends Bob a lock of hers.
2. Bob puts the keys in the box, locks it with Alice’s lock and sends the box to Alice.
3. Alice opens the box.
4. Now Alice and Bob have a key to a common lock.

Two locks

The key or message in the box is the shared secret. The other two keys the mutual secrets. From two two-sided one can be constructed by the interchangeability of the order of the encryptions, commutativity.

0. Alice puts a message or key in a box.
1. Alice padlocks the box (and keeps the key) and sends the locked box to Bob.
2. Bob obviously can’t open the box, but he secures the box with a second padlock (and also keeps the key) and sends the double-locked box back to Alice.
3. Alice opens her lock with her key and sends the box (still padlocked) to Bob.
4. Bob can now open the box with his own key.

1.4 Historical Overview

The history of cryptography dates back at least 4000 years. We distinguish three periods:

1. Till the 20th century, its methods were classic, mainly pen and paper.

2. In the early 20th century, they were replaced by more efficient and sophisticated methods by complex electromechanical machines, mainly rotor machines for polyalphabetic substitution, such as the Enigma rotor machine used by the axis powers during World War II.

3. Since then, digitalization, the replacement of analog devices by digital computers, allowed methods of ever greater complexity. Namely, the most tested algorithms are

   • DES (or its threefold iteration 3DES) and its successor AES for symmetric cryptography,
   • RSA and its successor ECC (Elliptic Curve Cryptography) for asymmetric cryptography.

Classic Cryptography

From antiquity till World War I, cryptography was carried out by hand and thus limited in complexity and extent to at most a few pages. The principles of cryptanalysis were known, but the security that could be practically achieved was limited without automatization. Therefore, given sufficient ciphertext and effort, cryptanalysis was practically always successful.

The principles of cryptanalysis were first understood by the Arabs. They used both substitution and transposition ciphers, and knew both letter frequency distributions and probable plaintext in cryptanalysis. Around 1412, al-Kalka-shandī gave in his encyclopedia Subīal-aīshī a manual on how to cryptanalyze ciphertext using letter frequency counts with lengthy examples.

Scytale

A scytale (from Latin scytala) consists of a rod with a band of parchment wound around it on which is written a secret message. It was rolled spirally upon a rod, and then written upon. The secret writing on the strip wound around the rod is only readable if the parchment was to be wound on a rod of the same thickness; It is a transposition cipher, that is, shuffles, or transposes, the letters of the plaintext.

Caesar’s Cipher

Caesar’s Cipher is one of the simplest and most widely-known chiphers, named after Julius Caesar (100 – 44 BC), who used it to communicate with his generals. It is a substitution cipher that replaces, substitutes, each alphabetic letter of the plaintext by a fixed alphabetic letter. In Caesar’s Cipher, each letter in the plaintext is shifted through the alphabet the same number of positions; that is, each letter in the plaintext is replaced by a letter some fixed number of positions further down the alphabet.

Bacon’s Cipher

Francis Bacon’s cipher from 1605 is an arrangement of the letters a and b in five-letter combinations (of which there are $2^5 = 32$ ) that each represent a letter of the alphabet (of which there are 26 ). Nowadays we would call a code, but at the time it illustrated the important principle that only two different signs can be used to transmit any information.

Alberti’s Cipher Disk

In 1470, Leon Battista Alberti described in Trattati in Cifra (“Treatise on Ciphers”) the first cipher disk to shift the letters of the alphabet cyclically. He recommended changing the offset after every three or four words, thus conceiving a polyalphabetic cipher in which the same alphabetic letters are replaced by different ones. The same device was used more than four centuries later by the U.S. Army in World War I.

ADFGVX cipher

The best known cipher of World War I is the German ADFGVX cipher:

1. The 26 Latin letters and 10 arabic digits were replaced in a 6 x 6 matrix by pairs of the letters A, D, F, G, V, and X.
2. The resulting text was then written into a rectangle, and
3. then the columns read in the order indicated by the key.

Invented by Fritz Nebel, it was introduced in March 1918 for use by mobile units. The French Bureau du Chiffre, in particular, Georges Painvin, broke the cipher a month later — still too late as the German attacks had already ceded.

Electromechanical Cryptography by Rotor Machines

The mechanization of cryptography began after World War I by the development of so-called rotor cipher machines:

These rotors are stacked. The rotation of one rotor causes the next one to rotate $1 / 26$ of a full revolution. (Just like in an odometer where after a wheel has completed a full revolution, the next one advances $1 / 10$ of a full revolution.) In operation, there is an electrical path through all rotors. Closing the key contact of the plaintext letter on a typewriter-like keyboard

1. emits a current to one of the contacts on the initial rotor,
2. The current then passes through the cable salad of the stacked rotors (which depends on their rotational positions!), and
3. ends up at an indicator where it lights up the lamp of the ciphertext letter.

In the US, Edward H. Hebern made in 1917 the first patent claim to accomplish polyalphabetic substitution by cascading a collection of monoalphabetic substitution rotors, wiring the output of the first rotor to the input of the following rotor, and so on. In Europe, Already in 1915 such a rotor machine had been built by two Dutch naval officers, Lieut. R.P.C. Spengler and Lieut. Theo van Hengel, and independently by a Dutch mechanical engineer and wireless operator, Lieut. W.K. Maurits. Around the same time as Hebern, Arthur Scherbius from Germany (who filed his patent in February 1918) and Hugo A. Koch from the Netherlands (a year later), also built rotor machines, which were commercialized and evolved into the German Enigma used in World War II.

In Japan, the Japanese Foreign Office put into service its first rotor machine in 1930, which was cryptanalyzed in 1936, using solely the ciphertexts, by the U.S. Army’s Signal Intelligence Service (SIS). (In 1939 a new cipher machine was introduced, in which rotors were replaced by telephone stepping switches, but readily broken by the SIS again solely relying on ciphertext; even more so, their keys could be foreseen.)

The Invention of Engima

Arthur Scherbius was born in Frankfurt am Main on 20 October 1878 as son of a businessman. After studying at the Technical College in Munich, he completed his doctoral dissertation at the Technical College in Hanover in 1903, then worked for several major electrical companies in Germany and Switzerland. In 1918, he submitted a patent for a cipher machine based on rotating wired wheels and founded his own firm, Scherbius and Ritter. Since both the imperial navy and the Foreign Office declined interest, he entered the commercial market in 1923 and advertised the Enigma machine, as it was now called, in trade publications or at the congress of the International Postal Union. This sparked again the interest of the German navy in the need for a secure cipher, and a slightly changed version was in production by 1925. Still, the corporation continued to struggle for profitability because commercial as public demand was confined to a few hundred machines. While Scherbius fell victim to a fatal accident involving his horse-drawn carriage, and died in 1929, his corporation survived and by 1935 amply supplied the German forces under Hitler’s rearmament program.

The Breakage of Enigma

Polish and British cryptanalysis solved the German Enigma cipher (as well as two telegraph ciphers, Lorenz-Schlüsselmaschine and Siemens & Halske T52). To this end

• the patents of the Enigma were filed in the United States,
• similar machines were commercially available, and
• the rotor wirings were known from a German code clerk:

Hans-Thilo Schmidt, decorated with an Iron Cross in World War I, worked as a clerk at a cipher office (previously lead by his brother). In June 1931, he contacted the intelligence officer at the French embassy and agreed with Rodolphe Lemoine to reveal information about the Enigma machine, copies of the instruction manual, operating procedures and lists of the key settings. However, French cryptanalysts made little headway, and the material was passed on to Great Britain and Poland, whose specialists had more success:

The commercial version of the Enigma had a rotor at the entry and his wiring was unknown. However, the Polish cryptanalyst Marian Rejweski, guided by the German inclination for order, found out that it did not exist in the military version; what is more, he inferred the internal wirings of the cylinders by distance, that is, by mere cryptanalysis of the enciphered messages.

The Britisch cryptanalysts in Bletchley Park (among them the mathematician Alan Turing, a founding father of theoretical computer science) could reduce by likely candidates the number of possible keys from 150 trillions to around a million, a number that allowed a work force of around 4200 (among them $80\%$ women) an exhaustive key-search with the help of the Turing Bomb, an ingenious electromechanical code-breaking machine that imitated a simultaneous run of many Enigma machines and efficiently checked the likelihood of their results.

Schmidt continued to inform the Allies throughout war till the arrest (and confession) of Lemoine in Paris which lead to that of Schmidt by the Gestapo in Berlin on 1 April 1943 and his death in prison.

Digital Cryptography

After World War II, cryptographic machines stayed conceptually the same till the early 80s: faster rotor machines in which rotors had been replaced by electronic substitutions, but still merely concatenating shifted monoalphabetic substitutions to obtain a polyalphabetic substitution.

However, such letter per letter substitutions are still linear over the letters, so the ciphertext obtained from a plaintext will reveal how to decrypt all letters of a plaintext of (at most) the same length. That is, a letter per letter substitution diffuses little, that is, hardly spreads out changes; optimal diffusion is attained whenever the change of a single letter of the plaintext causes the change of half of the letters of the ciphertext. If the attacker has access to the ciphertexts of many plaintexts, possibly of his own choosing, then he can obtain the key by the ciphertexts of two plaintexts that differ in a single position.

DES

Instead, computers made it possible to combine such substitutions (such as Caesar’s Cipher) with transpositions (such as the Scytale), achieving far better diffusion, which lead to the creation of one of the most widely used ciphers in history, the Data Encryption Standard (DES), in 1976.

AES

In January 1997 the U.S. National Institute of Standards and Technology (NIST; former National Bureau of Standards, NBS) announced a public contest for a replacement of the aging DES, the Advanced Encryption Standard (AES). Among 15 viable candidates from 12 countries, in October 2000 Rijndael, created by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, was chosen and became the AES.

Since improvements in computing power allowed to find the fixed 56-bit DES key by exhaustive key-search (brute force), the NIST specifications for the AES demanded an increasing key length, if need be. Rijndael not only was shown immune to the most sophisticated known attacks such as differential cryptanalysis (in Daemen and Rijmen (1999) and Daemen and Rijmen (2002)) and of an elegant and simple design, but is also both small enough to be implemented on smart cards (at less than 10 000 bytes of code) and flexible enough to allow longer key lengths.

Public-key cryptography

Since the ’80s, the advent of public-key cryptography in the information age made digital signatures and authentication possible; giving way to electronic information slowly replacing graspable documents.

Asymmetric encryption was first suggested publicly at Diffie and Hellman (1976).

Conceptually it relies on a trap function (more specifically, in op.cit. the modular exponential), an invertible function that is easily computable but whose inverse is hardly computable in the absence of additional information, the secret key.

To encrypt, the function is applied; to decrypt its inverse with the secret key. For example, in the approach according to Diffie and Hellman, this function is the exponential, however, over a different domain than the real numbers we are used to.

In fact, Diffie and Hellman (1976) introduced only a scheme for exchanging a secret key through an insecure channel. It was first put it into practice

• in Rivest, Shamir, and Adleman (1978), where the RSA cryptographic algorithm was introduced, or
• by the ElGamal algorithm, more recent, but the closest example of the original scheme.

Not only do these algorithms enable ciphering by a public key (thus removing the problem of its secret communication), but, by using the private key instead to encipher, made possible digital signatures, which might have been its commercial breakthrough. These algorithms still stand strong, but others, such as elliptic curve cryptography, are nowadays deemed more efficient at the same security.

Self-Check Questions

1. Please list the major epochs of cryptography: Classic (Pen and Paper), electromechanics (rotor machine) and digital age.
2. How many possible keys has Caesar’s Cipher? 26 including the trivial one.
3. Which one of Caesar’s Cipher and the Scytale is a substitution cipher? Caesar’s Cipher is a substitution cipher and the Scytale is a transposition cipher.
4. What deficiency was shared by all rotor machines? As substitution is letter-wise, the frequency of the alphabetical letters was preserved.

1.5 Security Criteria

Kerckhoff’s Principle

Kerckhoff principle postulates the independence of a cryptographic algorithm’s security from its secrecy:

Kerckhoffs’ principle: The ciphertext should be secure even if everything about it, except the key, is public knowledge.

While knowledge of the key compromises a single encryption, knowledge of the algorithm will compromise all encryptions ever carried out. A public algorithm guarantees the difficulty of decryption depending only on the knowledge of the key, but not on the algorithm. The more it is used, the more likely it becomes that the algorithm will be eventually known. For the algorithm to be useful, it thus needs to be safe even though it is public.

Claude Shannon (1916 – 2001) paraphrased it as: “the enemy knows the system”, Shannon’s maxim. The opposite would be to rely on a potentially weak, but unknown algorithm, “security through obscurity”; ample historic evidence shows the futility of such a proposition (for example, the above ADFGVX cipher of Section 1.4 comes to mind).

Shannon’s Criteria

Shannon’s principles of

• Confusion respectively Diffusion

give criteria for an uninferable relation between the ciphertext and

• the key respectively the plaintext.

Ideally, when one letter in the key respectively in the plaintext changes, then half of the ciphertext changes, that is, each letter in the ciphertext changes with a probability of 50%. While the output of the cipher, the ciphertext, depends deterministically on the input, the plaintext, and the key, the algorithm aims to obfuscate this relationship to make it as complicated, intertwined, scrambled as possible: each letter of the output, of the ciphertext, depends on each letter of the input, of the plaintext, and of the key.

Self-Check Questions

1. Name two algorithms that satisfy Kerckhoff’s principle. DES and AES.

Summary

Cryptography protects information by shuffling data (that is, transforming it from intelligible into indecipherable data) so that only additional secret information, the key, can feasibly reverse it. Up to the end of the ’70s, the key used to encrypt and decrypt was always the same: symmetric or (single-key) cryptography. In the 70s asymmetric cryptography was invented, in which the key to encipher (the public key) and the key to decipher (the secret or private key) are different. In fact, only the key to decipher is private, kept secret, while the key to encrypt is public, known to everyone. When the keys exchange their roles, the private key enciphers, and the public one deciphers, then the encryption is a digital signature. while the encrypted message will no longer be secret, every owner of the public key can check whether the original message was encrypted by the private key. Because historically only written messages were encrypted, the source data, though a stream of 1s and 0s (the viewpoint adopted in symmetric cryptography) or a number (that adopted in asymmetric cryptography), is called plaintext and the encrypted data the ciphertext.

The security

• of public-key algorithm relies on the inefficient computation of mathematical functions on the integers. For example, the most famous public-key algorithm, RSA , requires the factorization of a number with $> 500$ decimal digits into its prime factors, which is computationally infeasible (without knowledge of the key);
• of symmetric cryptographic algorithms depends on the diffusion of small differences on the input and key to large differences in the output; ideally, if one bit of the input or key changes, then about half of the bits of the output changes.

Good encryption, as achieved by standard algorithms such as AES or RSA, is practically impossible to break computationally; instead, keys are stolen or plaintext is stolen before encryption or after decryption.

A hash function is an algorithm that generates an output of fixed (byte) size (usually around 16 to 64 bytes) from an input of variable (byte) size, for example, a text or image file, a compressed archive. The output string of fixed length that a cryptographic hash function produces from a string of any length (an important message, say) is a kind of inimitable “signature”. A person who knows the “hash value” cannot know the original message, but only the person who knows the original message can prove that the “hash value” is produced from that message.

Questions

• How many keys has Caesar’s Cipher (excluding the trivial one)? 12, 13, $25$ , 26
• For which non-trivial key is Caesar’s Cipher idempotent, that is, encrypting the ciphertext again yields the plaintext? 1, 2, 26, $13$
• Which cryptographic algorithm comes closest to satisfying Kerckhoff’s principle? Scytale, Enigma, ADFGVX, One-time pad
• Which one is an encryption algorithm? MD5, SHA-1, AES, CRC
• Which one is a hash function that is not cryptographic? MD5, SHA-1, CRC, AES

Required Reading

The article Simmons et al. (2016) gives a good summary of cryptology, in particular, historically; read its introduction and the section on history. As does the first chapter of Menezes, Oorschot, and Vanstone (1997), which focuses more on the techniques. The most recent work is Aumasson (2017), and a concise but demanding overflight of modern cryptography. Get started by reading its first chapter as well.

Further Reading

Some classics are Frederick) Friedman (1976) which is a manual for cryptanalysis for the U.S. military, originally not intended for publication.

The books Kahn (1996) and Singh (2000) trace out the history of cryptanalysis in an entertaining way.

The book Schneier (2007) is a classic for anyone interested in understanding and implementing modern cryptographic algorithms.

2 Symmetric ciphers

Study Goals

On completion of this chapter, you will have learned …

• … that the two fundamental symmetric cryptographic algorithms are

  • substitution that replaces the alphabet of the plaintext by an alphabet of the ciphertext (such as Caesar’s cipher), and
  • transposition (or permutation) that transposes the letters of the plaintext (such as the Scytale).

• … that the only cryptographically perfectly secure cipher is the one-time pad in which the key is as long as the plaintext

• … that modern algorithms like DES and AES are Substitution and Permutation Networks that break the plaintext up into short blocks of the same size as the key and, on each block, iterate

  1. addition of the key,
  2. substitution, and
  3. permutation.

Introduction

Up to the end of the ’70s, before the publication of Diffie and Hellman (1976) and Rivest, Shamir, and Adleman (1978), all (known) cryptographic algorithms were symmetric (or single-key), that is, used the same key to encipher and decipher. Thus every historic algorithm, as sophisticated as it may be, be it Caesar’s Cipher, the Scytale or the Enigma, was symmetric.

While asymmetric algorithms depend on a computationally difficult problem, such as the factorization of a composed number into its prime factors, and regard the input as a natural number, symmetric ones operate on the input as a string (of bits or letters) by (iterated) substitutions and transpositions.

The only perfectly secure cipher is the one-time pad in which the key is as long as the plaintext and the ciphertext is obtained by adding, letter by letter, each letter of the key to the corresponding (that is, at the same position) letter of the plaintext.

However, such a large key is impractical for more complex messages, such as text, image or video files: In modern times, it means that to encrypt a hard drive, another hard drive that carries the key is needed.

To compensate the shorter key length, modern algorithms, ideally, create so much intertwining that they achieve almost perfect diffusion, that is, the change of a single bit of the input or key causes the change of around half of the output bits. Modern algorithms, such as DES or AES, are substitution and permutation network block ciphers, meaning that they encrypt one chunk of data at a time by iterated transpositions and substitutions.

2.1 Substitution and Transposition

The two basic operations to encrypt are transposition and substitution:

• A transposition changes the order (that is, transposes or permutes) of the symbols in the text but not the symbols themselves.
• A substitution replaces (that is, substitutes) every symbol in the text by another (group of) symbol, but not the order of the symbols.

The historical prototypical algorithms for these two operations are:

• the substitution cipher by Caesar, that advances every letter in the plaintext by the three positions, that is, encrypts A as D, B as E, and so forth, and
• the permutation of the plaintext by the scytale, or baton of Licurgo (Spartan lawgiver around the ninth century BC), where the parchment is wrapped around the baton and the text written on it horizontally.

We will see that even with many possible keys an algorithm, such as that given by any permutation of the alphabet which has almost $2^{80}$ keys, can be easily broken if it preserves regularities, like the frequency of the letters.

As a criterion for security, there is that of diffusion by Shannon: Ideally, if a letter in the plaintext changes, then half of the letters in the ciphertext changes. Section 2.2 will show how modern algorithms, called substitution and permutation networks, join and iterate these two complementary prototypical algorithms to reach this goal.

ideal diffusion (according to Shannon): if a bit in the plaintext or key changes, then half of the bits in the ciphertext changes.

Substitution ciphers

In a substitution cipher the key determines substitutions of the plaintext alphabet (considered as a set of units of symbols such as single letters or pairs of letters) by the ciphertext alphabet. For example, if the units of the plaintext and ciphertext are both the letters of the Latin alphabet, then a substitution permutes the letters of the Latin alphabet. If the substitution cipher is monoalphabetic (such as Caesar’s Cipher), then the same substitution is applied to every letter of the plaintext independent of its position. If the substitution cipher is polyalphabetic (such as the Enigma), then the substitution varies with the position of the letter in the plaintext. To encrypt, each alphabetical unit of the plaintext is replaced by the substituted alphabetical unit, and inversely to decrypt.

Substitution Cipher: a cipher that replaces each alphabetical unit of the plaintext by a corresponding alphabetical unit.

Every monoalphabetic substitution cipher, that is, every plaintext symbol is always encrypted into the same ciphertext symbol, is insecure: the frequency distributions of symbols in the plaintext and in the ciphertext are identical, only the symbols having been relabeled. Therefore, for example in English, around 25 letters of ciphertext suffice for cryptanalysis.

The main approach to reduce the preservation of the single-letter frequencies in the ciphertext is to use several cipher alphabets, that is, polyalphabetic substitution.

Shift by a fixed distance

The simplest substitution cipher is a cyclical shift of the plaintext alphabet; Caesar’s cipher.

Caesar’s Cipher A substitution cipher that shifts the alphabetical position of every plaintext letter by the same distance.

This method was used by Roman emperors Caesar (100 – 44 B.C.) and Augustus (63 – 14 B.C.): fix a distance $d$ between letters in alphabetical order, that is, a number between 0 and 25, and shift (forward) each letter of the (latin) alphabet by this distance $d$ . We imagine that the alphabet is circular, that is, that the letters are arranged in a ring, so that the shift of a letter at the end of the alphabet results in a letter at the beginning of the alphabet.

For example, if $d = 3$ , then $$A \mapsto D, B \mapsto E, ..., W \mapsto Z, X \mapsto A, ..., Z \mapsto C.$$

There are 26 keys (including the trivial key $d = 0$ ).

To decipher, each letter is shifted by the negative distance $-d$ , that is, $d$ positions backwards. If the letters of the alphabet form a wheel, then the letters are transferred

• clockwise during the encipherment, and
• counterclockwise during the decipherment.

By the cyclicity of the letter arrangement, we observe that a transfer of $d$ positions in counterclockwise direction equals one of $26-d$ positions in clockwise direction.

Substitution by Permutation of the letters of the alphabet

Instead of replacing each letter by one shifted by the same distance $d$ , let us replace each letter with some letter, for example:

To revert the encipherment, never two letters be sent to the same letter! That is, we shuffle the letters among themselves. This way we obtain $26 \cdot 25 \cdot s1 = 26! > 10^6$ keys (which is around the number of passwords with 80 bits).

Transposition (or Permutation) ciphers

A transposition (or permutation) cipher encrypts the plaintext by permuting its units (and decrypts by the inverse permutation). Each alphabetical unit stays the same; the encryption depends only on the positions of the units.

Transposition Cipher: Transpose the alphabetical units of the plaintext.

The Scytale or Licurgo’s Baton (= a Spartan legislator around 800 B.C.) is a cipher used by the Spartans, as follows:

1. wrap a stick into a narrow strip,
2. write on this strip horizontally, that is, along the larger edge, and
3. unroll the strip.

The letters thus transposed on the strip could only be deciphered by a stick with the same circumference (and being long enough) in the same way as the text was encrypted:

1. wrap the stick into the strip, and
2. read this strip horizontally, that is, along the larger edge.

Here, the key is given by the stick’s circumference, that is, the number of letters that fit around the stick.

For example, if the stick has a circumference of 2 letters (and a length of 3 letters), the two rows

become the three rows

which, once concatenated (to reveal neither the circumference nor the length), become

Security of Historical Examples

Let us apply the established security criteria to the substitution ciphers:

Caesar’s Cipher

This simple substitution cipher violates all desirable qualities: For example, Kerckhoff’s principle that the algorithm be public: Once the method is known, considering the small amount of 25 keys, the ciphertext gives way in short time to a brute-force attack:

brute-force attack: an exhaustive key-search that checks each possible key.

Substitution by any permutation of the letters of the Alphabet

A substitution by any permutation of the letters of the alphabet, such as,

has $$26 \cdot 25 \cdots 1 = 26! > 10^{26}$$ keys, so a brute-force attack is computationally infeasible.

But it violates the goals of diffusion and confusion. If the key (= permutation of the alphabet) exchanges the letter $\alpha$ for the letter $\beta$ , then there’s

• bad confusion because the substitution of $\beta$ in the key implies only the substitution of each letter $\beta$ in the ciphertext,
• bad diffusion because the substitution of a letter $\alpha$ in the plaintext implies only the substitution of the corresponding letter $\beta$ in the ciphertext.

In fact, the algorithm allows statistical attacks on the frequency of letters, bigrams (= pairs of letters) and trigrams (= triples of letters). See Section 12.1.

The Scytale

Also the scytale is weak in any sense given by the security principles. It violates

• the Kerckhoff principle that the algorithm be public.

In fact, the maximum value of the circumference of the stick in letters is $< n/2$ where $n$ = the number of letters in the ciphertext. So a brute-force attack is feasible.

It has

• bad diffusion because the substitution of a letter $\alpha$ in the plaintext only implies that of the same letter $\alpha$ in the ciphertext.

In fact, the algorithm is prone to statistical attacks on the frequency of bigrams (= pairs of letters), trigrams (= triples of letters), and higher tuples. For example, a promising try would be the choice of circumference as number $c$ that maximizes the frequency of the ‘th’ bigram between the letter strings at positions $1, 1 + c, 1 + 2c, ...$ , $2, 2 + c, 2 + 2c, ...$ . For example, if we look $$\text{TEHMHTUB}$$ we notice that T and H are one letter apart, which leads us to the guess that the circumference is three letters, $c = 3$ , yielding the decipherment $$\text{THE THUMB}.$$

Product ciphers

A product cipher composes ciphers, that is, if the product is two-fold, then the output of one cipher is the input of the other.

product cipher: a composition of ciphers where the output of one cipher serves as the input of the next.

The ciphertext of the product cipher is the ciphertext of the final cipher. Combining transpositions only with transpositions or substitutions only with substitutions, the obtained cipher is again a transposition or substitution, and hardly more secure. However, mixing them, a transposition with substitutions, indeed can make the cipher more secure.

A fractionation cipher is a product cipher that:

1. substitutes every symbol in the plaintext by a group of symbols (usually pairs),
2. transposes the obtained ciphertext.

The most famous fractionation cipher was the ADFGVX cipher used by the German forces during World War I:

1. The 26 letters of the Latin Alphabet and 10 digits were arranged in a $6 \times 6$ -table and replaced by the pair of letters among A , D , F , G , V , and X that indicate the row and column of the letter or digit.
2. The resulting text was written as usual from left to right into the rows of a table and then each column read in the order indicated by a keyword.

However, it was cryptanalyzed within a month by the French cryptanalyst Georges J. Painvin in 1918 when the German army entered in Paris. We will see in Section 2.2 how modern ciphers refine this idea of a product cipher to obtain good diffusion.

Self-Check Questions

1. For which distances $d$ is Caesar’s Cipher auto-inverse, that is, the output of the encipherment equals that of the decipherment? For $d = 0$ and $13$ .
2. Does Caesar’s Cipher satisfy Kerckhoff’s principle? No, the number of possible keys is too small.
3. Why is a substitution cipher insecure? Because two identical letters in the plaintext are replaced by two identical letters in the ciphertext.

2.2 Block Ciphers

Classic ciphers usually replaced single letters, sometimes pairs of letters. Systems that operated on trigrams or larger groups of letters were regarded as too tedious and never widely used.

Instead, it is safer to substitute a whole block (of letters instead of a single letter, say) according to the key. However, the alphabet of this replacement would be gigantic, so this ideal is practically unattainable, especially on hardware as limited as a smart card with an 8 bit processor. For a block of, for example, $4$ bytes, this substitution table would already have a $4$ gigabytes (= $2^{32} \cdot 4$ bytes). However, in modern single-key cryptography a block of information commonly has $16$ bytes, about 27 alphabetic characters (whereas two-key cryptography based on the RSA algorithm commonly uses blocks of $256$ bits, about $620$ alphabetic characters).

Instead, for example, AES only replaces each byte, each entry in a block, a replacement table of $2^8 = 256$ entries of $1$ byte (and afterwards transposes the entries.) We will see that these operations complement each other so well that they are practically as safe as a substitution of the whole block.

Block and Stream Ciphers

A block cipher partitions the plaintext into blocks of the same size and enciphers each block by a common key: While a block could consist of a single symbol, normally it is larger. For example, in the Data Encryption Standard the block size is 64 bits and in the Advanced Encryption Standard 128 bits.

stream cipher versus block cipher: a stream cipher operates on single characters (for example, single bytes) while a block cipher operates on groups of characters (for example, each 16 bytes large)

A stream cipher partitions the plaintext into units, normally of a single character, and then encrypts the $i$ -th unit of the plaintext with the $i$ -th unit of a key stream. Examples are the one-time pad, rotor machines (such as the Enigma) and DES used in Triple DES (in which the output from one encryption is the input of the next encryption).

In a stream cipher, the same section of the key stream that was used to encipher must be used to decipher. Thus, the sender’s and recipient’s key stream must be synchronized initially and constantly thereafter.

Feistel Ciphers

A Feistel Cipher (after Horst Feistel, the inventor of DES) or a substitution and permutation network (SPN ) groups the text (= byte sequence) into $n$ -byte blocks (for example, $n = 16$ for AES and enciphers each block by iteration (for example, 10 times in AES , and 5 times in our prototypical model) of the following three steps, in given order:

1. add (XOR) the key,
2. substitute of the alphabet (which operates in sub-blocks of the block, for example, on each byte), and
3. permute of all the sub-blocks in a block.

Substitution and Permutation Network: a cipher that iteratively substitutes and permutes each block after adding a key.

That is, after

1. the addition (by Or Exclusive) of the key as in the One-time pad,

are applied

2. the substitution of the alphabet, for example, in the AES algorithm (each byte, pair of hexadecimal letters, by another), and
3. the permutation of the text (from the current step, the state); for example, in AES , that groups the text into a $4\times 4$ square (whose entries are pairs of hexadecimal letters), the entries in each row (and the columns) are permuted.

These two simple operations,

• the substitution of the alphabet, and
• the permutation of text

complement each other well, that is, they generate high confusion and diffusion after a few iterations. In the first and last round, the steps before respectively after the addition of the key are omitted because they do not increase the cryptographic security: Since the algorithm is public (according to Kerckhoff’s principle), any attacker is capable of undoing all those steps that do not require knowledge of the key.

Though seemingly a Feistel Cipher differs from classical ciphers, it is after all a product cipher, made up of transpositions and substitutions.

Self-Check Questions

1. What distinguishes a stream cipher from a block cipher? a stream cipher operates on single characters while a block cipher operates on groups of characters
2. What is a Substitution and Permutation Network (or Feistel Cipher)? A block cipher that iteratively substitutes and permutes each block after adding a key.

2.3 Data Encryption Standard (DES)

The Data Encryption Standard (DES), was made a public standard in 1977 after it won public competition announced by the U.S. National Bureau of Standards (NBS; now the National Institute of Standards and Technology, NIST). IBM (International Business Machines Corporation) submitted the patented Lucifer algorithm invented by one of the company’s researchers, Horst Feistel, a few years earlier (after whom the substitution and permutation network was labelled Feistel Cipher). Its internal functions were slightly altered by the NSA (and National Security Agency) and the (effective) key size shortened from 112 bits to 56 bits, before it became officially the new Data Encryption Standard.

DES: Block cipher with an effective key length of 56 bits conceived by Horst Feistel from IBM that won a U.S. National competition to become a cryptographic standard in 1977.

DES is a product block cipher of 16 iterations, or rounds, of substitution and transposition (permutation). Its block size and key size is 64 bits. However, only 56 of the key bits can be chosen; the remaining eight are redundant parity check bits.

As the name of its inventor Horst Feistel suggests, it is a Feistel Cipher, or substitution and permutation network, similar to the prototype discussed above. It groups the text (= byte sequence) into 32-bit blocks with sub-blocks of 4 bits and enciphers each block in 16 iterations of the following three steps, called the Feistel function, for short F-function, in given order:

1. add (XOR) the key,

2. substitution of each 4-bit sub-blocks of the block by the S-box (in hexadecimal notation), and

   0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
   E	4	D	1	2	F	B	8	3	A	6	C	5	9	0	7

3. permutation of all the sub-blocks.

At each round $i$ , the output from the preceding round is split into the 32 left-most bits, $L(i)$ , and the 32 right-most bits, $R(i)$ . $R(i)$ will become $L(i+1)$ , whereas $R(i + 1)$ is the output of a complex function, $L(i) + f(R(i), K(i + 1))$ whose input is

• the $i+1$ -th block of the key bits, $K(i + 1)$ , and
• of the entire preceding intermediate cipher.

This process is repeated 16 times.

Essential for the security of DES is the non-linear S-box of the F -function $f$ specified by the Bureau of Standards; it is not only non-linear, that is, $f(A) + f(B) \neq f(A + B)$ but maximizes confusion and diffusion as identified by Claude Shannon for a secure cipher in Section 2.1.

Key Size and the Birth of 3DES

The security of the DES like any algorithm is no greater than the effort to search $2^{56}$ keys. When introduced in 1977, this was considered an infeasible computational task, but already in 1999 a special-purpose computer achieved this in three days. A workaround, called “Triple DES” or 3DES, was devised that effectively gave the DES a 112-bit key (using two normal DES keys).

3DES: Triple application of DES to double the key size of the DES algorithm.

(Which is after all the key size for the algorithm originally proposed by IBM for the Data Encryption Standard.) The encryption would be $E(1) \circ D(2) \circ E(1)$ while decryption would be $D(1) \circ E(2) \circ D(1)$ , that is, the encryption steps are:

1. Encrypt by the first key,
2. Decrypt by the second key, and
3. Encrypt by the first key;

while the decryption steps are:

1. Decrypt by the first key,
2. Encrypt by the second key, and
3. Decrypt by the first key.

If the two keys coincide, then this cipher becomes an ordinary single-key DES; thus, triple DES is backward compatible with equipment implemented for (single) DES.

DES is the first cryptographic algorithm to fulfill Kerckhoff’s principle of being public: every detail of its implementation is published. (Before, for example, the implementation records of the Japanese and German cipher machines in World War II were released only half a century after their cryptanalysis.)

Shortly after its introduction as a cryptographic standard, the use of the DES algorithm was made mandatory for all (electronic) financial transactions of the U.S. government and banks of the Federal Reserve. Standards organizations worldwide adopted the DES, turning it into an international standard for business data security. It only waned slowly after its successor AES was adopted around 2000 (after its shortcomings became more and more apparent and could only be worked around, by provisional means such as 3DES).

Self-Check Questions

1. What key size does DES use?

   • 256 bits
   • 128 bits
   • 112 bits
   • 56 bits

2. Name a cryptographic weakness of DES: Short key length.

3. What does 3DES stand for? Tripe DES, that is, tripe application of DES.

4. What key size does 3DES use?

   • 256 bits
   • 128 bits
   • 112 bits
   • 56 bits

2.4 Advanced encryption standard (AES)

In January 1997 the U.S. National Institute of Standards and Technology (NIST; former National Bureau of Standards, NBS) announced a public contest (National Institute for Standards and Technology (2000)) for an Advanced Encryption Standard (AES) to replace the former symmetric encryption standard, the Data Encryption Standard (DES). Since improvements in computing power allowed to find the fixed 56-bit DES key by exhaustive key-search (brute force) in a matter of days, the NIST specifications for the AES demanded an ever increasable key length, if ever need be. The winner of this competition, the algorithm that became the AES, was Rijndael (named after its creators Vincent Rijmen and Joan Daemen):

• Rijndael: 86 positive votes, 10 negative votes.
• Serpent: 59 votes in favour, 7 against.
• Twofish: 31 positive, 21 negative votes
• RC6: 23 positive, 37 negative votes
• MARS: 13 votes in favour, 84 against.

AES: Substitution and Permutation network with a (variable) key length of usually 128 bits conceived by Vincent Rijmen and Joan Daemen that won a U.S. National competition to become a cryptographic standard in 2000 and succeed DES.

Evaluation of Security

The creators of AES could demonstrate in Daemen and Rijmen (1999) that these two operations complement each other so well that, after several iterations, they almost compensate for the absence of a replacement of the entire block by another. For a more detailed source, see Daemen and Rijmen (2002).

As was the case with DES, the AES, decades after its introduction, still stands strong against any attacks of cryptanalysis, but foreseeably will not yield to developments in computing, as happened to the DES, also thanks to its adjustable key size.

Applications

Among the competitors of public contest by the NIST, none of them stood out for its greater security, but Rijndael for its simplicity, or clarity, and in particular computational economy in implementation. Since this algorithm is to be run everywhere, for example on 8-bit smart card processors (smartcards), the decision was made in favour of Rijndael. Rijndael not only was secure, but thanks to its elegant and simple design, also both small enough to be implemented on smart cards (at less than 10,000 bytes of code).

To this day, this algorithm remains unbroken and is considered the safest; there is no need for another standard symmetric cryptographic algorithm. And indeed, it runs everywhere: For example, to encrypt a wireless network, a single key is used, so the encryption algorithm is symmetrical. The safest option, and therefore most recommended, is AES.

Encipherment in Blocks

The AES algorithm is a block cipher, that is, it groups the plaintext (and the keys) into byte blocks of $4 \times B$-byte rectangles where $$B := \text{number of columns in the rectangle} = 4, 6 or 8.$$ Commonly, and for us from now on, $B = 4$ , that is, the rectangle is a $4 \times 4$-square (containing $16$ bytes or, equivalently, $128$ bits). Each entry of the block is a byte (= sequence of eight binary digits = eight-bit binary number).

On a hexadecimal basis (= whose numbers are 0 – 9, A = 10, B = 11, C = 12, D = 13, E = 14 and F = 15), such a square is for example

Rounds

The AES algorithm enciphers each byte block $B$ iteratively, in a number of rounds $R$ which depends on the number of columns of $B$: there are $R = 10$ rounds for $B = 4$ columns, $R = 12$ rounds for $B = 6$ columns and $R = 14$ rounds for $B = 8$ columns. For us, as we assume $B = 4$ columns, $R = 10$.

The Substitution and Permutation cipher AES operates repeatedly as follows on each block:

1. Substitute each byte of the (square) block according to a substitution table (S-box) with $2^8 = 256$ entries of $1$ byte each.
2. Permute the entries of each row, and
3. exchange the entries (= bytes = eight-digit binary numbers) of each column by sums of multiples of them.
4. Add the round key, which is a byte block of the same size, to the block (by XOR in each entry).

The first step is a substitution. The second and third step count as a horizontal permutation (of the entries in each row) respectively vertical permutation (of the entries in each column).

CrypTool 1 offers in Menu Individual Procedures -> Visualization of Algorithms -> AES

• an Animation entry to see the animation in Figure 2.1 of the rounds, and
• an Inspector entry in Figure 2.2 to experiment with the values of plaintext and key.

In these rounds, keys are generated, the plaintext replaced and transposed by the following operations:

1. Round $r = 0$ :

   • AddRoundKey to add (by XOR) the key to the plaintext (square) block

2. Rounds $r = 1, ..., R-1$ : to encrypt, apply the following functions:

   1. SubBytes to replace each entry (= byte = sequence of eight bits) with a better distributed sequence of bits,
   2. ShiftRows to permute the entries of each row of the block,
   3. MixColumn to exchange the entries (= bytes = eight-digit binary number) of each column of the block by sums of multiples of them,
   4. AddRoundKey to generate a key from the previous round’s key and add it (by XOR) to the block.

3. Round $r = R$ : to encrypt, apply the following functions:

   1. SubBytes
   2. ShiftRows
   3. AddRoundKey

   That is, compared to previous rounds, the MixColumn function is omitted: It turns out that MixColumn and AddRoundKey, after a slight change of AddRoundKey, can change the order without changing the end result of both operations. In this equivalent order, the operation MixColumn does not increase cryptographic security, as the last operation invertible without knowledge of the key. So it can be omitted.

The function MixColumn (and at its origin SubBytes) uses the multiplication of the so-called Rijndael field $\mathbb{F}_{2^8}$ to compute the multiple of (the eight-digit binary number given by) a byte; it will be presented at the end of this chapter. Briefly, the field defines, on all eight-digit binary numbers, an addition given by XOR and a multiplication given by a polynomial division with remainder: The eight-digit binary numbers $a = a_7 ... a_0$ and $b = b_7 ... b_0$ to be multiplied are identified with polynomials $$a(x) = a_7 x^7 + \cdots + a_0 \quad \text{ and } \quad b(x) = b_7 + \cdots + b_0$$ which are then multiplied as usual to give a polynomial $C(x) = a(x) b(x)$. To yield a polynomial with degree $\leq 7$, the remainder $c(x) = c_7 x^7 + \cdots + c_0$ of $C(x)$ by polynomial division with $$m(x) = x^8 + x^4 + x^3 + x + 1.$$ is computed. The product $c = a \cdot b$ is then given by the coefficients $c_7 ... c_0$.

Let us describe all round functions in more detail:

SubBytes

SubBytes substitutes each byte of the block by another byte given by the S-box substitution table.

To calculate the value of the entry by which the S-box substitutes each byte:

1. Calculate its multiplicative inverse $B$ in $\mathbb{F}_{2^8}$ ,

2. Calculate $$a_i = b_i + b_{i + 4} + b_{i + 5} + b_{i + 6} + b_{i + 7} + c_i$$ where $i$ = 0 , 1 , …, 7 is the index of each bit of a byte, and

   • $B$ = $b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0$ is the entry byte,
   • $A$ = $a_7 a_6 a_5 a_4 a_3 a_2 a_1 a_0$ is the output byte of the operation and
   • $c$ is the constant byte $01100011$.

In matrix form, $$\begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \\ a_6 \\ a_7 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{pmatrix}$$ in hexadecimal notation (where the row number corresponds to the first hexadecimal digit and the column number to the second hexadecimal digit of the byte to be replaced):

ShiftRows

ShiftRows shifts the $l$-th row (counted starting from zero, that is, $l$ runs through $0$ , $1$ , $2$ and $3$; in particular, the first row is not shifted) $l$ positions to the left (where shift is cyclic). That is, the (square) block with entries

is transformed into one with entries

MixColumn

MixColumn exchanges all entries of each column of the block by a sum of multiples of them. This is done by multiplying each column by a fixed matrix. More exactly,

• if $B_j$ (with coefficients $b_{0,j}$ , $b_{1,j}$ , $b_{2,j}$ and $b_{3,j}$ ) corresponds to the column $j$ of the input block, and
• if $A_j$ (with coefficients $a_{0,j}$ , $a_{1,j}$ , $a_{2,j}$ and $a_{3,j}$ ) corresponds to the column $j$ of the output block of the operation,

then $$\begin{pmatrix} a_{0,j} \\ a_{1,j} \\ a_{2,j} \\ a_{3,j} \end{pmatrix} = \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} b_{0,j} \\ b_{1,j} \\ b_{2,j} \\ b_{3,j} \end{pmatrix}$$ For example, the byte $a_{0,j}$ is computed by $$a_{0,j} = 2 \cdot b_{0,j} + 3 \cdot b_{1,j} + b_{2,j} + b_{3,j}$$

AddRoundKey

AddRoundKey adds, by the XOR operation, the key $W(r)$ of the current round $r$ to the current block $B$ of the ciphertext, the status, that is, $B$ is transformed into $$B \oplus W(r).$$ The key is generated column by column. We denote them by $W(r)_0$, $W(r)_1$, $W(r)_2$ and $W(r)_3$; that is, $$W(r) = W(r)_0 \mid W(r)_1 \mid W(r)_2 \mid W(r)_3.$$ Since the key has $16$ bytes, each column has $4$ bytes.

1. The first round key $W(0)$ is given by the initial $W$ key.
2. For $r = 1$ , …, $R$ (where $R$ is the total number of rounds, $R = 10$ for us), the four columns $W(r)_0$, $W(r)_1$, $W(r)_2$ and $W(r)_3$ of the new key are generated from the columns of the old $W(r-1)$ key as follows:
   1. The first column $W(r)_0$ is given by $$W(r)_0 = W(r-1)_0 \oplus \mathrm{ScheduleCore}(W(r-1)_3);$$ that is, the last column of the previous round key plus the result of ScheduleCore applied to the first column of the previous round key (which we denote by $T$ ); here ScheduleChore is the composition of transformations:
      1. SubWord : Substitutes each of the 4 bytes of $T$ according to the S-box of SubBytes .
      2. RotWord : Shift $T$ one byte to the left (in a circular manner, that is, the last byte becomes the first).
      3. Rcon(r): Adds (by XOR ) to $T$ the constant value, in hexadecimal notation, $(02)^{r-1} 00 00 00$ (where the power, that is, the iterated product, is calculated in the Rijndael field $\mathbb{F}_{2^8}$). That is, the only byte that changes is the first one, by adding either the value $2^{r-1}$ (for $r \leq 8$ ) or the value $2^{r-1}$ in $F_{2^8}$ for $r = 9, 10$.
   2. The next columns $W(r)_1$, $W(r)_2$ and $W(r)_3$ are given, for $i = 1, 2$ and $3$ , by $$W(r)_i = W(r)_{i-1} \oplus W(r-1)_i;$$ that is, the previous column of the current round key plus the current column of the previous round key.

Diffusion

We note that the only transformation that is not affine (that is, the composition of a linear application and a constant shift) is the multiplicative inversion in the Rijndael field $\mathbb{F}_{2^8}$ in the SubBytes operation. In fact

1. In the operation SubBytes are applied, in this order,
   1. the inversion in $\mathbb{F}_{2^8}$ ,
   2. a linear application, and
   3. the translation by a constant vector.
2. ShiftRows is a permutation, in particular, linear.
3. MixColumn is an addition, in particular, linear.
4. AddRoundKey is the translation by the round key.

Regarding the goals of ideal diffusion and confusion, we can point out that in each step about half of the bits (in SubBytes) or bytes (in MixColumn and ShiftRows)is replaced and transposed. To convince oneself of the complementarity of the simple operations for high security, that is, that they generate in conjunction high confusion and diffusion after few iterations:

• the substitution of the alphabet, and
• the permutation of text, in particular,
  • of the permutation between the entries of every row, and
  • of the permutation between the column,

it is worth to experiment in Individual Procedures -> Visualization of Algorithms -> AES -> Inspector with some pathological values, for example:

• All key and plaintext entries equal 00, and
• all key entries equals 00 and plaintext entries equals 00 except one entry equals 01, that is, change a single bit.

We see how this small initial difference spreads out, already generating totally different results after, say, four rounds! This makes plausible the immunity of AES against differential cryptanalysis.

In case all key and plaintext entries are equal to 00 , we also understand the impact of adding the Rcon(r) constant to the key in each round: that’s where all the confusion comes from!

The Rijndael binary field

The function MixColumn (as well as the computation of the power of Rcon in AddRoundKey) uses the multiplication given by the so-called Rijndael field, denoted $\mathbb{F}_{2^8}$, to compute the multiple of (the number given by a) byte; let us quickly introduce it:

Groups and Fields

A group is a set $G$ with

• an operation $\cdot: G \times G \to G$ that satisfies the associativity law,
• has a neutral element (that is, an element $e$ such that $x \cdot e = x = e \cdot x$ for all $x$ in $G$ ) and
• an inverse of every element (that is, for every $x$ in $G$ an element $y$ such that $x \cdot y = e = y \cdot x$ ).

Generally,

• the operation is denoted by $\cdot$ ,
• the neutral element by $1$ , and
• the inverse of $x$ in $G$ by $x^{-1}$.

Example. The set of nonzero rational numbers $\mathbb{Q}^*$ with the multiplication operation $\cdot$ is a group.

If the group $G$ is commutative, that is, if the operation satisfies the commutativity law, then commonly

• the operation is denoted by $+$
• the neutral element by $0$ , and
• the inverse element of $x$ in $G$ by $-x$ .

Example. The set of rational numbers $\mathbb{Q}$ with the addition operation $+$ is a commutative group.

A field is a set $F$ with an addition and multiplication operation $+$ and $\cdot$ such that

• the set $F$ with $+$ is a commutative group,
• the set $F^* = F - \{ 0 \}$ with $\cdot$ is a commutative group, and
• the distributivity law is satisfied.

Example. The set of rational numbers $\mathbb{Q}$ with addition $+$ and multiplication $\cdot$ is a field.

Bytes as Polynomials with Binary Coefficients of Degree 7

A byte, a sequence $b_7$ … $b_1$, $b_0$ of eight bits in $\{ 0, 1 \}$ is considered a polynomial with binary coefficients by $$b_7 ... b_1 b_0 \mapsto b_7 X^7 + \cdots + b_1 X + b_0$$ For example, the hexadecimal number $0x57$ , or binary number $0101 0111$ , corresponds to the polynomial $$x^6 + x^4 + x^2 + x + 1.$$ All additions and multiplications in AES take place in the binary field $\mathbb{F}_{2^8}$ with $2^8 = 256$ elements, which is a set of numbers with addition and multiplication that satisfies the associativity, commutativity and distributivity law (like, for example, $\mathbb{Q}$ ) defined as follows: Let $$\mathbb{F}_2 = \{ 0, 1 \}$$ be the field of two elements with

• addition $1 + 0 = 0 + 1 = 1$ and $0 + 0 = 1 + 1 = 0$ (which is the $\oplus$ addition given by XOR ), and
• (the natural) multiplication $1 \cdot 0 = 0 \cdot 1 = 0 \cdot 0 = 0$ and $1 \cdot 1 = 1$ .

Let $$\mathbb{F}_2[X] = \mathbb{Z} / 2 \mathbb{Z} = \text{the polynomials on } \mathbb{F}_2,$$ that is, the finite sums $a_0 + a_1 X + a_2 X^2 + \cdot s + a_n X^n$ to $a_0$ , $a_1$ , …, $a_n$ to $\mathbb{F}_2$ and be $$\mathbb{F}_{2^8} := \mathbb{F}_2[X] / (X^8 + X^4 + X^3 + X+1).$$ That is, the result of both operations $+$ and $\cdot$ in $\mathbb{F}_2 X$ is the remainder of the division by $X^{8 + X^4 + X} 3 + X + 1$ .

Addition

The $+$ addition of two polynomials is the addition in $\mathbb{F}_2$ coefficient to coefficient. That is, as bytes, the $+$ addition is given by the XOR addition.

Multiplication

The multiplication $\cdot$ is given by the natural multiplication followed by the division with rest by the polynomial $$m(x) = x^8 + x^4 + x^3 + x + 1.$$ For example, in hexadecimal notation, $57 \cdot 83 = C1$ , because $$(x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1) = x^{13} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1$$ and $$x^{13} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1 = (x^5 + x^3 + 1) (x^8 + x^4 + x^3 + x + 1) + x^7 + x^6 + 1$$ The multiplication by the polynomial $1$ does not change anything, it is the neutral element. For every polynomial $b(x)$ , Euclid’s extended algorithm, calculates polynomials $a(x)$ and $c(x)$ such that $$b(x)a(x) + m(x)c(x) = 1.$$ That is, in the division with the remaining $a(x) b(x)$ for $m(x)$ left over $1$ . This means that $a$ is the inverse multiplicative in $\mathbb{F}_{2^8}$ , $$b^{-1}(x) = a(x) \text{ in } \mathbb{F}_{2^8}.$$ When we invert a byte $b$ into $\mathbb{F}_{2^8}$ , we mean byte $a = b^{-1}$.

Self-Check Questions

1. How many rounds has AES for a 128 bit key?

   • $8$
   • 10
   • $12$
   • $16$

2. Which are the steps of each round? SubBytes, ShiftRows, MixColumn and AddRoundKey

3. Which one of the steps is non-linear?

   • SubBytes
   • ShiftRows
   • MixColumn
   • AddRoundKey

Summary

There are two basic operations in ciphering: transpositions and substitution.

• Transpositions rearrange the symbols in the text without changing the symbols themselves (such as Caesar’ cipher that advances every letter in the plaintext by the same distance in the alphabet).
• Substitutions replace the symbols of the text (be it one by one or in groups, …) by other symbols (or groups of symbols) without changing the order in which they occur (such as the scytale, where the parchment is wrapped around a stick and the text written on it horizontally).

Either of these ciphers is insecure because they preserve statistical data of the plaintext: For example, a mere (monoalphabetic) substitution cipher falls victim to the frequency distributions of symbols in the plaintext being carried over to the ciphertext. Instead, a modern cipher combines substitution and permutation ciphers, so called substitution and permutation network or Feistel cipher

While the only cipher proved to be perfectly secure, that is no method of cryptanalysis is faster than exhaustive key-search, modern ciphers such as DES from 1976 or AES from 2000 in practice achieve, up to (the k)now, the same, that is, no cryptanalytic method faster than exhaustive key-search is known. The key criterion for this feat is high diffusion as defined by Shannon, that is, if a bit in the plaintext or key changes, then half of the bits in the ciphertext changes. Compare it to that of ancient algorithms!

Questions

1. Which cipher is a substitution cipher? Scytale, Enigma, AES, DES
2. Which cipher is perfectly secure? RSA, one-time pad, AES, DES
3. What is the smallest key size used by AES? 56, $128$ , 512, 2048

Required Reading

Read the section on symmetric cryptography in the article Simmons et al. (2016).

Read (at least the beginnings of) Chapter 9 on hash functions in Menezes, Oorschot, and Vanstone (1997), and (at least the beginnings of) that in the most recent work Aumasson (2017), Chapter 6.

Further Reading

Cryptanalyze a substitution cipher in Esslinger et al. (2008).

Follow the encryption process

• of AES by the AES inspector in Esslinger et al. (2008).
• of the Enigma by the animation in Esslinger et al. (2012).

See the book Sweigart (2013a) for implementing some simpler (symmetric) algorithms in Python, a readable beginner-friendly programming language.

Read the parts of the book Schneier (2007) on understanding and implementing modern symmetric cryptographic algorithms.

3 Hash Functions

Study Goals

On completion of this chapter, you will have learned about the manifold uses of (cryptographic) hash functions whose outputs serve as IDs of their input (for example, a large file).

Introduction

A hash function is an algorithm that generates an output of fixed (byte) size (usually around 16 to 64 bytes) from an input of variable (byte) size, for example, a text or image file, a compressed archive.

hash function: algorithm that generates a fixed-size output from variable-size input

As a slogan it transforms a large amount of data into a small amount of information.

Concept

A hash function takes an input (or “message”), a variable-size string (of bytes), and returns a fixed-size string, the hash value (or, depending on its use, also (message) digest, digital fingerprint or checksum).

For example, the hash md5 (of 16 bytes) of the word “key” in hexadecimal coding (that is, whose digits run through 0, …,9, a,b, c,d,e and f) is 146c07ef2479cedcd54c7c2af5cf3a80.

One distinguishes between

• checksum (non-cryptographic) functions, and
• cryptographic (or one-way) hash functions

Checksum

A (simple) hash function, or checksum function, should satisfy:

• fast computation of a hash for any given data, and
• that it is highly unlikely for two (hardly) different messages to give the same hash.

That is, with respect to the second property, a hash function should behave as much as possible like a random function, while still being a fast and deterministic algorithm.

checksum function: algorithm that quickly generates a fixed-size output from variable-size input without collisions.

For example, the most naive checksum would be the sum of the bits of the input, truncated to the fixed output size. It is almost a hash function: it is fast, and it is indeed unlikely that two different messages give the same hash. However, one easily obtains two almost identical messages with the same hash. Tiny alterations could therefore go undetected.

Cryptographic hash function

A cryptographic (or one-way) hash function should, moreover, satisfy:

• it is unfeasible to calculate an input that has a given hash.

Thus the output string of fixed length that a cryptographic hash function produces from a string of any length (an important message, say) is a kind of inimitable signature. A person who knows the hash value cannot know the original message; only the person who knows the original message can prove that the “hash value” is produced from that message.

cryptographic (or one-way) hash function: a hash function such that, given an output, it is unfeasible to calculate a corresponding input.

More exactly:

• a hash function is weakly collision resistant if finding an inverse is computationally unfeasible, that is, given an output, finding a (yet unknown) corresponding input;
• a hash function is strongly collision resistant if finding a collision is computationally unfeasible, that is, finding two inputs with the same output.

weak collision resistance: computationally unfeasible to find an unknown message for a given hash.

strong collision resistance: computationally unfeasible to find two messages with the same hash.

Otherwise, an attacker could substitute an authorized message with an unauthorized one.

Applications

Hash functions are used for

• querying database entries,

• error detection and correction, for example,

  • for data integrity checks,

• in cryptography to identify data but conceal its content, for example,

  • for data authenticity checks,

  • for authentication, for example,

    • to store passwords and
    • for digital signatures.

Checksums

A checksum is a method of error detection in data transmission (where it also bears the name message digest) and storage. That is, a checksum detects whether the received or stored data was not accidentally or intentionally changed, that is, is free from errors or tampering. It is a hash of (a segment of) computer data that is calculated before and after transmission or storage.

That is, it is a function which, when applied to any data, generates a relatively short number, usually between 128 and 512 bits. This number is then sent with the text to a recipient who reapplies the function to the data and compares the result with the original number. If they coincide, then most probably the message has not been altered during transmission; if not, then it is practically certain that the message was altered.

Most naively, all the bits are added up, and the sum is transmitted or stored as part of the data to be compared with the sum of the bits after transmission or storage. Another possibility is a parity bit that counts whether the number of nonzero bits, for example, in a byte, is even or odd. (The sum over all bits for the exclusive-or operation instead of the usual addition operation.) Some errors — such as reordering the bytes in the message, adding or removing zero valued bytes, and multiple errors which increase and decrease the checksum so that they cancel each other out — cannot be detected using this checksum.

The simplest such hash function that avoids these shortfalls against accidental alterations is CRC, which will be discussed below. It is faster than cryptographic checksums, but does not protect against intentional modifications.

Hash Table

A hash table stores and sorts data by a table in which every entry is indexed by its hash (for a hash function that is fixed once and for all for the table). That is, its key is the hash of its value. This key has to be unique, and therefore the hash function ideally collision free. If not, then, given a key, first the address where several entries with this key are stored has to be looked up, and then the sought-for entry among them, causing a slow down.

Therefore, the hash size has to be chosen wisely before creating the table, just large enough to avoid hash collisions in the far future. If this can be achieved, then the hash table will always find information at the same speed, no matter how much data is put in. That is, hash tables often find information faster than other data structures, such as search trees, and frequently used; for example, for associative arrays, databases, and caches.

Examples

In practice, even for checksums, most hash functions are cryptographic. Though slower, they are still fast enough on most hardware. In fact, sometimes, for example to store passwords, they have to deliberately slow so that the passwords cannot be found quickly by their hash values through an exhaustive search among probable candidates (see rainbow tables in Section 12.6.2).

The most common cryptographic hash functions used to be MD5, usually with an output length of 128 bit, invented by Ron Rivest of the Massachusetts Institute of Technology in 1991. By 1996 methods were developed to create collisions for the MD5 algorithm, that is, two messages with the same MD5 hash. MD5CRK was a concerted effort in 2004 by Jean-Luc Cooke and his company, CertainKey Cryptosystems, to prove the MD5 algorithm insecure by finding a collision. The project started in March and ended in August 2004 after a collision for MD5 was found. In 2005, further security defects were detected. In 2007 the NIST (National Institute of Standards and Technology) opened a competition to design a new hash function and gave it the name SHA hash functions, that became a Federal Information Processing standard.

Cyclic Redundance Check (CRC)

One exception is the Cyclic Redundance Check (CRC) which is a fast simple hash function to detect noise, expected accidental errors, for example, while reading a disc, such as a DVD, or in network traffic. The CRC uses a binary generating polynomial (a formal sum in an unknown whose only coefficients are 0 and 1 such as $X^2 + X$ ). The CRC is computed by:

1. a polynomial division of the binary polynomial obtained from the binary input (that is, 1001 corresponds to $X^3 + 1$ ) by the generating polynomial, and
2. taking the remainder from the division as output.

The choice of the generator polynomial is the most important one to be made when implementing the CRC algorithm; it should maximize the error-detection and minimize the chances of collision. The most important attribute of the polynomial is its length (or degree) as it determines the length of the output. Most commonly used polynomial lengths are 9 bits (CRC-8), 17 bits (CRC-16), 33 bits (CRC-32) and 65 bits (CRC-64).

In fact, the type of a CRC identifies the generating polynomial in hexadecimal format (whose 16 digests run through 0, …, 9 and A, …, F). A frequent CRC type is that used by Ethernet, PKZIP, WinZip, and PNG; the polynomial $0x04$ .

Again, the CRC can only be relied on to confirm the integrity against accidental modification; through intentional modification, an attacker can cause changes in the data that remain undetected by a CRC. To prevent against this, cryptographic hash functions could be used to verify data integrity.

SHA

SHA stands for Secure Hash Algorithm. The SHA hash functions are cryptographic hash functions made by the National Security Agency (NSA) and the National Institute of Standards and Technology. SHA-1 is the successor to MD5 with a hash size of 160 bits, an earlier, widely-used hash function, that fell victim to more and more suspicious security shortcomings (even though it is not downright broken; for example, there is no known computationally feasible way to produce an input for a given hash ). SHA-1 was notably used in the Digital Signature Algorithm (DSA) as prescribed by the Digital Signature Standard (DSS) by the Internet Engineering Task Force.

In the meanwhile, there are three SHA algorithms SHA-1, SHA-2 and SHA-3, released in 2015 of ever-increasing security, mitigating the shortcomings of each predecessor. “SHA-2” permits hashes of different bit sizes; to indicate the number of bits, it is appended to the prefix “SHA”, for example, “SHA-224”, “SHA-256”, “SHA-384”, and “SHA-512”.

3.2 Hash as ID

A hash function should be

• onto, that is, all possible fixed-length sequences are hash function value, and
• similar to a uniformly random variable, that is, the probability of each of the values of the function is the same.

So if, for example, the output has 256 bits, then ideally each value should have the same probability $2^{-256}$. That is, the output identifies the input practically uniquely (with a collision chance of ideally $2^{-256}$); So one might think of a data hash, for example, from a file, as its ID card (or more accurately, identity number); a hash identifies much data by little information.

Since the length of the hash sequence is limited (rarely $\geq 512$ bits), while the length of the input sequence is unlimited, there are collisions, that is equal hashes from different files. However, the algorithm minimizes the probability of collisions by distributing their values as evenly as possible: Intuitively, make them as random as possible; more accurately, every possible fixed-length sequence is a value and the probability of each of the values is the same.

3.3 Cryptographic Hash Functions

It is cryptographic (or one-way)

• when reversion is computationally infeasible, that is, finding an input for a given output, and
• when similar inputs yield dissimilar outputs (in the sense of high diffusion, that is, ideally one different input bit implies about half of the output bits to be different).

Cryptographic or One-Way hash function: a hash function such that it is computationally infeasible to find an input for a given output and similar inputs have dissimilar output.

More exactly, the algorithm should resist

• against the creation of an inverse image (that is the function is unidirectional): given an output, the quickest way to find an input with this output is by brute force, that is by proving all possible inputs,
• against the creation of a second reverse image: given an input, the quickest way to find another input with the same output is by brute force, that is by proving all possible inputs,
• against the creation of collisions: the fastest way to find two (arbitrary) entries with the same output is by brute force, that is, by proving all possible entries.

According to Kerckhoff’s principle, the algorithm should also be public. In practice,

• the most important is resistance against the attack to create a second reverse image, and
• the least important is that against collisions attacks; there are several algorithms, for example, MD4, MD5 and SHA-1 that do not resist against collisions attacks, but are still in use.

For example, the CRC algorithm is a hash function (not cryptographic); Common cryptographic hash functions are, for example, MD4, MD5, SHA-1, SHA-256 and SHA-3.

For example, the output of the hash function SHA-256 of ongel is bcaec91f56ef60299f60fbce80be31c49bdb36bc500525b8690cc68a6fb4b7f6. The output of a hash function, called hash, but also message digest or digital fingerprint, depending on the input, is used, for example, for message integrity and authentication.

3.4 Common Cryptographic Hash Functions

The most commonly used hash (cryptographic) algorithms even today are 16 bytes (=128 bits) MD4 and MD5 or SHA-1, which uses 20 bytes (= 160 bits). Although all of these, MD4, MD5 and SHA-1 do not withstand collision attacks, they remain popular for use. Their implementation details are described in RFCs (Request for Comments): an RFC publicly specifies in a text file the details of a proposed Internet standard or of a new version of an existing standard and are commonly drafted by university and corporate researchers to get feedback from others. An RFC is discussed on the Internet and in formal meetings of the working group tasked by the Internet Engineering Task Force (IETF). For example, networking standards such as IP and Ethernet have been documented in RFCs.

• MD4 (Message-Digest algorithm):
  • Developed in 1991 by Ron Rivest, one of the three creators of the RSA algorithm (and the RSA Data Security company);
  • fast, but vulnerable to pre-image creation.
  • described in RFC 1320 .
• MD5:

  • Developed by RSA Data Security.

  • Described in RFC 132.

  • Vulnerable to collisions, but not to creating a second reverse image. Often used for

    • integrity check, by software with peer-to-peer protocol (P2P, or Peer-to-Peer, in English), and
    • password storage.
• SHA-1 (Secure Hash Algorithm):
  • Developed by NIST, the National Institute for Standards and Technology.
  • Vulnerable to collisions, but not to creating a second reverse image.

instead of MD4, MD5 or the ancient SHA-1, recommended are more recent versions like SHA-256 and SHA-3 of the Secure Hash Algorithm.

Secure Hash Algorithm: Hash algorithm recommended by the National Institute for Standards and Technology.

3.5 Construction Scheme

Similar to modern symmetric ciphers that follow the design laid out by Feistel’s Lucifer algorithm in the 70s, cryptographic hash functions follow the Merkle-Damgård construction:

The Merkle meta-method, or the Merkle-Damgård construction, builds from a lossless compression function (that is, whose inputs have the same length as the output) a lossy compression function, that is, a hash function. This method allows us to reduce the immunity of the entire hash function against

• the creation of an inverse image, and
• the creation of collisions

to the corresponding immunity of the compression function.

Merkle Meta-Method Scheme

This construction needs

• an initialization value (IV = initialization value),
• a compression function C, and
• a padding to pad the entry string $m$ of the hash function to a string $\bar m$ such that $\bar m$ = $(m_1 , m_2 , ...)$ consists of a multiple of blocks $m_1$, $m_2$, … which are accepted by the compression function.

With $h_0 = \mathrm{IV}$, one computes for $i = 1, 2, ...$ $$h_i = C(m_i, h_{i-1}).$$ That is, for the computation of the hash of the current block, the value of the compression function of the last block enters jointly with the current block value.

The C compression function consists of a Feistel Cipher (or substitution and permutation network) $c$ where

• or, in the Mayer-Davis scheme, $m_i$ is the key and $H_{i-1}$ the plaintext; then the ciphertext is added (by XOR ) to $H_{i-1}$ . This is $$h_i = h_{i-1} \oplus c(h_{i-1}, m_i)$$
• or in the Miyaguchi-Preneel scheme, $m_i$ is the plaintext and (a $g(H_{i-1})$ change) $H_{i-1}$ is the key; then, as in Mayer-Davis’s scheme, the ciphertext is added (by XOR ) to $H_{i-1}$ . This is $$h_i = h_{i-1} \oplus c(m_i, g(h_{i-1}))$$

The addition of $h_{i-1}$ ensures that the C compression function is no longer invertible (unlike the $c$ cipher for a fixed key); that is, for a given output, it is no longer possible to know the (unique) input. Otherwise, to create a collision, given an output $h_i$ , one could decipher by different keys, $m_i '$ and $m_i ''$ to get different entries $h_{i-1}'$ and $h_{i-1}''$ .

Padding

To reduce the immunity from hash to compression function, the padding $m \overline m$ needs to meet sufficient conditions:

• $m$ is a starting segment of $\overline m$ , that is, the message is extended, but its initial segment not changed!
• two messages of the same length are extended by the same final segment.
• two messages of different lengths are extended differently, so that they differ in the last block.

The simplest pad that meets these conditions is the one that attaches the length $|m|$ to $m$ and fills the segment between the end of $m$ and $|m|$ by the number of 0 s prescribed by the block size, that is, the concatenation $$\overline m = m \, \| \, 0^k \, \| \, |m|.$$

Observation: To avoid collisions, it is not enough for the padding to fill with zeros the rest of the message: This way, two messages that only differ in the number of final zeros at the last end would have the same padding!

Instead, the simplest way would be to attach a digit 1, and then the rest with 0s. However, we will see that this would allow collisions with the Merkle meta-method if the initial value IV was chosen in the following way:

Denote $B_1 , ..., B_k$ the message blocks and IV the starting value. The hash is calculated by iterating the compression function $C : (X,B) \to C(X,B)$ $$H(M) = C(C(..C(C(\mathrm{IV},B_1),B_2)...B_{k-1}),B_k)$$ The clou of Merkle’s meta-method is the reduction of collisions from the hash function to the compression function: a hash collision would imply a collision of the compression function, that is, different pairs of $X',B'$ and $X'',B''$ blocks with $C(X',B')=C(X'',B'')$ .

To see this, we note that

• if the $m'$ and $m''$ collident messages have different lengths, then the last $B'_k$ and $B''_k$ blocks are different (because they contain the different lengths!), but they collide, because the value of the compression function of the last entry is the hash function.
• Otherwise, that is, colliding messages have the same length, so there’s a block further to the right where the padded messages differ and we’ll find a block collision after it.

Without the length in the padding, the collision of two messages with different lengths can ultimately only be reduced to a pre-image of the initial value IV under the compression function, that is, a value B such that $$\mathrm{IV} = C(\mathrm{IV}, B).$$

If its choice were arbitrary, the authors of MD5 and SHA-256 could however have inserted the following back door: Both algorithms use Mayer-Davis’s scheme, that is, a compression function $$C(X,K) = X \oplus E(X, K)$$ for a Feistel cipher E with a key $K$ ; in particular, with $K$ fixed the decryption function $E_K = E( \cdot,K)$ is invertible! Now, if the authors wanted to, they could have chosen a key $K$ and set $$\mathrm{IV} := E_K^{-1}(0)$$ exactly so that IV = C(IV,K). Then C(IV, B) = C(C(IV, K), B) , that is, a collision between the hashes of $B$ and $K \oplus B$ !

Since, for example, MD5 and SHA-256 choose as IV a value whose pre-image is supposedly not known (for example, the hexadecimal digits in ascending order in MD5 or the decimal digits of the first eight primes in SHA-256) this problem is more theoretical than practical.

3.6 SHA-256

We won’t study the inner workings of SHA-256 in detail (in contrast to O’Connor (2022)), but a schematic look at its design shows that it follows the Merkle-Damgård construction:

It is then iterated in roughly 64 rounds:

On Lynn-Miller (2007), you can trace the bytes of an input of your choosing at each step of the SHA-1 algorithm.

3.7 Uses

Uses of cryptographic hash functions abound:

Digital Signatures

If the roles of the public and private key are flipped, then the encryption is a digital signature: while the encrypted message will no longer be secret, every owner of the public key can check whether the original message was encrypted by the private key. However, in theory, signing a file (using the RSA algorithm) that was encrypted using the RSA algorithm would decrypt it. Therefore, in practice, since for a signature it suffices to unequivocally identify the signed file (but its content often secret, for example, when signing a secret key), usually a cryptographic hash is encrypted by the private key.

(H)MAC

A message authentication code algorithm uses a one-way hash function (such as MD5 or SHA-1) and a block cipher that accepts a secret key and a message as input to produce a MAC. The MAC value provides the intended receivers (who know the secret key) to detect any changes to the message content by:

• an integrity check (by ensuring that a different MAC will result if the message has been altered) and
• an authenticity check (because only the person knowing the secret key could have produced a MAC).

Data Storage and Integrity

Hash functions (not necessarily cryptographic, like CRC) are used:

• for fast data query (that is, at fixed time, regardless of the number of entries, for example,

  • in a hash table, and
  • in a Merkle tree;

• to ensure the integrity of a file in case of accidental modifications, that is, to detect differences between the file and a reference version (typically the one before the file is transported).

Passwords

Cryptographic Hash functions are used:

• To distribute values evenly (key stretching), intuitively make them less predictable; that is, as KDF (= Key Derivation Function);
  • in particular, to generate and store passwords, that is, as PBKDF (= Password Based Key Derivation Function).
  • To ensure the integrity of a file against tampering, that is, to detect differences between the file and a reference version (typically the one before the file is transported);
  • in particular, to ensure the authenticity of a file: to detect differences between the file and a version that was under the control of a specific person.

Observation: Note the difference between authenticity and authentication: The former guarantees the equality of data received and sent from a person (for example, in the digital signature), the latter the identity of that person (for example, in a secure site access).

The cryptographic hash algorithms listed above, MD4/5, SHA … distribute the values evenly, but are fast; so they are unsuitable for password creation because they are vulnerable to brute-force attacks. To prevent these, the PBKDF algorithm, for example, PBKDF1, PBKDF2, bcrypt, scrypt, Argon2 (a new and more promising candidate), are

• deliberately slow, such as bcrypt,
• deliberately require a lot of memory to compute, such as scrypt algorithm;
• used only once for each entry (guaranteed by a salt, an additional, unique, usually random argument. Without salt, the algorithm is prone to attacks by so-called Rainbow Tables, tables of the hashes of the most common passwords.

3.8 Dispersion Table

A h table (or scatter table) uses a hash function to address the entries (= rows) of a array, that is, a data table.

Each entry has a name, that is, a unique identification (= key). For example, the key is the name of a person. The key data, for example, your telephone number, is stored in a table row. These rows are numbered from $0$.

The row number, your address, of the key is determined by your hash. As an advantage, at a fixed time, the data can

• from the key being found, and
• added.

While,

• for a list of $n$ entries, the search compares on average $n/2$ entries, and
• for a binary tree of $n$ entries, $log_2 n$ entries.

Collisions, that is, two entrances with the same hash are more frequent than you might think; see the Birthday Paradox. To avoid collisions, it is necessary

• choose the number of addresses large enough, and
• the sufficiently injector hash function, that is, it rarely sends different arguments at equal values.

When collisions occur, a strategy is

• instead of the hash number address a single entry, use Chaining: address a bucket, a bucket of multiple entries, a list, or

• use “Open Hashing. put the entry in another free position, for example,

  • the next one, or
  • use another hash function to calculate it (Double Hashing).

Up to $80$ of the table being filled, on average $3$ collisions occur. That is, finding an entry takes $3$ operations. To compare, with $1000$ entries, it would take on average

• in a $500$ operations table, and
• on a binary tree about $10$ operations.

However, after this factor collisions occur so often that the use of another data structure, for example a binary tree, is recommended.

3.9 Merkle Tree

A spreading or Merkle tree (invented in 1979 by Ralph Merkle) groups data into blocks by a tree (binary), whose vertices (= nodes) are hashes and whose sheets (= end nodes) contain the data blocks, in order to be able to quickly check (in linear time) each data block by computing the root hash.

In a $n$ (= $2^n$ sheets )deep scattering tree the data block of each sheet is verifiable

• by knowledge
  • of $n$ hashes “antagonists” from a source dubious, and
  • from the hash of the top of a source reliable, and
• by calculation
  • from the hash of the data block on the sheet,
  • of the $n$ hashes of his predecessors, and
  • the comparison of the calculated root hash with that obtained.

Use

The main use of Merkle trees is to ensure that blocks of data received from other pairs in a point-to-point network (P2P) are received intact and unchanged.

Operation

A Merkle tree is a (usually binary) hashes tree whose leaves are data blocks from a file (or set of files). Each node above the leaves on the tree is the hash of its two children. For example, in the image,

• Hash(34) is the hash of the concatenation of the hashes Hash(3) and Hash(4), that is, $\mathrm{Hash(34)} = \mathrm{Hash(3)} || \mathrm{Hash}(4))$,
• Hash(1234) is the hash of the concatenation of the hashes Hash(12) and Hash(34), that is, $\mathrm{Hash(1234)} = \mathrm{Hash(12)} || \mathrm{Hash}(34))$, and
• the radical hash Hash(12345678) is the hash of the concatenation of the hashes Hash(1234) and Hash(5678), that is, $$\mathrm{Hash(12345678)} = ||mathrm{Hash}(5678)).$$ .

Normally a cryptographic shuffling function' is used, for example,SHA-1. However, if the Merkle tree only needs to protect against unintentional damage, "checkums" are not necessarily cryptographic, such asCRC`s are used.

At the top of the Merkle tree resides the root-dispersion or master-dispersion. For example, on a P2P network, root dispersion is received from a trusted source, e.g. from a recognized website. The Merkle tree itself is received from any point on the P2P network (not particularly reliable). This (not particularly reliable) Merkle tree is compared by calculating the leaf hashes with the reliable root dispersion to check the integrity of the Merkle tree.

The main advantage of a tree (deep $n$ with $2^n$ leaves, that is, blocks of data), rather than a dispersion list, is that the integrity of each leaf can be verified by calculating $n$ (rather than $2^n$) hashes (and its comparison with the root hash).

For example, in Figure 3.1, the $3$ integrity check requires only

• the knowledge of the hashes Hash(4) Hash(12), and Hash(5678), and
• the computation of the hashes Hash(3) Hash(34), Hash(1234), and Hash(12345678)
• the comparison between the calculated Hash(12345678) and the hash obtained from the trusted source.

Self-Check Questions

1. How do a checksum and cryptographic hash function differ? Only for a cryptographic hash function it is unfeasible to create collisions.
2. What are typical uses of hash functions? Fast data queries, identification of files (for example, virus scanning), error correction and detection.
3. What are typical uses of cryptographic hash functions? Password storage, message authentication, integrity checks.
4. What is the clou of the Merkle-Damgård construction? Reduction of the resistance against collisions to that of the compression function.

Summary

A hash function transforms any data (such as a file), in other words, a variable-length string, into a fixed-length string (which is usually 16 or 32 bytes long); as a slogan, it transforms a large amount of data into a small amount of information. Their output, a hash, can be thought of as an ID-card of their input (such as a file); to this end, the hash function should

• diffuse well, that is, the inversion of an input bit implies the inversion of about half of the output bits (the avalanche effect), that is, each output bit should depend on each input bit,
• be onto, that is all possible fixed-length sequences are hash function values, and
• be similar to a uniformly random variable, that is, the probability of each of the values of the function is the same.

So if, for example, the output has 256 bits, then ideally each value should have the same probability $2^{-256}$. That is, the output identifies the input practically uniquely (with a collision chance of ideally $2^{-256}$);

It is cryptographic (or one-way)

• when reversion is computationally infeasible, that is, finding an input for a given output, and
• when similar data yield dissimilar hashes.

Recommended are, among others, the more recent versions SHA-256 and SHA-3 of the Secure Hash Algorithm.

Questions

1. How do a checksum and cryptographic hash function differ? Only for a cryptographic hash function it is unfeasible to create collisions.

2. What are typical uses for checksums? (Accidental) error detection and correction, for example, noise on reading a Compact Disc or in network traffic, and many more.

3. What are typical uses of cryptographic hash functions? (Intentional) alteration correction in storage or network traffic, and many more.

4. Name common cryptographic hash functions. The MD and the SHA family.

5. Which hash function is not cryptographic ? SHA-1, MD4, CRC, WHIRLPOOL

6. Which cipher is a stream cipher? RSA, Enigma, AES, DES

Required Reading

Read the section on symmetric cryptography in the article Simmons et al. (2016).

Read (at least the beginnings of) Chapter 9 on hash functions in Menezes, Oorschot, and Vanstone (1997), and (at least the beginnings of) that in the most recent work Aumasson (2017), Chapter 6.

Further Reading

Observe the diffusion created by a cryptographic hash function in Lynn-Miller (2007).

4 Asymmetric Cryptography

Study Goals

On completion of this chapter, you will have learned …

• the advantages of asymmetric cryptography, such as, key distribution over distance, and
• its limitations, principally the lack of trust in the distant owner of a public key.

Introduction

The big practical problem of single-key cryptography is key distribution, more exactly:

• to secretly pass the same key to all correspondents, usually far away from each other, before they can communicate securely. Even messengers as in diplomatic and military agencies have to be trusted unconditionally to neither intentionally nor accidentally disclose them.
• the high number of keys needed for a group of correspondents to communicate securely: Every pair of correspondents in a group needs a unique key to communicate securely. In a group of 10 correspondents, each user would need a different key for each of the other 9 correspondents; in total 45 different keys. The number of keys increases in proportion to the square of the number of correspondents: For example, in a group of 1000 correspondents, around half a million keys would be needed.

In 1976, Whitfield Diffie and Martin Hellman conceived that the key distribution problem could be solved by an algorithm that satisfied:

• (computationally) easy creation of a matched pair of keys for encryption and decryption,

• (computationally) easy encryption and decryption,

• (computationally) infeasible recovery of one of the keys despite knowledge of:

  • the algorithm,
  • the other key, and
  • any number of matching plaintext and ciphertext pairs.

• (computationally) infeasible recovery of the plaintext for almost all keys $k$ and messages $x$ .

Observation: This was the first public appearance of two-key cryptography. However, the British Government Communications Headquarters (GCHQ) knew it around a decade earlier.

If a user, say Alice, of such an algorithm keeps her decryption key secret but makes her encryption key public, for example, in a public directory, then:

• Everyone who wishes to communicate securely with Alice just needs to look up her public key to send her a ciphertext that only she can decrypt; that is, a message can be encrypted without any need for secrecy.
• a ciphertext encrypted with Alice’s secret key can be deciphered by everyone who uses the corresponding public key; that is, a sender can be identified without any need for secrecy.

The security of two-key cryptographic algorithms relies on the computational difficulty of a mathematical problem, for example, factoring a number that is the product of two large primes; ideally, computing the secret key is equivalent to solving the hard problem, so that the algorithm is at least as secure as the underlying mathematical problem is difficult. This has not been proved for any of the standard algorithms, although it is believed to hold for each of them.

4.1 Asymmetric Cryptography

In comparison with symmetric cryptography, asymmetric encryption avoids the risk of compromising the key to decipher that is involved in exchanging the key with the cipherer. This secure communication with anyone via an insecure channel is a great advantage compared to symmetric cryptography. Let us recall the classic methods to exchange a symmetric key, before looking at its asymmetric counterpart: While asymmetric cryptography made it possible to exchange a secret key overtly, this convenience comes at the risk of the unknown identity of the key holder, prone to a man-in-the-middle attack which Public Key Infrastructure work around by the use of certificates, digital signatures by third parties of public keys.

Symmetric Ciphers

A symmetric key must be passed secretly. Possible methods are:

• Derivation from a base key using a Key Derivation Function (KDF), a cryptographic hash function which derives a secret key from secret — and possibly other public — information, for instance, a unique number,

• Creating a key from key parts held by different persons, for example, as an analogue to the one-time pad: If $s$ is the secret (binary number, then $s = s_1 \oplus s_2 \oplus ... \oplus s_n$ for the partial secrets $s_1$, $s_2$, … Reconstruction of $s$ is only possible if all $s_1$, $s_2$, … are combined

• transmission via a different channel, for example:

  • personally,
  • a sealed letter,
  • by telephone, or
  • by quantum entanglement, where a change of state of one quantum particle (say from spin-up to spin-down) instantly implies that of the other and vice-versa. This information of state cannot be intercepted and lends itself to bit transmission; However, entanglement is fragile and can not be fully controlled. Quantum entanglement for key distribution was put into practice in Sasaki et al. (2011).

4.2 Man-in-the-middle Attack

Diffie and Hellman’s achievement was to separate secrecy from authentication: Ciphertexts created with the secret key can be deciphered by everyone who uses the corresponding public key; but the secret-key holder has no information about the owner of the public key!

Thus the public keys in the directory must be authenticated. Otherwise A could be tricked into communicating with C when he thinks he is communicating with B by substituting C key for B in A’s copy of the directory; the man-in-the-middle attack (MIM):

Man-in-the-middle attack: an attacker intercepts the messages between the correspondents and assumes towards each of them either correspondent’s identity.

Scenario

In an MITM, the attacker places himself between the correspondents, assuming towards each one of them the identity of the other to intercept their messages.

1. Bob sends his public key to Alice. Eve intercepts it, and sends Alice her own public key that claims Bob as its owner. If Alice sends a message to Bob, then she uses, without realizing it, the public key of Eve!
2. Alice enciphers a message with the public key of Eve and sends it to Bob.
3. Eve intercepts the message, deciphers it with her private key; she can read the message and alter it.
4. Eve enciphers the message with Bob’s public key.
5. Bob deciphers the message with his private key and suspects nothing.

So both Alice and Bob are convinced to use each other’s public key, but they are actually Eve’s!

Example

In practical terms, this problem occurs for example in the 1982 ‘ARP’ Address Resolution Protocol (in RFC 826) which standardizes the address resolution (conversion) of the Internet layer into link layer addresses. That is, ARP maps a network address (for example, an IPv4 address) to a physical address as an Ethernet address (or MAC address). (On Internet Protocol Version 6 (IPv6) networks, ARP has been replaced by NDP, the Neighbor Discovery Protocol).

The ARP poisoning attack proceeds as follows:

Maria Bonita wants to intercept Alice’s messages to Bob, all three being part of the same physical network.

Maria Bonita sends a arp who-has packet to Alice which contains as the source IP address that of Bob whose identity we want to usurp (ARP spoofing) and the physical MAC address of Maria Bonita’s network card.

0. Alice will create an entry that associates the MAC address of Maria Bonita with Bob’s IP address.
1. So when Alice communicates with Bob at the IP level, it will be Maria Bonita who will receive Alice’s packages!

4.3 Public and private key

Let us recall that there are two keys, a public key and a private key. Usually:

• The public key is used to encrypt, while the private key is used to decrypt.

Thus, a text can be transferred from the encipherer (Alice) to one person only, the decipherer (Bob).

The roles of the public and private keys can be reversed:

• The private key is used to encrypt, while the public key is used to decipher.

Thus, the encipherer can prove to all decipherers (those who have the public key) their ownership of the private key; the digital signature.

The (mathematical) algorithm behind the encryption either by the public key (for hiding the content of digital messages) or by the private key (for adding digital signatures) is in theory almost the same: only the roles of the arguments of the one-way function are exchanged (for example, in the RSA algorithm). In practice, however, usually:

• the public key encrypts paddings of the plaintext (to avoid a text so short that the private key can be easily computed), and
• the private key encrypts hashes, the value of a function that almost always sends different texts to different numbers. (This hash is usually a cryptographic hash, that is, given its output, it is practically impossible to deduce its input, so that the integrity of the signed message can be checked, that is, that whether it has been altered on the way).

That is, while

• for encryption by the public key, the preparatory transformation of the text (the padding) is easily invertible,
• for private key encryption, it (the hashing) is hardly invertible.

Ephemeral Sub Keys

A sub-key of a master key is a key (whose cryptographic checksum is) signed by the master key. The owner often creates subkeys in order to use the main key (public and private) only

• to sign

  • someone else’s key,
  • a personal sub key

• to revoke a key (that is, sign a revocation),

• to change the expiration date of a personal key.

The subkeys are used for all other daily purposes (signing and deciphering).

This way, if a sub key is eventually compromised (which is more likely that that of a main key due to its everyday use), then the main key will not be compromised. In this case,

• the owner revokes it (publishes a note invalidating the compromised public key which is digitally signed by its private main key), and
• creates another key.

We saw how subkeys work in practice in the common command-line program GPG discussed in Section 13.4. A good reference is https://wiki.debian.org/Subkeys.

Sub Keys for the Day-to-Day

For more security, you create (for example, in GPG)

• first a (public and private) main key and

• then several sub keys with expiry date, for everyday use:

  • a subkey to decipher in everyday life (for example, the encrypted emails received), and
  • a sub key to sign in everyday life (for example, the emails sent).

  Before their expiry, the keys are either extended, or revoked to create others.

As for using different keys to sign and encrypt,

• it’s necessary for some algorithms, for example,

  • Yes, in the ElGamal algorithm,
  • but not in “RSA”.

• it is safer (but more inconvenient, which can lead to the user’s sloppiness and then in practice it is less safe!) to have different keys to decipher and to sign,

  • because

    • it is useful to keep a copy of the private key to decipher (to be able, after its loss, to still read files enciphered by the corresponding public key)
    • it is useless to keep a copy of the private key to sign (because once lost another person can sign with it too).

  • because, for example in the RSA algorithm, the signature and the decipherment (by the private key) are equal (in theory, though in practice implemented differently) algorithms!

    Therefore, signing (by the private key) a document encrypted by the corresponding public key is equivalent to deciphering it! However, this possibility is theoretical, but it does not practice: All implementations of the RSA protect the user by the fact that always and exclusively

    • paddings of a document, and
    • sign a cryptographic check sum of a document (from which its original content cannot be deducted).

Best Practices for Key Management

Only the main key is immutably linked to the identity of the owner, and all others replaceable: While the

• main key is kept in a safe at home and only sees the light when keys need to be signed (be it from the owner or from someone else [for example, to establish the web of trust]).

  In practice,

  • is stored on a flash drive or memory card,

  • and to be more durable, it is even printed, for example:

    • By the paperkey program that extracts the secret part (of the file) of the private key (that is, it omits all public information like

      • the identity,
      • the algorithm, …,

      and encodes this part in hexadecimal notation (stored in a text file). (So if the key has, for example, $4096$ bits, the file generated by paperkey has $\geq 1024$ bits). This command

      gpg --export-secret-key 0xAE46173C6C25A1A1! > ~/private.sec
      paperkey --secret-key ~/private.sec > ~/private.paperkey

      • exports only (indicated by the !) the main secret key (0xAE46173C6C25A1A1) of the private keys, and
      • extracts and converts it by paperkey into a text file.

    • By the qrencoder program (for keys whose file has $< 2953$ characters) which encodes it into a QR code.

• the sub keys are stored in a smartcard that is accessed by a USB reader with its own keyboard. Compared to using a digital file, it has the advantage that

  • reading the keys on a smart card is much more difficult than a file (stored on a USB stick or hard drive)

  • leaves fewer traces:

    • It never reveals the key, but only what is necessary to prove that it can access it, and
    • is immune to keyloggers that record keystrokes.

(Perfect) Forward Secrecy

(Perfect) Forward Secrecy means that, after the correspondents exchanged their (permanent) public keys and established mutual trust,

1. before correspondence each correspondent creates an ephemeral key (the session key*) and signs it by the private (permanent) key to avoid a MITM attack (see Section 4.2),
2. after correspondence each correspondent deletes her (ephemeral) private key.

This way, even if the correspondence was eavesdropped and recorded, it cannot be deciphered later; in particular, it cannot be deciphered by obtaining a correspondent’s private key.

For example, the TLS protocol, which encrypts communication of much of the Internet, has since version 1.2 support for Perfect Forward Secrecy: In the handshake between client and server in Section 13.3 : after the client has received (and trusted) the server certificate, the server and the client exchange a ephemeral public key which serves to encrypt the communication of only this correspondence. This ephemeral key is signed by the public (permanent) key of the server. (The creation of this asymmetric key in Perfect Forward Secrecy makes the creation of a symmetric preliminary key by the client in the penultimate step in the handshake in the TLS protocol superfluous.)

Group Signature

Every granted signature shall first be thought through solemnly. The same goes for digital signatures:

A signature proves that the owner of the private key, say Alice, acknowledged the content. In e-mail communication, it avoids the risk that an attacker

• mimics the e-mail address of sender Alice, but
• enciphers with the key of the recipient Bob.

However, if the communication contains something Alice doesn’t want to be seen by others (for example, to be read out loud by a prosecutor in court), better not prove her acknowledgement! Since this message may eavesdropped, her correspondent may change his mind about the privacy of their conversation, or his account is hacked, …

To give an analogy to our analog reality, an automatic digital signature by Alice compares to the recording of every private conversation of Alice.

In fact, usually Alice wants to prove only to Bob that she’s the sender, but not to third parties! For this, in a group signature, an ephemeral key to sign is created and shared (that is, the public and private key) between Alice and Bob. This way, Alice and Bob are sure that the message was sent by the other correspondent, but a third party only that it was sent among the group members.

4.4 Public Key Infrastructures

A Public Key Infrastructure (PKI) of a network establishes trust among its spatially separated users by first authenticating them, then authorizing their public keys by signing them (referred to as digital certificates) and finally distributing them. In institutions and corporations, a PKI is often implemented as “a trust hierarchy” of Certification Authorities, whereas in looser communities it can be decentralized and trust mutually established by the users themselves.

A Public Key Infrastructure (PKI): establishes trust among its spatially separated users of a network by first authenticating them, then authorizing their public keys by signing them (referred to as digital certificates) and finally distributing them.

A PKI includes:

• (Digital) Certificates: public keys which are signed to authenticate their users. Other then the name and key, they contain additional personal data, such as an e-mail address, and usually an expiry date.

• Certificate Revocation List (CRL): A list of certificates that have been revoked before their validity expires, for example, because

  • the key has been compromised, or
  • the key owner is no longer trustable, for example, because of her departure.

• Directory Service: a searchable database of the emitted certificates; for example, in a trust hierarchy an LDAP server (Lightweight Directory Access Protocol; a standard used by large companies to administer access of users to files, printers, servers, and application data), and in the web of trust a server that hosts a database searchable by a web form.

Philosophy of Solutions

The identity of the key owner is confirmed by third parties, that is, other identities with private keys that confirm by their digital signatures that it is Alice who owns the private key.

However, the problem of the public key identity arises again: How can we ensure the identities of the private key owners? There are two solutions:

• hierarchical authorities, and

• the web of trust

For short: while in the Web-of-Trust the connections built by trust form a graph, in the approach by hierarchical authorities they form a tree.

Hierarchical Authorities

In the approach via hierarchical authorities, private key owners are distinguished by hierarchical levels. At the highest level lie the root authorities on which one trusts unconditionally.

hierarchical authorities: Key owners that confirm others’ identities by digital signatures and are organized in a hierarchy, where trust passes from a higher to a lower level; total trust is placed in those at the highest level, the root authorities.

For example,

• VeriSign, GeoTrust, Commode, … are major US certifying companies;

• as a recent addition, the (US intermediary) non-profit authority Let us encrypt;

• a look at the /etc/ssl/certs folder in the Linux distribution openSUSE reveals that there is, for example,

  • a German authority (TeleSec of Deutsche Telekom AG, the former national telecommunications operator),
  • three Spanish (Firmaprofesional, ACCVRAIZ1 — Agencia de Tecnología y Certificación Electrónica, and ACC RAIZ FNMT — Fábrica Nacional de Moneda y Timbre), and
  • many U.S. authorities.

Web of Trust

In the web of trust, private key owners cannot be distinguished from each other.

web of trust: Private key owners confirm other’s identities by successively passing trust to each other among equals.

The absence of root authorities, unconditionally trusted entities, is compensated for by the

1. trust initially established by

   • having obtained the public key personally (for example, at key-sign parties, meetings where participants exchange and sign their public keys mutually), or

   • by

     1. having obtained the key through a different channel (Website, e-mail, …) and
     2. having communicated your check sum via another channel (phone, SMS, instant messenger, …);

2. then the trust is successively (transitively) passed from one to the other: If Alice trusts Bob, and Bob trusts Charles, then Alice trusts Charles.

Standardization of Philosophies on the Internet

On the Internet,

• the system of trust by hierarchical authorities has been standardized by the scheme X.509, principally used to encrypt the communication between a user and a (commercial) Website (but also between users in corporate environments, such as, S/MIME e-mail encryption), and
• The OpenPGP scheme (as implemented by the GnuPG program), with its main use of encrypting e-mails. This scheme radically rejects any hierarchy: the user can publish a public key with an e-mail address on a public key server such as that of the MIT without even confirming (by an activation e-mail) that he has access to the account of this e-mail address.

4.5 DANE

The IETF (Internet Engineering Task Force) proposed (in RFC 63941: DANE use cases and RFC 66982: DANE protocol) the DANE protocol that aims to cryptographically harden the TLS, DTLS, SMTP, and S/MIME protocols using DNSSEC. By DNSsec, a DNS resolver can authenticate a DNS resolution, that is, whether it is identical to that on the authoritative DNS server, by checking its signature (of the authoritative DNS server). Instead of relying, like these protocols, entirely on certificate authorities (CAs), domain holders

• can restrict the CAs that validate the domain’s certificate, and
• can emit certificates for themselves, without reference to CAs.

Using CAs, there is no restriction on which CAs can issue certificates for which domains. If an attacker can gain control of a single CA among the many CAs that the client trusts, then she can emit fake certificates for every domain. DANE allows clients to ask the DNS servers, which certificate are trustworthy so that the domain holder can restrict the scope of a CA. When the user is passed a domain name certificate (as part of the initial TLS handshake), the client can check the certificate against a TLSA resource-record (TLSA-RR) published in the DNS for the service name which is authenticated by the authoritative DNS server.

The most common standard for a PKI is the hierarchy of X.509 certificate authorities. X.509 was first published in 1998 and is defined by the International Telecommunications Union’s Standardization sector (ITU-T), X.509 establishes in particular a standard format of electronic certificate and an algorithm for the validation of certification path. The IETF developed the most important profile, PKIX Certificate and CRL Profile, or “PKIX” for short, as part of RFC 3280, currently RFC 5280. It is supported by all common web browsers, such as Chrome and Firefox, which come with a list of trustworthy X.509 certificate authorities.

In more detail, the TLSA-RR contains the entry Certificate Usage, whose value (from 0 to 3, the lower, the more restrictive) restricts the authority allowed to validate the certificate for the user:

0. PKIX-TA (CA constraint). The client’s trust resides in a PKIX authority.
1. PKIX-EE (Service Certificate Constraint). The client’s trust resides in a PKIX certificate.
2. DANE-TA (Trust Anchor assertion). The client’s trust resides in an authority which, in contrast to PKIX-TA, does not have to be a PKIX certificate authority.
3. DANE-EE (Domain-issued certificate). The client’s trust resides in an certificate which, in contrast to PKIX-EE, does not have to be a PKIX certificate.

The DANE check therefore serves to confirm certificates issued by public certification authorities. With DANE values (2 and 3), the domain holder has the option of creating his own, even self-signed certificates for his TLS-secured services, without having to involve a certification authority known to the client. By choosing between “Trust Anchor” (TA) and “End Entity” (EE), the domain owner can decide for himself whether to anchor DANE security to a CA or server certificate.

4.6 Hybrid Ciphers

hybrid encryption: a two-key algorithm is used to authenticate the correspondents by digitally signing the messages or to exchange a key for single-key cryptography for efficient communication thereafter,

The most common key exchange method is to create a shared secret between the two parties by the Diffie-Hellman protocol and then hash it to create the encryption key. To avoid a man-in-the-middle attack, the exchange is authenticated by a certificate, that is, by signing the messages with a long term private key to which the other party holds a public key to verify. Since single-key cryptographic algorithms are more efficient than two-key cryptographic algorithms by a considerable factor, the main use of two-key encryption is thus so-called hybrid encryption where the two-key algorithm is used

• to authenticate the correspondents by digitally signing the messages, or
• to exchange a key for single-key cryptography for efficient secure communication thereafter.

For example, in the TLS (Transport Layer Security; former SSL) protocol, which encrypts secure sites on the World Wide Web, a cryptographic package such as TLS_RSA_WITH_3DES_EDE_CBC_SHA (identification code 0x00 0x0a) uses

• RSA to authenticate and exchange the keys,
• 3DES in CBC mode to encrypt the connection, and
• SHA as a cryptographic hash.

Self-Check Questions

1. What is a problem that Public Key cryptography solves? Distributing a secret key over an open channel.
2. What is a problem that Public Key cryptography does not solve? The authentication of the private key owner.
3. What are two common approaches to work around the Man-in-the-middle attack? Certificate authorities and Web-of-trust
4. What are common protocols to work around the Man-in-the-middle attack? X.509 (as used by S/MIME) and OpenPGP

Summary

Single-key (or symmetric) cryptography suffers from the key distribution problem: to pass the same secret key to all, often distant, correspondents. Two-key (or asymmetric) cryptography solves this problem seemingly at once, by enabling the use of different keys to encrypt and decrypt. However, the identity of the key owner must be confirmed; if not personally, then by third parties, that is, identities with private keys that confirm by their digital signatures that it is Alice who owns the private key. However, the problem of the public key identity arises again: How can we ensure the identities of these private key owners? There are two solutions: In the approach via hierarchical authorities, private key owners are distinguished by hierarchical levels. At the highest level lie the root authorities on which one trusts unconditionally. In the web of trust, trust is transferred from one to the other, that is, trust is transitive: If Alice trusts Bob, and Bob trusts Charles, then Alice trusts Charles.

Questions

Required Reading

Read the section on asymmetric cryptography in the article Simmons et al. (2016). Read in Menezes, Oorschot, and Vanstone (1997) Sections 3.1 and 3.3.

Further Reading

Read the parts of the book Schneier (2007) on understanding and implementing modern asymmetric cryptographic algorithms.

5 Modular Arithmetic

Study Goals

On completion of this chapter, you will have learned what a trapdoor function is, and:

1. why modular arithmetic is needed to define such a function, and
2. what modular arithmetic is by division with rest.

Introduction

The security of two-key cryptographic algorithms relies on the computational difficulty of a mathematical problem, for example, factoring a number that is the product of two large primes; ideally, computing the secret key is equivalent to solving the hard problem, so that the algorithm is at least as secure as the underlying mathematical problem is difficult. This has not been proved for any of the standard algorithms, although it is believed to hold for each of them.

To see the usefulness of (modular) arithmetic in cryptography, recall that asymmetric cryptography is based on a trapdoor function, which

• must be easily computable, but
• its inverse must be practically incomputable without knowledge of a shortcut, the key!

The ease of calculating the function corresponds to the ease of encryption, while the difficulty of calculating the inverse corresponds to the difficulty of decryption, that is, inverting the encryption. For example, RSA uses

• as an encryption function the raising to an $n$ -th power, and
• as a decryption function its inverse, the root extraction.

While both, the function itself and even its inverse, are easily computed using the usual multiplication of numbers, instead cryptographic algorithms (such as RSA) use modular arithmetic to entangle the computation of the inverse function without knowledge of the key (which in RSA is root extraction).

We already know modular or circular arithmetic from the arithmetic of the clock, where $m = 12$ is considered equal to $0$ : Because the indicator restarts counting from $0$ after each turn, for example, $3$ hours after $11$ hours is $2$ o’clock: $$11 + 3 = 14 = 12 + 2 = 2.$$ Over these finite circular domains, called finite rings and defined in Section 5.3, (the graphs of) these functions become irregular and practically incomputable, at least without knowledge of a shortcut, the key.

In what follows, we

1. convince ourselves of the difficulty on this domain in contrast to that of the real numbers, and
2. introduce this domain.
3. we explain how to calculate the inverse function on it.

5.1 Modular Arithmetic as Randomization

The difficulty of calculating the inverse corresponds to the difficulty of decryption, that is, inverting the encryption. In an asymmetric cryptographic algorithm,

• the ease of encrypting (a number), and
• the difficulty of deciphering (a number)

are based on an invertible function such that

• it is easily computable, but
• its inverse function is difficult to compute.

For example, the inverses of the trap-door functions

• raising to a power $x \mapsto x^e$ (in the RSA algorithm), and
• exponentiating $x \mapsto g^x$ (in the Diffie-Hellman algorithm)

are given by

• the root extraction $x \mapsto x^{1/n}$, and
• the logarithm $\log_g$.

They are

• easily computable on the domain of real numbers $\mathbb{R}$ (for example, by the bisection method for continuous functions thanks to the connectedness of $\mathbb{R}$ ),
• but on their finite cryptographic domains they are almost incomputable.

Observation. Both functions are algebraic, that is, they are expressed by a formula of sums, products, and powers. Analytical functions, that is, infinite convergent sums, for example, sine, cosine, …, are inconvenient by the rounding errors.

5.2 Functions on Discrete Domains

The domain of these functions is not the set of integers $\mathbb{Z}$ (or that of the real numbers $\mathbb{R}$ that includes them), because both functions, exponentiation and raising to a power, are continuous over $\mathbb{R}$:

If the domain of these functions were $\mathbb{R}$ , then their inverses could be approximated over $\mathbb{R}$ , for example, by iterated bisection where the inverse point is besieged in intervals that are halved at every iteration: Given $y_0$, find an $x_0$ such that $f(x) = y_0$ is equivalent to finding a zero $x_0$ of the function $$x \mapsto f(x) - y_0.$$

1. (Start) Choose an interval $[a, b]$ such that $$f(a) < 0 \text{ and } f(b) > 0.$$

2. (Recalibration) Calculate the midpoint $m := (a + b)/2$ of the interval $[a , b]$:

   • If $f(m) = 0$ , then $m = x_0$, and we have found our zero.

   Otherwise:

   • either $f(m) < 0$ , then replace the left edge $a$ with $m$ ,
   • or $f(m) > 0$ , then replace the right edge $b$ with $m$ ,

   and recalibrate the newly obtained interval $[m, b]$ respectively $[a, m]$.

By the Intermediate Value Theorem, the zero is guaranteed to be in the interval, which at each step decreases and converges to the intersection.

Finding the zero of the polynomial $$F(x) = x^3 + 3x^2 + 12x + 8$$ by bisection with starting points $x_1 = -5$ and $x_2 = 0$ , yields in steps $i = 2, ..., 15$ the successive approximations

5.3 Finite Rings

To avoid the iterative approximation of the zero of a function and thus complicate the computation of the inverse function (besides facilitating the computation of the proper function), the domain of a trapdoor function is a finite ring denoted by $$\mathbb{Z} / m \mathbb{Z} = \{ 0, 1, ..., m-1 \}$$ for a natural number $m$.

finite ring: A finite set that contains $0$ and $1$ and over which a sum $+$ is explained that obeys the laws of associativity and commutativity.

In such a finite ring $$m = 1 + \cdots + 1 = 0;$$ necessarily, every addition (and thus every multiplication and every raising to a power) has result $< m$. So the addition of $\mathbb{Z} / m \mathbb{Z}$ is different from that on $\mathbb{Z}$ (or $\mathbb{R}$). For example, for $m = 7$ , $$2^2 = 2 \cdot 2 = 4 \text{ and } 3^2 = 3 \cdot 3 = 7 + 2 = 0 + 2 = 2.$$ We will introduce these finite rings first by the examples $\mathbb{Z} / 12 \mathbb{Z}$ and $\mathbb{Z} / 7 \mathbb{Z}$, the rings given by the clock hours respectively weekdays), then for every $m$ .

When we look at the graphs of the functions, which are so regular on $\mathbb{R}$ , we note that over the finite ring $\mathbb{Z} /101 \mathbb{Z}$, either graph, that of

• the exponentiation with base $2$, and
• the parabola

is initially as regular over $\mathbb{Z} / 101 \mathbb{Z}$ as over $\mathbb{Z}$ , but starting

• from $x = 7$ (because $2^7 = 128 > 100$ ), respectively
• from $x = 11$ (because $11^2 = 121 > 100$ )

begins to behave erratically. (Except for the symmetry of the parabola on the central axis $x = 50.5$ due to $(-x)^2 = x^2$).

Task. Experiment with the function plotter Grau (2018d) to view the erratic behavior of other function graphs over finite domains.

5.4 Modular Arithmetic in Everyday Life

We apply modular arithmetic in everyday life when we add times in the daily, weekly and yearly cycle of clock hours, weekdays and months. It is this circularity that explains the naming “ring”.

Clock

The prototypical example of modular arithmetic is the arithmetic of the clock in which the pointer comes back to start after $12$ hours; formally, $$12 \equiv 0,$$ which implies, for example, $$9 + 4 \equiv 1 \quad \text{ and } \quad 1-2 \equiv 11. \qquad{(5.1)}$$ That is, $4$ hours after $9$ hours is $1$ o’clock, and $2$ hours before $1$ o’clock is $11$ o’clock. We can go further: $9 + 24 \equiv 9$; that is, if it is $9$ o’clock now, then in $24$ hours (one day later) as well.

Days of the Week

Another example of modular arithmetic in everyday life are the days of the week: after $7$ days, the days of the week start over: If we enumerate ‘Saturday’, ‘Sunday’, ‘Monday’, ‘Tuesday’, ‘Wednesday’, ‘Thursday’ and ‘Friday’ by $0$ , $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , then $$7 \equiv 0,$$ which implies, for example, $$4 + 4 \equiv 1 \quad \text{ and } \quad 1-2 \equiv 5.$$ Indeed, $4$ days after Wednesday is Sunday, and $2$ days before Sunday is Friday. We can go further: $5 + 14 \equiv 5$; that is if now it is Thursday, then in $14$ days (two weeks later) as well.