1
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.30
Public Key Cryptography
2
Public Key Cryptography
? The Inventors
– Whitfield Diffie and Martin Hellman 1976
– Ralph Merkle 1978
C = fKB(P)
Encryption with
one-way function
P = f-1KB(C,TB)
Joe
P = f-1KB(C)
Alice Bob
KB Computation of
inverse function
extremely expensive
Trap Door
One-way functions
are often based on well-
known hard problems
3
Public-Key Applications
? can classify uses 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,Only three
algorithms work well for both encryption
and digital signatures,RSA,ElGamal,and
Rabin,All of these algorithms are slow,
4
Security of Public-Key
Algorithms
? Since a cryptanalyst has access to the public key,
he can always choose any message to encrypt,
? Eve can generate a database of all possible session
keys encrypted with Bob’s public key,
? most public-key algorithms are particularly
susceptible to a chosen-ciphertext attack
? In systems where the digital signature operation is
the inverse of the encryption operation,this attack
is impossible to prevent unless different keys are
used for encryption and signatures,
5
The Knapsack Scheme
(Merkle and Hellman,1978)
? Given X = (x1,x2,…,x n ) and an integer s
? Finding B = (b1,b2,…,b n ) where bi = 0 or 1
such that
s = < X,B> = ? bi xi
? NP-Complete in general
6
Super-Increasing Sequence
? X = (x1,x2,…,x n ) is super-increasing if
?
?
?
?
1
1
i
j
ji xx
? (2,3,6,13,27,52 ) is super-increasing
7
Greedy Method
? Solve X = (2,3,6,13,27,52 ) and s = 70
? s > 52? Yes ==> b6 = 1,s1 = 70 - 52 = 18
? 18 > 27? No ==> b5 = 0
? 18 > 13? Yes ==> b4 = 1,s2 = 18 - 13 = 5
? 5 > 6? No ==> b3 = 0
? 5> 3? Yes ==> b2 = 1,s2 = 5 - 3 = 2
? b1= 1
? B = (1,1,0,1,0,1)
8
Greedy Method
? To solve,
– for i =1 down to 1
? If s?xi
– s = s-xi,bi = 1
? Else
– bi = 0
9
Knapsack Based Public-Key
? Key Generation,
– Choose a super-increasing sequence
X = (x1,x2,…,x n )
– Choose randomly two numbers Y and such that
GCD(N,Y) = 1,and
?
?
?
n
j
jxY
1
10
Knapsack Based Public-Key
? Public Key,
– K = (k1,k2,…,k n ) where ki = xi N mod Y
? Private Key,
– X,N,Y
11
Knapsack Based Public-Key
? Encryption,Suppose M = (m1,m2,…,m n )
is a binary message
– E(K,M) = <K,M> = ? ki mi
? Decryption,Given,cipher text Z,N,Y,X
– Computing N-1 mod Y
– D(Z) = GREEDY(Z N-1 mod Y,X)
12
Correctness
Z N-1 mod Y = <K,M> N-1 mod Y
= < XN,M>N-1 mod Y
= < X,M> mod Y
= <X,M>
Therefore,greedy on Z N-1 mod Y is like
greedy on <X,M> and hence we can find M
13
Example
? X = (2,3,6,13,27,52)
? Y = 105 and N = 31
– 2*31 mod 105 = 62
– 3*31 mod 105 = 93
– 6*31 mod 105 = 81
– 13*31 mod 105 = 88
– 27*31 mod 105 = 102
– 52*31 mod 105 = 37
? K = (62,93,81,88,102,37)
14
Example,Encryption
? K = (62,93,81,88,102,37)
? M = 011000110101101110
? Break up in to three sub messages
– M1 = (011000)
– M2 = (110101)
– M3 = (101110)
? E(M1) = 93 + 81 = 174
? E(M2) = 62+93 + 88+ 37 = 280
? E(M3) = 62+81+ 88+102 = 333
15
Example,Decryption
? X = (2,3,6,13,27,52),N-1 = 61
? D(M1) = GREEDY(61*174 mod 105) =
GREEDY(9) = (011000)
? D(M2) = GREEDY(61*280 mod 105) =
GREEDY(70) = (110101)
? D(M3) = GREEDY(61*333 mod 105) =
GREEDY(48) = (1011010)
? M = 011000110101010110
16
Security and Weakness
? Shamir and Zippel broken several variations
of the Knapsack protocols,
17
RSA Public Key Cryptosystem
? The Inventors
– R - Ron Rivest
– S - Adi Shamir
– A - Leonard Adleman
? The One-Way Function
– The exponentiation function y = f(x) = xe mod n
can be computed with reasonable effort,
– Its inverse x = f -1(y) is extremely difficult to
compute,
? The Hard Problem Securing the Trapdoor
– The RSA public key algorithm is based on the well-
known hard problem of factoring large numbers into
its prime factors that has been studied over many
centuries,
18
At Crypto 82
19
20
Key Generation Algorithm
? Step 1,Choose two random large prime numbers p and q
– For maximum security,choose p and q of about equal length,
e.g,512-1024 bits each,
? Step 2,Compute the product n = p·q
? Step 3,Choose a random integer e < (p-1)(q-1) ?(n)= (p-1)(q-1)
– The numbers e and (p-1)(q-1) must be relatively prime,i.e,they
should not share common prime factors,
? Step 4,Compute the unique inverse d = e-1 mod (p-1)(q-1)
– The equation d·e mod (p-1)(q-1) = 1
can be solved using the Euclidian algorithm,
21
Public Key,
n product of two primes,p and q (p and q must remain secret)
e relatively prime to (p - 1)(q - 1)
Private Key,
d e-1 mod ((p - 1)(q - 1))
Encrypting,
c = me mod n
Decrypting,
m = cd mod n
RSA Encryption
22
Checking RSA
? de ? 1 (mod ?(n))
? de = t(?(n)) + 1,t >= 1
? (me)d ? mt(?(n)) + 1 (mod n)
? (m ?(n))tm (mod n)
? (1)tm (mod n) by
Euler’s Thm,
? m (mod n)
23
? (p-1)·(q-1) = 2 · 10 = 2 · 2 · 5 = 20
Key Generation Example
? p = 3,q = 11,n = p·q = 33
? the public exponent e must be relatively
prime to (p-1)·(q-1),
i.e,it cannot contain any factors of 2 and 5
e d e·d e·d mod 20
3 7 21 1
7 3 21 1
9 9 81 1
11 11 121 1
13 17 221 1
17 13 221 1
19 19 361 1
all possible choices for
the exponents e and d
24
RSA Example
1,Select primes,p=17 & q=11
2,Compute n = pq =17× 11=187
3,Compute ?(n)=(p–1)(q-1)=16× 10=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 23× 7=161= 10× 160+1
6,Publish public key KU={7,187}
7,Keep secret private key KR={23,17,11}
25
RSA Example cont
? sample RSA encryption/decryption is,
? given message M = 88 (nb,88<187)
? encryption,
C = 887 mod 187 = 11
? decryption,
M = 1123 mod 187 = 88
26
p=43,q=59,r=pq=43*59=2537,?(r)=(p-1)(q-1)
=42*58 =2436,e=13,Determine d,de=1 mod 2436
2436 =13* 187+ 5,13= 2* 5+ 3
5= 3+ 2,3= 2+ 1
1= 3- 2, 2= 5- 3,3 =13- 2* 5
5 =2436- 13* 187
1= 3- 2= 3-（ 5- 3） = 2* 3- 5
=2*（ 13- 2* 5） - 5= 2 *13- 5* 5
=2* 13- 5*（ 2436 -13 *187）
=937* 13- 5* 2346
937* 13 ≡ 1 mod 2436
d= 937
RSA Example
27
DES vs,RSA
? RSA is about 1500 times slower than DES
– Exponentiation and modulus
? Generation of numbers used in RSA can take
time
? Test n against known methods of factoring
– http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.ht
ml
28
RSA Signature
p,q,primes,n = pq,ed = 1 mod (n),
e,n,public key,d,secret key,(factoring,n,1024 bits)
M,message,M in {0,1,..,n-1},
Signing,S = Md mod n
Verification,M = Se mod n
Key generation,p = 3,q = 5,n = 15,e = 3 => d = 3
Signing,M = 13,S = 13d mod n,=> S = 7
Verification,Checking M = Se mod n
?
29
RSA,Component Operations
? Exponentiation
– We need to do it fast
? Factorization
– Believed to be difficult (security is here)
? Finding prime numbers and testing primality
– Rabin Miller test
– New polynomial time algorithm
? http://mathworld.wolfram.com/news/2002-08-07_primetest/
? http://www.cse.iitk.ac.in/primality.pdf
30
Efficient Exponentiation of Large
Numbers
? Multiplication in finite fields
? (a·b) mod n = [ (a mod n) · (b mod n) ] mod n
? Straight exponentiation method with e-1 multiplications
? y = xe = x · x ·..,· x mod n
? Efficient exponentiation with < 2·log2 e multiplications
? based on the binary representation of the exponent
e = bk 2k + bk-1 2k-1 +,.,+ bi 2i +,.,+ b2 22 + b1 2 + b0
with bi = {0,1} and k = log2 e
y x x x x x nk k k kb b b b b? ? ? ? ? ?? ?2 2 2 21 1 2 2 1 0e j e j e j c h b g? m o d
x x ni i2 2 21? ?e j m o d
with the iterative squaring,
31
Efficient Exponentiation of Large
Numbers
? Square-and-Multiply(x,e,n)
Z=1
For i=k downto 0
Do
z=z*z mod n
if bi=1
then z=z*x mod n
Return(z)
1 2 012 2 2 2(,,,, ( ( ( ) ) ),,,, )k k kb b b bbex x x x x x???
32
Security Analysis of RSA Cryptosystem
Factoring n = pq Number theoretic Problems (key size)
Strong prime,Cycling attack,low exponent attack Other parameters
Chosen Ciphertext Attack (Simmons) Protocol failure
Timing
Attack
Differential Fault
Attack (DFA)
Side Channel
Attack (SCA)
Bleichenbacher Attack (PKCS1) Padding failure
Com
mon m
odu
lus
Broa
d c
ast
at
tac
k
Implementation
failure
Klima-Rosa attack against PGP Programming or Coding failure
SECURE RSA!
33
Factorization
? Brute force is stupid and slow
– d = 1,2,3,4,… Does d divide n?
– Factoring n = pq,If p <= q,n >= p2,so ?n >= p
– d can go high as ?n in worst case
– For n ~ 1040,1020 number of divisions
? Use structure of Zn
– p –1 method (not really used,but a good speedup)
– Pollard’s rho method
– Quadratic sieve,Number Field Sieve (NFS)
– Is there a better method out there?
34
Security of Method
? Schroeppel Factoring formula
? Calculates the number of steps needed to factor
these large prime numbers
))l n (l n (/)ln(
)ln(/)ln(ln
))( l n (
))l n ( l n (*)l n (e x p
nn
nn
n
n
nn
?
?
35
Problems with method
? 1992 Arjen Lenstra and Dan Bernstein factored
2^523 - 1 into primes,using about three weeks of
MasPar time,
? MasPar is a 16384-processor SIMD machine; each
processor can add about 200000 integers per
second.)
? used `number field sieve' it is quite a bit faster for
special numbers like 2^523 - 1
? runs in exp(O(log{1/3} n log{2/3} log n)) in any
case,
36
History of Factoring
? Year # Digits Method
? 1970 41 Continued Fraction - Morrison-Brillhart
? 1980 50
? 1982 55
? 1983 62
? 1984 72
? 1991 100 Quadratic Sieve
? 1993 120 Quadratic Sieve
? 1994 129 Quadratic Sieve (RSA predicted 40 quadrilllion
years!)
? 1996 130 Number Field Sieve (1000 MIPS yrs)
? 1999 140 Number Field Sieve (2000 MIPS yrs,8.9 CPU
yrs)
? 2000 155 Number Field Sieve (35.7 CPU yrs) (512 bits)
? 174 RSA challenge not yet factored (576 bits)
37
Strong Primes
? Factoring p and q is one of the attacks against RSA
- some properties make it harder
? gcd(p - 1,q - 1) should be small
? p - 1 and q - 1 should have large prime factors p’
and q’
? p’ - 1 and q’ - 1 should have large prime factors p”
and q”
? Both (p - 1)/2 and (q - 1)/2 should be prime
? Some factoring algorithms work better on numbers
which aren’t strong primes,others are unaffected
38
Timing Attacks
? developed in mid-1990’s
? exploit timing variations in operations
– eg,multiplying by small vs large number
– or IF's varying which instructions executed
? infer operand size based on time taken
? RSA exploits time taken in exponentiation
? countermeasures
– use constant exponentiation time
– add random delays
– blind values used in calculations
39
Finding some prime numbers
? A famous result in number theory,called the Prime
number theorem,states that the number of primes
not exceeding N is approximately N/In N,
? Hence,if p is chosen at random,the probability that
it is prime is about l/lnp,For a 512 bit modulus,we
have l/lnp = 1/ 177,
? There are 10151 primes 512 bits in length or
less.There are only 1077 atoms in the universe.The
chance that two people choose the same prime
factors for key generation is therefore near to nil !
40
Finding some prime numbers
? Easy to generate a number,but how do you know if
it’s prime?
? Rabin Miller
– If n is prime,output is always,could be”
– If n is composite,output is,composite” or,could be”
– If n is composite and,could be” is returned,the
probability of a wrong answer is <= ?
? New polynomial algorithm that can say yes/no!
41
Finding some prime numbers
? To prove that a randomly chosen number is really
prime you would have to factor it,Try small factors
(3,5,7,11,...)
? Probabilistic Primality Tests (e.g,Rabin-Miller)
? After passing 5 tests,assume a random number to be prime
is prime
composite number
0 %
100 % 0.1 %
not prime
prime number 99.9 %
random number is a Result
of
Primality
Test
42
Chosen Ciphertext Attack
? Scenario 1,To recover m from c,m = cd
? she first chooses a random number,r,such that
r is less than n,
? x = re mod n ; y = xc mod n ; t = r-1 mod n
? Eve gets Alice to sign y with her private key,
thereby decrypting y,
? u = yd mod n
? Now,Eve computes
? tu mod n = r-1yd mod n = r-1xdcd mod n = r-1rm mod
n = m
43
Chosen Ciphertext Attack
? Scenario 2,Mallory wants Trent to sign a
message m’ he otherwise wouldn’t,
? First,Mallory chooses an arbitrary value x and
computes y = xe mod n,
? Then he computes m = ym’ mod n,and sends m
to Trent to sign,
? Mallory calculates (md mod n)x-1 mod n=
(ym’ )d x-1 mod n= m’ d
44
Chosen Ciphertext Attack
? Scenario 3,Eve wants Alice to sign m3,
? She generates two messages,m1 and m2,such
that m3 ≡ m1m2 (mod n)
? If Eve can get Alice to sign m1 and m2,she can
calculate m3,
? m3d = (m1d mod n)(m2d mod n )
45
Common Modulus Attack
=> We should not use different exponents for a common modulus
Encryption
message
M
C1
C2
attacker
Message M
46
Common Modulus Attack
? Let m be the plaintext message,The two encryption
keys are e1 and e2,The common modulus is n,The two
ciphertext messages are,
? c1 = me1 mod n ; c2 = me2 mod n
? The cryptanalyst knows n,e1,e2,c1,and c2,Here’s
how he recovers m,
? find r and s,such that re1 + se2 = 1
? Assuming r is negative (either r or s has to be,so
just call the negative one r),then the extended
Euclidean algorithm can be used again to calculate
c1-1,Then
? (c1-1)-r * C2s = m mod n
47
Low Encryption Exponent Attack
? RSA encryption and signature verification are
faster if you use a low value for e,but that can
also be insecure
Fact (small message attack),e < log n/log M => Me mod = Me,
e = 3,(77)e mod 987654321 = (77)e,
0 M Me n
? We should choose enough large e,
(or We pad M with an integer T like M||T)
0 M M||T n
T
48
Related Message Attack
Encryption
message
M
C1 =Me
C2 = (aM+b)e
attacker
Message M
=> We should randomize each message M,
49
Low Decryption Exponent Attack
? Another attack,this one by Michael Wiener,
will recover d,when d is up to one quarter the
size of n and e is less than n,
Fact (Wiener),If d < (1/3)n1/4,then we can find
d for given (n,e)
50
Attack on Encrypting and
Signing with RSA
? Alice wants to send a message to Bob,
? (meB mod nB)dA mod nA
? Here’s how Bob can claim that Alice sent him m’
and not m,Realize that since Bob knows the
factorization of nB (it’s his modulus),he can
calculate discrete logarithms with respect to nB,
? m’x = m mod nB
? Then,if he can publish xeB as his new public
exponent and keep nB as his modulus,he can
claim that Alice sent him message m’ encrypted
in this new exponent
51
Semantic security
? Total break
– The adversary can determine the private key of a
public key cryptosystem,or the secret key of a
symmetric key encryption system,
? Partial break
– The adversary is able with non-negligible probability
to
? decrypt a previously unseen ciphertext (without knowing
the private/secret key),or
? determine some specific information about the plaintext
given
the ciphertext,
52
Semantic security
? Distinguishability of ciphertexts
– The adversary is able to distinguish with probability greater
than ?,
? encryptions of different plaintexts,or
? encryptions of a given plaintext and a random string,
A public key cryptosystem in which the adversary cannot
(in polynomial time) distinguish ciphertexts,under certain
computational assumptions hold,is said to achieve
semantical security,
53
Semantic security
(2) Algorithm A2,on input m0,m1,c =E(mb),guesses b (guess stage),
(1) Algorithm A1,on input pk,finds two message m0,m1 (find stage),
e,public key
m1,message
m0,message
ciphertext of m0 or m1
A1
A2 b
random encryption c=E(mb)
54
Perfect vs,Semantic security
? perfect secrecy,
– a passive adversary,even with infinite computational
resources
– can learn nothing about plaintext from ciphertext,
except its length
– Limitation,cannot be achieved unless key is as long as
message
? semantic security,polynomially bounded perfect
secrecy
– a passive adversary with poly,bounded resources can
learn nothing
55
RSA is not semantically secure
It is easy to distinguish M0e mod n and M1e
mod n for given M0,M1,
An easy way is to encrypt (M||r)e mod n for a
random integer r<n-M,
But there is no security proof for this padding
way!
56
A semantically secure public key
cryptosystem
Let m.k be positive integers,
let F a family of trapdoor one-way permutations
such that
f, {0,1} k ? {0,1} k for all f ?F,and
let G, {0,1} k ? {0,1} m be a random oracle,
Let P = {0,1} m,C = {0,1} k x {0,1} k and
K = {(f,f -1,G), f ? F },
57
A semantically secure Public Key
cryptosystem
For K = (f,f -1,G),let r ? {0,1} k be chosen randomly,
and define
eK(x) = (y1,y2) = ( f (r ),G(r ) x ),
where y1 ? {0,1} k,x,y2 ? {0,1} m
Further define
dK(y1,y2) = G (f -1(y1)) y2
Public key = (f,G),
Private key f -1,
?
58
A semantically secure Public Key
cryptosystem
In the case of the RSA cryptosystem,
take n = pq,P = C = Zn,f (x) = x
e mod n,and f
-1(x) =
xd modn,
where ed = 1 mod f (n),
59
Partial information concerning
plaintext bits
In some cryptosystems partial information about
the plaintext may be leaked by the ciphertext,
This is the case with RSA,
60
Partial information concerning
plaintext bits
Suppose y = xe mod n,with x the plaintext,Since
gcd (e,f (n)) =1,
e must be odd,So the Jacobi symbol,
Hence given y anyone can easily compute the value of the
Jacobi symbol of x,
This is a partial brake of RSA,
????????????????????? nxnxny
e
61
Rabin
? Rabin’s scheme gets its security from the difficulty
of finding square roots modulo a composite number,
This problem is equivalent to factoring,
? SUMMARY,each entity creates a public key and a
corresponding private key,Each entity A should do
the following,
? 1,Generate two large random (and distinct) primes
p and q,each roughly the same size,
? 2,Compute n = pq,
? 3,A’s public key is n; A’s private key is (p; q),
62
Rabin
? 1,Encryption,
? (a) Obtain A’s public key n,
? (b) Represent the message as an integer m in the
range [0; 1;,,, ; n – 1],
? (c) Compute c = m2 mod n,
? 2,Decryption,
? (a) Find the four square roots m1,m2,m3,and m4
of c modulo n,
? (b) The message sent was either m1,m2,m3,or
m4,A somehow decides which of these is m,
63
Rabin
? If p and q are both chosen to be congruent
3 (mod 4),then computing the four square
roots of c modulo n is easy,
pyyyyy ppp m o d)( 2/)1(2/)1(24/)1( ???? ???
?Suppose that Bob wants to decrypt y x 2
mod n,When p,q 3 mod 4,there is a
simple formula to find quadratic residues mod
n,we have,
?
?
64
The Rabin cryptosystem
Let n = pq,p,q primes with p,q 3 mod 4,Let P = C =
Zn*
and define K = {(n,p,q)},
For K = (n,p,q) define
eK(x) = x 2 mod n
dK(y) = mod n
The value of n is the public key,while p,q are the
private key,
?
y
65
Example
Suppose n = 77,
Then eK(x) = x 2 mod 77
dK(y) = mod 77
Suppose Bob wants to decrypt y = 23,
y
7m o d42)23( 224/)17( ??? ?
11m o d11)23( 324/)111( ??? ?
66
Example,continued
Using the Chinese Remainder Theorem we compute
the 4 square roots of 23 modulo 77 to be,
77m o d32,10 ??
67
Security of Rabin
? Rabin = SQRT = Factoring
– Provably secure against passive adversary
? Susceptible to chosen ciphertext attack similar to RSA
? Many RSA attacks can be also applicable to RSA
– Solved by Padding such as OAEP
? Use of redundancy
– To find exact m
68
References
? Diffie,Hellman.,New Directions in
Cryptography”,
? R.L,Rivest,A,Shamir,and L,Adleman,”A
Method for Obtaining Digital Signatures
and Public-Key Cryptosystems”,
http://theory.lcs.mit.edu/~cis/pubs/rivest/rsapa
per.ps
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.30
Public Key Cryptography
2
Public Key Cryptography
? The Inventors
– Whitfield Diffie and Martin Hellman 1976
– Ralph Merkle 1978
C = fKB(P)
Encryption with
one-way function
P = f-1KB(C,TB)
Joe
P = f-1KB(C)
Alice Bob
KB Computation of
inverse function
extremely expensive
Trap Door
One-way functions
are often based on well-
known hard problems
3
Public-Key Applications
? can classify uses 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,Only three
algorithms work well for both encryption
and digital signatures,RSA,ElGamal,and
Rabin,All of these algorithms are slow,
4
Security of Public-Key
Algorithms
? Since a cryptanalyst has access to the public key,
he can always choose any message to encrypt,
? Eve can generate a database of all possible session
keys encrypted with Bob’s public key,
? most public-key algorithms are particularly
susceptible to a chosen-ciphertext attack
? In systems where the digital signature operation is
the inverse of the encryption operation,this attack
is impossible to prevent unless different keys are
used for encryption and signatures,
5
The Knapsack Scheme
(Merkle and Hellman,1978)
? Given X = (x1,x2,…,x n ) and an integer s
? Finding B = (b1,b2,…,b n ) where bi = 0 or 1
such that
s = < X,B> = ? bi xi
? NP-Complete in general
6
Super-Increasing Sequence
? X = (x1,x2,…,x n ) is super-increasing if
?
?
?
?
1
1
i
j
ji xx
? (2,3,6,13,27,52 ) is super-increasing
7
Greedy Method
? Solve X = (2,3,6,13,27,52 ) and s = 70
? s > 52? Yes ==> b6 = 1,s1 = 70 - 52 = 18
? 18 > 27? No ==> b5 = 0
? 18 > 13? Yes ==> b4 = 1,s2 = 18 - 13 = 5
? 5 > 6? No ==> b3 = 0
? 5> 3? Yes ==> b2 = 1,s2 = 5 - 3 = 2
? b1= 1
? B = (1,1,0,1,0,1)
8
Greedy Method
? To solve,
– for i =1 down to 1
? If s?xi
– s = s-xi,bi = 1
? Else
– bi = 0
9
Knapsack Based Public-Key
? Key Generation,
– Choose a super-increasing sequence
X = (x1,x2,…,x n )
– Choose randomly two numbers Y and such that
GCD(N,Y) = 1,and
?
?
?
n
j
jxY
1
10
Knapsack Based Public-Key
? Public Key,
– K = (k1,k2,…,k n ) where ki = xi N mod Y
? Private Key,
– X,N,Y
11
Knapsack Based Public-Key
? Encryption,Suppose M = (m1,m2,…,m n )
is a binary message
– E(K,M) = <K,M> = ? ki mi
? Decryption,Given,cipher text Z,N,Y,X
– Computing N-1 mod Y
– D(Z) = GREEDY(Z N-1 mod Y,X)
12
Correctness
Z N-1 mod Y = <K,M> N-1 mod Y
= < XN,M>N-1 mod Y
= < X,M> mod Y
= <X,M>
Therefore,greedy on Z N-1 mod Y is like
greedy on <X,M> and hence we can find M
13
Example
? X = (2,3,6,13,27,52)
? Y = 105 and N = 31
– 2*31 mod 105 = 62
– 3*31 mod 105 = 93
– 6*31 mod 105 = 81
– 13*31 mod 105 = 88
– 27*31 mod 105 = 102
– 52*31 mod 105 = 37
? K = (62,93,81,88,102,37)
14
Example,Encryption
? K = (62,93,81,88,102,37)
? M = 011000110101101110
? Break up in to three sub messages
– M1 = (011000)
– M2 = (110101)
– M3 = (101110)
? E(M1) = 93 + 81 = 174
? E(M2) = 62+93 + 88+ 37 = 280
? E(M3) = 62+81+ 88+102 = 333
15
Example,Decryption
? X = (2,3,6,13,27,52),N-1 = 61
? D(M1) = GREEDY(61*174 mod 105) =
GREEDY(9) = (011000)
? D(M2) = GREEDY(61*280 mod 105) =
GREEDY(70) = (110101)
? D(M3) = GREEDY(61*333 mod 105) =
GREEDY(48) = (1011010)
? M = 011000110101010110
16
Security and Weakness
? Shamir and Zippel broken several variations
of the Knapsack protocols,
17
RSA Public Key Cryptosystem
? The Inventors
– R - Ron Rivest
– S - Adi Shamir
– A - Leonard Adleman
? The One-Way Function
– The exponentiation function y = f(x) = xe mod n
can be computed with reasonable effort,
– Its inverse x = f -1(y) is extremely difficult to
compute,
? The Hard Problem Securing the Trapdoor
– The RSA public key algorithm is based on the well-
known hard problem of factoring large numbers into
its prime factors that has been studied over many
centuries,
18
At Crypto 82
19
20
Key Generation Algorithm
? Step 1,Choose two random large prime numbers p and q
– For maximum security,choose p and q of about equal length,
e.g,512-1024 bits each,
? Step 2,Compute the product n = p·q
? Step 3,Choose a random integer e < (p-1)(q-1) ?(n)= (p-1)(q-1)
– The numbers e and (p-1)(q-1) must be relatively prime,i.e,they
should not share common prime factors,
? Step 4,Compute the unique inverse d = e-1 mod (p-1)(q-1)
– The equation d·e mod (p-1)(q-1) = 1
can be solved using the Euclidian algorithm,
21
Public Key,
n product of two primes,p and q (p and q must remain secret)
e relatively prime to (p - 1)(q - 1)
Private Key,
d e-1 mod ((p - 1)(q - 1))
Encrypting,
c = me mod n
Decrypting,
m = cd mod n
RSA Encryption
22
Checking RSA
? de ? 1 (mod ?(n))
? de = t(?(n)) + 1,t >= 1
? (me)d ? mt(?(n)) + 1 (mod n)
? (m ?(n))tm (mod n)
? (1)tm (mod n) by
Euler’s Thm,
? m (mod n)
23
? (p-1)·(q-1) = 2 · 10 = 2 · 2 · 5 = 20
Key Generation Example
? p = 3,q = 11,n = p·q = 33
? the public exponent e must be relatively
prime to (p-1)·(q-1),
i.e,it cannot contain any factors of 2 and 5
e d e·d e·d mod 20
3 7 21 1
7 3 21 1
9 9 81 1
11 11 121 1
13 17 221 1
17 13 221 1
19 19 361 1
all possible choices for
the exponents e and d
24
RSA Example
1,Select primes,p=17 & q=11
2,Compute n = pq =17× 11=187
3,Compute ?(n)=(p–1)(q-1)=16× 10=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 23× 7=161= 10× 160+1
6,Publish public key KU={7,187}
7,Keep secret private key KR={23,17,11}
25
RSA Example cont
? sample RSA encryption/decryption is,
? given message M = 88 (nb,88<187)
? encryption,
C = 887 mod 187 = 11
? decryption,
M = 1123 mod 187 = 88
26
p=43,q=59,r=pq=43*59=2537,?(r)=(p-1)(q-1)
=42*58 =2436,e=13,Determine d,de=1 mod 2436
2436 =13* 187+ 5,13= 2* 5+ 3
5= 3+ 2,3= 2+ 1
1= 3- 2, 2= 5- 3,3 =13- 2* 5
5 =2436- 13* 187
1= 3- 2= 3-（ 5- 3） = 2* 3- 5
=2*（ 13- 2* 5） - 5= 2 *13- 5* 5
=2* 13- 5*（ 2436 -13 *187）
=937* 13- 5* 2346
937* 13 ≡ 1 mod 2436
d= 937
RSA Example
27
DES vs,RSA
? RSA is about 1500 times slower than DES
– Exponentiation and modulus
? Generation of numbers used in RSA can take
time
? Test n against known methods of factoring
– http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.ht
ml
28
RSA Signature
p,q,primes,n = pq,ed = 1 mod (n),
e,n,public key,d,secret key,(factoring,n,1024 bits)
M,message,M in {0,1,..,n-1},
Signing,S = Md mod n
Verification,M = Se mod n
Key generation,p = 3,q = 5,n = 15,e = 3 => d = 3
Signing,M = 13,S = 13d mod n,=> S = 7
Verification,Checking M = Se mod n
?
29
RSA,Component Operations
? Exponentiation
– We need to do it fast
? Factorization
– Believed to be difficult (security is here)
? Finding prime numbers and testing primality
– Rabin Miller test
– New polynomial time algorithm
? http://mathworld.wolfram.com/news/2002-08-07_primetest/
? http://www.cse.iitk.ac.in/primality.pdf
30
Efficient Exponentiation of Large
Numbers
? Multiplication in finite fields
? (a·b) mod n = [ (a mod n) · (b mod n) ] mod n
? Straight exponentiation method with e-1 multiplications
? y = xe = x · x ·..,· x mod n
? Efficient exponentiation with < 2·log2 e multiplications
? based on the binary representation of the exponent
e = bk 2k + bk-1 2k-1 +,.,+ bi 2i +,.,+ b2 22 + b1 2 + b0
with bi = {0,1} and k = log2 e
y x x x x x nk k k kb b b b b? ? ? ? ? ?? ?2 2 2 21 1 2 2 1 0e j e j e j c h b g? m o d
x x ni i2 2 21? ?e j m o d
with the iterative squaring,
31
Efficient Exponentiation of Large
Numbers
? Square-and-Multiply(x,e,n)
Z=1
For i=k downto 0
Do
z=z*z mod n
if bi=1
then z=z*x mod n
Return(z)
1 2 012 2 2 2(,,,, ( ( ( ) ) ),,,, )k k kb b b bbex x x x x x???
32
Security Analysis of RSA Cryptosystem
Factoring n = pq Number theoretic Problems (key size)
Strong prime,Cycling attack,low exponent attack Other parameters
Chosen Ciphertext Attack (Simmons) Protocol failure
Timing
Attack
Differential Fault
Attack (DFA)
Side Channel
Attack (SCA)
Bleichenbacher Attack (PKCS1) Padding failure
Com
mon m
odu
lus
Broa
d c
ast
at
tac
k
Implementation
failure
Klima-Rosa attack against PGP Programming or Coding failure
SECURE RSA!
33
Factorization
? Brute force is stupid and slow
– d = 1,2,3,4,… Does d divide n?
– Factoring n = pq,If p <= q,n >= p2,so ?n >= p
– d can go high as ?n in worst case
– For n ~ 1040,1020 number of divisions
? Use structure of Zn
– p –1 method (not really used,but a good speedup)
– Pollard’s rho method
– Quadratic sieve,Number Field Sieve (NFS)
– Is there a better method out there?
34
Security of Method
? Schroeppel Factoring formula
? Calculates the number of steps needed to factor
these large prime numbers
))l n (l n (/)ln(
)ln(/)ln(ln
))( l n (
))l n ( l n (*)l n (e x p
nn
nn
n
n
nn
?
?
35
Problems with method
? 1992 Arjen Lenstra and Dan Bernstein factored
2^523 - 1 into primes,using about three weeks of
MasPar time,
? MasPar is a 16384-processor SIMD machine; each
processor can add about 200000 integers per
second.)
? used `number field sieve' it is quite a bit faster for
special numbers like 2^523 - 1
? runs in exp(O(log{1/3} n log{2/3} log n)) in any
case,
36
History of Factoring
? Year # Digits Method
? 1970 41 Continued Fraction - Morrison-Brillhart
? 1980 50
? 1982 55
? 1983 62
? 1984 72
? 1991 100 Quadratic Sieve
? 1993 120 Quadratic Sieve
? 1994 129 Quadratic Sieve (RSA predicted 40 quadrilllion
years!)
? 1996 130 Number Field Sieve (1000 MIPS yrs)
? 1999 140 Number Field Sieve (2000 MIPS yrs,8.9 CPU
yrs)
? 2000 155 Number Field Sieve (35.7 CPU yrs) (512 bits)
? 174 RSA challenge not yet factored (576 bits)
37
Strong Primes
? Factoring p and q is one of the attacks against RSA
- some properties make it harder
? gcd(p - 1,q - 1) should be small
? p - 1 and q - 1 should have large prime factors p’
and q’
? p’ - 1 and q’ - 1 should have large prime factors p”
and q”
? Both (p - 1)/2 and (q - 1)/2 should be prime
? Some factoring algorithms work better on numbers
which aren’t strong primes,others are unaffected
38
Timing Attacks
? developed in mid-1990’s
? exploit timing variations in operations
– eg,multiplying by small vs large number
– or IF's varying which instructions executed
? infer operand size based on time taken
? RSA exploits time taken in exponentiation
? countermeasures
– use constant exponentiation time
– add random delays
– blind values used in calculations
39
Finding some prime numbers
? A famous result in number theory,called the Prime
number theorem,states that the number of primes
not exceeding N is approximately N/In N,
? Hence,if p is chosen at random,the probability that
it is prime is about l/lnp,For a 512 bit modulus,we
have l/lnp = 1/ 177,
? There are 10151 primes 512 bits in length or
less.There are only 1077 atoms in the universe.The
chance that two people choose the same prime
factors for key generation is therefore near to nil !
40
Finding some prime numbers
? Easy to generate a number,but how do you know if
it’s prime?
? Rabin Miller
– If n is prime,output is always,could be”
– If n is composite,output is,composite” or,could be”
– If n is composite and,could be” is returned,the
probability of a wrong answer is <= ?
? New polynomial algorithm that can say yes/no!
41
Finding some prime numbers
? To prove that a randomly chosen number is really
prime you would have to factor it,Try small factors
(3,5,7,11,...)
? Probabilistic Primality Tests (e.g,Rabin-Miller)
? After passing 5 tests,assume a random number to be prime
is prime
composite number
0 %
100 % 0.1 %
not prime
prime number 99.9 %
random number is a Result
of
Primality
Test
42
Chosen Ciphertext Attack
? Scenario 1,To recover m from c,m = cd
? she first chooses a random number,r,such that
r is less than n,
? x = re mod n ; y = xc mod n ; t = r-1 mod n
? Eve gets Alice to sign y with her private key,
thereby decrypting y,
? u = yd mod n
? Now,Eve computes
? tu mod n = r-1yd mod n = r-1xdcd mod n = r-1rm mod
n = m
43
Chosen Ciphertext Attack
? Scenario 2,Mallory wants Trent to sign a
message m’ he otherwise wouldn’t,
? First,Mallory chooses an arbitrary value x and
computes y = xe mod n,
? Then he computes m = ym’ mod n,and sends m
to Trent to sign,
? Mallory calculates (md mod n)x-1 mod n=
(ym’ )d x-1 mod n= m’ d
44
Chosen Ciphertext Attack
? Scenario 3,Eve wants Alice to sign m3,
? She generates two messages,m1 and m2,such
that m3 ≡ m1m2 (mod n)
? If Eve can get Alice to sign m1 and m2,she can
calculate m3,
? m3d = (m1d mod n)(m2d mod n )
45
Common Modulus Attack
=> We should not use different exponents for a common modulus
Encryption
message
M
C1
C2
attacker
Message M
46
Common Modulus Attack
? Let m be the plaintext message,The two encryption
keys are e1 and e2,The common modulus is n,The two
ciphertext messages are,
? c1 = me1 mod n ; c2 = me2 mod n
? The cryptanalyst knows n,e1,e2,c1,and c2,Here’s
how he recovers m,
? find r and s,such that re1 + se2 = 1
? Assuming r is negative (either r or s has to be,so
just call the negative one r),then the extended
Euclidean algorithm can be used again to calculate
c1-1,Then
? (c1-1)-r * C2s = m mod n
47
Low Encryption Exponent Attack
? RSA encryption and signature verification are
faster if you use a low value for e,but that can
also be insecure
Fact (small message attack),e < log n/log M => Me mod = Me,
e = 3,(77)e mod 987654321 = (77)e,
0 M Me n
? We should choose enough large e,
(or We pad M with an integer T like M||T)
0 M M||T n
T
48
Related Message Attack
Encryption
message
M
C1 =Me
C2 = (aM+b)e
attacker
Message M
=> We should randomize each message M,
49
Low Decryption Exponent Attack
? Another attack,this one by Michael Wiener,
will recover d,when d is up to one quarter the
size of n and e is less than n,
Fact (Wiener),If d < (1/3)n1/4,then we can find
d for given (n,e)
50
Attack on Encrypting and
Signing with RSA
? Alice wants to send a message to Bob,
? (meB mod nB)dA mod nA
? Here’s how Bob can claim that Alice sent him m’
and not m,Realize that since Bob knows the
factorization of nB (it’s his modulus),he can
calculate discrete logarithms with respect to nB,
? m’x = m mod nB
? Then,if he can publish xeB as his new public
exponent and keep nB as his modulus,he can
claim that Alice sent him message m’ encrypted
in this new exponent
51
Semantic security
? Total break
– The adversary can determine the private key of a
public key cryptosystem,or the secret key of a
symmetric key encryption system,
? Partial break
– The adversary is able with non-negligible probability
to
? decrypt a previously unseen ciphertext (without knowing
the private/secret key),or
? determine some specific information about the plaintext
given
the ciphertext,
52
Semantic security
? Distinguishability of ciphertexts
– The adversary is able to distinguish with probability greater
than ?,
? encryptions of different plaintexts,or
? encryptions of a given plaintext and a random string,
A public key cryptosystem in which the adversary cannot
(in polynomial time) distinguish ciphertexts,under certain
computational assumptions hold,is said to achieve
semantical security,
53
Semantic security
(2) Algorithm A2,on input m0,m1,c =E(mb),guesses b (guess stage),
(1) Algorithm A1,on input pk,finds two message m0,m1 (find stage),
e,public key
m1,message
m0,message
ciphertext of m0 or m1
A1
A2 b
random encryption c=E(mb)
54
Perfect vs,Semantic security
? perfect secrecy,
– a passive adversary,even with infinite computational
resources
– can learn nothing about plaintext from ciphertext,
except its length
– Limitation,cannot be achieved unless key is as long as
message
? semantic security,polynomially bounded perfect
secrecy
– a passive adversary with poly,bounded resources can
learn nothing
55
RSA is not semantically secure
It is easy to distinguish M0e mod n and M1e
mod n for given M0,M1,
An easy way is to encrypt (M||r)e mod n for a
random integer r<n-M,
But there is no security proof for this padding
way!
56
A semantically secure public key
cryptosystem
Let m.k be positive integers,
let F a family of trapdoor one-way permutations
such that
f, {0,1} k ? {0,1} k for all f ?F,and
let G, {0,1} k ? {0,1} m be a random oracle,
Let P = {0,1} m,C = {0,1} k x {0,1} k and
K = {(f,f -1,G), f ? F },
57
A semantically secure Public Key
cryptosystem
For K = (f,f -1,G),let r ? {0,1} k be chosen randomly,
and define
eK(x) = (y1,y2) = ( f (r ),G(r ) x ),
where y1 ? {0,1} k,x,y2 ? {0,1} m
Further define
dK(y1,y2) = G (f -1(y1)) y2
Public key = (f,G),
Private key f -1,
?
58
A semantically secure Public Key
cryptosystem
In the case of the RSA cryptosystem,
take n = pq,P = C = Zn,f (x) = x
e mod n,and f
-1(x) =
xd modn,
where ed = 1 mod f (n),
59
Partial information concerning
plaintext bits
In some cryptosystems partial information about
the plaintext may be leaked by the ciphertext,
This is the case with RSA,
60
Partial information concerning
plaintext bits
Suppose y = xe mod n,with x the plaintext,Since
gcd (e,f (n)) =1,
e must be odd,So the Jacobi symbol,
Hence given y anyone can easily compute the value of the
Jacobi symbol of x,
This is a partial brake of RSA,
????????????????????? nxnxny
e
61
Rabin
? Rabin’s scheme gets its security from the difficulty
of finding square roots modulo a composite number,
This problem is equivalent to factoring,
? SUMMARY,each entity creates a public key and a
corresponding private key,Each entity A should do
the following,
? 1,Generate two large random (and distinct) primes
p and q,each roughly the same size,
? 2,Compute n = pq,
? 3,A’s public key is n; A’s private key is (p; q),
62
Rabin
? 1,Encryption,
? (a) Obtain A’s public key n,
? (b) Represent the message as an integer m in the
range [0; 1;,,, ; n – 1],
? (c) Compute c = m2 mod n,
? 2,Decryption,
? (a) Find the four square roots m1,m2,m3,and m4
of c modulo n,
? (b) The message sent was either m1,m2,m3,or
m4,A somehow decides which of these is m,
63
Rabin
? If p and q are both chosen to be congruent
3 (mod 4),then computing the four square
roots of c modulo n is easy,
pyyyyy ppp m o d)( 2/)1(2/)1(24/)1( ???? ???
?Suppose that Bob wants to decrypt y x 2
mod n,When p,q 3 mod 4,there is a
simple formula to find quadratic residues mod
n,we have,
?
?
64
The Rabin cryptosystem
Let n = pq,p,q primes with p,q 3 mod 4,Let P = C =
Zn*
and define K = {(n,p,q)},
For K = (n,p,q) define
eK(x) = x 2 mod n
dK(y) = mod n
The value of n is the public key,while p,q are the
private key,
?
y
65
Example
Suppose n = 77,
Then eK(x) = x 2 mod 77
dK(y) = mod 77
Suppose Bob wants to decrypt y = 23,
y
7m o d42)23( 224/)17( ??? ?
11m o d11)23( 324/)111( ??? ?
66
Example,continued
Using the Chinese Remainder Theorem we compute
the 4 square roots of 23 modulo 77 to be,
77m o d32,10 ??
67
Security of Rabin
? Rabin = SQRT = Factoring
– Provably secure against passive adversary
? Susceptible to chosen ciphertext attack similar to RSA
? Many RSA attacks can be also applicable to RSA
– Solved by Padding such as OAEP
? Use of redundancy
– To find exact m
68
References
? Diffie,Hellman.,New Directions in
Cryptography”,
? R.L,Rivest,A,Shamir,and L,Adleman,”A
Method for Obtaining Digital Signatures
and Public-Key Cryptosystems”,
http://theory.lcs.mit.edu/~cis/pubs/rivest/rsapa
per.ps
