-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-= -= A History of Cryptography =- -= By SigningiS =- -= signingis@hotmail.com =- -= http://www.2600slc.org =- -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Simple Ciphers Secrets are as old as language itself. In the effort to keep information secret, various methods have been used: codewords, secret meetings, messengers and ciphers. Ciphers ended up being the most widely used. The true meaning of codewords can be inferred from the context of the message. Meetings can be infiltrated. Messengers can be bribed or tortured, thus divulging their message. Only the ciphered message, given to an individual with no actual knowledge of what it contained, was to be considered beyond betrayal. But to have a good code, the method used to extract the information must be agreed upon. If this isn't the case, the recipient is no better of for having the message because he can't understand it. During this presentation, I'll show a few methods of encryption and give some background on them. The Caesar Cipher or substitution cipher is considered to be one of the first successful methods of encryption. The method for encrypting a message via the Caesar Cipher was to write out the alphabet twice, staggering the second line by the desired number of letters. In this case, seven letters. -------------------------------------------------------------------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z G H I J K L M N O P Q R S T U V W X Y Z A B C D E F -------------------------------------------------------------------- To encrypt "The quick brown fox jumps over the lazy dog." you would find the letters that make up that message in the first line and write down the corresponding letter from the second row, producing "ZNK WAOIQ HXUCT LUD PASVY UBKX ZNK RGFE JUM". This is a pretty straightforward method of encrypting a message. Relatively quick and easy. Unfortunately, it isn't perfect. It's susceptible to analysis of how often particular letters appear as well as analysis of when certain letters pair with other letters and what configurations they make. There are certain ratios and combinations that are glaring when dealing with a monoalphabetic cipher. Letter pairs such as "nn" in "skinny" or "tt" in "little" are examples. Vowel-consonant pairs are another. The encrypted result could also be fitted into blocks of characters to prevent any information about the length of words from being divined. This would make our previous result "ZNKWA OIQHX UCTLU DPASV YUBKX ZNKRG FEJUM". Another cipher with roots in this method is the Vignere Cipher. Blaise de Vigenere finalized this method in 1562. Vigenere studied the works of Leon Battista Alberti, Johannes Trimethemius and Giovanni Porta while in Rome on a two-year diplomatic mission in 1549 at the age of 26. When he was 39 he retired and began to study the work of his predecessors in detail. During the 1460's, while walking through the gardens of the Vatican, Leon Alberti had a casual conversation about cryptography with the pontifical secretary, Leonardo Dato. Cryptography was widely used by heads of state and had mostly been broken by frequency analysis. This meeting apparently got Alberti to consider a new possible method for encryption. Using more than one set of letters to encrypt the message which would hopefully confuse any cryptanaylsts. The message would use the two cipher alphabets alternately to encrypt the message. This would prevent telltale signs such as letter pairs. "Hello" would be enciphered to AFPAD instead of AIPPD, thus eliminating two letters being together in the ciphertext, thus eliminating any clues as to what those letters may be. Very few letters in the English language appear paired in words. ------------------------------------------------------------- Plaintext A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Cipher1 F Z B V K I X A Y M E P L S D H J O R G N Q C U T W Cipher2 G O X B F W T H Q I L A P Z J D E S V Y C R K U H N ------------------------------------------------------------- Though Alberti, Trimethemius and Porta all made contributions to the development of this method of encryption, it's known as the Vigenere to honor the man who put it into its final form. Its strength lies the use of not two or three cipher alphabets, but 26. They are arranged into a Vigenere square. Vigenere Square with keyword CODE highlighted A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 B C D E F G H I J K L M N O P Q R S T U V W X Y Z A *---------------------------------------------------* 2 |C D E F G H I J K L M N O P Q R S T U V W X Y Z A B| *---------------------------------------------------* 3 |D E F G H I J K L M N O P Q R S T U V W X Y Z A B C| *---------------------------------------------------* 4 |E F G H I J K L M N O P Q R S T U V W X Y Z A B C D| *---------------------------------------------------* 5 F G H I J K L M N O P Q R S T U V W X Y Z A B C D E 6 G H I J K L M N O P Q R S T U V W X Y Z A B C D E F 7 H I J K L M N O P Q R S T U V W X Y Z A B C D E F G 8 I J K L M N O P Q R S T U V W X Y Z A B C D E F G H 9 J K L M N O P Q R S T U V W X Y Z A B C D E F G H I 10 K L M N O P Q R S T U V W X Y Z A B C D E F G H I J 11 L M N O P Q R S T U V W X Y Z A B C D E F G H I J K 12 M N O P Q R S T U V W X Y Z A B C D E F G H I J K L 13 N O P Q R S T U V W X Y Z A B C D E F G H I J K L M *---------------------------------------------------* 14|O P Q R S T U V W X Y Z A B C D E F G H I J K L M N| *---------------------------------------------------* 15 P Q R S T U V W X Y Z A B C D E F G H I J K L M N O 16 Q R S T U V W X Y Z A B C D E F G H I J K L M N O P 17 R S T U V W X Y Z A B C D E F G H I J K L M N O P Q 18 S T U V W X Y Z A B C D E F G H I J K L M N O P Q R 19 T U V W X Y Z A B C D E F G H I J K L M N O P Q R S 20 U V W X Y Z A B C D E F G H I J K L M N O P Q R S T 21 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 22 W X Y Z A B C D E F G H I J K L M N O P Q R S T U V 23 X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 24 Y Z A B C D E F G H I J K L M N O P Q R S T U V W X 25 Z A B C D E F G H I J K L M N O P Q R S T U V W X Y 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z To use the Vigenere Cipher a keyword is chosen. Repeating letters in the keyword are eliminated, if there are any, and the encryption of the message cycles through the rows that correspond to the keyword until it had been completely enciphered. Thus, if the message "Hack the planet" were encrypted with the Vigenere Cipher using the keyword CODE the result would be "JOFOV VHTNO QIV". Also, note that the enciphered message could be padded with two extra letters at the end of this message to make it exactly three sets of five letters. Why? It just makes it look prettier. The person on the other end could discard the extraneous characters and make whatever use of the message that was intended. KEYWORD CODECODECODECOD MESSAGE HACKTHEPLANETXX CIPHERTEXT JOFOVVHTNOQIVKD To decipher the message, the codeword would be arranged on top of the ciphertext and each letter would be looked up in reverse. KEYWORD CODECODECODECOD CIPHERTEXT JOFOVVHTNOQIVKD MESSAGE HACKTHEPLANETXX In row C the letter J is found and H is the deciphered letter. In row O the letter O is found and A is the deciphered letter. In row D the letter F is found and C is the deciphered letter. In row E the letter O is found and K is the deciphered letter. In row C the letter V is found and T is the deciphered letter. This is pretty time consuming but it was a very secure process for the time. Unfortunately, for his efforts Venigere was accused of witchcraft and burned at the stake. Just kidding. Actually, no one wanted to use his cipher (which was almost as bad as being burned at the stake). It was too complex and time consuming for general use. And for that reason, it wasn't used for over two centuries after it was developed. Computers Enter the Game Computers got into the cryptography game almost as soon as they were invented. Given that computers only read information as binary data, a protocol for converting text to binary data and back was developed. One of those is ASCII. ASCII assigns a binary seven-digit binary digit to each letter of the alphabet as well as to other symbols. Once a message is in binary form, computer based encryption can be done. One method for encrypting could be done by swapping the bits that compose the individual letters. Swapping the first and second bits, the second and third bits and so on until the entire message had been changed into its encrypted form is one way. Message in ASCII 01001000 01000101 01001100 01001100 01001111 Encrypted Text 10000100 10001010 10001100 10001100 10001111 Another would be to mask the message against a key by "adding" the key to the message text: 0 and 1 yielding 1, 0 and 0 yielding 0 and 1 and 1 yielding 0. Message in ASCII 01001000 01000101 01001100 01001100 01001111 Key in ASCII 01000100 01000001 01010110 01001001 01000100 Encrypted Text 00001100 00000100 00011010 00000101 00001011 Doing the same process in reverse gives you the original message. Encrypted Text 00001100 00000100 00011010 00000101 00001011 Key in ASCII 01000100 01000001 01010110 01001001 01000100 Decrypted Message 01001000 01000101 01001100 01001100 01001111 In the early 70s, Horst Feistel developed an encryption program dubbed Lucifer. Lucifer encrypted messages by translating a message into its binary counterpart. That string is divided up into blocks of 64 digits and each of those blocks are encrypted. Encryption happens in the following manner. The 64-digit block is mangled according to the algorithm and then split into two blocks of 32 digits, called Left0 and Right0 respectively. Right0 is then "mangled" and the value of Left0 is added to it and it is relabeled as Right1. The old value of Right0 is renamed to Left1 and the process is repeated. Right1 is "mangled" and the value of Left1 is added to it and it is relabeled as Right2. The old value of Right1 is renamed to Left2. This occurs 16 times. The recipient decrypts it by reversing the process. The exact function of the encryption engine can change and is dependent on the key. A different key will yield different results from the same original data. They keys used are just numbers. The sender and receiver agree on what number is to be used and use that as their key. However the NSA stepped in at this point and made sure that Lucifer could only use a 56-bit key as opposed to a 128-bit key, which was being used during development. A 56-bit key would allow for 144,115,188,075,855,872 different keys to be used. A 128-bit key would allow for a whole hell of a lot more. Businesses adopted this system as a standard. It was labeled DES, for Data Encryption Standard. Distributing keys was a huge hurdle to these businesses. No on wanted to send the keys over the telephone line in case it was tapped at some point. The only other option was to physically deliver the keys via a courier. This turned out to be pretty expensive. A way around this had to be found. Key Distribution A way to distribute these keys was necessary. It was the proverbial catch-22. In order to send secret data (the encrypted message) you already had to have sent the key, which you wanted to keep a secret. How could you get it to the other person without having to meet somewhere, transmit it over insecure means (telephone), or use a third party courier? Whitfield Diffie and Marty Hellman discovered that traditional mathematics would not get them what they needed. They decided to try finding a solution based on a set of one way functions. A one way function being a function that was easy to calculate initially but drastically more difficult to reverse, essentially making it one way. An example of one way functions is modular arithmetic. If you've dealt with military time, you've used a one way function. 13:00 hours in civilian time is 1:00 pm. In this case 13=1 (mod 12). Just as when you know that you have a meeting in 5 hours and it's 10:00 am. Your meeting is at 3:00 pm. 10+5=3 (mod 12). This was the same sort of function Whit and Marty were looking for in order to solve their key distribution problem. There are an infinite number of equations that will equal 1 or 3 if it's based on mod 12. 10+5=3 (mod 12). 64+23=3 (mod 12). That ambiguity was the basis for their key distribution scheme. The equation for that system is YX (mod P). Pretty simple. Over the phone Kenny and Grifter can choose values for Y and P. They don't have to keep those values a secret. Individually they choose secret numbers for X. For the sake of simple math, say Grifter chooses XA = 3 and Kenny chooses XB = 6. Grifter puts 3 into the one way function and gets the result. 73 (mod 11) = 343 (mod 11) = 2 Grifter labels this result a (alpha) and calls Kenny on the phone to give him the value, which was 2. Kenny puts 6 into his function and gets his result 76 (mod11) = 1117,649 (mod 11) = 4 Kenny labels his result b (beta) and calls Grifter, giving him his result, which was 4. Right here it may seem that any possible eavesdropper would have it made. They're exchanging their answers! But it doesn't matter. These answers aren't the key. Anyone can hear them and it won't matter. The original numbers chosen are where the secret is. As long as those remain unknown, the process is safe. Grifter takes Kenny's result and works out b^XA (mod 11): 43 (mod 11) = 64 (mod 11) = 9 Kenny takes Grifter's result and works out a^XB (mod 11): 26 (mod 11) = 64 (mod 11) = 9 They both get the same number, 9. This is their key. This is great for generating keys but there's even more mathematical strangeness out there. Asymmetric cryptography. Public Key Cryptography With DES and every other cryptography method up to this point, the system relied on both parties having the same information to both encrypt and decrypt the message. Public Key Cryptography eliminated that need. Public Key crypto (aka RSA, named after Rivest, Shamir and Adleman) was discovered in the United States by Ron Rivest, Adi Shamir and Leonard Adleman in April 1997. They spent a lot of time on the problem and then one Passover after having quite a bit of Manischewitz wine making their respective ways back home, Ronald made a breakthrough. He scribbled it all down and had a complete scientific paper ready before dawn. The key to RSA is that it is based on the fact that it's incredibly difficult to factor large numbers. Multiplying two large (over 100- digit) prime numbers creates the key in RSA. The key's owner keeps the two prime numbers that were used to create that key private and the safety is up to that individual. The public key can be spread all over the world, and it should be. That's the only way the private key will work; if someone encrypts something with the public key. Creating a keypair with RSA is pretty straightforward. Kenny wants a key. 2 giant prime numbers are selected, p and q. For the sake of easy math I'll use p=17 and q=11. Those numbers are multiplied to get N. 17*11=187=N. Now, another number, e, is picked. In this case e=7. To encrypt a message, it has to be converted to a number, M. A word or message is converted to binary digits and those digits are then turned into a decimal number. M is then encrypted to give the ciphertext, C, according to C = Me (mod N). If Hannah wanted to send Kenny a kiss by sending him a letter X she'd convert it to binary (01011000, though that could be skipped in this case, since there's only on letter.) and then to decimal (88) To encrypt it Hannah would have to look up Kenny's Public Key and she finds that e = 7 and N = 187. This provides her with the formula required to send an encrypted message to Kenny. C = 887 (mod 187). 887 (mod187) = [884 (mod 187) * 883 (mod 187) * 881 (mod 187)] (mod 187) 881 = 88 = 88 (mod 187) 882 = 7744 = 77 (mod 187) 884 = 59,969,536 = 132 (mod 187) 88*77*132 =894,432 = 11 (mod 187) C = 11. Hannah can send the ciphertext to Kenny. Exponential functions in modular arithmetic are one way functions so it's incredibly difficult to work back from C = 11 and recover the original message, M. The message is safe. Hannah can express her undying love for Kenny without fear of being beaten up by all those jealous women that are out there. Kenny can decrypt the message though. He knows the values of p and q. Kenny calculates a special decryption key d. The number d is calculated according to the following formula. e*d = 1 (mod (p-1)*(q-1)) 7*d = 1 (mod 16*10) 7*d = 1 (mod 160) (A little piece of magic called Euclid's algorithm happens here) d=23 (don't ask, I don't know how it works exactly) To decrypt, Kenny uses the following formula, M = Cd (mod N) M = 1123 (mod 187) M = [111 (mod 187)*112 (mod 187)*114 (mod 187)*1116 (mod 187)] (mod 187) M = 11*121*55*154 (mod 187) M = 88 = X in ASCII The examples I gave for generating a Diffie-Hellman key and and the methods for generating a keypair and encrypting/decrypting a message with RSA were pretty much ripped off from The Code Book, by Simon Singh. I didn't want to do the math on my own. Here's his website: http://www.simonsingh.com/ If you notice anything especially screwed, up let me know via email signingis@hotmail.com or AIM: SigningiS ASCII TABLE Decimal Octal Hex Binary Value ------- ----- --- ------ ----- 033 041 021 00100001 ! 034 042 022 00100010 " 035 043 023 00100011 # 036 044 024 00100100 $ 037 045 025 00100101 % 038 046 026 00100110 & 039 047 027 00100111 ' 040 050 028 00101000 ( 041 051 029 00101001 ) 042 052 02A 00101010 * 043 053 02B 00101011 + 044 054 02C 00101100 , 045 055 02D 00101101 - 046 056 02E 00101110 . 047 057 02F 00101111 / 048 060 030 00110000 0 049 061 031 00110001 1 050 062 032 00110010 2 051 063 033 00110011 3 052 064 034 00110100 4 053 065 035 00110101 5 054 066 036 00110110 6 055 067 037 00110111 7 056 070 038 00111000 8 057 071 039 00111001 9 058 072 03A 00111010 : 059 073 03B 00111011 ; 060 074 03C 00111100 < 061 075 03D 00111101 = 062 076 03E 00111110 > 063 077 03F 00111111 ? 064 100 040 01000000 @ 065 101 041 01000001 A 066 102 042 01000010 B 067 103 043 01000011 C 068 104 044 01000100 D 069 105 045 01000101 E 070 106 046 01000110 F 071 107 047 01000111 G 072 110 048 01001000 H 073 111 049 01001001 I 074 112 04A 01001010 J 075 113 04B 01001011 K 076 114 04C 01001100 L 077 115 04D 01001101 M 078 116 04E 01001110 N 079 117 04F 01001111 O Decimal Octal Hex Binary Value ------- ----- --- ------ ----- 080 120 050 01010000 P 081 121 051 01010001 Q 082 122 052 01010010 R 083 123 053 01010011 S 084 124 054 01010100 T 085 125 055 01010101 U 086 126 056 01010110 V 087 127 057 01010111 W 088 130 058 01011000 X 089 131 059 01011001 Y 090 132 05A 01011010 Z 091 133 05B 01011011 [ 092 134 05C 01011100 \ 093 135 05D 01011101 ] 094 136 05E 01011110 ^ 095 137 05F 01011111 _ 096 140 060 01100000 ` 097 141 061 01100001 a 098 142 062 01100010 b 099 143 063 01100011 c 100 144 064 01100100 d 101 145 065 01100101 e 102 146 066 01100110 f 103 147 067 01100111 g 104 150 068 01101000 h 105 151 069 01101001 i 106 152 06A 01101010 j 107 153 06B 01101011 k 108 154 06C 01101100 l 109 155 06D 01101101 m 110 156 06E 01101110 n 111 157 06F 01101111 o 112 160 070 01110000 p 113 161 071 01110001 q 114 162 072 01110010 r 115 163 073 01110011 s 116 164 074 01110100 t 117 165 075 01110101 u 118 166 076 01110110 v 119 167 077 01110111 w 120 170 078 01111000 x 121 171 079 01111001 y 122 172 07A 01111010 z 123 173 07B 01111011 { 124 174 07C 01111100 | 125 175 07D 01111101 } 126 176 07E 01111110 ~ -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=- © 2600SLC.ORG 2001 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-