Publickey

Public Key Algorithms

Modular Arithmetic ► Modular

Addition  Using the last digit of the answer  Additive inverse- subtracting x or adding – x  Number you’d have to add to x to get 0  4’s inverse will be 6  addition modulo (mod) K a (poor) cipher with key K

Modular Addition ► Addition

modulo (mod) K

 Poor cipher with (dk+dm) mod K, e.g., if K=10 and dk is the key.

+ 0

0 0

1 0

2 0

3 0

4 0

5 0

6 0

7 0

8 0

9 0

1

1

2

3

4

5

6

7

8

9

0

2

2

3

4

5

6

7

8

9

0

1

3

3

4

5

6

7

8

9

0

1

2

inverse: addition mod K yields 0. ► “Decrypt” by adding inverse. ► Additive

Modular Multiplication ► Multiplication modulo

K

*

0

1

2

3

4

5

6

7

8

9

0

0

0

0

0

0

0

0

0

0

0

1

1

2

3

4

5

6

7

8

9

1

2

0

2

4

6

8

0

2

4

6

8

3

0 3 6 9 2 5 8 1 4 7 ► Multiplicative inverse: multiplication mod K yields 1 ► Only some numbers have inverse

Modular Multiplication the numbers relatively prime to n will have mod n multiplicative inverse ► x, m relative prime: no other common factor than 1 ► Only

 Eg. 8 & 15 are relatively prime - factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only common factor

Modular Exponentiation xy 0 1 2 3 4 5 6 7 8 9

0 1 1 1 1 1 1 1 1 1

1 0 1 2 3 4 5 6 7 8 9

2 0 1 4 9 6 5 6 9 4 1

3 0 1 8 7 4 5 6 3 2 9

4 0 1 6 1 6 5 6 1 6 1

5 0 1 2 3 4 5 6 7 8 9

6 0 1 4 9 6 5 6 9 4 1

7 0 1 8 7 4 5 6 3 2 9

8 0 1 6 1 6 5 6 1 6 1

9 0 1 2 3 4 5 6 7 8 9

Modular Exponentiation ► xy

mod n = xy mod ø(n) mod n ► if y mod ø(n) = 1, then xy mod n = x mod n ► Once you get the answer divide by n and get the remainder ► 4^6 = 6 mod 10 ► 4 ^ 6 = 4096 in ordinary airthmentic and ► 4096 = 6 mod 10

RSA (Rivest, Shamir, Adleman)

► The

most popular one. ► Support both public key encryption and digital signature. ► Assumption/theoretical basis:  Factoring a big number is hard.

► Variable

key length (usually 512 bits). ► Variable plaintext block size.

 Plaintext must be “smaller” than the key.  Ciphertext block size is the same as the key length.

► Based

on the theory of Prime Numbers

RSA Algorithm

1. Choose two large prime numbers P and Q. 2. Calculate N = P x Q.

3. Select the public key (i.e. the encryption key) E such that it is not a factor of (P – 1) and (Q – 1). 4. Select the private key (i.e. the decryption key) D such that the following equation is true: (D x E) mod (P – 1) x (Q – 1) = 1 5. For encryption, calculate the cipher text CT from the plain text PT as follows: CT = PTE mod N 6. Send CT as the cipher text to the receiver. 7. For decryption, calculate the plain text PT from the cipher text CT as follows: PT = CTD mod N Fig 4.4

Example of RSA Algorithm

A

Encryption algorithm using the public key

Decryption algorithm using the private key

1. Encode the original character using A = 1, B = 2 etc.

1. Raise the number to the power D, here 77.

2. Raise the number to the power E, here 5.

2. Divide the result by 119 and get the remainder. The resulting number is the cipher text.

3. Divide the result by 119 and get the remainder. The resulting number is the cipher text.

3. Decode the original character using 1 = A, 2 = B etc.

F

F 6 5 6 Result modulo 119 = 41

41

4177 Result modulo 119 6 F

F

B

RSA Example • • • • • • •

Select primes: p=17 & q=11 Compute n = pq =17×11=187 Compute ø(n)=(p–1)(q-1)=16×10=160 Select e : gcd(e,160)=1; choose e=7 Determine d: de=1 mod 160 and d < 160 Value is d=23 since 23×7=161= 10×160+1 Publish public key KU={7,187} Keep secret private key KR={23,17,11}

How Does RSA Work? ► Given

   

pub = <e, n> and priv =

encryption: c = me mod n, m < n decryption: m = cd mod n signature: s = md mod n, m < n verification: m = se mod n

► given message ► encryption:

M = 88 (nb. 88<187)

C = 887 mod 187 = 11 ► decryption:

M = 1123 mod 187 = 88

Why Does RSA Work? ► Given

pub = <e, n> and priv =

n =p*q, ø(n) =(p-1)(q-1) e*d = 1 mod ø(n) xe∗d = x mod n encryption: c = me mod n decryption: m = cd mod n = me∗d mod n = m mod n = m (since m < n)  digital signature (similar)     

Is RSA Secure? ► Factoring

512-bit number is very hard! ► But if you can factor big number n then given public key <e,n>, you can find d, hence the private key by:   

Knowing factors p, q, such that, n = p*q Then ø(n) =(p-1)(q-1) Then d such that e*d = 1 mod ø(n)

► Threat

 Moore’s law  Refinement of factorizing algorithms

► For

the near future, a key of 1024 or 2048 bits needed

Symmetric (DES) vs. Public Key (RSA)

► Exponentiation

of RSA is expensive ! ► AES and DES are much faster

 100 times faster in software  1,000 to 10,000 times faster in hardware

► RSA

often used in combination in AES and DES  Pass the session key with RSA

Digital Certificate ► Problem

of man-in-the-middle attack was solved by using digital certificates ► Digital certificates similar to passport ► It is simply a small computer file ► Establishes the relation between a user and her public key ► DC must contain the user name and the user’s public key to prove that a particular values belongs to a particular user.

Digital Certificate Contents ► Main

contents are the subject name (user), validity and public key ► Signed by a Certification Authority (CA) ► Provides guarantees about a user’s identity ► No two digital certificates issued by the same user can have the same serial number

Digital Certificate Example Digital Certificate

Subject Name: Atul Kahate Public Key: Serial Number: 1029101 Other data: Email [email protected] Valid From: 1 Jan 2001 Valid To: 31 Dec 2004 Issuer Name: VeriSign …

Similarities between a Passport and a Digital Certificate Passport entry

Corresponding digital certificate entry

Full name

Subject name

Passport number

Serial number

Valid from

Same

Valid to

Same

Issued by

Issuer name

Photograph and signature

Public key

Public Key Cryptography Standard (PKCS) ► PKCS

model developed by RSA ► Purpose of PKCD is to standardize Public Key Infrastructure (PKI) ► Standard : PKCS#1 to PKCS#15

► PKCS#1

 Defines the basic formatting rules for RSA public key functions.  It defines how digital signatures should be calculated  structure of data and format of signature is defined  Also defines syntax for RSA private and public keys

► PKCS#2

 Outlines the message the message digest calculation  Now merged with PKCS#1

► PKCS#3

 Defines mechanism to implement DiffieHellman Key Agreement

► PKCS#4

 Merged with PKCS#1

► PKCS#5

– Password Based Encryption (PBE)

 Solution for keeping the symmetric session keys safe  Step 1 : First encrypt the plain text message with symmetric key  Step 2: then encrypt the symmetric key with a Key Encryption Key (KEK)  Where to store the KEK – never store it anywhere  Generate key on demand use it for encryption/decryption the symmetric key and then discard it  KEK is generated using a password using a key generation process Password

Key generation process

KEK

► Drawback

 Attacker can launch a dictionary attack against this scheme  Attacker simply pre-compute all the possible English words and their permutationscombinations & store in a file & try each word as passwd which may succeed having access to KEK  To prevent 2 additional pieces of info are used Salt and iteration count  Salt is simply a bit string combined with passwd to produce the KEK  Iteration count specifies the no. of operation that must be performed on the combination of thepasswd and the salt to generate the KEK.

► Salt

and Iteration count need not be secret.

Password salt Iteration Count

Key Encryption Key

► PKCS#6

: Extended Certificate Syntax Std

► PKCS#7

:Cryptographic Message Syntax Std

 Defines syntax for extending attributes of an digital certificate

 Specifies a format/syntax for data that is the result of cryptographic operation  Examples :digital signatures and digital envelopes

► PKCS#8:Private

Key Information Syntax Std

 Describes the syntax for storing the private key and some attributes of a user securely  Describes the syntax for encryption private keys so that they cannot be attacked

►PKCS#10

Std

– Certificate Request Syntax

 Describes syntax for certification request  Request information consists of 3 aspects : ►Entity's distinguished name ►Entity public key ►Set of attributes  Entity requesting for the certificate signs with the private key and sends the request information, signed request and signature algo to CA  CA verifies the signature and other aspects & if OK issues certificate

► PKCS#11

: Cryptographic Token Interface Std (Cryptoki)

 Specifies operations performed using hardware token such as smart card

► PKCS

#12 : Personal Info Exchange Std

 Was developed to solve the problem of certificate and private key storage & transfer  Increment to PKCS#8

► PKCS#13

: Elliptic Curve Cryptographic Std

 under development  Deals with new cryptographic mechanism called Elliptic Curve Cryptography

► PKCS#14:

Pseudo Random Number Generation Std

 Under development  Defines the requirements for generating random numbers ► PKCS#15

: Cryptographic Token Syntax Std

 Smart cards – problem – Lack of interoperability  Info in Smarts cards of different vendors are stored differently  PKCS#15 specifies uniform token format to resolve incompatibilities

Digital Signature Techniques ► DSS

was developed for performing digital signatures ► DSS makes use of the SHA-1 algorithm for calculating the MD over an original message & uses the message digest to perform the digital signature ► DSS uses algorithm called as Digital Signature Algorithm (DSA)

RSA & Digital Signatures

► RSA

can be used to for performing digital signatures ► Step-by-Step procedure ► Step-1  Sender (A) uses SHA-1 to calculate MD1 of message M

► Step-2

 Sender (A) encrypts the MD with her private key.

► Step-3

 Sender (A) sends message M along with digital signature (DS) to receiver B

► Step-4

 B uses same MD algo as A and calculates MD2

► Step-5

 B uses sender A public key to decrypt the Digital Signature  Output is the original MD as calculated by A

► Step-6

 B compares  If MD1 = MD2 then  B accepts the original message(M) as correct unaltered  B is also assured that the message came form A

DSA & Digital Signatures ► DSA

is complicated and mathematical in nature ► Variables used

p = prime number of length L bits L = A multiple of 64 between 512 & 1024. Original p – 512 bits q = A 160-bit prime factor of p-1 g = h^(p-1)/q mod p where h is a no.< p-1 such that h^(p-1)/q mod p > 1 x = a number < q Y = g^x mod p H = message Digest algorithm - SHA-1

► p,q

g are public, x is private corresponding public key is y. ► If message m is to be signed the sender generates a random number k, < q ► Sender calculates  r = (gkmod p)mod q  s = k1 (H(m) + xr)) mod q

► Values

of r and s are the signatures of the sender which are sent to the receiver ► To verify w = s-1 mod q; u1=(H(m) *w)mod q u2 = (rw) mod q; v = ((gu1*yu2) mod p ) mod q If v = r the signature is said to be verified

El-Gamal Signatures ► The

ElGamal Signature scheme is a

 Digital signature scheme which is based on the difficulty of computing discrete logarithms.  It was described by Taher El-Gamal in 1984

System Parameters H be a collision-resistant hash function. ► Let p be a large prime such that computing discrete logarithms modulo p is difficult. ► Let g be a randomly chosen generator of the multiplicative group . ► These system parameters may be shared between users. ► Let

Key generation ► Choose

randomly a secret key x with 1 < x

< p − 1. ► Compute y = gx(mod p). ► The public key is (p,g,y). ► The secret key is x. ► These steps are performed once by the signer.

Signature generation sign a message m the signer performs the following steps. ► Choose a random k such that 0 < k < p − 1 and gcd(k,p − 1) = 1. i.e relatively prime to p-1 ► Compute r = gk(mod p) ► Compute s = ykM mod p ► If s = 0 start over again. ► Here M = ( rx + ks ) mod p-1 ► Then the pair (r,s) is the digital signature of m. The signer repeats these steps for every signature. ► To

Verification signature (r,s) of a message m is verified as follows. ► 0 < r < p and 0 < s < p − 1. ►A

► ► The

verifier accepts a signature if all conditions are satisfied and rejects it otherwise.

Security ►A

third party can forge signatures either by finding the signer's secret key x or by finding collisions in the hash function. ► Both problems are believed to be difficult. ► The signer must be careful to choose a different k uniformly at random . for each signature and make sure that k or even partial information about k is not leaked. ► Otherwise a third party may be able to deduce the secret key x with less difficulty. ► In particular, if two messages are sent using the same value of k then a third party can compute x.

Zero-knowledge protocols ► In

cryptography, a zero-knowledge proof or zero-knowledge protocol

 interactive method for one party to prove to another that a (usually mathematical) statement is true  without revealing anything other than the veracity of the statement.

Zero-knowledge protocols ► Alice

wants to prove to Bob that she is Alice.  If she sends identification, Bob (or an eavesdropper) can use it.

► Example:

Authority chooses a number N=77, known by all. ► Alice’s public ID: (58, 67) ► Alice’s private ID: (9,10)

 These are multiplicative inverses mod 77

Zero-knowledge protocols ► Alice

chooses some random numbers and computes their square mod N.  {19, 24, 51} -> 192(mod 77) = 53, 242(mod 77) = 37, 512(mod 77) = 60  Alice sends {53,37,60} to Bob.  Bob sends back a random 2x3 matrix of 1s and 0s. 01 10 11

Zero-knowledge protocols ► Alice

uses this grid, plus her original random numbers and her secret numbers, to compute: ► 19 * 90 * 101 (mod 77) = 36 ► 24 * 91 * 100 (mod 77) = 62 ► 51 * 91 * 101 (mod 77) = 47 ► She

sends {36,62,47} to Bob.

Zero-knowledge protocols ► Bob

verifies Alice’s identity by computing:

 {58,67} are Alice’s public numbers

► 36^2

*58^0 *67^1 (mod 77)= 53 ► 62^2 *58^1 * 67^0 (mod 77) = 37 ► 47^2 * 58^1 * 67^1 (mod 77) = 60 ► Alice’s

original numbers reappear!

 (Actually, an attacker would have a 1 in 64 chance of guessing correctly …)

Zero-knowledge protocols a real system, N would be very large

► In

 160 digits.

► Many

more numbers would be generated. ► This works because Alice’s secret numbers are multiplicative inverses of her public numbers mod N. ► Also, Bob learns nothing that he didn’t know before.