FAQ from the Cryptology Lectures

Frequently Asked Questions with Responses

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Notation and Conventions

What does cryptography mean in English?

»Hidden Writing« (classic greek kryptos = »hidden«, graphein = »to write«). Cryptology is the »science of hidden writing«. The newer term cryptanalysis means »analysis of hidden writing«. All these are made-up words modeled after ancient Greek. The earliest known occurrence of »cryptography« and »cryptology« are the latin forms cryptographia and cryptologia used by John Wilkins 1641. (Hint: The terms steganographia and polygraphiae occured even some hundred years earlier as the titles of two works by Trithemius.)

Why »cryptanalysis« instead of »cryptoanalysis«?

Apparently Friedman coined the term »cryptanalysis«, and this became accepted in English (British as well as American). Other languages adopted the term with an »o« inside. German: »Kryptoanalyse«, Spanish: »criptoanálisis«, Italian: »crittoanalisi«, Russian: »kriptoanalis«, Czech and Polish: »kryptoanalyza«, Swedish: »kryptoanalys«. Only the French usually say »cryptanalyse«. In contrast the »o« in psychoanalysis is used in all languages (except French).

Why are so many cryptological procedures named after random people instead of their true inventors?

That's a matter of speculation. In most cases the true inventor seemed unknown to the first who wrote up the procedure for the public. Instead they baptized it after people from whom they themselves had learned it. Don't forget that cryptology in past times almost always was a secret science. Many inventions were »classified« for long times, and there was no public teaching in this discipline. [Overview]

Why cryptograms often are written down in groups of 5 letters?

This conceals the natural word boundaries that otherwise would help the cryptanalyst a lot. The number 5 goes back to early telegraphy: In the 1860's usually some text portions were replaced by short »codes« for money saving. This led to unpronouncable »words«, therefore the telegraphy companies constrained this to groups of 5 letters (and prevented price dumping by concatenating the groups into longer words). Later this practice was adopted by radio operators when cryptograms were transmitted by wire or radio: Groups of 5 can be handled with almost no errors. Sometimes also groups of 4 were used, for example by the German army in the context of the Enigma.

What is the difference between »codes« and »ciphers«? Or between »encryption« und »coding«?

These terms are not used consistently, not even in the cryptologic literature. Often ciphers are denoted as codes, sometimes as »secret codes«. »Every day speech« (press, books) uses the terms »coding« und »encryption« as synonyms, as well as »code« and »cipher«.
For these lecture notes we declare:

A cipher (or encryption) is a transformation that depends on a secret key, and therefore can be reversed only by targeted subjects who know the key.

A code is a transformation that is not secret, and therefore can be reversed by anyone who cares.

However there exists a method of encryption using a secret codebook. Also in this case we should avoid confusion and call this procedure a »codebook cipher« rather than a »code«.

How large is a terabyte?

Here is a table of prefixes:

2¹⁰	2²⁰	2³⁰	2⁴⁰	2⁵⁰	2⁶⁰
Kilo	Mega	Giga	Tera	Peta	Exa

We use the »binary kilo« 1024 instead of the »decimal kilo« 1000. They differ a little but have the same order of magnitude.

How large is a terrabyte?

There is no such thing as a terrabyte. See terabyte. The term derives from the greek »teras« = monster. »Terra« in contrast is the latin word for earth.

Encryption Methods—General

I've invented a new encryption method. Now I would like to know how ingenious it is.: The ultimative answer to this question is by the well-known cryptologist Bruce Schneier. You find it here.
I've programmed a new cool encryption app. Now I would like you to test and use it.: Here is the answer by John R Levine.
Can we improve encryption by using strange symbols (such as here) instead of normal letters?: No. The smart cryptanalyst, as a first step, is free to replace the mysterious symbols by normal letters (or, if there are too many, by groups of letters). As an example in the cryptogram (from E. A. Poe's »Goldbug«, with some symbols already changed to ASCII characters)
53##+305))6*;4826)4#.)4#);806*;48+8$ 60))85;1#(;:#*8+83(88)5*+;46(;88*96* ?;8)*#(;485);5*+2:*#(;4956*2(5*-4)8$ 8*;4069285);)6+8)4##;1(#9;48081;8:8# 1;48+85;4)485+528806*81(#9;48;(88;4( #?34;48)4#;161;:188;#?;
replace each 5 by A, each 3 by B, each # by C and so on. Then the cryptogram reads
ABCCDBEAFFGHIJKLGFJCMFJCFIKEGHIJKDKN GEFFKAIOCPIQCHKDKBPKKFAHDIJGPIKKHRGH SIKFHCPIJKAFIAHDLQHCPIJRAGHLPAHTJFKN KHIJEGRLKAFIFGDKFJCCIOPCRIJKEKOIKQKC OIJKDKAIJFJKADALKKEGHKOPCRIJKIPKKIJP CSBJIJKFJCIOGOIQOKKICSI
and the mysterious and confusing symbols become accessible to standard cryptanalytic methods and computer tools as counting letters, finding patterns etc.
Using fancy symbols as cipher alphabet is cryptologically equivalent with a general monoalphabetic substitution. And it has the drawback of a complicated key agreement—the method is practically usable only with a written substitution table—and a difficult change of key.

Cipher Machines

Do Enigma's rotors turn before or after the currently typed letter is encrypted?: The rotor movement is a purely mechanical function of the key pressing. The pressed key closes the circuit to the light bulbs. This effects a stable electrical contact and causes the corresponding bulb to light up as long as the key is pressed.
If the machine would first encrypt and then move the rotors, the movement must be delayed until the release of the key. This would need an additional force, as by a strained spring. Moving the rotors by pressing a key requires a mechanically much simpler construction.
Why does Enigma's middle rotor move somewhat irregularly?: Here is a comprehensive explanation.
Do Fialka's rotors turn before or after the currently typed letter is encrypted?: In contrast to Enigma, Fialka has its rotors stepping after the currently typed letter is encrypted. Probably the additional force for this movement is taken from the electrical power supply. See the description of Fialka referenced here (near the end of the page).

Block Ciphers

Why should I avoid ECB mode? After all, each plaintext block gets encrypted by a very strong cipher, say AES.

To see what can go wrong look at the Wikipedia entry for ECB.

Does it make sense to treat the initialization vector in ECB or some other chaining mode as secret and use it as an additional key component?

(Then for the example of DES we had 56 proper key bits plus a 64 bit initialization vector, making a total of 120 key bits.)
No! In the decryption process only the first plaintext block depends on the initialization vector. This means that keeping the initialization vector secret conceals known plaintext only for the first block. If the attacker knows the second or a later plaintext block, then she may determine the key as in ECB mode (by exhaustion, or by an algebraic attack, or by any other attack with known plaintext).

I have to encrypt some very short pieces (shorter than 128 bits) of plaintext (in fact the entries of a database column). What is the preferred way for this?

There are two answers, depending on the scenario.

If the encrypted information is to be processed automatically only:
Pad the information with random junk up to the block length of 128 bits. Then apply AES with a fixed key. Keep the random bits secret. The receiver of the information (that is an algorithm) has to know which bits of the decrypted information are junk and then discards them.
If the encrypted information is to be processed by humanoid beings: For this problem we have no smooth solution.
Requirements: The ciphertext should (a) have about the same length as the plaintext and (b) consist of printable characters.
To fulfill requirement (a) use AES in OFB or CTR mode. To avoid a codebook attack the key should change after significantly less than 2^n/2 plaintexts where n is the 2-logarithm of the number of possible different plaintexts. (That means plaintexts might be represented by n bits or in other words n is the information content of a plaintext.)
Example: For the approximately 200 different country codes of the world n would be 8. And by the rule of thumb the key should change every 2⁴ = 16 plaintexts. Hardly a good solution!
Instead choose a blocklength N ≥ 2n. Then there is no need to change the key on the fly.
In the example of country codes we would choose a blocklength of 16 bits = 2 bytes. Then we can encode each plaintext by two bytes and get two-byte ciphertexts.
To fulfil requirement (b) and make ciphertexts human-readable encode them in hexadecimal. In the example each encrypted country code consists of 4 hexadecimal figures.
Note: 2 bytes might be encoded by 3 printable characters.

RSA

Are there enough primes for RSA to be secure from brute force attacks?: Yes. More than enough, even strong primes (= primes of the form p = 2q+1 with another prime q). Even very strong primes where p is strong with q also being strong. For more concrete estimates look here and here.
Why does RSA use products of two primes?: RSA also works with products of arbitrary many primes. However the case of two primes is the best understood one. For more detailed information look here.
What happens if two different participants use the same RSA module n?: Obviously both can read each other's messages since both can factorize n and hence compute the other's private key. But it's even worse: A message sent to both of them is readable by everyone, see here.
Is RSA in danger if someone chooses a small public exponent e?: Not necessarily. However sending the same message to several receivers could compromise it, see here. Even in classical cryptography an important maxim was: Never encrypt the same plaintext with different keys.
Why the recommendation to use different key pairs for encryption and digital signatures?: Otherwise the user has to take care that he doesn't inadvertently decrypt a ciphertext in the erroneous belief that he digitally signs a document. There are several scenarios where this danger is real, see here.
Instead of proven primes common RSA implementations use so called pseudoprimes. What could happen if such a pesudoprime is not prime?: There are a few messages (very few!) that don't decrypt properly. It is unknown whether this case yet occured in this universe, see here.

Cryptanalysis

When the cryptanalyst performs an exhaustion—how can she recognize whether the tentative decryption yields sensible plaintext?: By the statistical properties and patterns of the target language. If she gets four letters, two »e«'s, one »n«, and one »r«, then for almost all european languages this hints at a sensible text. In contrast a »q« followed by »r« aspects in disfavour of a correct decryption. For systematic tests see here.
What the heck is an »attack with known plaintext«? If the attacker knows the plaintext, there is nothing left to crack!: Short answer: Often the cryptanalyst knows a chunk of plaintext, maybe only a single »probable word«, and then tries to determine some further chunks of plaintext—or the key, or the complete plaintext.
Long answer here.
Should we take an attack with 2⁴³ known plaintext blocks seriously?: This depends on the situation. An attacker who eavesdrops a communication channel hardly has a chance for catching that many known plaintext blocks, especially if the sender follows the rules of the trade and changes the key quite often. But imagine the following scenario: The pay-TV station »Platinum Channel« distributes settop boxes containing a fixed cryptographic key. Eve taps the data streams in front of and behind the box. Let's assume that the block size is 64 bits, that is 8 bytes. Then Eve needs 2⁴⁶ bytes, that is 2⁶ = 64 TB of data for her attack. If a typical movie has 6 GB and she taps 10 movies per day, she needs about 1000 days, that is three years, for collecting enough data. Maybe she gives up in between, or the box breaks down. But as a security margin the 2⁴³ seem insufficient, especially against organized crime or intelligence agencies.

Miscellany

How to teach cryptology to kids?

There is a paper by Michael Fellows and Neal Koblitz: Kid Krypto, Crypto '92, Springer-Verlag (1993), pp. 371–389. See also here.
The Secret Code Breaker (Bob Reynard) has a lot of elementary material that's also great for kids.
CrypTool also offers a lot of educational material and challenges.

Why does it make sense dealing with classic ciphers?

Short answer: The algorithms are out-of-date, the methods and principles are up-to-date.
Long answer here.

How to use cryptology in the real life of today?

An answer is here.

Who is Eve?

Cryptologists already in the 1970's invented an early form of gender mainstreaming and staffed their scenarios with men and women alternately:

Alice and Bob are communicating partners. They are children of Ron Rivest.
If more communication partners are needed, Carol and Dave enter the scene.
Eve is an eavesdropper.
Mallory is the »man in the middle« who not only listens but also forges messages. Eve and Mallory, as well as a lot of other characters, are Bruce Schneier's offsprings.

In classical cryptology the role of the cryptanalyst corresponds to the eavesdropper. For this reason in the following we consider the cryptanalyst as female. Among the famous cryptanalysts are Elizebeth FRIEDMAN and Mavis LEVER. Perhaps in classical cryptology it would be adequate to call the cryptanalyst »Elizebeth«.

Author: Klaus Pommerening, 2007-Oct-24; last change: 2016-Feb-23