Report

Computer Security Set of slides 4 Dr Alexei Vernitski Public-key cipher • We consider a scenario when Alice wants to send a confidential message to Bob • Alice and Bob use two different keys • Alice’s key is the public key: it is publicly known • Bob’s key is the private key: only Bob knows it • Also called asymmetric cipher Public-key cryptography • Public-key cryptography is called public-key cryptography because it uses two types of keys: – Public keys, which are known to everyone and used to encrypt messages – Private keys, which are known only to the person who has received the message and wants to decrypt it. Public-key cryptography • Suppose Bob wants other people to send messages to him confidentially • He chooses (but does not tell anyone) a private key. This is the key he shall use for decrypting messages arriving to him. • At the same time, he chooses and published a public key. This is the key other people will use to encrypt messages to send them to Bob. Keys and blocks • In ciphers like DES, keys are just arrays of bits. • In public-key cryptography, keys are parameters of some complicated calculations, and they are not necessarily arrays of bits. • In ciphers like DES, a message is treated as a long array of bits, and is split in blocks. • In public-key cryptography, blocks are not necessarily arrays of bits. RSA • RSA is a public-key cipher invented in the 1970s. • It is still considered secure and is used in many applications Modular arithmetic • This example is modulo 7 • The numbers allowed are 0 to 6 • After 6, numbers “wrap around” • 0 = 7 (mod 7) • 3+3 = 6 (mod 7) 4+4 = 1 (mod 7) 0 6 1 5 2 4 3 Mock RSA • This is a simplified version of RSA • Bob finds three numbers e, d, n such that ed = 1 (mod n) • e is for encryption, d is for decryption • For example, e = 2, d = 3, n = 5 • Each block m in a message is a number between 0 and n-1 Mock RSA • • • • For example, e = 2, d = 3, n = 5 m is a number between 0 and n-1 To encrypt, calculate c = em modulo n To decrypt, calculate dc = dem = 1m = m modulo n • Alice’s (public) key is the pair e and n • Bob’s (private) key is the pair d and n • Both keys are prepared by Bob RSA • • • • For example, e = 3, d = 7, n = 33 m is a number between 0 and n-1 To encrypt, calculate c = me modulo n To decrypt, calculate cd = med = m1 = m modulo n • Alice’s (public) key is the pair e and n • Bob’s (private) key is the pair d and n • Both keys are prepared by Bob • Now say we want to encrypt the message m = 7 • c = me (mod n) = 73 (mod 33) = 343 (mod 33) = 13. • Hence the ciphertext c = 13. • To decrypt, we compute m = cd (mod n) = 137 (mod 33) = 7. RSA • RSA is secure because it is difficult to find d when n and e are known • Of course, n, e and d should be larger than in our example (say, 21000) Large integers • We need to perform arithmetic with large integers, say, numbers occupying 1000 bits in memory. • Is the standard implementation of integer suitable for this? Raising into large powers • We need to raise into large powers • For the sake of an example, we can say that we need to calculate m100 • How can we do this efficiently? – Using the modular arithmetic – Re-using smaller powers, where possible Encoding data • Blocks of RSA have an exotic format • How do you prepare data for being encrypted by RSA? • Homework: where can you find the standard describing the recommended scheme for data encryption and decryption with RSA? Using RSA with other ciphers • How can RSA and, say, AES work together as parts of a cryptographic protocol of a software system? • We want to use the best of each of them RSA – Problem 1 Recall how the RSA works: • The public key is a pair e and n • Bob’s private key is a pair d and n • To encrypt, calculate c = me (mod n) • To decrypt, calculate cd = med = m1 = m (mod n) Problem 1: • Bob has published the public key e = 7, n = 247. • Use this public key to encrypt a message m = 100. RSA – Problem 2 • Recall how the RSA works: • The public key is a pair e and n • Bob’s private key is a pair d and n • To encrypt, calculate c = me (mod n) • To decrypt, calculate cd = med = m1 = m (mod n) Problem 2: • Bob has published the public key e = 317, n = 851. • Alice has encrypted a message m = 111 using this key and obtained an encrypted message c = 148. • Use this information to find the private key. Stream ciphers • What is the simplest implementation of a cipher based on a key stream? • What is the difference between a one-time pad cipher and a stream cipher? • What are the ways of obtaining a random key stream for a one-time pad cipher? • What are the ways of obtaining a pseudorandom key stream for a stream cipher? Linear feedback shift register XOR • At each step, each bit is shifted by one position to the right • The new value of the leftmost bit is calculated as an XOR of the bits that stood at so-called tap positions Linear feedback shift register • For example, populate the register as follows: 00010110011010111 • Use the rightmost bit (1) as the first bit of the key stream • Find the bits in the tap positions and XOR their values: 00010110011010111 • Shift the register: ?0001011001101011 • Provide a new value for the leftmost bit (as the XOR of the bits that were in tap positions): 00001011001101011 Linear feedback shift register • LFSRs can be used to produce a pseudorandom key stream • The length of the register and the choice of the tap positions are important • If they are chosen correctly, the LFSR will get back to its original value only after it has taken all other possible values • Such an LFSR is called maximum-length Sample exam questions • Explain the difference between symmetric and asymmetric ciphers. • What are the relative advantages of each of these types of cipher? • Give an example of a public key cipher • Show exactly (with formulas) how a message is encrypted and decrypted in RSA Sample exam questions • Explain the difference between block ciphers and stream ciphers • Compare one-time pad ciphers and stream ciphers. What are the relative advantages of each of these types of cipher? • Explain briefly how a pseudorandom key stream can be produced for a stream cipher