Transcript William Stallings, Cryptography and Network Security 3/e

Cryptography and Network Security
Third Edition
by William Stallings
and by Lawrie Brown
Modified without permission.
Dr. M. Sakalli
RSA
Very Briefly:
- Determine two large primes, p and q.
- Find n=pq (the public modulus) and ø(n) = (p-1)(q-1). Euler’s
Totient function.
- Choose encryption key e (public key), coprime to n such that e < n.
- Compute d private key such that e.d mod(ø(n))= 1 mod(ø(n)).
- e is the public exponent and d is the private one.
• p and q never revealed, preferably destroyed
• PGP keeps p and q to speed up operations by use of the Chinese
Remainder Theorem, but they are kept encrypted.
• Public one segments the message into blocks smaller than n and
then applies modular exponentiation to encipher with your public
key,
C = Pe mod(n)
• And only key owner can decipher, P = Cd mod(n).
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
The time to carry out modular exponentation increases with the number of bits set to one in
the exponents. Encryption, an appropriate choice of e to reduce the computational burden
required C = P mod n.
Popular choices e, Fermat’s primes 3, 17 and 65537, but all primes with only two bits set.
j
Fermat’s primes: a2 H, a=2, k:0..
However, the bits in the decryption exponent d, will not be so convenient and so the time
for decryption will take longer than encryption, with the standard modular exponentiation.
Don't make mistake of trying to contrive a small value for d; it comprises security.
An alternative method of representing the d uses Chinese Remainder Theorem (CRT).
d is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of
n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT
method of decryption is four times faster overall than calculating P = Cd mod n. Precomputed values along with p and q as the private key are:
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
v = (1/q) mod p where p > q
To compute the message m for given CT
m1 = cdP mod p
m2 = cdQ mod q
h = v (m1 - m2) mod(p)
m = m2 + hq
Even though there are many steps in this procedure, the modular exponentation uses
much shorter exponents and so it is less expensive overall.
A better approach to compute modular exponentiations use Montgomery's multiplications.
Esoteric RSA Attacks. Chosen cipher-text attack
•
•
•
This attack is not a critical weakness to RSA itself, just for the protocol to be
careful in the implementation stage.
An attacker snoofing on an insecure channel in which RSA messages are passed
thr, collecting an encrypted messages CT. In here attacker simply wants to be
able to read without giving a serious factoring effort, P = Cd.
To recover PT message, attacker uses target’s public key info, e and n,
– chooses a random number, R < n, and multiplicative inverse of R, T=R-1 mod n.
– encrypts X = Re mod n
– Then computes Y = X C mod n
•
•
•
•
•
•
•
•
The attacker counts on the fact that: Target will try decipher Y, and return it back
to clarify at least since it is not clear to the target.
For attacker X=Re mod n, and R=Xd mod n
Then the party attacked, receives Y, and signs with her private-key, (which
actually decrypts y) U = Yd mod n, and sends U back.
Attacker computes TU, to eliminate random R, TU mod n = (R-1)(Yd) mod n,
TU mod n = (R-1)(Yd) mod n = (R-1)(XC)d mod n = (R-1)(RedCd) mod n
= (R-1)(RedCd) mod n = Cd mod n = M
To avoid this attack, do not sign some random document presented to you. Sign a
one-way hash of the message instead.
Avoid, low encryption key, e=3,
– M [for M < 3rdroot(N)]3 mod(N) will be equivalent to M3
Timing attack against RSA
• Exploiting computational timing differences in RSA to
recover d. Passive attack, attacker snoofing a network
and tracing the RSA operations.
• Measuring the time of each operation it takes, t, to
compute each modular exponentiation operation: M = Cd
mod n.
• Pseudo code of the attack is:
– Computing M = Cd mod n:
M0 = 1.
C0 = x.
for i=0 to length(d-1),
if (bit i of d) is 1
Mi+1 = (Mi * Ci) mod n.
else
Mi+1 = mi.
di+1 = di2 mod n.
End.
Sun-Tsu’s Chinese Remainder Thr
 To compute faster modular exponentiation (comprising security).
 States that when the moduli of a system of linear congruencies are
pairwise prime, there is a unique solution of the system modulo, the
product of the moduli.
 ax = b (mod m).
The 1st Century CE (Common Era, ~400 AD), the Chinese mathematician Sun
Tsu Suan-Ching asking the following problem:
“There are certain things whose number is unknown. When divided by 3, the
remainder is 2; when divided by 5, the remainder is 3; and when divided by
7, the remainder is 2. What will be the number of things?”
Discrete Math Kenneth H Rosen, page 186.
 x = 2 mod(3)
 x = 3 mod(5)
 x = 2 mod(7)
Let m1, m2, …, mn be (pairwise) relatively prime numbers. Then the system:
 x = a1 mod (m1) = a2 mod (m2) = …. = an mod (mn)
 Has a unique solution modulo
 M = m 1 m2 … m n .
The CRT says that only one number of x mod(3x5x7) satisfies all eqns.
x = 23 (mod 105),. x = 23 = 7*3 + 2 = 2 (mod 3),
x = 23 = 4*5 + 3 = 3 (mod 5), x = 23 = 3*7 + 2 = 2 (mod 7)
How to construct the solution in mod(M)
• 23 mod(105) = 23 + 105 n  { …, -292, -187, -82,
23, 128, 233, 338, …}
• Therefore, all these congruent numbers are
solutions of Sun-Tsu’s three equations.
– M = (πk=1:n mi) = m1m2 … mn all mk’s have to be pairwise
relatively prime.
– For each equation of x = ak mod(mk) calculate Mk = M /
mk; all mk except for mk.
– yk inverse of Mk from Mk yk = 1 mod (mk) = Mkmod(mk)yk
x = 2 mod (3) 
(5*7) y1 = 1 mod(3)  y1 =2.
x = 3 mod (5) 
(3*7) y2 = 1 mod(5)  y2 =1
x = 2 mod (7) 
(3*5) y3 = 1 mod(7)  y3 =1
– x = (a1 M1 y1 + a2 M2 y2 + a3 M3 y3) = 233 = 23 mod(105)
Why does this work? (without going into detail)
Suppose I take the solution x and “mod” it by m1:
M1y1 is equal to a1, since M1y1 = 1 mod (m1).
M2y2, M3y3 , …, every other term is zero mod(m1), since MK is a multiple of m1.
x = a1M1y1 + a2M2y2 + … + anMnyn.
= 2 (5*7) 2 + 3 (3*7) 1 + 2 (3*5) 1
But it would be true for any of the mk. Therefore, x satisfies all of the
equations.
Ancient Chinese Problem:
A band of 17 pirates stole a sack of gold coins.
When they tried to divide the fortune into
equal portions, 3 coins remained. In the
ensuing brawl over who should get the extra
coins, one pirate was killed. The wealth was
redistributed, but this time an equal division
left 10 coins. Again an argument developed in
which another pirate was killed, but now the
fortune could be evenly distributed.
What was the least number of coins which could have been stolen?
What are all possible numbers of coins which could have been stolen?
If x is the number of coins, it has to satisfy the following modular equations:
x = 3 mod (17)
x = 10 mod (16)
x = 0 mod (15)
These numbers are relatively prime, so the Chinese Remainder Theorem says
there IS a solution mod 17x16x15 = 4080.
It might have been possible that there is NO SOLUTION.
Write down the equations for yk:
x = 3 (mod 17)

(16 . 15) y1 =1 (mod 17)
x = 10 (mod 16) 
(17 . 15) y2 = 1 (mod 16)
x = 0 (mod 15)

(17 . 16) y3 = 1 (mod 15)
240 y1 =1(mod 17)
255 y2 =1(mod 16)
272 y3 =1(mod 15)
Solve the equations for yk by whatever way is easiest (brute force or by finding
inverses):
(16 . 15) y1 = 1 (mod 17)  2 y1 = 1
 y1 = 9 (mod 17)
(17 . 15) y2 = 1 (mod 16)  15 y2 = 1
 y2 = 15 (mod 16)
(17 . 16) y3 = 1 (mod 15)  2 y3 = 1
 y3 = 8 (mod 15)
Construct the solution x (mod 17x16x15):
x
= a1M1y1 + a2M2y2 + … + anMnyn.
= 3 . (16 .15) . 9 + 10 . (17 . 15) . 15 + 0 . (17 . 16) . 8
= 44730 = 3930 (mod 105).
3930
= 231 . 17 + 3
= 3 (mod 17)
= 245 . 16 + 10 = 10 (mod 16)
= 262 . 15
= 0 (mod 15)
Therefore the solution works
What is the smallest number of coins which the pirates could have stolen? 3930.
What other possible numbers of coins could the pirates have stolen?
Any number which satisfies all of those equations is equal to 3930 (mod 4080).
Therefore, Any number of the form 3930 + 4080n could have been stolen.
N = { 3930, 8010, 12090, 16170, …}
Systems of Linear Modular Equations:
Suppose a system of n linear modular equations :
a1x = b1 (mod m1)
a2x = b2 (mod m2)
….
anx = bn (mod mn)
From the last section how to solve each equation aix = bi (mod mi) individually.
(when the solution actually exists).
a1x = b1 (mod m1)
x = c1 (mod m1)
a2x = b2 (mod m2)
x = c2 (mod m2)
….
….
anx = bn (mod mn)
x = cn (mod mn)
Solve the following set of simultaneous congruences:
i)
x = 5 (mod 6)
iii)
2x = 1 (mod 5)
x = 4 (mod 11)
3x = 9 (mod 6)
x = 3 (mod 17)
4x = 1 (mod 7)
5x = 9 (mod 11)
ii)
x = 5 (mod 11)
x = 14 (mod 29)
x = 15 (mod 21)
Question iii is a bit harder than I would probably ask on a test. How badly do you want
an A+?
Homeworks:
Answer Brahmagupta’s question: (7th century AD)
An old woman goes to market and a horse steps on her basket
and crashes the eggs. The rider offers to pay for the damages and
asks her how many eggs she had brought. She does not
remember the exact number, but when she had taken them out
two at a time, there was one egg left. The same happened when
she picked them out three, four, five, and six at a time, but when
she took them seven at a time they came out even. What is the
smallest number of eggs she could have had?
What other possible number of eggs could she have?
[Hint: x = 1 (mod 2,3,4,5,6), x = 0 (mod 7).]
Chinese Remainder Theorem
• used to speed up modulo computations
• working modulo a product of numbers
– eg. mod M = m1m2..mk
• Chinese Remainder theorem lets us work in each
moduli mi separately
• since computational cost is proportional to size, this
is faster than working in the full modulus M
• can implement CRT in several ways
• to compute (A mod M) can firstly compute all (ai
mod mi) separately and then combine results to get
answer using:
Euler Totient Function ø(n)
• For p prime, Fermat;s little thr says
a(p) = a mod(p)  a(p-1 = 1 mod(p).
• a does not have a p as its product.
• Its converse is not true, for example p=11*31
• The Sieve of Eratosthenes (κόσκινον Ἐρατοσθένους)
• Euler generalizes Fermat’s thr,
• aø(n)mod N = 1, where gcd(a,N)= 1, coprimes to n
form a group
• reduced set of residues is those numbers (residues) which
are relatively prime to n
– eg for n=10, complete set of residues is {0,1,2,3,4,5,6,7,8,9} 
reduced set of residues is {1,3,7,9}
• to compute ø(n): exclude every fold of its primes.. and count
excluded ones..
• For coprimes of p.q,
– for p (p prime)
ø(p) = p-1
– for p.q (p,q prime)
ø(p.q) = ø(q) ø(q)=(p-1)(q-1)
Euler Totient Function ø(n)
• Consider the # of integers that are not relatively prime in
{0…(pq-1)}  {p,2 p,..., (q-1)p}, and {q,2 q,..., (p-1)q},
therefore
– ø(p.q)= p.q-(p-1)-(q-1)-1 = p.q-p-q+1 = (p-1)(q-1)
• eg.
– ø(37) = 36
– ø(21) = (3–1)×(7–1) = 2×6 = 12
• For p prime, Φ(p) = p-1; and from Fermat’s thr
a(p-1) = 1 mod(p)  a(p) = a mod(p).
• eg.
–
–
–
–
a=3;n=10; ø(10)= (5-1)(2-1)=4;
hence 34 = 81 = 1 mod 10
a=2;n=11; ø(11)=10;
hence 210 = 1024 = 1 mod 11
Euler’s theorem
• Corollary, n=pq, both primes, and 0<m<n,
mΦ(n) = m(p-1)(q-1) =1 mod(n) holds.
If gcd(m, n) =1, by virtue of Euler’s thr it holds.
Suppose gcd(m,n) ≠ 1, then n= pq, means that, either p or q must divide
m. If m=c1p, (or m=c2q, where c is integer and c>0) then m and n cannot
be relative to each other, therefore gcd(m,n) ≠ 1.
• Suppose p, q are primes, m = cp, and gcd(m, q)=1, from Euler’s thr
mΦ(q)
= 1 mod(q),
[mΦ(q)]Φ(p) mod(q) = 1 mod(q)
mΦ(n) mod(q) = 1 mod(q)
mΦ(n) mod(q) = 1 + kq, k is an arbitrary constant,
mΦ(n)+1
= m + mkq = m + kcpq = m + kcn
mΦ(n)+1
= m mod(n)
• Or an alternative way,
mkΦ(n)+1 =[[mΦ(n) ]k + 1 ]mod(n)= [1k m] mod(q) =m mod(n)
• Factoring a number n: n=a b c
• Relatively hard when compared to multiplying
the factors together to generate the number
• Prime factorisation of a number n
– eg. 91=7 13; 3600=24 32 52
• two numbers are relatively prime to each other if..
• Conversely; gcd  the common least powers of
prime factorizations.
– 300=21 31 52 18=21 32 hence GCD(18,300)=21 31
50=6
• Fermat’s Little Theorem: ap-1 = 1 mod p = 1
where p is prime and naturally gcd(a, p)=1
Primality Testing
•
traditionally sieve using trial division
– ie. divide by all numbers (primes) in turn less than the square root of the number
– only works for small numbers
•
Wilson’s test (p-1)!=-1mod(p), in proof pair numbers with their inverse,
a^2=1mod(p)p|a^2=(a-1)(a+1)..
•
Miller Rabin Algorithm based on Fermat’s Theorem a(n-1) =1 mod(n) = 1 if n is
prime.
•
Consider an odd number n>2, then n-1 is even number, therefore equal to 2kq
with k>0, q must be odd. Keep dividing n-1 by 2, k divisions, you’ve got the q,
determine a number 1<a<n-1, compute 2kq power of the number a, and
check the equality to n-1 (line 5), or to 1 (line 3):
•
TEST (n) is:
1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq;
2. Select a random integer a, 1<a<n–1;
3. if aq mod n = 1 then return (“maybe prime");
4. for j = 0 to k – 1 do
j
5. if (a2 q mod n = n-1)
then return(" maybe prime ")
6. return ("composite")
Primality Testing
If n is prime there is a smallest value of j, 0jk, such that
j
a2 q mod n = 1. ???
For j=0,
For 1jk,
aq-1 = 0,
jq
2
a mod(n)
(j-1)q
2
(a
or
n|(aq-1).
=1
(j-1)q
2
(a
mod(n) - 1) *
mod(n) + 1) = 1
n divides either side, by assumption j is the smallest such
(j-1)q
2
that n does not divide (a
mod(n)-1), therefore
(j-1)
q mod(n)-1).
n|(a2
Or equivalently a^(2(j-1)q)mod(n)=(-1)mod(n)=n-1; line5.
Probabilistic Considerations
• Millar-Rabin test returns inconclusive for (n-1)/4 < ¼
• if Miller-Rabin returns “composite” the number is definitely
not prime otherwise is a prime or a pseudo-prime chance
it detects a pseudo-prime is < ¼
• Therefore if test returns inclusive t times in succession ..
then probability n is prime is 1-4-t…
• Prime distribution: Considering distribution of the primes,
“prime number theorem states that the primes near n are
spaced on the average one every ln(n) integers”, so the is
on the order of ln(n), even integers and fold of 5 are
rejected.. So, 0.4ln(n), for example if the order of prime
number is 2200, 0.4ln(n)=55 trials. Closely located
ones, 1.000.000.000.061, 1.000.000.000.063 are primes.
Probabilistic Considerations of Miller-Rabin
• n=29, 2kq=28= 22 7, k=2;
• a=10;
– j=0, 107mod(29)=17, neither 28, nor 1..
– j=1, (107)2 mod(29)=28, inconclusive, may be pr..
• a=2,
– j=0, 27mod(29)=12,
– j=1, 214mod(29)=28, inc..
• For all a’s this will give inconclusive, so n is a prime..
• n=13*17=221, 2kq=220= 22 55, k=2;
• a=5;
– j=0, 555mod(221)=112..
– j=1, (555)2 mod(221)=168, n returns composite..
• But if a would have been chosen as 21,
– j=0, 217mod(221)=200..
– j=1, 2114mod(221)=220, returns inclusive, which points 221 as prime..
• In fact of the 220 integers, 1, 21, 47, 174, 200, 220 return inc..
Primitive Roots
Primitive Roots
• From Euler’s theorem have aø(n)mod n=1
• consider ammod n=1, and (a, n) relative prime
GCD(a,n)=1
– at least one positive m<n satisfying ammod n=1, for example m =
ø(n) or may be smaller, this is called the order of a (mod n)..
– once powers reach m, cycle will repeat
• if smallest is m= ø(n) then corresponding a is called a
primitive root
• To check if a number x is primitive root, it suffices to check
xm=1 mod p, ***
– the order of any x coprime to p has to be a divisor of (p − 1) since xp1=1 mod p, *** following words are not clear yet to me too but the
statement written is valid** --- if n is not a primitive root, then there
exists a strict positive divisor m of p-1, such that p-1, xm=1 mod p,
so there the statement we made suffices.. ---
• if p is prime, then successive powers of a "generate" the
group mod p
Primitive Roots
• Example: from previous table,
p=19, p-1 = 2.32, divisors 1, 2, 3, 6, 9, 18,
check a=10, 102=5, 103=12, 103=5, 106=11,
109=18, 1018=1 mod(19),
so the smallest power of x, such that xm=1 mod p is 18,
hence ordp(a) = ord19(10)=18.
• Check if the rule applies to a=5,
53=11, 59=1,.. Then will recycle the
numbers periodically since 1018= 1 mod(19)
.
Primitive Roots
• Similarly, you can do the rest of the homework by yourselves. The
complete list of primitive roots is:
–
–
–
–
–
–
–
mod 3 : 2
mod 5 : 2, 3
mod 7 : 3, 5
mod 11 : 2, 6,
mod 13 : 2, 6,
mod 17 : 3, 5,
mod 19 : 2, 3,
7, 8
7, 11
6, 7, 10, 11, 12
10, 13, 14, 15
• Once you have found '(p − 1) many primitive roots mod p, you are
done, because mod p there are exactly '(p − 1) distinct primitive roots.
Discrete Logarithms or Indices
• Input: p - prime number, a- primitive root of p, b - a residue mod p.
• Goal: Find k such that ak = b( mod p). (In other words, find the position of
y in the large list of {a, a2, . . . , aq-1}.
• 14 is a primitive root of 19.
• The powers of 14 (mod 19) are in order: 14 6 8 17 10 7 3 4 18 5 13 11 2
9 12 16 15 1
• For example L14(5) = 10 mod 19, because 1410 = 5( mod 19).
• the inverse problem to exponentiation is to find the discrete logarithm
of a number modulo p
• that is to find x where ax = b mod p
• written as x=loga b mod p or x=inda,p(b)
• if a is a primitive root then always exists, otherwise may not
– x = log3 4 mod 13 (x st 3x = 4 mod 13) has no answer
– x = log2 3 mod 13 = 4 by trying successive powers
• whilst exponentiation is relatively easy, finding discrete logarithms is
generally a hard problem
Diffie-Hellman, 1976, Section 10.2 of Stallings
• Based on the difficulty of computing discrete logarithms of large numbers.
• No known successful attack strategies.
• Two numbers public: a prime p, a primitive root q of P.
• User A chooses a random integer XA < q and computes YA = qXamod(p) for
secret A (known only to itself) and similarly user B chooses XB < q and
computes YB = qXbmod(p)..
• Each exchanges YA and YB, while XA, XB remains private
• Parties A and B compute K = YBXamod(p) and K= YAXbmod(p), respectively,
• K= (YB)Xa mod p = (qXb)Xa mod p = (qXa)Xb mod p = (YA)Xb mod p
• Attacking the secret key of user A for example will require opponent to
calculate
XA= indb,p(YA)= dlogb,p(YA)or the other way around.
• Example p= 353 and a primitive root of 353, q = 3. Suppose A and B choose
XA=97, XA= 233.
• YA = 397mod(353) = 40, YB = 3233mod(353) = 248
• K= 160.. Attacker must 3Xamod(353) = 40 or 3Xbmod(353)=248..
• RSA is more convenient because there is no need to distribute keys.
• DES is within two orders of magnitude faster.
• A viable combination is to distribute the secret keys using RSA, and
then, for the bulk data to use DES.
• Similar combination is implemented in the Pretty Good Privacy
(PGP) method.
• A number of public-key ciphers are based on the use of an abelian
group. For example, Diffie-Hellman key exchange involves
multiplying pairs of nonzero integers modulo a prime number p.
Keys are generated by exponentiation over the group, with
exponentiation defined as repeated multiplication.
Elliptic Curves Chapter 10.3 and 10.4..
• The same level of security but shorter key are possible.
• An equation in two variables. For cryptography, the variables
and coefficients are restricted to elements in a finite field,
which results in the definition of a finite abelian group.
• Elliptic curves are not ellipses. They are so named because
described by cubic equations, similar to the circumference of an
ellipse. In general, cubic equations for elliptic curves take the
form of y2 + axy + by = x3 + cx2 + dx + e..
• Limiting attention (Stallings) to y2 = y3 + ax + b is sufficient. y
= sqrt(y3 + ax + b)
El Gamal public-key cryptosystem
•
•
•
•
•
Secure against CT only attacks.
Each party (say Bob) chooses the following parameters.
p, large prime number, q- primitive root of p, made public.
a random a {2, 3, . . . , p − 1}, private
¯= qa(mod p), made public.
• Encrypting: Choose a random k {1, 3, . . . , p − 1} (a).
Suppose message is a number x < p.
• Epublic−k(x) = {qk(mod p), x · ¯k( mod p)}.
• Two numbers, the first one hides k, and the second one the
message.
• Decrypting: Dprivate−k(y1, y2) = y2 · (y1a)-1(mod p)
• y2 · (y1a)-1 = x · ¯k(qak)-1 = x · = x · (qak) · (qak)-1(mod p) = x
• Check example next slight.
El Gamal public-key cryptosystem
• Example:
– p = 43, q=3 primitive root of p, Alice’s choice of secret
key is a=7,
– ¯ = qa( mod p) = 37( mod 43) = 37,
– Bob picks a random key k=26, and his message x=14,
y1= 326 = 15 mod(43), y2= 3726 14 = 31 mod(43),
– CT= {15, 43}
large prime number, q- primitive root of p, made public.
• Alice: 31 · (157)-1 = 14( mod 43).
• El Gamal encryption is randomized, depends on
random k. So the same x has many encryptions.