Copy Link
Add to Bookmark
Report
A History of Cryptography
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=
-= A History of Cryptography =-
-= By SigningiS =-
-= signingis@signingis.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
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
