-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=

                          -= 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
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

