Day 04- Cryptography Acknowledgements to Dr. Ola Flygt of Växjö University, Sweden for providing the original slides
2
Conventional Encryption Principles An encryption scheme has five ingredients: Plaintext Encryption algorithm Secret Key Ciphertext Decryption algorithm
3
Conventional Encryption Principles
4
Requirements for Security Strong encryption algorithm Even if known, should not be able to decrypt or work out key Even if a number of cipher texts are available together with plain texts of them Sender and receiver must obtain secret key securely Once key is known, all communication using this key is readable
5
Cryptography Classified along three independent dimensions: The type of operations used for transforming plaintext to ciphertext The number of keys used symmetric (single key) asymmetric (two-keys, or public-key encryption) The way in which the plaintext is processed
6
Average time required for exhaustive key search Key Size (bits) Number of Alternative Keys Time required at 106 Decryption/µs 32 232 = 4.3 x 109 2.15 milliseconds 56 256 = 7.2 x 1016 10 hours 128 2128 = 3.4 x 1038 5.4 x 1018 years 168 2168 = 3.7 x 1050 5.9 x 1030 years
7
Classical Encryption Techniques Substitution Techniques : plaintext are replaced by other letters or by numbers or symbols Caesar Cipher Monoalphabetic Cipher Polyalphabetic Cipher Transposition Techniques : some sort of permutation on the plaintext letters
8
Caesar Cipher Replacing each other letter of the alphabet with the letter standing three places further down - plain : meet me after the toga party - cipher : PHHW PH DIWHU WKH WRJD SDUWB Note that the alphabet is wrapped around, so that the letter following Z is A. - plain : abcdefghijklmnopqrstuvwxyz - cipher : DEFGHIJKLMNOPQRSTUVWXYZABC If we assign a numerical equivalent to each letter(a=1, b=2 etc) - C = E(p) = (p+3) mod (26) - P = D(c) = (c–3) mod (26)
9
Crypto analysis of the Caesar Cipher brute-force cryptanalysis Three important characteristic of this problem: The encryption/decryption algorithm are known There are very few keys to try The language of the plaintext is known and easily recognized
10
Monoalphabetic Cipher Cipher line can be any permutation of the 26 alphabetic characters If an enemy agent could check one of these possible keys every second, it would take roughly one billion times the lifetime of the universe to check all of them and find the correct one.This simple brute force approach clearly will not work. http://www.simonsingh.net/The_Black_Chamber/generalsubstitutionWithMenu.html
11
Crypto analysis of the Monoalphabetic Cipher Attack : regularities of the language
12
Polyalphabetic Cipher Instead of having one key (table) that is used to encrypt each block of plaintext, we use several different keys. The Vigenère cipher is the classical example. http://www.simonsingh.net/The_Black_Chamber/Swapping_Cipher_Alphabets.html
Vignere cipher
To produce an unbreakable Vignere cipher, you must: Choose a key that is as long as the plaintext message(Vernam cipher). Build the key from random characters. Never use the key again. Don't use text decorations (spaces, punctuations, capitalization). Protect the key 13
Unfortunately, these steps take all the fun out of the Vigenere cipher. Most people use English words or phrases for the key (violating step 2) that are significantly shorter than the message being coded (violating step 1). Then they use the same key to encrypt additional messages (violating step 3) because they don't want to remember a new key for each message. Some people use quotations from their favorite book for the key or invent one and write it down (violating step 5). Lastly, it's no fun to handle text that doesn't look like text, so they don't remove the decorations (violating step 4). The moral of the story is that security is free, but it requires effort. http://sharkysoft.com/misc/vigenere/ ‹#›
Example: Vernam cipher
14 Figure 2-3 Vernam Cipher
Example: Vernam cipher
15
16
17
One time pad Messages n-bit strings [b1,…,bn] Keys Random n-bit strings [k1,…,kn] Encryption/Decryption c = E(b, k) = b k = [b1 k1, …, bn kn] denotes exclusive or b = D(b, k) = c k = b k k = b [1, …, 1] = b
18
One time pad (cont.) Properties Provably unbreakable if used properly Keys must be truly random Must not be used more than once Key same size as message
One-time pad
Book ciphers Use the text of a book, piece of music as key Key should be known to both parties Vignere table can be used for encryption 19
20
Transposition ciphers An alternative to substitution ciphers Instead of changing the coding of the characters (blocks) in the plaintext, we rearrange the text. The effect is that the cipher text and the plaintext contains the same symbols.
Comments