Transcript security engineering - University of Sydney

computer and network security
matt barrie
<[email protected]>
CNS2010
handout 8 :: introduction to number theory
1
introduction to number theory
•
Motivation:
– To understand the security of Diffie-Hellman
– To understand asymmetric crypto (e.g. RSA)
– Slides 1..9 are background
•
Notation:
Z
Z+
a|b
p, q
•
the set of all integers
the set of all non-negative integers
a divides b i.e. there exists c є Z such that b=ac
-3|18, since 18 = (-3)(-6)
173|0, since 0 = (173)(0)
will be reserved for prime numbers
The prime decomposition of n є Z+ is n = Π piei where ei є Z+
– in other words, n = p1e1p2e2p3e3 … pkek (note ei can be zero)
CNS2009
handout 8 :: introduction to number theory
2
groups
•
A Group (G, *) consists of a set G with a binary operation * on
G satisfying:
– The group operation is associative i.e. a*(b*c) = (a*b)*c
– There is an element 1 є G called the identity element
• a * 1 = 1 * a = a for all a є G
– For each element a є G, there exists and element a-1 є G, called the inverse
of a, such that a * a-1 = a-1 * a = 1
•
A Group is commutative, if furthermore:
– a * b = b * a for all a, b є G
•
Example: the set of integers Z with addition forms a group
– The identity element is 0 and the inverse of a is -a
CNS2009
handout 8 :: introduction to number theory
3
rings
•
A ring (R, +, x) consists of a set R with two binary operations
arbitrarily denoted + (addition) and x (multiplication) on R
where:
– (R, +) is a commutative group
– The operation x is associative i.e. a x (b x c) = (a x b) x c
– There is a multiplicative identity denoted 1, with 1 ≠ 0 such that 1 x a = a x
1 = a for all a є R
– The operation x is distributive over +, that is:
• a x (b + c) = (a x b) + (a x c) and
• (b + c) x a = (b x a) + (c x a)
•
The ring is a commutative ring if:
– a x b = b x a for all a, b є R
•
Example: the set of integers Z with addition and multiplication
forms a commutative ring
CNS2009
handout 8 :: introduction to number theory
4
fields
•
A field is a commutative ring in which all non-zero elements
have inverses.
•
Fact: Zp is only a field if p is a prime number.
•
For example, Zn = <0, 1, … n-1> where n is a composite
(product of two primes) is not a field (it is a ring).
•
e.g. Z6 = <0,1,2,3,4,5>
2 x 3 = 0 (mod 6)
2-1 does not exist so Z6 is not a field
– no element e such that 2 x e = 1 (mod 6)
CNS2009
handout 8 :: introduction to number theory
5
gcd, lcm
•
The greatest common divisor, gcd(a,b) of a, b є Z is the largest
possible integer, d, such that d|a and d|b.
– e.g. gcd(12, 18) = 6
•
The least common multiple, lcm(a,b) of a, b є Z is the smallest
integer, m, such that a|m and b|m.
– e.g. lcm(12, 18) = 36
•
In terms of prime factors, if a = Π pidi and b = Π piei then
gcd(a,b) = p1min(d1,e1) p2min(d2,e2) ... pkmin(dk,ek) = Π pimin(di,ei)
lcm(a,b) = p1max(d1,e1) p2max(d2,e2) ... pkmax(dk,ek) = Π pimax(di,ei)
CNS2009
handout 8 :: introduction to number theory
6
euclidean algorithm
•
Suppose we wish to find gcd(a, b) with a ≥ b
•
Algorithm:
while b ≠ 0 do:
set r ← a mod b, a ← b, b ← r
return a
•
Example: gcd(4864, 3458):
4864
3458
1406
646
114
76
=
=
=
=
=
=
1
2
2
5
1
2
.
.
.
.
.
.
3458 + 1406
1406 + 646
646 + 114
114 + 76
76 + 38
38 + 0
Hence gcd(4864, 3458) = 38
CNS2009
handout 8 :: introduction to number theory
7
extended euclidean algorithm
•
EEA: extended to find u,v such that gcd(a, b) = ua + vb
Algorithm:
INPUT: two non-negative integers a, b with a ≥ b
OUTPUT: d = gcd(a, b) and integers x, y such that ax + by = d
(1) If b = 0 then set d ← a, x ← 1, y ← 0 and return (d, x, y)
(2) Set x2 ← 1, x1 ← 0, y2 ← 0, y1 ← 1
(3) While b > 0 do :
q ← floor(a/b), r ← a - qb, x ← x2 - qx1, y ← y2 - qy1
a ← b, b ← r, x2 ← x1, x1 ← x, y2 ← y1, y1← y
(4) Set d ← a, x ← x2 , y ← y2 and return (d, x, y)
CNS2009
handout 8 :: introduction to number theory
8
finite fields, Zn and Zp
•
Again, Zp = <0, … p-1> where p is prime is a called a field
– In a field we can add, multiply, take inversions, and the commutative and
distributive laws hold.
•
If a and b are integers, then a is said to be congruent to b mod
p, if p divides (a-b) i.e. p|a-b
a ≡ b (mod p)
•
We can say b is a residue of a (mod p)
•
The inverse of a є Z is b є Z such that
ab ≡ 1 (mod p)
•
We can find a-1 by noting that gcd(a, p) = 1, since p is prime.
CNS2009
handout 8 :: introduction to number theory
9
inverses
•
So by the Extended Euclidean Algorithm (EEA) we can find u, v
such that
ua + vp = 1
therefore
ua = -vp + 1
i.e.
ua ≡ 1 (mod p)
so
u (mod p) = a-1 є Zp
•
Again Zn = <0, 1, … n-1> where n is a composite (product of
two or more primes) is a ring.
•
If a є Zn is such that gcd(a, n) = 1, then we say a is relatively
prime to n. Then, by the EEA, there exists u є Z (the inverse)
where :
ua ≡ 1 (mod n)
CNS2009
handout 8 :: introduction to number theory
10
Z*, Φ(n)
•
Define Zn* = {a є Zn | gcd (a, n) = 1}
– i.e. all the integers of Zn relatively prime to n (n is composite)
– otherwise known as the reduced set of residues (mod n)
– in other words, all the elements which have inverses
•
Since 0 is not є Zn*, Zn* forms a multiplicative group
– a,b є Zn* implies ab є Zn*
– a є Zn* implies a-1 є Zn*
•
We define Euler’s (“Oiler”) Totient Function Φ(n) as the
number of elements in this set Zn*
– If p is prime, then Φ(p) = p - 1
– If gcd(m, n) = 1, then Φ(mn) = Φ(m) . Φ(n)
CNS2009
handout 8 :: introduction to number theory
11
finding inverses with euler’s theorem
•
Euler’s theorem states that for any a є Zn
– (a is relatively prime to n)
aΦ(n) ≡ 1 (mod n)
•
This is Euler’s generalisation of Fermat’s little theorem
– If p is prime and a is a positive integer not divisible by p then
ap-1 ≡ 1 (mod p)
•
Now finding an inverse a-1 mod n is easy:
x = aΦ(n)-1 mod n
•
Example: what is the inverse of 5 (mod 7)?
– Since 7 is prime, Φ(n) = 7-1 = 6
– x = 56-1 mod 7 = 55 mod 7 = 3
CNS2009
handout 8 :: introduction to number theory
12
order, generators
•
An element, a є Zn* has order d if d is the smallest positive
integer such that:
ad ≡ 1 (mod n)
•
It may be that all of the elements in Zn* can be obtained as
powers of a single element, g, called the generator or primitive
element of Zn* :
Zn* = <1, g, g2, …., gΦ(n)-1>
= <g>
•
If it has a generator, we say Zn* is a cyclic group.
•
It may be shown that Zn* is a cyclic group if and only if n = 2, 4,
pa, 2pa for odd primes p
CNS2009
handout 8 :: introduction to number theory
13
exponentiation in Zn
•
Can be done efficiently with repeat-and-square
•
Algorithm:
t
INPUT: a є Zn and integer 0 ≤ k < n
(where k is t-bits in binary = Σi=0 ki2i)
OUTPUT: ak mod n
(1)
(2)
(3)
(4)
b ← 1. If k = 0 then return (b)
A ← a
If k0 = 1 then b ← a
for i = 1 .. t do
A ← A2 mod n
if ki = 1 then b ← A . b mod n
(5) return b
CNS2009
handout 8 :: introduction to number theory
14
computing in Zp
•
Let p be a large prime (~300 digits or 1024 bits).
•
The following are easy to do in Zp :
–
–
–
–
–
–
•
Generate a random element.
Addition and multiplication.
Computing gr mod p, even if r is large.
Inverting an element.
Solving linear systems.
Solving polynomial equations of degree d in polynomial time d.
Problems believed to be hard:
– Let g be a generator of Zp. Given x є Zp find r such that x = gr mod p.
– This is known as the discrete log problem.
CNS2009
handout 8 :: introduction to number theory
15
computing in Zn
•
Let’s now consider Zn where n is instead a large composite
(~1024 bits) which is a product of two primes (~512 bits).
•
The following are easy to do in Zn :
–
–
–
–
–
•
Generating a random element.
Addition and multiplication.
Computing gr mod n, even if r is large.
Inverting an element.
Solving linear systems.
Problems believed to be hard if the factorisation of n is
unknown:
– Finding prime factors of n.
– Computing the square root (as hard as factoring n).
– Solving polynomial equations of degree d.
CNS2009
handout 8 :: introduction to number theory
16
hard problems in Zn
• Discrete Log Problem
– Let g be a generator of Zn*.
– Given x є Zn* find r such that x = gr mod n.
– This is known as the discrete log problem.
•
Diffie-Hellman Problem
– Let g be a generator of Zn*.
– Given x, y є Zn* where x = ga and y = gb, find gab.
– This is known as the Diffie-Hellman problem.
CNS2009
handout 8 :: introduction to number theory
17
discrete log problem revisited
•
Given:
Consider the finite field Zp* = <g>
Let g є Zp be the generator, i.e. Zp* = <g, g2, …, gp-1>
gp-1 ≡ 1 mod p
•
The discrete log problem asks how to find r given gr
•
Example : Z11* = <1, 2, 3, …, 10>
– Consider :
g = 2, g2 = 4, g3 = 8, g4 = 5, g5 = 10 = -1
g6 = 9, g7 = 7, g8 = 3, g9 = 6, g10 = 1 (thus 2 is a generator)
– Now consider
g = 3, 32 = 9, 33 = 5, 34 = 4, 35 = 1
thus 3 is not a generator of Z11* - order 5 not order 10
CNS2009
handout 8 :: introduction to number theory
18
diffie-hellman key exchange
Alice
p, g, ga (mod p)
Bob
gb (mod p)
Computes gab (mod p)
Computes gab (mod p)
Eve ???
Only knows p, g, ga, gb
CNS2009
handout 8 :: introduction to number theory
19
diffie-hellman key exchange
•
Protocol:
Consider the finite field Zp* = <g>
Let g є Zp be the generator, i.e. Zp* = <g0, g, g2, …, gp-1>
gp-1 ≡ 1 mod p
g and p are public information
(1)
(2)
(3)
(4)
(5)
=>
CNS2009
Alice
Alice → Bob
Bob
Bob → Alice
Alice and Bob
: Alice chooses a random large integer a є Zp
: Alice sends Bob ga (mod p)
: Bob chooses a random large integer b є Zp
: Bob sends Alice gb (mod p)
: compute gab
: Alice computes (gb)a = gab (mod p)
: Bob computes (ga)b = gab (mod p)
Alice and Bob now share secret gab
handout 8 :: introduction to number theory
20
strength of diffie-hellman
•
The strength of Diffie-Hellman is based upon two issues:
– given p, g, ga, it is difficult to calculate a (the discrete logarithm problem)
– given p, g, ga, gb it is difficult to calculate gab (the Diffie-Hellman problem)
– we know that DL → DH but it is not known if DH → DL
•
Essentially, the strength of the system is based on the
difficulty of factoring numbers the same size as p.
CNS2009
handout 8 :: introduction to number theory
21
attacks on discrete log
Question:
– Given: G=<g>, gn = 1, y = ga where 1≤ a ≤n-1
– Find: a = logg(y)
•
Most obvious algorithm: exhaustive search
Algorithm:
– Compute g, g2, g3, … until we find ga = y (i.e. a)
Problem:
– computation is O(n)
– i.e. slow
CNS2009
handout 8 :: introduction to number theory
22
attacks on discrete log
Question:
– Find a = logg(y)
•
•
Baby-step giant-step (square root) algorithm
A time-memory tradeoff of the exhaustive search method.
Algorithm:
Let m = floor(√n)
Create a table containing j, gj (j = 0 .. m-1)
Sort the table by gj
Compute g-m
Set γ = y
for i = 0 .. m-1
1. if γ is in the table then break;
2. Else set γ = γ g-m and loop
output a = j + im
CNS2009
handout 8 :: introduction to number theory
23
example of baby-step giant-step
•
•
Let p = 113, g = 3 is a generator of Z113* of order n= 112
Question: Find log357 :
Set m ← floor(√112) = 11
j
0 1 8 2 5 9 3 7 6 10 4
3j mod 113
1 3 7 9 17 21 27 40 51 63 81
Baby Step
Now g-1 = 3-1 mod 113 = 38 as (38 . 3) = 1 mod 113
So g-m = 3811 mod 113 = 58
Next γ = y g-mi for i = 0, 1, 2 …
i
0
1
2 3 4
5 6 7 8 9
γ = 57.58i mod 113
57 29 100 37 112 55 26 39 2 3
Giant Step
Since y g-9m = 3 is in the table (g1),
we output a = j +im = 1 + 9.11 = 100 i.e. 57 = 3100 or log357 = 100
CNS2009
handout 8 :: introduction to number theory
24
attacks on discrete log
•
Baby-step giant-step is a time-memory tradeoff of the
exhaustive search method (which is obviously O(n)).
–
–
–
–
•
Requires O(√n) storage for group elements
Requires O(√n) multiplications to construct
Requires O(√n log n) to do sort of table
Loop takes O(√n) multiplications and O(√n) table lookups
Under the assumption that group multiplication takes longer
than log n comparisons
– the running time complexity of baby-step giant-step is O(√n)
– the storage complexity is O(√n)
•
Pollard-rho is another, more efficient attack on DL.
CNS2009
handout 8 :: introduction to number theory
25
references
•
Handbook of Applied Cryptography
– read §1, §2-2.4.4, §2.5 - 2.5.3
•
Stallings
– §7
CNS2009
handout 8 :: introduction to number theory
26