The Keys to Codemaking and Codebreaking
The Keys to Codemaking and Codebreaking
Dr. John Polhill
Bloomsburg University
Penn State Wilkes Barre
March 30, 2001
Cryptology
Cryptography - science of making secret codes
Cryptanalysis - science of breaking secret codes
KEY
Basic Problems
1.For cryptographers, how can we modify (encode, encrypt) our message so that it will be unreadable to anyone except its intended recipient?
2.For cryptanalysts, having intercepted an encoded message (Ciphertext), how can we decode it?
For both problems there are two basic categories of techniques:
1. Abstract "Pure" Mathematics
a. Linear Algebra
b. Abstract Algebra
c. Analysis
d. Number Theory
2. Real World Methods
a. Frequency counts
b. Three B's
Ancient Cryptology
Steganography -
1. Demaratus vs. Xerxes – message covered with wax
2. Shaved head of messenger – A message was written on a
head of a messenger, then the messenger grew his hair
back out before he was sent to deliver the message.
(The messenger was then sacrificed to the gods).
Ciphers - Message altered by exchanging symbol for
Symbol (one letter at a time)
Caesar Cipher: Julius Caesar used a simple substitution
cipher to encode military messages.
Al-kindì
Earliest known account of how to break ciphers by a frequency count.
A. "The philosopher of the Arabs"
B. Ninth century
Polyalphabetic Ciphers (Alternating Alphabets)
Vigenere's Cipher - around 1565
Babbage/Kasiski - broke Vigenere's scheme in
the mid 19th century
- frequency analysis +
counting offsets of
repeated letter groupings
Historical Events and Cryptology
1) Mary Queen of Scots
2) World War II -
a) The European Theatre - Cracking the Enigma - Marian Rejewski, Alan Turing (Bletchley Park)
b) The Pacific Theater - Cracking Red and Purple - William Friedman and Company
3) The Computer Age - Public-Key Cryptology
With encryption systems prior to 1970, the key (KEY) is exactly the same for encoding and decoding.
The problem KEY DISTRIBUTION!
Especially with electronic mail, sharing keys ahead of time is very impractical. How can we defeat this problem?
Public-key encryption
We want a scheme where encryption and decryption schemes are separate. More precisely, the key k in a public-key system is written as a key-pair k = (e,d) where e is used for encryption and d is used for decryption.
e = public key and isn’t secret
d = private key and is only known by those needing to decrypt messages
To be a useful encryption scheme, it must be computationally infeasible for an adversary in possession of e and ciphertext c to
find the plaintext m associated with c (so that Ee(m) = c).
Uses NP – complete problems: – problems that are impossible, or at least infeasible, to solve in real time. The resulting code should be unbreakable.
One-way Functions:
Informal Definition: f: S ( T so that
1. for an x in S, f (x) is easy to compute;
2. given that f (x) = y, there is no "feasible" way of computing x for most of y in T.
Basically, this type of function makes it easy to make plaintext into ciphertext, but given an encrypted message it is virtually impossible to recover the original message unless you have the private key.
Examples:
The Knapsack Code
RSA (Rivest, Shamir, and Adleman)
RSA
-published 1978
The NP-complete problem is the following:
Given large primes (100-200 digits long) p and q it is very easy to calculate the product n = pq. On the other hand, given n it would be virtually impossible to calculate p and q.
To generate the keys, choose two large primes p and q, and compute n = p × q.
For the encryption key, e, choose any number that is relatively prime (has no common factors) with (p – 1) × (q –1).
(Use the Euclidean Algorithm to) compute the decryption (private) key, d, so that
e × d ( 1 (mod (p – 1) × (q – 1))
So d ( e –1 (mod (p – 1) × (q – 1))
The public key is (e, n), while the private key is d.
Discard p, q (you don’t need them, and you certainly don’t want anyone else to know them).
To encode a numerical message m, take
me (mod n).
To decode numerical cipher text c, take
cd (mod n).
Very Small Example:
Suppose p = 23 and q =31, so n = 713.
Then choose e = 139 since 139 is relatively prime to
(22)(30) = 660. This means that d = 19, since
(19)(139) = 2641 ( 1 (mod 660).
So the public key is (139, 713) and the private key is 19.
If Bob wants to send you a message, say "Help," he must first make the message into a number.
Use 01 = a, 02 = b, 03 = c,…, 26 = z:
So help = 08 05 12 16 or
M = 08051216
Now we split the message up into groups of digits, depending on the size of n. n = 713 has 3 digits, and this means we make our blocks size 3-1 = 2 digits.
M = 08 | 05 | 12 | 16
We encode M with (139, 713) one block at a time:
08139 (mod 713) ( 35
05139 (mod 713) ( 408
12139 (mod 713) ( 499
16139 (mod 713) ( 64
The encrypted message is c = 035 408 499 064
When you receive c, you break c into blocks of 3 digits, since that is the size of n.
C = 035 | 408 | 499 | 064
Decode with d = 19 and n = 713:
03519 (mod 713) ( 8
40819 (mod 713) ( 5
49919 (mod 713) ( 12
06419 (mod 713) ( 16
So m = 08051216 or HELP!
Data Encryption Standard (DES) - 1976 - 2000
Advanced Encryption Standard (AES) - Rijndael - 2000 adoption, to be implemented
-currently accepting comments on the system
Article in New York Times - Harvard Professor makes provably unbreakable code (February, 2001)
References:
Hankerson, Hoffman, et. al. Coding Theory and
Cryptography: The Essentials, 2nd ed. Marcel
Dekker, 2000.
Schneier, Bruce. Applied Cryptography. 2nd ed.
Wiley, 1996.
Singh, Simon. The Code Book. Anchor Books,
1999.
Contact Information:
Jpolhill@bloomu.edu
-----------------------
Algorithm
Plaintext
Cipher text over insecure channel
Plaintext
Algorithm
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- keys to success in life
- keys to successful business relationships
- keys to good customer service
- keys to success in college
- keys to academic success
- funny keys to success
- business keys to success examples
- the five keys to success
- keys to being successful
- keys to a great relationship
- keys to a successful company
- keys to effective classroom management