What jobs are there in cryptanalysis today?

Cryptography from Caesar to RSA. Classic and modern methods in comparison

Table of Contents

List of figures

List of tables

List of abbreviations

1 Introduction
1.1 Objective
1.2 Outline

2 Basics of Cryptography

3 Classic cryptography
3.1 Caesar encryption
3.1.1 Example
3.1.2 Variants
3.2 Vigenère encryption
3.2.1 Principle
3.2.2 Example
3.3 Cryptanalysis: Kasiski test. .
3.3.1 History
3.3.2 Basic principle
3.4 Cryptanalysis: Friedman test.
3.4.1 Definition of the coincidence index.
3.4.2 Determining the key length of a Vigenére text

4 Modern cryptography
4.1 RSA cryptosystem
4.1.1 Historical
4.1.2 Security Effectiveness
4.1.3 Algorithm and Example

5 authentication
5.1 Zero knowledge
5.1.1 The secret door
5.1.2 Fiat Shamir Protocol

6 Summary and Outlook

attachment

Bibliography

List of figures

1 Principle of RSA encryption

2 Zero Knowledge: The Secret Door

List of tables

1 Caesar encryption

2 Reverse Caesar encryption

3 Kasiski test

4 Friedman test

List of abbreviations

Figure not included in this excerpt

1 Introduction

Thousands of years ago people encrypted messages so that they were not readable by everyone. Above all, kings and other hegemons wanted to be sure that their often important messages were not in the hands of their enemies. Especially in wars, be it the traditional Caesarian wars (including the Gallic War 58-51 BC) or wars in the 20th century, such as the Second World War (1939-1945), the skills of cryptologists and their encryption played an important role . They were always opposed by the cryptanalysts and their methods of breaking the encryption. Often either one side or the other made a decisive contribution to the outcome of the war - victory or defeat. For centuries, both sides fought head-to-head to be the better of the two.

But even in the present, in the wake of the exponentially increasing spread of computers, the Internet and the age of digital communication, cryptography is of essential importance in order to be able to securely disseminate and protect private information. Cryptography is commonplace and ubiquitous.

1.1 Objective

The subject of cryptography is too powerful to be described in detail in these few pages. Therefore, this practical work is limited according to the specifications to give an insight into some of the most concise representatives of classic and modern cryptography, as well as classic cryptanalysis.

1.2 Outline

Chapter 2 describes the basic features of cryptography and gives a synopsis of relevant terms in this topic. Chapter 3 below explains two representatives of classic cryptography: Caesar and Vigènere encryption. The classic cryptanalysis according to Kasiski and Friedman is also described. While Chapter 4 introduces a modern method of cryptography, the RSA cryptosystem, Chapter 5 sums up the functions of the zero-knowledge paradigm using the example of the Fiat Shamir protocol.

The final chapter 6 summarizes this work and gives an outlook on the future importance of cryptography.

2 Basics of Cryptography

The term cryptography, derived from the Greek kryptós (German for “hidden”) and gráphein (German for “to write”), describes the science of encryption. Cryptanalysis describes a further sub-area of ​​cryptology. The aim of this is to use various techniques to obtain information about encrypted texts in order to break them, i. H. getting into possession of the actual information without being the actual recipient.

In order to encrypt information or a text, a key is required in addition to the unencrypted message, often referred to as plain text. Using this key, as well as certain methods and techniques, a so-called ciphertext, also known as a cipher, can then be created. This does not seem to make any sense for an unspecified reader. Only those who have the relevant key can bring the encrypted text back into legible form. Many different methods have been developed over the millennia to encrypt messages and keep them hidden from third parties - especially enemies. In the same way, cryptanalysts have repeatedly found and developed methods to find out the secret keys used to decipher the cipher or to break the cipher in other ways (e.g. by analyzing frequencies).

Most encryption algorithms have always had a decisive advantage of not being decrypted, or at least not being decrypted too quickly: time. But with every decade, with every century that passed, people - or more succinctly: the cryptologist - gained more mathematical and logical knowledge. Another strong computer support came into play in the 20th century. Our current computers are getting faster and more powerful and therefore it is probably only a matter of time until the time factor plays no role or at least only a minor role for the algorithms currently in use and supposedly safe. A race between cryptologists and cryptanalysts that has always existed.

In recent years in particular, a paradigm has manifested itself that was mentioned as early as 1883 by the Dutch cryptologist and linguist Auguste Kerckhoff in his work La Cryptographie Militaire: “The security of a cryptosystem must not depend on the secrecy of the algorithm. The security is based only on the secrecy of the key. "1 Many developers of encryption systems have decided in the last few decades to make their algorithms publicly available and thus subject their security to the masses2. Greatest attention was paid to keeping the key secret.

A basic distinction is made between symmetrical and asymmetrical cryptosystems.

While the former uses the same key for encryption and decryption, asymmetric encryption requires a different key to decrypt the ciphertext than for encryption.

3 Classic cryptography

3.1 Caesar encryption

The monoalphabetic substitution known today as Caesar encryption is used by the Roman writer Gaius Suetonius Tranquillus (70-120 AD) in his work D E V I TA CAESARUM (Life of Caesars)3 described as follows [...] si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset; quae si qui investigare et persequi velit, quartam elementorum litteram, id est D pro A et perinde reliquas commutet. "

Translated this means something like: "[...] when something secret was to be conveyed, he wrote in characters, that is, he arranged the letters so that no word could be read: To read them, you swap the fourth letter, So D for A and the same with the rest. "4

Caesar used an encryption that is simple from today's perspective, in which each letter is shifted by a fixed length (namely always n = 3) and replaced by the nth successor. In this way he was able to create a secret code by substitution, which the opponents were probably not able to decipher.

Figure not included in this excerpt

Tab. 1: Caesar encryption

A ciphertext alphabet is defined under the plain text alphabet, which is shifted by the corresponding number of places. A total of 25 different shift options are possible5.

3.1.1 Example

For the following example, as described by Suetonius, the shift length n = 3 was chosen, i.e. an A is replaced by a D, a B by an E and so on.

The plain text

"Attacks at dawn"

would then look like this as ciphertext:

"JUHLIW LP PRUJHQJUDXHQ DQ"

This is then divided into blocks of the same length, in order not to draw any conclusions about the

allow individual word lengths:

"JUHLI WLPPR UJHQJ UDXHQ DQ"

3.1.2 Variants

The classic Caesar encryption is still used today: The shift cipher known as ROT13 replaces each letter by thirteen places and was often used in earlier Usenets6 used. However, not to encrypt securely, but rather to disguise the text and thus force the reader to interact.

A variant of the classic Caesar encryption is, for example, the reverted Caesar encryption7, in which the shifted ciphertext alphabet is written in reverse order under the plaintext alphabet.

Figure not included in this excerpt

Tab. 2: Reverse Caesar encryption

3.2 Vigenère encryption

“Le Chiffre indéchiffrable” (Eng. “The indecipherable encryption”) The Vigenère encryption, named after the French diplomat Blaise de Vigenère (1523-1596), is exactly like the Caesar encryption (see 3.1 ) a symmetrical procedure, d. H. a message is both encrypted and decrypted with the same key.

It is based on the basic principle of Caesar encryption, but it is a polyalphabetic encryption, i.e. each letter is encrypted with a different Caesar cipher. This is intended to make the analysis of the frequency of letters and thus the possibility of breaking the cipher more difficult.

For a long time, this variant was also considered safe and "indecipherable"8. The opposite was only proven independently by Kasiski (see 3.3) and Friedman (see 3.4) more than 300 years later.

3.2.1 Principle

The essential security of Vigenère encryption lies in the length and complexity of the key. In order to encrypt a message, the Tabula Recta, known as the Vigenère square (see Appendix A.1), is required. In the tabula recta, all letters of the alphabet are shown in squares, shifting one letter further to the left per line. It was first mentioned in the work "POLYGRAPHIAE LIBRI SE" (German. SIX BOOKS ON POLYGRAPHY) by Benedictine Abbot Johannes Trithemius (1462-1516)9.

3.2.2 Example

Using the tabula recta, the plain text used in 3.1.1 is encrypted as follows. "HONEY" is chosen as the keyword. HONIGH ON IGHONIGHONIG HO Attacks at dawn NFRQLA WZ UUYURVMYOHMT HB It can be seen that a plain text letter is now (in most cases) not encoded after the same letter when it is repeated. In the example shown above, the "r" from "Greift" is z. B. encoded according to "O", which results in an "F". With the word “Dawn” the first “r” is encoded after “H”, which results in an encrypted “Y”.

A first repetition happens to show up with the “r” in the partial word “gray”. Here, too, “H” is used, which also results in a “Y”.

The Kasiski test described in the following section starts with precisely these “random” repetitions in order to break encrypted messages without knowledge of the keyword.

A Vigenère encryption is only considered unbreakable if

1. The key is at least as long as the text to be encrypted itself
2. and the key is distributed "randomly", so it should not make any sense (e.g. copied paragraphs from a book, etc.)

The following example has no repetitions in the keyword and fulfills the above

Conditions:

Figure not included in this excerpt

3.3 Cryptanalysis: Kasiski test

3.3.1 History

The basic idea of ​​the Kasiski test is based on the repetition of individual blocks of code.

The English mathematician Charles Babbage (1791-1871) discovered a similar method for deciphering the Viginère code as early as 1854, but never published it10. The procedure became known as the Kasiski test, named after the retired Prussian officer Friedrich Wilhelm Kasiski (1805-1881). He developed the method independently of Babbage and published it in 1863 in his book The Secret Scripts and the Art of Deciphering.

3.3.2 Basic principle

Under the premise that the cipher is encrypted according to Vigenère, the encrypted text is searched for repetitive character strings with a minimum length of three characters or more. The distance between them is then determined by counting up to the first letter of the second sequence in the first sequence, including the first letter11.

Once this has been done for all the sequences found, the individual values ​​are broken down into their prime factors, which means that equal factors can be determined relatively quickly. Outliers, i.e. coincidental matches, are not considered any further. Disadvantage of the Kasiski test: It is not possible to determine the exact key length of the cipher, rather you only get a multiple of the key length. For this reason, the Kasiski test is often used in combination with the Friedman test. Together they make a pretty accurate way to get the keyword12.

The analysis of a cipher is described as an example in Appendix B.1.

3.4 Cryptanalysis: Friedman test

The Friedman test, named after the well-known cryptologist William Frederick Friedman (1891-1969), takes a different approach: To decipher the encrypted text or to preserve the key length, one falls back on mathematical-statistical methods and a coincidence index, which Friedman in his 1922 published work "The index of coincidence and its applications in cryptography" describes.

3.4.1 Definition of the coincidence index

The coincidence index I (also IC or κ) is based on the question of the probability that any two letters taken from the text are the same. Let the length of the alphabet be 26 (Latin alphabet) and let n1 be the number of all occurring "a", n2 the number of all "b",. . ., as well as n26 all occurring "z"13.

The length n of a text is then defined as follows:

Figure not included in this excerpt

Furthermore, the total number of all letter pairs is through

the order does not matter. n1 × (n1 −1)

Figure not included in this excerpt

defined, where

For the letter pair a. . . a then applies, for example.

, where n1 is the number of possible

the first “a” and (n1 - 1) represent the possibilities to choose another “a”.

Across the entire alphabet, the following results for the total number of all identical letter pairs:

Figure not included in this excerpt

The assumption that two arbitrarily chosen letters are the same is calculated according to that of

Friedman defined the coincidence index as follows:

Figure not included in this excerpt

For the German language and an "average" text, the coincidence index is approx. 7.62% (κD ≈ 0.07619), in English it is approx. 6.6% (κE ≈ 0.06577)14.

In the case of randomly distributed texts, approximately 3.85% is obtained by solving equation 3.3 (see Appendix B.2).

3.4.2 Determining the key length of a Vigenére text

Assuming that it is a German Vigenère cipher and that I is less than 0.0762 (if I = 0.0762, the text would obviously be encoded in mono-alphabet), the encoded text is now broken down into individual columns ( see Appendix B.2.2). Each column forms a monoalphabetic cipher.

Let n be the length of the text and l the keyword length, the following formula results for the approximate calculation of l (derivation see Appendix B.2.3):

Figure not included in this excerpt

4 Modern cryptography

4.1 RSA cryptosystem

RSA encryption, a public-key cryptosystem, is an asymmetric method, i.e. H. it is based on the use of key pairs, which consists on the one hand of a secret or private key and on the other hand of a public key15.

You encrypt with the publicly available public key, but the message can only be decrypted with the secret private key (see Appendix C).

4.1.1 Historical

The principle of RSA encryption was developed in 1977 by Ronald L. Rivest, Adi Shamir and Leonard M. Adleman at the Massachusetts Institute of Technology (MIT). Your considerations were based on the theory of public key cryptography16 by Whitfield Diffie and Martin Hellman.

4.1.2 Security Effectiveness

The effectiveness of public key cryptosystems, and thus also that of RSA, is based, among other things, on mathematical problems of being able to carry out calculations relatively easily in one direction, but not vice versa17.

This applies e.g. B. for the multiplication of prime numbers, the product of which can usually be calculated easily, but the decomposition of the product into prime factors is no longer possible with very large prime numbers. In other words, no adequate algorithm is known to date that can accomplish this in a reasonable time.

4.1.3 Algorithm and Example

Suppose Bob wants Alice18 transmit a message sent by Eve19 should not be deciphered, it should intercept them.

The functionality of the RSA method can now be explained using the following example20:

1. First Alice has to choose two very large prime numbers. To simplify the representation, it is assumed that p = 17 and q = 11.

2. Now these two prime numbers have to be multiplied to get the required n:

Figure not included in this excerpt

3. Next, an e has to be found that uses coprime as a condition

ϕ (n) has, d. H.

Figure not included in this excerpt

Let ϕ (n) = (p - 1) (q - 1) = (17 - 1) (11 - 1) = 16 × 10 = 160, then z. B. e = 3, which means that both of these conditions are met21.

4. e and n represent the public key. Depending on e

and ϕ (n) the private key d is now calculated as follows

Figure not included in this excerpt

Let e ​​= 3 ∧ ϕ (187) = 160, then for d = 107.

5. The required boundary conditions are met and Bob can now use Alice's public key to transmit a message in encrypted form as follows:

Figure not included in this excerpt

The message is numerically encoded, i. H. the ASCII value is used for each letter or character:

Figure not included in this excerpt

F or the numerical coding 06 is now encrypted.

21 It would have, inter alia. any other prime number for which 1

The condition m1

Figure not included in this excerpt

Bob gets c1 = 29 and does the same with the rest of the message. He then transmits the result to Alice.

6. Alice, for her part, can now decrypt the received message as follows:

Figure not included in this excerpt

It also proceeds with the remaining part of the message (m2, m3, · · ·, mn) in the same way as for m1 and at the end receives the decrypted message.

Since exponents are one-way functions in modular arithmetic, Eve can use the under

Do not decrypt an intercepted encrypted message under certain circumstances. As things stand today, it is very difficult or even impossible to infer the original m1 = 6 from c1 = 29.

5 authentication

5.1 Zero knowledge

The basic idea of ​​the zero-knowledge process is based on the paradigm of not disclosing the secret used, but merely showing the other party that you are in possession of it. It is only used for clear identification.

5.1.1 The secret door

Jean-Jacques Quisquater describes in "HOW TO EXPLAIN ZERO-KNOWLEDGE PROTOCOLS TO YOUR CHILDREN"22 the functionality of Zero Knowledge is quite clear.

In the following, Peggy would like to Victor23 prove she has the secret to go through the secret door in the cave. The secret itself should not be mentioned.

Rather, Peggy takes one of the two gears, whereby Victor cannot see whether she is choosing the left or the right gear (see Appendix D). As soon as she has reached the other side, Victor tells her which corridor to use to come back. Peggy can be lucky and “randomly” choose the exact corridor through which Victor calls her back.

In the first run, the probability of this is 50%.

For this reason, the procedure is repeated n times. With every run where Peggy comes back out of the right aisle, the likelihood that she actually has the secret to open the door increases, even if it is not actual evidence (e.g. a third party could claim that the two had agreed beforehand for all attempts).

Let n be the number of iterations in which Victor calls Peggy back through a corridor, then the probability is that Peggy will do 100 repetitions24 Is lucky and can deceive Victor:

Figure not included in this excerpt

5.1.2 Fiat Shamir Protocol

Historical

The Fiat-Shamir protocol is certainly one of the best-known algorithms of the zero-knowledge process. In 1986, together with Amos Fiat, Adi Shamir designed the first practical approach to the zero-knowledge process. A year earlier, the American computer scientists Shafrira "Shafi" Goldwasser, Silvio Micali and Charles Rackoff had provided the theoretical basis for this in their treatise "TH E KN OW L E D G E CO M P L E X I T Y O F I N T E R AC T I V E PRO O F - SYSTEMS"25.

The Fiat-Shamir Protocol is fundamentally based on the difficulty of computing square roots modulo n when the factorization of n is unknown26.

Algorithm and example

Suppose Peggy wants to authenticate herself to Victor without having to divulge the actual agreed secret. The Fiat Shamir Protocol defines the following

Method:

1. Peggy lets Trent first27 issue an n, which is defined as the product of p and q. As with the RSA method, both factors are very large prime numbers.

Figure not included in this excerpt

For a simplified representation, let p = 17 and q = 11.

2. Now she has to choose a secret s ∈ N prime to n that only she knows.

3. Using s and n, she now calculates v, where s = 69:

Figure not included in this excerpt

She deposited the created v with Trent.

4. In the following Peggy chooses a random number r = 34 and calculates x, which she transmits to Victor:

Figure not included in this excerpt

5. Victor for his part now chooses a random bit e ∈ {0, 1}, which he sends back to Peggy. Let e ​​= 1.

6. Now Peggy has to calculate a value again, namely y, which is then sent again to Victor.

Figure not included in this excerpt

7. Victor can now verify Peggy using her public key v, which he received from Trent. To do this, he calculates:

Figure not included in this excerpt

So Peggy was successfully verified.

The procedure can be repeated as often as required. With every successful run n, Peggy's credibility of actually being in possession of the secret increases with Victor. Assuming n is 10 for the sake of simplicity, Victor is already 99.9% certain that Peggy is credible:

Figure not included in this excerpt

[...]



1 Quoted in: Singh (2006), p. 27

2 See Hansen et al. (2009), p. 392

3 See Tranquillus, chapter 56, verse 6

4 See Hebisch (2010b)

5 The classic Roman alphabet consists of 23 letters, so there were 22 shifting options. See Hebisch (2010)

6 See Schneier (1996), p. 11

7 See Hebisch (2010b)

8 See Beutelspacher (2002), p. 31 f.

9 See Hebisch (2010a)

10 See Singh (2006), p. 105 f.

11 See Ertel (2007), p. 38 f.

12 See Bronstein et al. (2008), p. 389 f.

13 See Ertel (2007), p. 42 f .; and Völler (2003), p. 80 ff.

14 See Bauer (2000), p. 326

15 See Hansen et al. (2009), p. 393 f.

16 DIFFIE, WHITFIELD AND HELLMANN, MARTIN: New directions in cryptography (1976)

17 See Zimmermann (1998), p. 111

18 The names Bob and Alice symbolize sender and receiver in literature.

19 Eve (from the English eavesdropper, dt. Eavesdropper.) Is a passive attacker in the literature. She tries to listen to messages, but cannot change them

20 The example is based on the information provided by Singh (2006), p. 436 ff .; and Hansen et al. (2009), p. 394

21 It would have, inter alia. for e any other prime number can be chosen for which 1 [figure not included in this reading sample] applies.

22 See Quisquater et al. (1989), p. 628 ff.

23 Peggy: from engl. prover, stands for the prover; Victor: from the engl. verifier, stands for the verifier

24 See Ertel (2007), p. 105

25 See Beutelspacher (2002), p. 91

26 See Fiat et al. (1987), p. 187

27 From the Engl. TRusted ENTity stands for a third, trustworthy entity such as a notary

End of the reading sample from 34 pages