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.

Google Online Preview   Download