Transcript n-1

Outline
•
•
•
•
Review of RSA
Discrete logarithms
Testing for primality
Key management in public-key
cryptosystem
• Diffie-Hellman Key exchange
Revisit proof of RSA

If (a×b)≡(a×c) mod n then b≡c mod n
True if a is relatively prime to n
Suppose b > c
ab – ac = kn
 a(b-c) = kn
kn
b-c
=

gcd(a,n)=1
a
Ex.
2x1 mod 8 = 2
2x5 mod 8 = 2
b-c = qn
1 ≡ 5 mod 8
Proof of Fermat’s law
Recall: p is a prime, Zp is a Galois Field

Any a multiplied by
{1,2,…,p-1} will span
{1,2,…,p-1} in some
order
{a mod p, 2a mod p,…, (p-1)a mod p} 等於 {1,2,…,p-1} 的重排
1
左邊集合內元素都與 p 互質
2
ax ≡ ay mod p => x ≡ y mod p
 左邊集合內的元素都不同
Proof for Euler’s theorem



aø(n)≡ 1 mod n, gcd(a,n)=1
n is a prime => Fermat’s theorem
Arbitrary n: ø(n) means the number of integers
that is relatively prime to n, denote the set of
integers as R  x1 , x2 ,  , x ( n ) 
Multiply each by a, modulo n:
S  (ax1 mod n) , (ax2 mod n) , , (ax ( n ) mod n) 
S is a permutation of R !!!
* a is relatively prime to n, and xi is relative prime to n => so does axi
* There is no duplicate in S
RSA concept

n=pq, p and q are primes
a a2 a3
1
2
3
4
.
.
.
pq-2
pq-1
a
…
a(n)-1 a(n)
a(n)
a
(n)
a…
a(n)
a(n)
a(n)
Euler’s formula:
1
1
1
1
.
.
.
1
1
a ( n )  1 (mod n)
2. a ( n )1  a (mod n)
k ( n ) 1
a
 a (mod n)
3.
1.
ak(n)+1
(ae)d
a
ae
RSA algorithm : key generation
and encryption/decryption Example:
1.
2.
3.
4.
Select primes p and q (pq).
Calculate n=pq.
Calculate (n)=(p-1)(q-1)
Select e that is relative prime
to and less than (n)
5. Determine d such that
de ≡ 1 mod (n), and d< (n)
(d is the multiplicative inverse of e, find it
using Extended Euclid’s algorithm)
p=17, q=11
n= 17x11 = 187
(n)= 16x10 = 160
e=7
d = 23
RSA encryption/decryption
example


Public key: KU={e,n}={7,187}
Private key: KR={d,n}={23,187}
Computational issues in RSA

Select primes p and q (pq)


Calculate d such that d ≡ e-1 mod (n)


How to select a large prime? (Chap. 8.3)
How to compute multiplicative inverse? =>
Extended Euclid’s algorithm (Chap. 4.4)
Encryption: M = Cd mod n

How to compute exponentiation fast?
Computation issues –
encryption/decryption


Modular exponentiation: M = Cd mod n
Fast algorithm use the property:
(a x b) mod n = (a mod n) x (b mod n) mod n
1123 mod 187 =(1116×114×112×111) mod 187
=[(1116 mod 187)×(114 mod 187)×(112 mod 187)×(111 mod 187)] mod 187
=…=88

Write exponential d as binary number: bkbk-1…b1b0

ex. 2310 = 101112 = 24+22+21+20






j
2j
2
C mod n   C  mod n    C mod n  mod n
 b 0

b j 0 
j


d
Pseudo-code for fast
exponentiation: ab mod n
Timing attacks
c=0; /* c will be the exponent at last */
d=1; /* d will be the ab mod n at last */
for(i=k; i>=0; i--){ /* k+1 bits for b */
c = 2*c;
d = (d*d) mod n;
if ( bi == 1 ){
c = c+1;
d = (d*a) mod n
}
}
If this bit is 1,
exec. time will
be slower
Resist to timing attacks

Constant exponentiation time


Random delay


return the results of exponentiation after a fixed
time
Add random delay to the exp. execution time
Blinding

Multiply ciphertext by a random number
Outline





Review of RSA
Discrete logarithms
Testing for primality
Key management in public-key cryptosystem
Diffie-Hellman Key exchange
The power of an integer, modulo n


Euler’s formula (1):aø(n)≡ 1 mod n, gcd(a,n)=1
General form (2): am ≡ 1 mod n, gcd(a,n)=1


There is at least one m (m(n)) satisfies (2)
For any 0<a<n, the least positive m satisfies (2)
is referred as



The order of a (mod n)
The exponent to which a belongs (mod n)
The length of the period generated by a
Example: modulo 19
Primitive root of 19:
1. period = 18
2. Span {1,…,18}
4? ≡ 17 mod 19
period = 9
period = 3
Euler’s
formula
Discrete logarithms

For real numbers: y = xr
=>

logx y = r
For prime integer p, and its primitive root a

There is a unique i such that
b ≡ ai mod p
where 0 ≤ i ≤ (p-1)
Given b, a, and p, we can find a unique i
=> inda,p (b) = i
• Unique discrete logarithm mod m to some base a exist
only if a is a primitive root of m
Example: discrete log, mod 19
Calculation of discrete log

Equation: b = ai mod p
Calculation of power is straightforward
Calculation of discrete log (if exists) is hard !!!
=> The same complexity of factoring primes
(
(ln p 
e
1/ 3
(ln(ln p ) 2 / 3 
Not feasible for large primes
Outline





Review of RSA
Discrete logarithms
Testing for primality
Key management in public-key cryptosystem
Diffie-Hellman Key exchange
How to select a large prime?

In RSA, we have to





select two primes p and q (pq)
select e or d (that is relatively prime to (n))
p, q, e, d must be sufficiently large to avoid
exhaustive search attack
However, no useful method to generate
arbitrarily large primes
Sol: pick at random an odd number of the
desired order of magnitude, and test whether
it is a prime
Test for primality



Miller-Rabin algorithm: decide whether a number
is a prime with a bounded error probability
Given an odd integer n for test
Ex. n = 29
Factor (n-1) as
28 = 22 (7)
n-1 = 2kq, k > 0, q odd
Recall Fermat’s theorem: an-1≡1

mod n if n is a prime
Choose an integer a, 1<a<n-1
k-1
k
generate aq,a2q,…,a2 q,a2 q mod n
See next page
a = 10
107,102x7,104x7 mod 29
=17, 28, 1
Test for primality (cont.)

For a given integer a
k-1
k
generate aq,a2q,…,a2 q,a2 q mod n
…
square
If n is a prime,
kq
2
a =an-1≡1
mod n
However, we don’t have to test until
k
a2 q
2q mod n = -1=(n-1)
a
If this number aq mod n = 1 or -1 If this number
k
q
2
q
2
Then (a ) mod n = 1
Then (a ) mod n = 1
(aq)4 mod n = 1
…
k
(aq)2 mod n = 1
Repeated use of Miller-Rabin
Algorithm
Fermat’s theorem: an-1≡1
mod n , for all 0<a<n, if
n is a prime
• It has been shown that, for one random chosen integer a,
the probability of false positive is less than 1/4
(n 非質數，但是偵測為質數)
Run M-R test 2 times with different a => Prob = (1/4)2
Run M-R test t times with different a => Prob = (1/4)t
How many integers to test to find
a prime?

Prime number theory: the primes near n are spaced
on the average one every ln (n) integers
Density of prime?
1


n
no. of primes
n
= ln (n)
Discard even integers, and ending with digit 5
=> test about 0.4ln (n) numbers
Ex. prime on the order of magnitude of 2200 (200
bits) => 0.4ln (2200) = 55 trails to find a prime
How to generate public/private
keys?


Q: select e or d that is relatively prime to (n)?
A: Extended Euclid’s algorithm




Test gcd(e, (n)) = 1?
Calculate the multiplicative inverse at the same time if
they are relatively prime
Procedure: Generate a series of random numbers,
test each against (n)
How many random numbers to test?

The prob. that two random numbers are relatively
prime is about 0.6 (problem 8.1)
Outline





Review of RSA
Discrete logarithms
Testing for primality
Key management in public-key cryptosystem
Diffie-Hellman Key exchange
Key management (Ch 10.1)

Two issues for public-key cryptosystem



Distribution of public keys
The use of public-key encryption to distribute
secret keys (keys for symm. cipher)
Distribution of public keys




Public announcement
Public available directory
Public-key authority
Public-key certificates
1. Public announcement
Ex. post public keys to public forums, such as USENET
newsgroup and Internet mailing list

Drawback: the opponent can pretend to be
another user
2. Public available directory

Some trusted entity maintains a publicly available
dynamic directory of public keys
{A, KUa }
{B, KUb }
…
Register the
public key
Register the
public key
Attack: an opponent invades the public-key directory, and
counterfeit public keys
3. Public-key authority
Central authority:
1. Maintain directory of public keys
2. Each participant knows the public key for the authority
A can confirm
the message from
the authority
N1 :認證B的身份
N2 :認證A的身份
4. Public-key certificates 憑證
Certificate: contain public key and other information, generate
from the certificate authority
Application must
be in person or by
secure channel
1. Anyone can read, verify
2. Only CA can create
Time: verify currency of certificate
Simple secret key distribution
Public-key scheme has slow data rate
 use public key to distribute secret key
 use secret key scheme for data encryption
intercept
session key
(secret key)
KUe || IDA
E
KUa[ Ks ]
Ks
E KUe[ Ks ]
Secret key distribution with
confidentiality and authentication

Against active and passive attacks
Authenticate B
Authenticate A
Confidentiality
(only B can read)
authentication
(only A can create it)
A hybrid and hierarchical scheme
Use public-key scheme
to distribute master key
A
MKA
Ks
KDC
MKA
MKB
C
B
MKB
Ks
Use master keys with KDC to distribute session key
Advantage:
1. Use master key to distribute session keys, instead of using
public-key scheme => faster !
2. Backward compatible to old KDC scheme (master +
session key)
Outline





Review of RSA
Discrete logarithms
Testing for primality
Key management in public-key cryptosystem
Diffie-Hellman Key exchange
Diffie-Hellman key exchange

Purpose: enable two users to exchange a key
securely that can then be used for subsequent
encryption of message
A

Setup up a secret key K
B
• The issue of distribution
of secret keys
Diffie-Hellman algorithm: take advantage of the
hard problem – discrete logarithm
Protocol of D-H key exchange
Public: q, a
(q is a prime;
a<q, is a primitive
root of q)
Discrete log ?
Verify D-H algorithm

Both users get the same secret key K
User A gets:
Eq:
K  (YB ) X A mod q
 (a X B mod q) X A mod q
( A mod q)  ( A mod q) mod q  A2 mod q
 a X B X A mod q
User B gets:
(YA )
XB
mod q  a
the same
X AXB
mod q
Other issues about D-H

Brute-force attack: Ex. 3a mod 353 = 40


Try all 3x mod 353, 0<x<353, until it equal 40
Use D-H algorithm as public-key system
KDC
{User, Public Key}
{A, YA (aX A}
{B, YB (aXB}
YB
A
E K[Message]
K  (YB ) X A mod q
B