Transcript 4-RSA

Public-Key Cryptography and RSA
p1.
Public-Key Cryptography
• Also known as asymmetric-key cryptography.
• Each user has a pair of keys: a public key and a private key.
• The public key is used for encryption.
– The key is known to the public.
• The private key is used for decryption.
– The key is only known to the owner.
p2.
Bob
Alice
p3.
Why Public-Key Cryptography?
• Developed to address two main issues:
– key distribution
– digital signatures
• Invented by Diffie & Hellman in 1976.
p4.
Public-Key Cryptosystem (PKC)
• Each user u has a pair of keys (PKu, SKu).
– PKu is the public key, available in a public directory.
– SKu the private key, known to u only.
• Key-generation algorithm: to generate keys.
• Encryption algorithm E: to send message M to user u,
compute C = E(PKu, M).
• Decryption algorithm D: Upon receiving C, user u computes
D(SKu, C).
• Requirement: D(SKu , E(PKu, M)) = M.
p5.
One-way function with trapdoor
Easy:
f
x 
y
f 1
Hard:
x  y
Easy:
f 1
trapdoor
x  y
Use trapdoor as the private key.
 Most (believed) one-way functions come from
number theory.
p6.
Modular Arithmetic
p7.
Integers





a | b: a divides b, a is a divisor of b.
gcd( a, b): greatest common divisor of a and b.
Coprime or relatively prime: gcd( a, b)  1.
Euclid's algorithm: compute gcd( a, b).
Extented Euclid's algorithm: compute integers
x and y such that ax  by  gcd( a, b).
p8.
Euclidean Algorithm
Comment: compute gcd(a, b), where a  b  1.
r0 : a
r1 : b
for i : 1, 2,
until rn 1 = 0
ri 1 : ri 1 mod ri
return (rn )
Running time:
O(log a) iterations
when a is large: O(log 2 a) time for each mod operation.
p9.
Extended Euclidean Algorithm
Given a  b  0, compute x, y such that gcd(a, b)  ax  by.
1. Set r0 : a and r1 : b
2. For i : 1, 2,
, until rn 1  0 compute
ri 1 : ri 1 mod ri
qi : ri 1 div ri
3. Then ri 1  ri 1  qi  ri for i : 1, 2,
,n
4. gcd(a, b)  rn  rn  2  qn 1  rn 1
 linear(rn  3 , rn 1 ) 
 linear(r0 , r1 )  ax  by.
p10.
Example: gcd(299,221)  ?
299  1  221  78
221  2  78  65
78  1  65  13
65  5  13  0
gcd(229, 221)  13  78  65
 78  (221  2  78)  3  78  221
 3  (299  1  221)  221
 3  299  4  221
p11.
Integers modulo n
 Let n  2 be an integer.
 Def: a is congruent to b modulo n, written
a  b mod n, if n | ( a  b), i.e., a and b have the
same remainder when divided by n.
 Note: a  b mod n and a  b mod n are different.
 Def: [a]n  all integers congruent to a modulo n.
 [a]n is called a residue calss modulo n, and a is a
representative of that class.
p12.
 There are exactly n residue classes modulo n :
[0], [1], [2],
, [n  1].
 Note: "congruence mod n" is an equivalence relation, whose
equivalence classes are the residue classes.
 If x  [a], y  [b], then x  y  [a  b] and x  y  [a  b].
 Define addition and multiplication for residue classes:
[a]  [b]  [a  b]
[a]  [b]  [a  b].
p13.
 Define Z n  [0], [1], ..., [n  1].
 Or, more conveniently, Z n  0, 1, ..., n  1.

 Z n ,   forms an abelian additive group.
 For a, b  Z n ,
a  b  (a  b) mod n. (Or, [a]  [b]  [ a  b]  [ a  b mod n].)
0 is the identity element.
The inverse of a, denoted by  a, is n  a.
 When doing addition/substraction in Z n , just do the regular
addition/substraction and reduce the result modulo n.
In Z10 , 5+5+9+4+6+2+8+3=?
p14.

 Z n ,  is not a group, because 01 does not exist.
 Even if we exclude 0 and consider only Z n  Z n \ {0},

1
Z
,

is
not
necessarily
a
group;
some
a
may not exist.
 n 
 For a  Z n , a 1 exists if and only if gcd(a, n)  1.
 gcd(a, n)  1  ax  ny  1 for some integers x and y
 [ a][ x]  [ n][ y]  [1] in Z n
 [ a][ x]  [1] in Z n
 [ a]1  [ x] in Z n
p15.
 Let Z n*  a  Z n : gcd(a, n)  1.

 Z n , 
is an abelian multiplicative group.
 a  b  ab mod n.
a  b  ab mod n.
1 is the identity element.
The inverse of a, written a 1 , can be computated by the
Extended Euclidean Algorithm.
*
 For example, Z12
 1,5,7,11. 5  7  35 mod12  11.
 Q: How many elements are there in Z n* ?
p16.
 Euler's Phi function:
 ( n)  a : 1  a  n and gcd( a, n)  1
= Z n*
 Facts:
1.  ( p )  ( p  1) p
e
e 1
for prime p
2.  ( ab)   ( a)  (b) if gcd(a, b)  1
p17.
 Let G be a (multiplicative) finite group.
 The order of G, ord(G ), is the number of elements in G.
 The order of a  G, written ord( a ), is the smallest
positive integer t such that a t  e. (e, identity element.)
 Lagrange's theorem: For any element a  G, ord( a ) | ord(G ).
 Corollary: For any element a  G, a ord( G )  e.
 Fermat's little theorem:
If a  Z *p ( p a prime), then a ( p )  a p 1  1 in Z *p .
 Euler's theorem:
If a  Z n* (for any n  1), then a ( n )  1 in Z n*.
p18.
Example: n  15
 Z15* = 1, 2, 4, 7, 8, 11, 13, 14
 Z15*   (15)   (3)   (5)  2  4  8
a  Z15* :

ord(a ) :
1 2 4 7 8 11 13 14
1 4 2 4 4 2 4 2
 a ( n )  a 8  1
p19.
The Chinese Remainder Problem
• A problem described in an ancient Chinese arithmetic
book, Sun Tze Suan Ching (孫子算經), by Sun Tze
(around 300AD, author of The Art of War).
• Problem: We have a number of objects, but we do not
know exactly how many. If we count them by threes we
have two left over. If we count them by fives we have
three left over. If we count them by sevens we have two
left over. How many objects are there?
Mathematically, if x  2mod3, x  3mod5, x  2mod 7,
what is x ?
p20.
Chinese remainder theorem
If integers n1 ,
, nk are pairwise coprime,
then the system of congruences
 x  a1 mod n1
 x  a mod n

2
2


 x  ak mod nk
has a unique solution modulo N  n1n2
nk :
k
x   ai N i yi mod N
i 1
where N i  N ni and yi  N i 1 mod ni (A formula by Gauss)
p21.
Proof of CRT
k
1. x   ai N i yi mod N is a solution. i ,
i 1
 k

 k

x mod ni    a j N j y j mod N  mod ni    a j N j y j  mod ni
 j 1

 j 1

 ai N i yi mod ni
(for j  i, N j is a multiple of ni )
 ai N i  N i 1 mod ni  mod ni = ai mod ni
 x  ai mod ni .
2. If x is also a solution  x  x mod ni i
 x  x mod N .
p22.
Example: Chinese remainder theorem
Suppose
x  1 mod 3
x  6 mod 7
x  8 mod 10
By the Chinese remainer theorem, the solution is:
x  1  70  (70 1 mod 3)  6  30  (30 1 mod 7)  8  21  (211 mod10)
 1  70  (11 mod 3)  6  30  (2 1 mod 7)  8  21  (11 mod10)
 1  70  1  6  30  4  8  21  1 mod 210
 958 mod 210
 118 mod 210
p23.
Another version of CRT
 N  n1n2
nk (the numbers ni are pairwise coprime)
 There is a one-to-one correspondence :
ZN

 Z n1 
A


 a1 ,
 Z nk
, ak  , where A  Z N and ai  A mod ni
  ( x  y )   ( x)  ( y ).
  ( x  y )   ( x)   ( y ).
p24.
Chinese remainder theorem
Let N  n1n2
nk , where n1 ,
, nk are pairwise coprime.
Define a mapping
 : Z N  Zn  Zn 
1
x
2
 Z nk
( x mod n1 , x mod n2 ,
, x mod nk )
Then,
  is bijective (one-to-one and onto).
  ( x  y )   ( x)  ( y ).
  ( x  y )   ( x)   ( y ).
p25.
 Computations in Z N can be done by performing
corresponding computations in Z n1 , Z n2 ,
, Z nk , and
then solve the CRP.
 If
a 

b 
 a1 ,
 b1 ,
, ak 
, bk 
ab
ab
a b

mod N



 a1  b1 ,
 a1  b1 ,
 a1  b1 ,
then

mod n1
, ak  bk 
, ak  bk 
, ak  bk  if b  Z N*

mod nk
p26.
Example: Chinese remainder theorem
 Z15  Z 3  Z 5
*
*
*
Z

Z

Z
 15 3 5 
8   8mod 3, 8mod 5   (2,3)
11  11mod 3, 11mod 5   (2,1)
 Suppose we want to compute 8  11 mod15.
 8  11mod15  (2  2 mod 3, 3  1mod 5)  (1,3).
 x  (1,3) (which number x  Z15 corresponds to (1,3)?)
 x  1mod 3
 Solve 
 x  13
 x  3mod 5
p27.
Important Problems
 gcd(a, b)
1
 a mod n
 a k mod n
1
 a mod n
 Can be done in O(log 3 n) time.
p28.
How to compute a 1 mod n ?
 Compute a 1 in Z n*.
1
 a exists if and only if gcd(a, n)  1.
 Use extended Euclidean algorithm to find x, y
such that ax  ny  gcd(a, n)  1 (in Z )
 [a][ x]  [n][ y ]  [1]
 [a ][ x ]  [1]
(since [n]  [0])
 [a ]1  [ x ].
 Note: may omit [ ], but reduce everything modulo n.
p29.
Example
 Compute 151 mod 47.
47  15  3  2 (divide 47 by 15; remainder  2)
15  2  7  1 (divide 15 by 2; remainder  1)
1  15  2  7
( mod 47)
 15  (47  15  3)  7
 15  22  47  7
( mod 47)
( mod 47)
 15  22
( mod 47)
151 mod 47  22
*
That is, 151  22 in Z 47
p30.
Algorithm: Square-and-Multiply(x, c, n)
Comment: compute x c mod n, where c  ck ck 1
c0 in binary.
z 1
for i  k downto 0 do
z  z 2 mod n
if ci  1

ci
mod n
x

z

z
i.e.,

then z   z  x  mod n 


return (z )
Note: At the end of iteration i, z  x ck ...ci .
p31.
Example: 1123 mod187
23  10111b
z 1
z  z 2  11 mod 187  11 (square and multiply)
z  z 2 mod 187  121
(square)
z  z 2  11 mod 187  44 (square and multiply)
z  z 2  11 mod 187  165 (square and multiply)
z  z 2  11 mod 187  88
(square and multiply)
p32.
The RSA Cryptosystem
• RSA Encryption
• RSA Digital signature
p33.
The RSA Cryptosystem
 By Rivest, Shamir & Adleman of MIT in 1977.
 Best known and most widely used public-key scheme.
 Based on the assumed one-way property of modular
powering:
f : x  x e mod n
(easy)
f 1 : x e  x mod n
(hard)
p34.
Idea behind RSA
It works in group Z n*.
Encryption (easy):
Decryption (hard):
RSA
x 
 xe
RSA 1
x  x e
Looking for a trapdoor: ( x e ) d  x.
If d is a number such that ed  1mod  ( n ), then
ed  k ( n )  1 for some k , and
(x )  x
e d
ed
x
 ( n ) k 1
 x

 (n) k
 x  1  x  x.
p35.
RSA Cryptosystem
 Key generation:
(a) Choose large primes p and q, and let n : pq.
(b) Choose e (1  e   ( n)) coprime to  ( n), and
compute d : e mod  ( n). (ed  1 mod  (n).)
(c) Public key: pk  (n, e). Secret key: sk  (n, d ).
1
 Encryption: E pk ( x) : x mod n, where x  Z .
e
*
n
 Decryption: Dsk ( y ) : y d mod n, where y  Z n*.
( E pk and Dsk work for x, y  Z n \ Z n* , but not secure.)
p36.
Why RSA Works?
 The setting of RSA is the group  Z n* ,
In group  Z ,
*
n
:
 , for any x  Z , we have x
*
n
 (n)
 1.
We have chosen e, d such that ed  1 mod  ( n ), i.e.,
ed  k ( n )  1 for some positive integer k .
For x  Z ,  x
*
n

e d
x
ed
x
k ( n ) 1
 x

 (n) k
x  x.
p37.
What if x  Z n \ Z n* ?
 RSA still works, but not secure.
 x  Z n*  gcd( x, n )  1  x  ap or x  aq for some a.
 Say x  ap. Then
 x ed  0 mod p
 ed
 x  x mod q

x ed  x k ( n )1  x k ( p 1)( q 1)1 
 By CRT,
x ed  x mod n  x ed mod n  x
 D  E ( x)  x
p38.
RSA Example: Key Setup
 Select two primes: p  17, q  11.
 Compute the modulus n  pq  187.
 Compute  (n)  ( p  1)(q  1)  160.
 Select e between 0 and 160 such that gcd(e,160)  1.
Say e  7.
 Compute d  e 1 mod  (n)  7 1 mod160  23
(using extended Euclid's algorithm).
 Public key: pk  (e, n)  (7, 187).
 Secret key: sk  (d , n)  (23, 187).
p39.
RSA Example: Encryption & Decryption
 Suppose m  88.
 Encryption: c  me mod n  887 mod187  11.
 Decryption: m  c d mod n  1123 mod187  88.
 When computing 1123 mod187, we do not first
compute 1123 and then reduce it modulo 187.
 Rather, use square-and-multiply, and reduce intermediate
results modulo 187 whenever they get bigger than 187.
p40.
Encryption Key e
 To speed up encryption, small values are usually
used for e.
 Popular choices are 3, 17  24  1, 65537  216  1.
These values have only two 1's in their binary
representation.
 There is an interesting attack on small e.
p41.
Decryption Key d
 One may be tempted to use a small d to speed up
decryption.
 Unfortunately, that is risky.
 Wiener's attack: If d  n1/ 4 /3 and p  q  2 p,
then the decryption exponent d can be computed
from (n, e).
 CRT can be used to speed up decryption.
p42.
Speeding up Decryption by CRT
 Multiplying two numbers of k bits takes O ( k 2 ) time.
 n  pq.
n  1024-2058 bits. p, q  half the size.
 Decryption: c d mod n.
 Instead of computing c d mod n directly, we
compute
compute
1
1
mod
 1
and
mod
2
and
recover the plaintext by solving
mod
2
 2
1
mod
mod
2
1
2
p43.
p44.
Mathematical Attacks
 Factor n into pq. Then  ( n)  ( p  1)( q  1) and
d  e 1 mod  (n) can be calculated easily.
 Determine  (n) directly. Equivalent to factoring n.
Knowing  (n) will enable us to factor n by solving
n  pq

 (n)  ( p  1)( q  1)
 Determine d directly. The best known algorithms are
not faster than those for factoring n. Also, if d is known,
n can be factored with high probability.
p45.
Integer Factorization
 A difficult problem, assumed to be infeasible.
 More and more efficient algorithms have been developed.
 In 1977, RSA challenged researchers to decode a
ciphertext encrypted with a key ( n ) of 129 digits (428 bits).
Prize: $100. RSA thought it would take quadrillion years
to break the code using best algorithms of that time.
Solved in 1994.
 In 1991, RSA put forward more challenges, with prizes,
to encourage research on factorization.
p46.
RSA Numbers
 Each RSA number is a semiprime. (A number is
semiprime if it is the product of two primes.)
 There are two labeling schemes.
by the number of decimal digits:
RSA-100, ..., RSA-500, RSA-617.
by the number of bits:
RSA-576, 640, 704, 768, 896, 1024, 1536, 2048.
p47.
RSA Numbers which have been factored
 RSA-100 (332 bits), 1991, 7 MIPS-year, Quadratic Sieve.
 RSA-110 (365 bits), 1992, 75 MIPS-year, QS.
 RSA-120 (398 bits), 1993, 830 MIPS-year, QS.
 RSA-129 (428 bits), 1994, 5000 MIPS-year, QS.
 RSA-130 (431 bits), 1996, 1000 MIPS-year, GNFS.
 RSA-140 (465 bits), 1999, 2000 MIPS-year, GNFS.
 RSA-155 (512 bits), 1999, 8000 MIPS-year, GNFS.
 RSA-160 (530 bits), 2003, Lattice Sieve.
 RSA-576 (174 digits), 2003, Lattice Sieve.
 RSA-640 (193 digits), 2005, Lattice Sieve.
 RSA-200 (663 bits), 2005, Lattice Sieve.
p48.
RSA-200 =
27,997,833,911,221,327,870,829,467,638,
722,601,621,070,446,786,955,428,537,560,
009,929,326,128,400,107,609,345,671,052,
955,360,856,061,822,351,910,951,365,788,
637,105,954,482,006,576,775,098,580,557,
613,579,098,734,950,144,178,863,178,946,
295,187,237,869,221,823,983.
49
p49.
Remarks
 In light of current factorization technoligies,
RSA recommends that n be of 1024-2048 bits.
 If a message m  Z n \ Z n* ,
RSA works, but
Since gcd(m, n)  1, the sender can factor n.
Also, sincegcd(me , n)  1, the adversary can factor n, too.
 Question: how likely is m  Z n \ Z n* ?
p50.
Miscellaneous attacks against RSA
 Common modulus:
Suppose two users use the same modulus n,
and their encryption exponents e1 and e2 are coprime.
A message m sent to them, encrypted as c1  me1 mod n
and c2  me2 mod n, is not protected by RSA:
e1 , e2 coprime  re1  se2  1 for some r , s.
m  m re1  se2  c1r c2 s mod n.
p51.
 Another problem with common modulus:
Owners of keys ( n, e, d ) usually do not know n  pq.
But, actually, given ( n, e, d ), one can factor n with high
probability of success.
Thus, if two RSA users share the same n, they can
figure out each other's secret key (d value).
So, do not use a common n.
Also, if your secret key is compromised, do not just
change the exponents e and d . You should also
change n.
p52.
 If d is known, we can factor n:
x 2  1mod n has four solutions:
 1,  a for some a  1.
If a 2  1mod n and a  1
 a 2  1  0 mod n

n | ( a  1)( a  1)
 gcd( n, a  1) yield the factors of n.
Factor n by looking for a nontrivial square root of 1
mod n (i.e., an a  1 such that a 2  1mod n).
p53.
For all w  Z n* , wed 1  1 mod n, since wed  w mod n.
Write ed  1  r 2 , where r is odd. (So, w
s
Pick any w  Z n*.
r
r2
 1mod n)
(What if w  Z n \ Z n* ?)
Compute w , w , w
r 22
,w
until we find the first w
If t  1, let a  w
r 2s
r 2t 1
r 23
r 2t
,
,w
r 2t 1
r 2t
, w ,
, w
r 2s
 1mod n for some t.
mod n. Then a 2  1mod n, and a  1.
If a  n  1, then a is a nontrivial square root of 1 mod n.
Otherwise (t  0 or a  n  1), try another w.
p54.
 Low encryption exponent attack
 A message m sent to e users who employ the same
encryption exponent e is not protected by RSA.
 Say, e  3, and Bob sends a message m to three
recipients encrypted as:
c1  m3 mod n1 , c 2  m3 mod n2 , c3  m3 mod n3.
 Eve intercepts the three ciphertexts, and recovers m:
m  c1 mod n1 , m  c2 mod n2 , m  c 3 mod n3.
3
3
3
By CRT, m3  c mod n1n2 n3 for some c  n1n2 n3 .
Also, m3  n1n2 n3. So, m3  c, and m  3 c .
p55.
 Wiener's low decryption exponent attack:
Recall: pk  (n, e), sk  ( n, d ), and Dsk (c)  c d mod n.
One may be tempted to use a small d to speed up
decryption. Unfortunately, that may be risky.
The decryption exponent d can be computed
from ( n, e) if
3d  n1/ 4 and p  q  2 p.
(Before Wiener's attack, the condition p  q  2 p often
held in practice.)
p56.
Continued fraction :
1
q1 
 [q1 , q2 ,..., qm ]
1
q2 
1
q3  
qm
Any (positive) rational number a b can be expressed
as a continued fraction, called its continued fraction
expansion.
Convergents of [q1 , q2 ,..., qm ]: [q1 ], [q1 , q2 ], [q1 , q2 , q3 ],
[q1 , q2 ,..., qm ]. (This sequence converges to [q1 , q2 ,..., qm ].)
p57.
34
Example:
0
99
2
1
 [0,2,1,10,3]
1
1
1
1
10 
3
Obtained from Euclidean algorithm:
34  0  99  34, 99  2  34  31, 34  1  31  3,
31  10  3  1, 3  3  1
Convergents of [0,2,1,10,3]:
[0], [0,2], [0,2,1], [0,2,1,10], [0,2,1,10,3]
p58.
a c
1
Theorem. If gcd(a, b)  gcd(c, d )  1 and   2 ,
b d 2d
then c d equals one of the convergents of the continued
fraction expansion of a b .
e
e
t
For RSA, ed  t (n)  1 for some t. So, 
 .
n  ( n) d
e t
1
If 3d  n and p  q  2 p, then   2 .
n d 2d
So, t d equals one of the convergents of e n . Check the
convergents one by one to find the right one.
1/ 4
p59.
 Small message space attack:
If the message space is small. The adversary can
encrypt all messages and compare them with the
intercepted ciphertext.
This attack is not specific to RSA.
p60.
Timing Attacks
 Paul Kocher in mid-1990’s demonstrated that a snooper
can determine a private key by keeping track of how
long a computer takes to decipher messages.
 RSA decryption: c d mod n.
 Countermeasures:
Use constant decryption time
Add a random delay to decryption time
Blinding: modify the ciphertext c to c and compute
 c 
d
mod n.
p61.
Blinding in Some of RSA Products
 RSA encryption has a homomorphism property:
RSA(m  r )  RSA( m)  RSA( r ).
 To decrypt a ciphertext cm  RSA(m ):
Generate a random message r.
Encrypt r as cr  RSA( r ).
Multiply the two ciphertexts: c  cm cr  RSA( mr ).
Decrypting c yields a value equal to mr.
Multiplying that value by r 1 yields m.
 Note: all calculations are done in Z n* (i.e., modulo n ).
p62.
A chosen-ciphertext attack
 Based RSA's homomorphism property:
RSA( m  r )  RSA( m)  RSA( r )
 Assume Eve has acess to a decryption oracle.
 The attack:
Given c : RSA( m), Eve wants to know m  ?
She computes RSA( r ) for an arbitrary r  Z .
*
n
Now, presenting RSA( m  r )  RSA( m)  RSA(r )
to the Oracle, she obtains m  r , from which she can
compute m  (m  r )  r 1.
p63.
Security of RSA
 We have seen many attacks on RSA.
 Also, RSA is deterministic and, therefore, not CPA-secure
(i.e., not ciphertext-indistinguishable against CPA).
 We wish to make RSA secure against CPA and
aforementioned attacks.
 RSA primitive: the RSA we have described.
also called plain RSA or textbook RSA
p64.
Padded RSA
 Encryption: E pk ( m)  RSA( r m)  ( r m) e mod n,
where r is a random string.
 Thus, Padded-RSA( m)  RSA( r m) for some random r.
 Secure against many of aforementioned attacks.
 Theorem: Padded RSA is CPA-secure if m  O  log n  .
 Padded RSA is adopted in PKCS #1 v.1.5.
p65.
Padded RSA as in PKCS #1 v.1.5




PKCS: Public Key Cryptography Standard.
Let (n, e, d ) give a pair of RSA keys.
Let k denote the length of n in bytes (e.g., k  216).
To encrypt a message m :
pad m so that m  00 02 r 00 m (k bytes)
where r  8 or more random bytes  00.
original message m must be  k  11 bytes.
the ciphertext is c : RSA  m   m mod n.
e
 In 1998, Bleichenbacher published a chosen-ciphertext
attack, forcing RSA to upgrade its PKCS #1.
p66.
Bleichenbacher's chosen-ciphertext attack
 A message is called PKCS conforming if it has the
specified format:
00 02 padding string 00 original message.
 PKCS #1 implementations usually send you (sender)
an error message if RSA 1 (c) is not PKCS conforming.
 It is just like you have an Oracle which, given c, answers
whether or not RSA 1 (c ) is PKCS conforming.
 Bleichenbacher's attack takes advange of such an Oracle.
p67.
 Given c  RSA( m ), Eve tries to find m.
(Assume m is PKCS conforming.)
 How can Oracle help?
Recall that RSA is homomorphic:
RSA(a  b) =RSA(a )  RSA(b) (computated in Z n* )
Given RSA(m ), Eve can compute RSA(m  s) for any s  Z n* .
She can ask the Oracle,
Is ms  Z n* PKCS conforming?
(That is, is ms mod n PKCS conforming? )
 Why is this info useful?
p68.
 Recall PKCS Format (k bytes):
00 02 padding string 00 original message
 Let B  00 01 08( k  2)  28( k  2) (as a binary integer)
 Then, 2B  00 02 08( k  2) and 3B  00 03 08( k  2).
 If m is PKCS conforming  2B  m  3B.
 If, in addition, ms mod n is PKCS conforming
 2B  ms mod n  3B
 2B  tn  ms  3B  tn for some t
 2B s  t  n s  m  3B s  t  n s for some t
p69.
 If m is PKCS conforming  m is in the blue area.
 If, in addition, ms mod n is PKCS conforming
 ms mod n is in the blue area
 ms is in red areas
 m is in red lines.
 Thus, m is in the red lines of the blue area.
2B 3B
•••
0
n
2n
3n
4n
•••
ns
p70.
 Let's focus on the blue area, (2B, 3B).
 If m is PKCS conforming  m is in the blue area.
 If ms mod n is also PKCS conforming
 m is in red areas/lines
 If ms mod n is also PKCS conforming
 m is in purple areas/lines
 So, m  blue  red  purple
2B
3B
p71.
 So, starting with the fact that m is PKCS conforming,
Eve finds a sequence of integers s1 , s2 , s3 , ... such that
2si 1  si and
msi mod n is PKCS conforming.
 To find si , randomly choose an s  2si 1 , and ask the oracle
whether ms mod n is PKCS conforming. If not, then
try a different s.
 This way, Eve can repeatedly narrow down the area
containing m, and eventually finds m.
 For n having 1024 bits, it takes roughly 1 million accesses
to the oracle in order to find s1 , s2 , s3 , ...
p72.
Protecting Every Bit
 There are CCAs that only require the oracle to reveal
partial information about the plaintext such as:
 whether the plaintext is PKCS conforming
 whether the plaintext is even or odd
 whether the plaintext x  Z n* is in the first half or the
second half of Z n (i.e., x  n / 2 or x  n / 2 ?)
 It is desirable to protect every bit (or any partial information)
of the plaintext.
p73.
OAEP: basic idea
 Message padding: instead of encrypting m directly,
we encrypt m  r r, where r is a random bit string.
 As such, however, there is a 50% overhead.
So, we wish to use a shorter bit string r.
 Besides, r should be protected, too.
 This leads to a scheme called Optimal Asymmetric
Encryption Padding (OAEP). It can be applied not only
to RSA but to other trapdoor functions.
p74.
OAEP
 Choose k , l (k
l ) s.t. k  l = n . (n, RSA modulus).
 G :{0,1}k  {0,1}l , a pseudorandom generator.
 h :{0,1}l  {0,1}k , a hash function.
 Encryption. To encrypt a block m of l bits :
1. choose a random bit string r  {0,1}k .
2. encode m as x : ( m  G (r ) r  h(m  G (r )))
(if x  Z n , the message space of RSA, return to step 1).
3. compute the ciphertext y : E pk ( x).
 Decryption: x : Dsk ( y )  a b. m  a  G  b  h(a )  .
p75.
Remarks on OAEP
 OAEP is adopted in current RSA PKCS #1 (v. 2.1).
 A padding or encoding scheme, not an encryption scheme.
 Intuitively, with OAEP, the ciphertext should not reveal any
information about the plaintext if RSA is one-way and
h and G are truely random (random oracles).
 A slightly more complicated version of OAEP, in which
x  ( m0k   G ( r ) r  h( m0k   G ( r ))),
has been proved CCA-secure in the random oracle model
(i.e., if G , h are random oracles.)
 In practice, hash functions such as SHA-1 are used for G, h.
p76.
The Random Oracle Model
 A random oracle is a random function f :{0,1}n  {0,1}l ( n ) .
l ( n )  2n
 Recall: there are 2
such functions.
 Each random oracle is a black box that implements one
of the 2
l ( n )  2n
random functions, say f 0 .
 The 2n values of f 0 are totally independent.
 The only way to know the value of f 0 ( x) is to explicitly
evaluate f 0 at x (i.e., ask the oracle).
 No feasible way to implement a random oracle.
Infeasible: use a trusted authority.
Infeasible: use a l ( n)  2 n -bit disk.
p77.
The Random Oracle Model
 Since random oracles cannot be implemented, is it
useful to prove that some scheme is secure in the
random oracle model?
 It's controversial, but more "for" than "against."
p78.
Digital Signatures
p79.
Digital Signatures
 RSA (or any one-way function f ) can be used for
digital signatures.
 Digital signature is the same as MAC except that
the tag (signature) is produced using a public-key
cryptosystem.
Message m
MACk(m)
Message m
Sigsk(m)
p80.
 Digital signature:
1. Bob has a key pair ( sk , pk ).
2. Bob sends m Sig sk ( m) to Alice.
3. Alice verifies the received m s
by checking if s  Verify pk ( m)?
 Sig sk ( m) is called a signature for m.
 Security requirement: infeasible to produce a valid
pair ( m, Sig sk ( m)) without knowing sk .
p81.
Encryption (using RSA):
Alice
M
SKBob
PKBob
E
C
D
Bob
M
Signing (using RSA-1):
Alice
E(S)
=M?
SKBob
PKBob
E
Verify the signature
S
D
Bob
M
Sign
p82.
Basic RSA Signature
 Keys are generated as for RSA encryption:
Public key: pk  ( n, e). Secret key: sk  ( n, d ).
 Signing a message m  Z n*:   Dsk ( m)  m d mod n.
That is,   RSA 1 ( m).
 Verifying a signature ( m,  ) :
check if m  E pk ( )   e mod n, or m  RSA( ).
p83.
 Correctness:
As in RSA encryption, E D( m)  m, for all m  Z n .
A signed message ( m,  ) produced by Bob using
his sk will be verified and accepted.
 Remarks:
Basic RSA signature is the reverse of basic RSA
encryption.
Secure RSA signature is not the reverse of secure
RSA encryption.
p84.
 Existentially forgeable:
1. Every message m is a valid signature of its ciphertext
c, since RSA 1 (c)  m.
2. If Bob signed m1 and m2 , then the signature for m1m2
can be easily forged:  (m1m2 )   (m1 ) (m2 ).
 Remedy: hash then sign (HTS):
  Dsk (h(m)), using some collision-resistant hash
function h.
p85.
 Question:
Does hash-then-sign make RSA signature secure
against all chosen-message attacks?
 Answer:
Yes, if h is a full-domain random oracle, i.e.,
h is a random oracle mapping {0,1}*  Z n
(Z n is the full domain of RSA)
p86.
How does a random hash h help against
chosen-mesage attacks?
RSA 1
 ( m1 )  m1
RSA 1
 ( mk )  mk
RSA 1
 ( m1 )  h( m1 ) 
 m1
h
RSA 1
h
 ( mk )  h( mk ) 
 mk
Forgery:
RSA 1
 ( m)  m
RSA 1
h
 ( m)  h( m) 
m
p87.
Theorem: Full-domain hash RSA signature is secure
against any chosen-message attack under the random
oracle model.
 We will show RSA 1  Chosen-message attack.
 Thus, assume a polynomial-time probabilistic chosenmessage forger F with non-negligible success probability.
 We will design a polynomial-time algorithm A that
computes RSA 1 ( y ) for y  Z n* with non-negligible success
probability, by calling F .
 This contradicts the RSA one-way assumption.
p88.
 F , the forger, has access to a random oracle h and a
hash-then-sign oracle Sig , and works as follows.
 F requests h( mi ) and/or Sig(mi ) for various messages mi
and then produces a forgery ( m,  ) :
RSA 1
h
 0  h(m1 ) 
 m1
h
h (mt ) 
 mt
RSA 1
h
 k  h(mk ) 
 mk
Forgery:
RSA 1
h
  h(m) 
 m (m  mt for some t )
p89.
Algorithm A( N , e, y ) //compute RSA 1 ( y ) by calling F //
0. Let k be the max number of queries F may make to
the random oracle; k is bounded by the running time of F .
1. Randomly choose k signatures  1 ,  2 , ,  k ;
compute hi  RSA( i )   ie mod N , 0  i  k ;
randomly replace one of them, say ht , by y.
2. Run algorithm F (which adaptively prepares up to k
messages m1 , m2 , , mk ; requests h( m1 ), h( m2 ), , h(mk );
requests Sig ( m) for polynomial times).
3. Whenever F asks for h( mi ), give it hi . Thus, for F ,
y
h (mi )  
hi
if i  t
otherwise
p90.
Algorithm A (to compute RSA 1 ( y )) :
RSA 1
h
 1  h1  RSA( 1 ) 
 m1
y
h

 mt
RSA 1
h
 k  hk  RSA( k ) 
 mk
Forgery:
RSA 1
 
y
h

 mt
p91.
4. Whenever F asks for Sig (m),
if m  mt , return("failure");
if m  mi , i  t , give it  i ;
if m  mi for all 1  i  k , give it a random value in Z n*.
// F didn't ask for h(m) but now asks for Sig (m) //
5. If F returns a valid forgery (m,  ) with m  mt ,
then return( )
//  RSA
1
 h(mt )   RSA
1
( y )//
else return("failure")
p92.
 Analysis: (corrected version)
Let M  {m1 , ..., mk ( n ) }, queries to the random oracle.
A computes RSA 1 (y ) if and only if
F forges a valid ( m,  ) and m  mt .
Pr  F forges a valid ( m,  ) with m  mt 
 Pr  F forges a valid ( m,  )   Pr  m  mt 
1
 (non-negligible(n )) 
k (n)
 non-negligible(n ), where n  |N|.
p93.
 Problem with full-domain hash:
In practice, h is not full-domain.
For instance, the range of SHA-1 is {0,1}160 ,
while Z n  0,1,..., 2n  1 , with n  1024.
 Desired: a secure signature scheme that does not
require a full-domain hash.
p94.
Probabilistic signature scheme
 Hash function h :{0,1}*  {0,1}l  Z N (not full domain).
l  n  |N |. (E.g., SHA-1, l  160; RSA, n  1024.)
pad
 Idea: m 
m r
 {0,1}*
hash

 w  h( m r )
 {0,1}l
expand

 y  w ( r 0n 1l k )  G ( w)
sign

  RSA 1 ( y )
where
 {0,1}n 1
 ZN
r  {0,1}k
G : {0,1}l  {0,1}n 1l
(pseudorandom generator)
p95.
 Signing a message m  {0,1}*:
1. choose a random r  {0,1}k ; compute w  h(m r );
2. compute y  w r  G1 ( w) G2 ( w);
// G  G1 G2 //
3. The signature is   RSA 1 ( y ).
 Verifying a signature ( m,  ) : compute RSA( )  w t u;
check if u  G2 ( w), w  h(m t  G1 ( w)).
p96.
Remarks
 PSS is secure against chosen-message attacks in the
random oracle model (i.e., if h and G are random oracles).
 PSS is adopted in PKCS #1 v.2.1.
 Hash functions such as SHA-1 are used for h and G.
 For instance,
let n  1024, and l  k  160
let h = SHA-1
(G1 , G2 )( w)  G ( w)  h( w 0) h( w 1) h( w 2), ...
p97.
Generating large primes
To set up an RSA cryptosystem,
we need two large primes p and q.
p98.
How many prime numbers are there?
 Infinitely many.
 First proved by Euclid:
• Assume only a finite number of primes p1 , p2 , , pn .
• Let M  p1 p2  pn  1.
• M is not a prime, because M  pi , 1  i  n.
• So, M is composite and has a prime factor pi for some i
 pi | M  pi |1  contradiction.
p99.
Distribution of Prime Numbers
The Prime Number Theorem:
Let  ( x) denote the number of primes  x. Then
x
 ( x) 
for large x.
ln x
Dirichlet's Theorem: For b  Z n* , let  n ,b ( x) denote the number
of primes y such that y  x and y  b mod n. Then,
x
1
 n , b ( x) 

for large x.
ln x  (n)
p100.
How to generate a large prime number?
 Generate a random odd number n of desired size.
 Test if n is a prime.
 If not, discard it and try a different number.
 Q: How many numbers are expected to be tested before
a prime is found?
p101.
Primality test : Is n a prime?
 Can it be solved in polynomial time?
 A long standing open problem until 2002.

 AKS(Agrawal, Kayal, Saxena) : O  log n 

12  
Later improved by others to O  log n 

to O  log n 
6
.
10.5
.
 , and then
 In practice, Miller-Rabin's probabilistic algorithm is still


the most popular --- much faster, O  log n  .
3
p102.
Miller-Rabin primality test : Is n a prime?
 Looking for a characteristic property of prime numbers:
n is prime  what?
 Fermat's little theorem:
If n is prime  a  Z n* , a n 1  1 mod n.
 The converse is not true. There are composite numbers n,
called Carmichael numbers, for which a n 1  1 mod n a  Z n*.
 Need to refine the condition a  Z n* , a n 1  1 mod n.
p103.
 Fact: if n  2 is prime, then 1 has exactly two square
roots in Z n* , namely  1.
 Write n  1  u 2 k , where u is odd.
 If n is prime
 a  Z , a
*
n
u 2k
 1 mod n
(Fermat's little theorem)
u

a
 1 mod n or
* 
 a  Z n ,  i
(1)
u2
a  1 mod n for some i, 0  i  k  1
 Why? Consider the sequence
u
u2
a ,a ,a
u 22
,
,a
u 2k 1
,a
u 2k
1
p104.
 If condition (1) does not hold for some a  Z n* , then
n is composite.
 Such an a is called a strong witness that n is composite.
 Questions:
If n is composite, does it necessarily have a strong
witness?
If so, how many?
p105.
 A composite number n is a prime power if n  p e for
some prime p and integer e  2. (A perfect power if
n  k e for some integer k and e  2.)
 Theorem: If n is an odd composite and not a prime power,
then at least one half of the elements a  Z n* are strong
witnesses.
 Idea of Proof: The set A  a  Z n* : condition (1) holds
forms a proper subgroup of Z n*. So, ord(A)  ord(Z n* ) and
1
ord(A) | ord(Z ). So, ord(A)  ord(Z n* ). (Elements in
2
Z n* \ A are strong witnesses.)
*
n
p106.
Algorithm: Miller-Rabin primality test
Input: integer n  2 and parameter t
Output: a decision as to whether n is prime or composite
1. if n is even, return "composite"
2. if n is a perfect power, return "composite"
3. for i : 1 to t do
choose a random integer a, 2  a  n  1
if gcd(a, n)  1, return "composite"
if a is a strong witness, return "composite"
4. return ("prime")
p107.
Analysis: Miller-Rabin primality test
 If the algorithm answers "composite", it is always correct.
 If the algorithm answers "prime", it may or may not be correct.
 The algorithm gives a wrong answer if n is composite but
the a lg orithm fails to find a strong witness in t iterations.
 This may happen with probability at most 2  t .
 Actually, at most 4  t , by a more sophisticated analysis.
p108.
Monte Carlo algorithms
 A Monte Carlo algorithm is a probabilistic algorithm
which always gives an answer
but the answer may sometimes be incorrect.
 A Monte Carlo algorithm for a decision problem is yes-biased
if its “yes” answer is always correct but a “no” answer may
be incorrect with some error probability.
 A t -iteration Miller-Rabin is a “composite”-biased Monte Carlo
algorithm with error probability at most 1 4  t .
p109.
Las Vegas algorithms
 A Las Vegas algorithm is a probabilistic algorithm
which may sometimes fail to give an answer
but never gives an incorrect one
 A Las Vegas algorithm can be converted into a
Monte Carlo algorithm.
p110.