Transcript ECE578-Class 6_GD_2010

ECE578:
Cryptography
6: Primes, Galois Fields, ECC, and
the Discrete Logarithm Problem
Professor Richard A. Stanley, P.E.
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #1
Map to the Endpoint
Class # Date
Topic
6
5/10
7
8
5/17
5/24
Primes, Galois fields, ECC, discrete
logarithm problem
Advanced Encryption System
Authentication, Signatures, PKI
9
10
5/31
6/7
6/14
No class—Memorial Day
Student presentations; take-home final
Final exam due by email
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #2
Review: Asymmetric Key Protocol
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #3
RSA Setup
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #4
En/Decryption
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #5
Asymmetric Key Summary
• Public key, or asymmetric cryptosystems
add a new dimension to cryptography
• The difficulty of attacking these systems is
believed to be equivalent to factoring, but
this has not been formally proven
• Asymmetric cryptography is slower than
symmetric cryptography, thus hybrid
systems are commonly used
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #6
The Problem With Assumptions
• As you have seen from the homework, it was
assumed that hash functions required
approximately 269 operations to create a collision,
and systems were based on that
• Now, we discover that as few as 28 operations may
be required, a reduction in complexity of 261  2 x
1018
• What does this mean for asymmetric
cryptography?
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #7
Prime Numbers
• Essential to some forms of asymmetric key
cryptography, as they underlie the key
generation
• Finding primes is difficult
– Database approach
– Generate primes
– Test for primality
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #8
The Search for Prime Numbers
• Before computers, a
44-digit prime was
found in 1951 =
(2148+1)/17
• That same year, a
computer found a 79digit prime
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #9
Database of Primes?
• Infinitely many primes, as proven by Euclid
long ago
• 5000 largest known primes take up a text
file of about 460 KB
• Storable, searchable
• Not fast
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #10
Construct a Prime?
• A formula which will generate all of the primes?
– Determine the nth prime, for any value of n?
– A few tantalizing pattern fragments:
• 31, 331, 3331, 33331, 333331, 3333331, and 33333331 are all
prime but the next number in this sequence: 333333331 is not
prime; it can be factored as 17 times 19607843
• n2 + n =41 produces prime numbers for n = 0, 1, 2, ..., 40; but
fails at n = 41.
• There is no polynomial that produces only prime
numbers as values.
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #11
One Process
•
•
•
•
Start with the number 2, the first prime
Keep a list of new primes as they are discovered
Examine each positive integer in turn
Test each integer to see if it is divisible by any of
the primes in the list with zero residue
– If yes, then the new number is not prime
– If no, then it is prime, and we add it to the list of primes
• Do-able, but slow (because most integers are not
prime)
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #12
Fermat’s Little Theorem
• If p is a prime and if a is any integer, then ap = a
(mod p). In particular, if p does not divide a, then
ap-1 = 1 (mod p)
• Test for compositeness:
– Given n > 1, choose a > 1 and calculate an-1 modulo n
– If the result is not 1 modulo n, then n is composite
– If the result is 1 modulo n, then n might be prime
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #13
Mersenne Numbers
• A Mersenne number is a number that is one less
than a power of two, e.g. Mn = 2n − 1
• A Mersenne prime is a Mersenne number that is
a prime number
– As of August 2008, only 45 Mersenne primes are
known; the largest known prime number (243,112,609−1)
is a Mersenne prime of 12,978,189 digits
– In modern times the largest known prime has nearly
always been a Mersenne prime
• If Mn is a Mersenne prime, the exponent n itself
must be prime
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #14
What Good Are They?
• Mersenne primes are used in some PRNGs
• Finding new Mersenne primes could lead to
better pseudorandom number generation
• The search for new Mersenne primes is
time-consuming and has become somewhat
of a fad
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #15
To Factor n in RSA Cryptography…
• Why not just keep a database of all known
products of all known primes and search for
n?
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #16
Other Approaches?
• Many of them
– e.g. Yaschenko’s book on cryptography
• Search continues for practical and fast way
to construct primes
• Corollary is search for primality tests that
are also fast and efficient
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #17
Galois Fields
• A Galois Field is a field of finite order
• Notation: GF(n) = Galois Field of order n
• Named in honor of Évariste Galois
– French mathematician (1811-1832)
– Laid foundations for this branch of abstract
algebra
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #18
Galois Field Arithmetic - 1
• Theorem: The integers 0, 1 …p-1 where p
is a prime, form the field GF(p) under
modulo p addition and multiplication.
• Definition: Let β be an element in GF(q).
The order of β is the smallest positive
integer m such that βm = 1
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #19
Galois Field Arithmetic - 2
• Definition: An element with order (q-1) in
GF(q) is called a primitive element in GF(q)
• Every field GF(q) contains at least one
primitive element α.
• All nonzero elements in GF(q) can be
represented as (q-1) consecutive powers of
a primitive element α
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #20
Galois Field Arithmetic - 3
• Theorem: The order q of a Galois Field
GF(q) must be a power of a prime
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #21
Theorem
• For any prime number n, and any natural
number p, there exists a unique field GF[np]
called Galois field of order np.
• Let’s take a look at some GFs
– Galois fields with p=1
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #22
Polynomials over Galois Fields
• Definition: GF(q)[x] = α0+α1x+α2x2+…+xn the
collection of all polynomials of arbitrary degree
with coefficients {αi} in the finite field GF(q).
• Definition: A polynomial p(x) is irreducible in
GF(q) if p(x) cannot be factored into a product of
lower-degree polynomials in GF(q)[x].
• Definition: An irreducible polynomial
p(x) GF(q)[x] of degree m is said to be primitive
if the smallest positive integer n for which p(x)
divides xn-1 is n = qm - 1
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #23
Roots
• Theorem: The roots {αj} of an mth-degree
primitive polynomial p(x) GF(q)[x] have
order qm - 1.
• Theorem implies that the roots {αj} are
primitive elements in GF(qm).
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #24
Construction of Galois Field
GF (2m)
• Construction of GF(8)
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #25
Logarithms: A Review
• If 102=100, then log10 100 = 2
• Logarithms can use any base: 10, 2, etc.
• For example:
23 = 8, therefore log2 = 3
Logarithms calculated to different bases are
related by a constant factor
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #26
So What?
• Logarithms can simplify complex and
resource-intensive calculations
• Multiplication becomes addition, etc.
• Example:
100 x 100 = 10,000  multiplication
log10 100 + log10 100 = log10 (100x100)  add
log10-1 (100x100) = 10,000  lookup
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #27
Discrete Logarithms (DL)
• DL is the underlying one-way function for:
–
–
–
–
Diffie-Hellman key exchange
DSA (digital signature algorithm)
El Gamal encryption/digital signature scheme
Elliptic curve cryptosystems.
• DL is based on finite groups
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #28
Groups
• A group is a set G of elements together with
a binary operation “o” such that:
– If a, b  G then a o b = c  G  (closure)
– If (a o b) o c = a o (b o c)  (associativity)
– There exists an identity element e  G:
e o a = a o e = a  (identity)
– There exists an inverse element ã, for all a  G:
a o ã = e  (inverse)
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #29
Examples
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #30
Definition
• “Z*n” denotes the set of numbers i, 0 < i <
n, which are relatively prime to n
• Example:
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #31
Theorem
• Z*n forms a group under modulo n
multiplication
– The identity element is e = 1
• The inverse of a  Z*n can be found through
the extended Euclidean algorithm
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #32
Finite Groups
• A group (G, o) is finite if it has a finite
number of g elements.
• We denote the cardinality of G by |G|
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #33
Order
• The order of an element a  (G; o) is the
smallest positive integer o such that
a o a … o a = a0 = 1
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #34
Cyclic Groups
• A group G is called cyclic if there exists an
element g  G such that G = { gn} where
n is an integer
• Example: if G = { g0, g1, g2, g3, g4, g5 } is a
group, then g6 = g0, and G is cyclic
• For every positive integer n there is exactly
one cyclic group whose order is n
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #35
P vs. NP
• The Class P consists of all those decision
problems that can be solved on a deterministic
sequential machine in an amount of time that is
polynomial in the size of the input
• The class NP consists of all those decision
problems whose positive solutions can be verified
in polynomial time given the right information, or
equivalently, whose solution can be found in
polynomial time on a non-deterministic machine
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #36
NP-Problems
• A problem is assigned to the NP (nondeterministic
polynomial time) class if it is solvable in
polynomial time by a nondeterministic Turing
machine
• A problem is NP-hard if an algorithm for solving
it can be translated into one for solving any NPproblem
• A problem is NP-complete if it is both NP and NPhard (e.g. traveling salesman problem)
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #37
Traveling Salesman Problem
•
•
Spring 2010
© 2000-2010, Richard A. Stanley
Given a collection of cities and the cost
of travel between each pair of them, the
traveling salesman problem, or TSP for
short, is to find the cheapest way of
visiting all of the cities and returning to
your starting point. In the standard
version we study, the travel costs are
symmetric in the sense that traveling
from city X to city Y costs just as much
as traveling from Y to X.
The simplicity of the statement of the
problem is deceptive -- the TSP is one of
the most intensely studied problems in
computational mathematics and yet no
effective solution method is known for
the general case. Indeed, the resolution of
the TSP would settle the P versus NP
problem and fetch a $1,000,000 prize
from the Clay Mathematics Institute.
ECE578/6 #38
Example
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #39
Generators
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #40
Example
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #41
Properties of Cyclic Groups
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #42
General DL Problem
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #43
Example 1
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #44
Example 2
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #45
Attacks on Discrete Logarithms
• Brute Force
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #46
Attacks on Discrete Logarithms
• Shank's algorithm (Baby-step giant-step)
and Pollard's- method
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #47
Attacks on Discrete Logarithms
• Pohlig-Hellman Algorithm
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #48
Attacks on Discrete Logarithms
• Index-Calculus Method
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #49
Elliptic Curve Cryptosystem
• Relatively new cryptosystem, suggested
independently:
– 1987 by Koblitz at the University of Washington,
– 1986 by Miller at IBM
• Believed to be more secure than RSA/DL in Z*p ,
but uses arithmetic with much shorter numbers
(160 - 256 bits vs. 1024 - 2048 bits).
• It can be used instead of D-H and other DL-based
algorithms
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #50
ECC Drawbacks
• Not as well studied as RSA and DL-base
public-key schemes
• Conceptually more difficult.
• Finding secure curves in the set-up phase is
computationally expensive
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #51
Elliptic Curves
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #52
Elliptic Curves - 2
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #53
Elliptic Curve Definition
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #54
Elliptic Curves
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #55
Objective
• Goal: Finding a (cyclic) group (G, o) so that
we can use the DL problem as a one-way
function.
• We have a set (points on the curve). We
“only” need a group operation on the points.
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #56
Finding the Set
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #57
Point Addition (group operation)
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #58
Theorem
• Theorem: The points on an elliptic curve,
together with O , have cyclic subgroups
• Remark: Under certain conditions all points
on an elliptic curve form a cyclic group as
the following example shows
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #59
Example (con’t.)
In general, finding the group order of #E is computationally very
complex
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #60
So What?
• Are there practical uses for elliptic curves in
cryptography?
• What are the implications of computational
complexity?
• What might they be?
• What could be the benefits of using ECs
rather than traditional methods of
structuring groups?
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #61
Homework
• Read Stinson, Chapters 5 & 6
• Come to our next class prepared to
describe and discuss the El Gamal
cryptosystem. What are its benefits?
What are its drawbacks? Why is it not
more widely used?
Spring 2010
© 2000-2010, Richard A. Stanley
ECE578/6 #62