Cryptography Lecture Notes PDF

Preview

Summary

Cryptography ...

Description

Cryptography (G1032 and 860G1) Lecture Notes Dr Konstantin Blyuss Office: 5c9 Pev III. Email: [email protected]

1

Introduction to Cryptography

Cryptography has a long and fascinating history, starting with the Egyptians some 4000 years ago, all the way up into the twentieth century where it played a crucial role in the outcome of both world wars. The predominant practitioners of the art have been those associated with the military, the diplomatic service and government in general. Cryptography was used as a tool to protect national secrets and strategies. Cryptography (from Greek: κρυπτ oς, ”hidden, secret”; and γραφεiν, ”writing”) literally means encryption (’secret writing’), but modern cryptography involves much more than just encrypting written messages. In fact, it is used in many aspects of our everyday lives, from credit cards and TV remotes to email, internet Bearing in mind a wide range of possible application areas, there are several possible definitions of cryptography. A useful and insightful definition of Cryptography can be found in the Handbook of Applied Cryptography: Cryptography is the study of mathematical techniques related to aspects of information security. On the one hand, this definition means that cryptography is a part of mathematics (in particular, algebra and number theory). On the other hand, it highlights the importance of information security. Over the centuries, security of information was mainly achieved through physical or legal means, but with the majority of information now being transmitted and processed electronically, a new set of tools and methods is required. It is important to remember that in practice besides cryptography there are may other aspects that have to be taken into account, such as procedural measures, abidance by laws, good practical implementation, physical security mechanisms etc. Let us now consider the relevant aspects of information security that pertain to both paper and electronic information security. 1. Confidentiality is responsible for ensuring that the content of information is kept secret from anyone who is not authorized to have access to it. There are two ways how confidentiality can be achieved. The first one is a physical protection mechanism. In this case, the message is physically protected from being intercepted, an example being courier mail. Another way of achieving confidentiality is by using cryptographic encryption mechanisms. In this case, even if an unauthorized party intercepts a message, they would be unable to decrypt it, and therefore the message would be secure. 2. Data integrity addresses the issue of unauthorized alteration or manipulation of data. In particular, it concerns with preventing and identifying instance of data insertion, deletion and substitution. 3. Authentication relates to identification, both with regards to authenticating entities involved in information exchange and also with respect to information itself. The two parties exchanging information should be able to identify each other (entity authentication). An example is a user 1

seeking access to a computer network; in this case the server should be able to authenticate the user prior to granting them access to the internet. Common techniques for proving entity authentication are PINs, passwords etc. Another aspect of authentication is that it should be possible to authenticate the information being transmitted in terms of its origin, date of origin, data content, time sent etc. Data origin authentication applies to data that is sent over a communication channel. In this case, the receiver needs to authenticate that the data has actually come from the sender. In order to guarantee data origin authentication, one must also have data integrity, as if the information has actually come from the sender, then it cannot have been altered in transit. At the same time, data integrity does not imply data origin authentication. 4. Non-repudiation prevents an entity from denying a previous action or commitment. When a party denies that certain actions were taken, usually a procedure involving a trusted third part is needed to resolve the dispute. In order to illustrate how these different aspects on information security come into play, we consider the following example. Example. Alice wants to buy something over the internet from Bob. Alice send her credit card number and payment details over the internet (unsecured channel) to Bob.

Alice is the sender, Bob is the receiver, and Eve is the attacker or adversary. When discussing the exchange of information between two or more parties, we use the following concepts.

Channel: a means of conveying information from one party to another. Channels can refer both to physical and electronic means of information exchange.

Unsecured channel: a channel, from which an attacker can read, re-order, delete or insert data. Secured channel: a channel, from which an attacker cannot read, re-order, delete or insert data. A secured channel is physically or cryptographically protected. Let us consider how different aspects of information security can be interpreted within this example. First of all, consider confidentiality: Alice requires her instruction to be confidential, so that no other person would know her credit card details or what she is buying. Both Alice and Bob require that the integrity of the message is preserved, so that the amount of transaction would not be altered in transit. Bob requires data origin authentication, so that he would know the instruction has actually come from Alice, and not from an impostor. Bob is also interested in non-repudiation, so that Alice would not be able to deny that she had sent an instruction to Bob and therefore refuse payment.

2

Cryptography provides mathematical techniques to address the four objectives of information security. These mathematical techniques or cryptographic tools are sometimes called cryptographic primitives. We will be primarily concerned with the following examples of cryptographic primitives: Encryption algorithms (e.g. AES, RSA) can provide confidentiality. Signature algorithms (e.g. DSA, RSA, ElGamal) can provide data origin authentication, data integrity and non-repudiation. Hash functions (e.g. SHA-1, SHA-256, MD5) can provide data integrity. Message Authentication Codes (MACs) can provide data integrity and data origin authentication. Cryptography is the study of mathematical techniques related to aspects of information security. Cryptanalysis is the study of mathematical techniques attempting to defeat cryptographic tools. Finally, Cryptology is the study of both cryptography and cryptanalysis.

2

Classical cryptography

Up until about forty years ago, most information was stored and transmitted on paper. However, nowadays most information is stored and transmitted electronically. The change from paper to electronic data has had a profound effect on cryptography. Before the digital age, the function of cryptography was simply to provide data confidentiality using encryption algorithms. Data integrity was achieved by physically safeguarding paper documents. It is noteworthy that it is much harder to alter a paper document that an electronic file. Similarly, authentication and nonrepudiation were usually provided by hand-written signatures, not by cryptography. Since it is much easier to copy and alter digital data than data that is written on paper, new techniques were required for protecting digital data. Therefore, cryptographic techniques for providing data integrity, authentication and non-repudiation are comparatively recent. This means that all historic examples of cryptography are encryption algorithms. Lysander of Sparta (404 BC) used the ’Skytale’, a simple encryption device in a war against Athenians. Indirect evidence from Archilocus (≈ 7th century BC) suggests it existed even earlier, but first clear description come from Plutarch (50-120 AD). This is the first recorded military use for a cryptographic device.

The Skytale is an example of a simple transposition cipher or permutation cipher. In such ciphers, the symbols stay the same and just get permuted.

3

A Transposition cipher splits up the plaintext message M into blocks of fixed length t called the period or order of the cipher. There is a permutation P of the t positions, which is called the ’encryption key’. There are t! possible keys. Decryption is the inverse permutation P −1 . For the example of Skytale, the period of cipher is the diameter of the cylinder. Example. Take the period of the cipher to be t = 5.Choose the message to be M = UNIVE|RSITY| OF S|USSEX Choose the key to be P = (134)(25) in cycle notation: -

Position Position Position Position Position

1 3 4 2 5

goes goes goes goes goes

to to to to to

position position position position position

3 4 1 5 2

We work on each 5-letter block independently and transpose the characters according to the rules specified in P . Then the ciphertext C is C=VEUIN|TYRIS| S FO|EXUSS Decryption is given by the inverse permutation P −1 = (143)(25). Since the symbols in the transposition ciphers remain the same and only their order changes, transposition ciphers are easy to recognize and cryptanalyse. In particular, if an attacker has some plaintext corresponding to ciphertext, it is very easy to find the permutation. This is called a known-plaintext attack. Caesar cipher (believed to be used by Julius Caesar) works by shifting the alphabet by a certain number of places, e.g. shifting by 3 places gives this table ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC

Then we substitute using the table. For example, the plaintext DOG gives the ciphertext GRJ. Another way to think of this cipher is to assign a number to each letter in the alphabet. A=0, B=1, C=2, D=3, ..., Y=24, Z=25. Then a shift of 3 places corresponds to ’adding’ D to every letter. Here, D is the ’key’ - this is the shift that tells both parties how the alphabet has to be modified for encryption/decryption. To encrypt BOY using D=3 as the key, we proceed as follows: B+D=1+3=4=E O+D=14+3=17=R Y+D=24+3=27=1 (mod 26) = B So, BOY encrypts to ERB. 4

Caesar cipher is an example of a simple substitution cipher or a mono-alphabetic substitution cipher. The key for a mono-alphabetic substitution cipher is a permutation of the letters of the alphabet. So, there are 26! keys (≈ 4 · 1026 ), using English alphabet (without a ’space’ character). For an alphabet with q symbols, there will be q! keys. With a mono-alphabetic cipher, each letter of the alphabet always gets encrypted in the same way. This means that this type of cipher is very easy to cryptanalyse using frequency analysis, and hence an attacker will be able to find the permutation key by analysing quite a small amount of ciphertext. A more sophisticated type of substitution cipher is the so-called Vigen` ere cipher. It was originally described by Giovan Battista Bellaso in 1553, but was later misattributed to Blaise de Vigen`ere in the 19th century. Historically, it was known as the chiffre ind´ echiffrable (undecipherable cipher) for centuries until it was cracked by Charles Babbage in 1854, in a more general form by Kasiski in 1863. Vigen`ere cipher is actually a generalization of the Caesar cipher. The key of the Vigen`ere cipher is a repeated block of letters of length t (for Caesar cipher, t = 1). The cipher works by splitting the plaintext into blocks of length t and then adding the key to each block individually. For example, let us choose CBK for the key (so the period is 3). Then we encrypt the word AUTOMATIC as CVDQNKVJM, as shown below AUT CBK CVD

OMA CBK QNK

TIC CBK VJM

since A+C=0+2=2=C, etc. This is a poly-alphabetic substitution cipher. It has an advantage that symbol frequencies are not preserved.

5

Despite the fact that the Vigen`ere cipher was not broken for 300 years, it is actually quite easy to cryptanalyse and recover the key that has been used. The first step is to determine the period t, which is done by trial and error. Once the block length is known, the letters in the ciphertext can be divided into t grous, and then frequency analysis can be performed on each group. An improvement on a Vigen`ere cipher is a one-time pad, invented by Gilbert Vernam in 1917. It provides perfect secrecy as it is theoretically unbreakable. For this reason, it has been used by military, diplomats and politicians across the globe for much of the 20th century. The one-time pad itself is a random sequence of letters (or bits). The main aspect of this approach is that the pad is the same length as the plaintext.

Because the one-time pad is random, it is impossible to recover the plaintext from the ciphertext, as every plaintext is equally likely. Using bits instead of letters, the one-time pad looks like this

The encryption and decryption work like this: p i ⊕ ki = c i ,

c i ⊕ ki = p i ,

for i ≥ 0. Here, ⊕ it the logical XOR operation working as follows 0⊕0=0 1⊕0=1 0⊕1=1 1⊕1=0 The one-time pad offers unconditional security or perfect secrecy since observation of the ciphertext provides no information whatsoever about the plaintext or the one-time pad to the adversary. The question is then: why don’t we always use a one-time pad?

6

Despite its theoretical superiority, there are several problems with practical implementation of one-time pads. First of all, each time it has to be as long as the plaintext message, which may all be of different lengths. The sender should be able to somehow physically transport the pad to the receiver. Another implementation issue is how to generate a truly random pad. Finally, to ensure unbreakability every pad should be used only once, and it should never be used to encrypt two different plaintext messages.

3

Symmetric-key encryption

In the examples considered above, in each case Alice uses a key to encrypt her plaintext messages. So far, we have seen the following examples of keys: a permutation of the positions of the plaintext characters (transposition ciphers), a permutation of characters in the alphabet (simple substitution ciphers), one-time pads. In all of the encryption algorithms that we shall consider from now on, a key will simply be a very large integer number. Since encryption algorithms are implemented on computers, we usually think of a key as a long string of bits. The idea is that the key is so large that it is not feasible for an attacker to guess what this key is. The range of all possible values of the key is called a keyspace. In order to encrypt the plaintext message M , Alice uses a key K. The result is the ciphertext message C. We write EK(M ) = C. For decryption of the ciphertext C, Bob uses the same key K as follows: DK(C) = M.

This is called symmetric-key encryption or single key encryption. The main feature of this scheme is that the same key is used both for encryption, and for decryption. This is different to asymmetric-key encryption (e.g. RSA), which uses different keys for encryption and decryption. The security of symmetric-key encryption relies on the so-called Kerckhoffs’ assumption: security of en encryption algorithm is provided by keeping the key secret, not by keeping the algorithm secret. In fact, the majority of encryption algorithms are publicly available, so everyone knows the details of how those algorithms work. There are some secret algorithms, but one cannot rely on keeping the algorithm secret to provide security. There are two types of symmetric-key encryption algorithms: stream ciphers (RC4, SEAL, etc.) and block ciphers (DES, Triple-DES, AES, etc.). 7

4

Stream ciphers

Stream ciphers operate on the plaintext a single bit (or byte, or symbol) at a time. We shall consider binary stream ciphers in this section (i.e. they work on bits of plaintext), but the same general principles apply to non-binary case. The plaintext is combined with a keystream to produce the ciphertext. Motivation for stream ciphers is a one-time pad we discussed earlier.

With a stream cipher, the sender and receiver generate the same keystream of ’random bits’ ki .

We no longer have perfect security, since the keystream is generated from a short key. The two related observations are: the keystream is no longer truly statistically random, and the entropy (randomness) of the keystream cannot exceed the entropy of the short key. There are two types of stream ciphers: synchronous stream ciphers and self-synchronizing (or aysnchronous) strea, ciphers. In the case of synchronous stream cipher, the keystream is generated as a function of the key only and completely independent of the plaintext and the ciphertext. In contrast, for the self-synchronizing stream cipher, the keystream is generate as a function of the key and a fixed number t of the previous ciphertext bits. The synchronous stream cipher works as follows

This is a ’binary additive cipher, which operates like this: Encrypt: pi ⊕ ki = ci . Decrypt: ci ⊕ ki = pi ⊕ ki ⊕ ki = pi .

8

Properties of a synchronous stream cipher: • Sender and receiver must be synchronized. To give a proper decryption, the keystream generators for the sender and receiver must be in the same state. If some part of ciphertext is lost or inserted during the transmission, then the decryption will fail. • There is no error propagation, i.e. even if a single bit is corrupted, this has no bearing on the correct decryption of subsequent bits. • Such ciphers are vulnerable to ’bit-toggling’ or ’bit-flipping’. An attacker can change ciphertext bits and, thereby, alter the encrypted plaintext. An alternative is given a self-synchronizing cipher.

Properties of a self-synchronizing stream cipher: • Self-synchronisation is possible if ciphertext bits are deleted or inserted. Decryption depends on a fixed number of preceding ciphertext bits, so the cipher can recover even after deletion/insertion of bits. • Limited error propagation. Since the state of the keystream generator depends on t preceding ciphertext bits, if a single ciphertext bit is modified in transmission, then t bits of decrypted data will be lost. For any stream cipher, it is essential that the keystream never gets re-used, i.e. keystream should only be used to encrypt one set of plaintext. Alternatively, one has to change the key before the keystream starts to repeat itself (if keystreams are periodic). The reason for this is the following: if the keystream repeats itself, one has ki+h = kj+h for all h ≥ 0. By XOR-ing the corresponding ciphertext, we find ci+h ⊕ cj+h = pi+h ⊕ ki+h ⊕ pj+h ⊕ kj+h = pi+h ⊕ pj+h .

Therefore, by XOR-ing two sections of ciphertext, we obtain the XOR of two sections of plaintext. From this it is then possible to recover both section of plaintext. This is one reason why keystream generators are required to have a long period. If a generator has a short period, then one has to update the key more frequently. 9

5

Linear feedback shift registers

For symmetric-key encryption, keystream generators produce a sequence of bits that appears ’random’. The actual entropy of the keystream comes from a short key. A basic building block of many keystream generators is the so-called Linear Feedback Shift Register (LFSR). Linear Feedback Shift Registers are useful and convenient for the following reasons: • they are well-suited to hardware implementation; • they can produce sequences that have a long period; • they can produce sequences that have good statistical properties. An LFSR of length L consists of 1) L registers R0 , R1 ,..., RL−1 in a row. Each register stores a single bit. 2) a clock to control the movement of data 3) the initial state [sL−1 , ..., s1 , s0 ], wheresi ∈ {0, 1} denotes the bit in Ri .

During each unit of time the following sequence of operations is performed: • t...