Modern Cryptology

-Much more mathematical than classical cryptology

-Includes the following:

1. The Data Encryption Standard (DES)

2. The Advanced Encryption Standard (AES)

3. Public-Key Cryptology:

(i) The Knapsack Code

(ii) RSA (Rivest, Shamir, Adleman)

(iii) Elliptic Curve Cryptography

Public-Key Cryptography

Recall the symmetric key cryptography diagram:

See earlier handout for the diagram!

The key (KEY) is exactly the same for encoding and decoding.

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).

What we will use to achieve such schemes is a type of problem called NP-complete.

NP – complete problems – problems that are impossible, or at least infeasible, to solve in real time. The resulting code should be unbreakable.

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.

Example 1-

Let p,q, be 2 "large" primes, and f(p,q) = pq = n.

Multiplying 2 large primes together is easy. But given n, it is very difficult to factor (NP- complete). (RSA is based on this.)

Use of one-way functions: Password Problem

Consider a computer system in which each user must log on with an I.D. and password. It would be stupid to have a file of I.D.’s and passwords, as anyone with access to such a file could access any of the accounts.

If f is a one-way function whose domain is the set of all possible passwords, we can use it to secure the system.

When a new user u_i chooses a password p_i, the computer computes f (p_i) and stores the pair (u_i, f (p_i)).

The file storing the pair may be seen by anyone, because it is impossible to find p_i given

f (p_i).

Note: When the user u_i logs on with password p_i, the computer checks for a match

(u_i, f(p_i)).

GCDs and the Euclidean Algorithm

GCD – greatest common divisor

GCD(12,30) = 6 GCD(15,31) = 1, etc.

One method to find GCDs:

12 =

30 =

Factor both numbers into primes, circle common factors.

A better method – The Euclidean Algorithm

larger # smaller #

30 = 2(12) + 6

quotient remainder

12 = (2)(6) + 0

previous quotient previous

divisor remainder

Once you have a 0 remainder, the previous remainder is the GCD.

Another Example

GCD(15,22)

22 = (1)(15) + 7

15 = (2)(7) + 1

7 = (7)(1) + 0

GCD(15,22) = 1

When two numbers have GCD = 1 they are called relatively prime, or coprime. So 15 and 22 are coprime.

Now: A harder, related problem.

("Euclidean Algorithm in Reverse")

If m and n are integers not both 0, you can always find integers x and y so that

mx + ny = gcd(m,n).

(Proof by well-ordering principle)

We found GCD(15,22) = 1. How do we find x,y so that 15x + 22y = 1?

Step 1: Do the Euclidean Algorithm.

22 = (1)(15) + 7 (row 1)

15 = (2)(7) + 1 (row 2)

7 = (7)(1) + 0 (row 3)

Step 2: Start with the second last row, and re-write the GCD by solving for it (we use row 2).

15 = 2(7) + 1, so 1 = 15 – 2(7).

Step 3: Move up a row and replace the remainder from that row into your equation:

22 = (1)(15) + 7, so 7 = 22 – (1)(15).

Replacing into our previous equation gives:

1

So,

Another Example:

Find GCD(21,34) = d and then write d = 34x + 21y for integers x,y.

a

b

c

d

e

f     Now we know that GCD(34,21) = 1.

g

row f

row e

row d

row c

row b

row a

So 1 = 13(21)-8(34)

The Knapsack Code (Merkle/Hellman)

-A Public-key Cryptographic Scheme

-Based on an NP-complete problem

The Problem: (Knapsack Problem) – Given several items, each with a different weight, is it possible to put some of the items in a knapsack so that the knapsack weighs a given amount?

Example: Weights 1,5,6,11,14,20

Is it possible to pack a knapsack that weighs 22?

yes (5,6,11)

What about weighing 24?

no

Mathematically, given values (weights) m₁,m₂,…,m_n and a sum S (the weight you want in the knapsack), compute the values of the b’s so that

S = b₁m₁ + b₂m₂ +…+ b_nm_n

The values of the b’s are either 0 or 1.

0 = not in the knapsack

1 = in the knapsack

We will use this strategy (problem) to encode a message as a solution to a series of knapsack problems.

(e,d) = encryption key, decryption key

e = public key à the "hard knapsack"

à easy to encode with but "impossible" (infeasible) to use to decode

d = private key à decodable ("the easy knapsack")

Note: This is a one-way function of sorts. Given a bunch of items in a a knapsack, it is trivial to compute their total weight (just add!). But given the total weight, it is not always easy to find which weights add to this numbers.

Easy knapsack: If the list of weights is a superincreasing sequence, the knapsack problem is easy. Superincreasing means every term is greater than the sum of all the previous terms.

E.G. (1,3,4,9,15,25) – not superincreasing

(1,3,6,13,27,52) – superincreasing

A solution to the superincreasing knapsack is easy to find.

Ex: Consider the weights (2,3,6,13,27,52) and total weight 70.

We must put 52 in the knapsack (since 2+3+6+13+27=51) 70-52 = 18. We can’t

get 27 in, and we must put 13 in (it is the largest weight less than 18).

18-13 = 5, and so no to 6, yes to 2 and 3.

70 = 2 + 3 + 13 + 52

Note: number systems are knapsack easy

(1,2,4,8,16,…)

(1,10,100,1000,…)

When we have A = (2,3,6,13,27,52) and

70 = 2 + 3 +13 + 52 we give

2 3 6 13 27 52

70 => 1 1 0 1 0 1 is the decoding.

The problem is hard without the superincreasing sequence.

Take a superincreasing knapsack sequence, for example

(2,3,6,13,27,52), and multiply all the values by a number w, mod m.. m is

chosen greater than the largest number in the sequence, say m = 56 in our example.

The multiplier, w, should have no factors in common with, m, in particular. Some sources say w should be coprime with all the other number (those in also).

Choose w = 31, for example.

easy knapsack

The normal knapsack sequence would be:

(mod 56) ≡ 6

(mod 56) ≡ 37

(mod 56) ≡ 18

(mod 56) ≡ 11

(mod 56) ≡ 53

(mod 56) ≡ 44

Then the hard (normal) knapsack is

A = (6,37,18,11,53,44)

If someone wants to send you a binary message, they first break the message into blocks of length n where n = # of items in the knapsack

n = 6 in our case

Suppose message = 011000110101 101110

then split into 6-digit pieces

011000 110101 101110

A = (6,37,18,11,53,44)

011000 is encodes as 37 + 18 = 55

110101 is encoded as 6 + 37 + 11 + 44 = 98

101110 is encoded as 6 + 18 + 11 + 53 = 88

The ciphertext is 55; 98; 88

If you want to decode if you must know the easy sequence (which you kept private), and w and m. (Actually in our small example you could figure out the message with the hard knapsack)

You need w ^-1 to unscramble the message. To find w ^–1, use the Euclidean Algorithm (backwards)

m = 56 w = 31

ww ^–1 ≡ 1 (mod m)

31 w ^–1 ≡ 1 (mod m)

31 w ^–1 +56 y = 1

56 = (1)(31) +25

31 = (1) (25) + 6

25 = (4)(6) + 1

6 = (6)(1) + 0

1 = 25 – 4(6)

= 25 – 4(31-25)

= 5(25) – 4(31)

= 5(56-31) – 4(31)

= 5(56) – 9(31)

w ^–1 = -9 ≡ 47 (mod 56)

Once you have w ^–1, multiply each of the ciphertext messages by w ^–1 (mod m) and decode with the easy sequence.

(mod 56) ≡ 9

(mod 56) ≡ 14

(mod 56) ≡ 48

= (2,3,6,13,27,52)

 

9 = 3 + 6 => 011000

14 => can’t do => try

14 + 56 = 70 70 = 52 + 13 + 3 + 2

14 + 56 = 70 => 110101

48 = 27 + 13 + 6 + 2 = 101110

message = 011000 110101 101110

This is the original message!

 

A hacker who intercepts the encrypted message must use the hard knapsack sequence. With only 6 items in the knapsack, this could be done. But in practice, the knapsack contains 200+ items with values of terms in the superincreasing sequence being 200 and 400 digits long and with modulus » 100 to 200 digits long.

Now hacking with the normal sequence becomes infeasible.

 

 

 

 

RSA (Rivest, Shamir, Adleman)

- Another public-key cryptosystem

- published 1978

- The one-way function is a product of two large primes (~100 to 200 digits)

Fact: It is easy to multiply two large primes, but (essentially) impossible, or infeasible, to

factor the product.

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

If you want to encrypt a "long" message, you first divide it into blocks so that each block is represented uniquely as some number between 0 and n – 1.

Note: If you want to use binary, you could use all strings of length k where 2 ^k is the largest power of 2 less than n. For decimal, all strings length k where 10 ^k is the largest power of 10 less than n.

We call the message blocks m_i.

Then the encrypted message c will be made up of similarly sized blocks c_i, where the c_i have the same length and size c_i » size m_i.

Encoding Formula: c_i = m_i^e (mod n)

The sender only needs e and n.

Decoding Formula: m_i = c_i^d

(Fact (c_i^d) = (m_i^e)^d = m_i^ed º m_i (mod n))

Now to use RSA, messages must be numerical. You could use, for example:

A = 01 A = 00001

B = 02 B = 00010

C = 03 or C = 00011

Z = 26 Z = 11010

Example (RSA):

Very small example: p = 47, q = 71

(so p and q aren’t 100-200 digits long!)

p × q = 3337

e, the encryption key, must be relatively prime with (p – 1) (q – 1) = 46 × 70 = 3220.

e = 79 certainly works.

How do we get d from e? Evelidean Algorithm backwards

d º e ^–1 (mod (p – 1)(q – 1))

ed º 1 (mod (p – 1)(q – 1)) or

79e º 1 (mod 3220)

79x + 3220y = 1

3220 = (40)(79) + 60

79 = (1)(60) + 19

60 = (3)(19) + 3

19 = (6)(3) + 1

3 = (3)(1) + 0

1 = 19 – (6)(3) = 19 – 6(60-3(19))

= 19(19) – 6(60)

= 19(79-60) – 6(60)

= 19(79) – 25(60)

= 19(79) – 25(3220 – 40(79))

= (1019)(79) – 25(3220)

d = 1019

Check (79)(1019) = 80,501

º 1 (mod 3220)

Publish (e, n) = (79, 3337)

keep private d = 1019

Now suppose someone wants to send us the message

m = 6882326879666683

Break m into small blocks.

Since

n = 3337, break m into blocks of size 3, because 10³ < n .

m₁ = 688

m₂ = 232

m₃ = 687

m₄ = 966

m₅ = 668

m₆ = 3

Encryption:

c₁ = m₁^e = 688⁷⁹ (mod 3337) º 1570

c₂ = m₂^e = 232⁷⁹ (mod 3337) º 2756

c₃ = m₃^e = 687⁷⁹ (mod 3337) º 2714

c₄ = m₄^e = 966⁷⁹ (mod 3337) º 2276

c₅ = m₅^e = 668⁷⁹ (mod 3337) º 2423

c₆ = m₆^e = 3⁷⁹ (mod 3337) º 0158

c = 1570 2756 2714 2276 2423 0158

Decryption is similar:

m₁ = c₁^d = 1570¹⁰¹⁹ (mod 3337) º 688

m₂ = c₂^d = 2756¹⁰¹⁹ (mod 3337) º 232

m₃ = c₃^d = 2714¹⁰¹⁹ (mod 3337) º 687

m₄ = c₄^d = 2276¹⁰¹⁹ (mod 3337) º 966

m₅ = c₅^d = 2423¹⁰¹⁹ (mod 3337) º 668

m₆ = c₆^d = 0158¹⁰¹⁹ (mod 3337) º 3

(Probably when you encrypt you should make 3 => 300 so that all the messages m_i will have the same length)