(4)WHY PUBLIC-KEY CRYPTOGRAPHY

P

K

C

Ref: Cryptography and Network security by William Stallings

P

-K

C

 All previous cryptographic systems have been based on of substitution and permutation.

 Traditional private/secret/single key cryptography uses one key shared by both sender and receiver

 If this key is disclosed communications are compromised

P

-K

C

 Probably most significant advance in the 3000 year history of cryptography

 Uses two keys – a public & a private key

 Uses clever application of number theoretic concepts to function

 Complements rather than replaces private key crypto.

W

P

-K

C

?

 Developed to address two key issues:

 key distribution – how to have secure communications in general without having to trust a KDC with your key

 digital signatures – how to verify a message comes intact from the claimed sender

 Invention by Whitfield Diffie & Martin Hellman at Stanford Uni in 1976

 known earlier in classified community

P

-K

C



Public-key/two-key/asymmetric cryptography involves the use of two keys:

 a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures

 a related private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures



Infeasible to determine private key from public



Asymmetric because

 those who encrypt messages or verify signatures cannot decrypt messages or create signatures

P

-K

C

S

P

-K

P

-K

C

P

-K

A

 It can be applied into 3 categories:

 encryption/decryption (provide secrecy)

 digital signatures (provide authentication)

 key exchange (of session keys)

 Some algorithms are suitable for all uses, others are specific to one

P

-K

R

 Public-Key algorithms rely on two keys where:

 It is computationally easy for a party B to generate a pair (public key PUb, private key PRb).

 It is computationally feasible to en/decrypt messages when the relevant (en/decrypt) key is known

 It is computationally infeasible to find decryption key knowing only algorithm & encryption key

 It is computationally infeasible for an adversary, knowing the public key, Pb, to determine the private key, PRb

 It is computationally infeasible for an adversary, knowing the public key, Pb, and a ciphertext, C, to recover the original message, M.

 The above are formidable requirements which only a few algorithms have satisfied

P

-K

R

 Need a trapdoor one-way function

 One-way function has the following property:

 Y = f(X) easy

 X = f^–1(Y) infeasible

 A trap-door one-way function has

 Y = f_k(X) easy, if k and X are known

 X = f_k^–1(Y) easy, if k and Y are known

 X = f_k^–1(Y) infeasible, if Y known but k not known

 A practical public-key scheme depends on a suitable trap- door one-way function

S

P

K

S



Like private key schemes brute force exhaustive search attack is always theoretically possible

 but keys used are too large (>512bits)

 requires the use of very large numbers

 hence is slow compared to private key schemes

RSA



Proposed by Rivest, Shamir & Adleman of MIT in 1977.



Best known & widely used public-key scheme



Uses large integers (eg. 1024 bits).



Security due to cost of factoring large

numbers.

RSA E

/

 To encrypt a message M the sender:

 obtains public key of recipient PU={e,n}

 computes: C = M^e mod n, where 0≤M<n

 To decrypt the ciphertext C the owner:

 uses their private key PR={d,n}

 computes: M = C^d mod n

 Note that the message M must be smaller than the modulus n (block if needed)

RSA K

S



Each user generates a public/private key pair by: selecting two large primes at random: p, q

 computes their system modulus n=p.q

 note ø(n)=(p-1)(q-1)



selecting at random the encryption key e

 where 1<e<ø(n), gcd(e,ø(n))=1



solve following equation to find decryption key d

 e.d=1 mod ø(n) and 0≤d≤n



publish their public encryption key: PU={e,n}



keep secret private decryption key: PR={d,n}

H

RSA W



In RSA have:

 n=p.q

 ø(n)=(p-1)(q-1)

 carefully chose e & d to be inverses mod ø(n)

 hence e.d=1 mod ø(n) for some k

RSA E

- K

S

1.

Select primes: p=17 & q=11

2.

Calculate n = pq =17 x 11=187

3.

Calculate ø(n)=(p–1)(q-1)=16x10=160

4.

Select e: gcd(e,160)=1; choose e=7

5.

Determine d: de=1 mod 160 and d < 160 Value is d=23 since 23x7=161= 10x160+1

6.

Publish public key PU={7,187}

7.

Keep secret private key PR={23,187}

RSA E

- E

/D

 sample RSA encryption/decryption is:

 given message M = 88 (note: 88<187)

 encryption:

C = 88⁷ mod 187 = 11

 decryption:

M = 11²³ mod 187 = 88

E

E

 Encryption uses exponentiation to power e

 Hence if e small, this will be faster

 often choose e=65537 (2¹⁶-1)

 also see choices of e=3 or e=17

 But if e too small (eg e=3) can attack

RSA K

G

 Users of RSA must:

 determine two primes at random - p, q

 select either e or d and compute the other

 Primes p,q must not be easily derived from n=p.q

 means must be sufficiently large

 Exponents e, d are inverses, so use Inverse algorithm to compute the other

S

Q

RSA

 Perform encryption and decryption using the RSA algorithm

 b. p = 5; q = 11, e = 3; M = 9

 p = 3; q = 11, e = 7; M = 5

 In a public-key system using RSA, you intercept the ciphertext C = 10 sent to a user whose public key is e = 5, n = 35. What is the plaintext M?

 In the RSA public-key encryption scheme, each user has a public key, e, and a private key, d.

Suppose Bob leaks his private key. Rather than generating a new modulus, he decides to generate a new public and a new private key. Is this safe?

D

-H

K

E

 First public-key type scheme proposed by Diffie &

Hellman in 1976

 note: now it is revealed that Williamson (UK CESG) secretly proposed the concept in 1970

 It is a practical method for public exchange of a secret key

 It is used in a number of commercial products

D

-H

K

E



A public-key distribution scheme



cannot be used to exchange an arbitrary message



rather it can establish a common key



known only to the two participants



Value of key depends on the participants (and their private and public key information).



The Diffie-Hellman algorithm depends for its

effectiveness on the difficulty of computing

discrete logarithms.

D

-H

K

E

D

L

 A primitive root of a prime number p is one whose powers modulo p generate all the integers from 1 to p - 1.

 If a is a primitive root of the prime number p, then the numbers

a mod p, a² mod p,,,, a^p-1 mod p

are distinct and consist of the integers from 1 through p - 1 in some permutation.

 For any integer b and a primitive root a of prime number p, we can find a unique exponent i such that

 The exponent i is referred to as the discrete logarithm of b for the base a, mod p.

 We express this value as dlog_a,p(b)

D

-H

S

 All users agree on global parameters:

 large prime integer q

 a being a primitive root mod q

 Each user (eg. A) generates their key

 chooses a secret key (number): x_A < q

 compute their public key: y_A = a^xA mod q

 Each user makes public that key y_A

D

-H

K

E



shared session key for users A & B is K

:

K_AB = a^xA.xB mod q

= y_A^xB mod q (which B can compute)

= y_B^xA mod q (which A can compute)



K

is used as session key in private-key encryption scheme between Alice and Bob



if Alice and Bob subsequently

communicate, they will have the same key as before, unless they choose new public-keys



attacker needs an x, must solve discrete

log

D

-H

E



users Alice & Bob who wish to swap keys:



agree on prime q=353 and a=3



select random secret keys:

 A chooses x_A=97, B chooses x_B=233



compute respective public keys:

 y_A=3⁹⁷ mod 353 = 40 (Alice)

 y_B=3²³³ mod 353 = 248 (Bob)



compute shared session key as:

 K_AB= y_B^xA mod 353 = 248⁹⁷ = 160 (Alice)

 K_AB= y_A^xB mod 353 = 40²³³ = 160 (Bob)

K

E

P



Users could create random private/public D-H keys each time they communicate



Users could create a known private/public D-H key and publish in a directory, then consulted and used to securely communicate with them



Both of these are vulnerable to a meet-in-the- Middle Attack



Authentication of the keys is needed

M

-

-

-M

A

S

Q

D

-H

1. Consider a Diffie-Hellman scheme with a common prime q = 11 and a primitive root a = 2.

a. Show that 2 is a primitive root of 11.

b. If user A has public key Y_A = 9, what is A’s private key X_A? c. If user B has public key Y_B = 3, what is the secret key K shared with A?

2. In the Diffie-Hellman protocol, each participant selects a secret number x and sends the other participant a^x mod q for some public number a. What would happen if the participants sent each other x^a for some public number a instead? Give at least one method Alice and Bob could use to agree on a key.

Can Eve break your system without finding the secret numbers? Can Eve find the secret numbers?

E

G

C

 Public-key cryptosystem related to D-H

 Provides security because of difficulty in computing discrete logarithms, as in D-H

 Each user (eg. A) generates their key

 chooses a secret key (number): 1 < x_A < q-1

 compute their public key: y_A = a^xA mod q

E

G

M

E



Bob encrypt a message to send to A with following computation:

 represent message M in range 0 <= M <= q-1

 longer messages must be sent as blocks

 chose random integer k with 1 <= k <= q-1

 compute one-time key ^{K = y}_A^{k mod q}

 encrypt M as a pair of integers (C₁,C₂) where

 C₁ = a^k mod q ; C₂ = KM mod q



A then recovers message by

 recovering key K as K = C₁x_A mod q

 computing M as M = C₂ K^-1 mod q



A unique k must be used each time

 otherwise result is insecure

E

G

E



Use q=19 and a=10



Alice computes her key:

 A chooses x_A=5 & computes y_A=10⁵ mod 19 = 3



Bob send message m=17 as (11,5) by

 chosing random k=6

 computing K = y_A^k mod q = 3⁶ mod 19 = 7

 computing ^C₁ ^{= ak mod q = 106} mod 19 = 11;

C₂ = KM mod q = 7.17 mod 19 = 5



Alice recovers original message by computing:

 recover K = C₁^xA mod q = 11⁵ mod 19 = 7

 compute inverse K^-1 = 7^-1 = 11

 recover M = C₂ K^-1 mod q = 5.11 mod 19 = 17