Transcript n - Read

Dept. of Computer Engineering
Information Security Lab.
PART II Public-Key Encryption &
Hash Function
CHAPTER 8 Introduction to Number Theory
8.1 Prime Numbers
8.2 Fermat’s and Euler’s Theorems
8.3 Testing for Primality
8.4 The Chinese Remainder Theorem
8.5 Discrete Logarithms
204/223
Dept. of Computer Engineering
Information Security Lab.
8.1 Prime Numbers

Prime numbers only have divisors of 1 and self
 they cannot be written as a product of other numbers
 eg. 2,3,5,7 are prime, 4,6,8,9,10 are not
 Prime numbers are central to number theory
 Prime factorisation : Any integer a > 1 can be factored
in a unique way as: hard problem
a  p1a1 p2a2
k
pkak   piai
i 1
where p1 < p2 < … < pk are primes

Another expression : P = set of all primes
ap
pP
ap
11011 = 7  112  13
a7 = 1, a11 = 2, a13 = 1
205/223
Dept. of Computer Engineering
Information Security Lab.
8.1 Prime Numbers

Multiplication : a   p
ap
pP
k=ab
bp
bp
pP
k   p , k p  a p  bp
kp
pP
Example : a = 12 = 22  3, b = 90 = 2  32  5
k = a  b = 1080 = 23  33  5
k2(3) = a2(2)+b2(1); k3(3)= a3(1)+b3(2);
k5(1) = a5(0)+b5(1)

Given a and b, If a | b, then ap  bp for all p
Example : a = 12 = 22  3, b = 180 = 22  32  5
a2 = 2 = 2 =b2, a3 = 1 < 2 = b3,
a5 = 0 < 1 = b5
206/223
Dept. of Computer Engineering
Information Security Lab.
8.1 Prime Numbers

If k = gcd(a, b), then kp = min(ap, bp) for all p
Example :
a = 12 = 22  3 : a2= 2, a3 = 1
b = 180 = 22  32  5 : b2= 2, b3 = 2, b5 = 1
k = gcd(a, b) = ?
k2 = min(a2, b2) = 2, k3 = min(a3, b3) = 1,
k5 = min(a5, b5) = 0
k = 2k2  3k3  5k5 = 22  31  50 = 12
k = gcd(a, b) = gcd(12, 180) = 12 :
207/223
Dept. of Computer Engineering
Information Security Lab.
8.2 Fermat’s and Euler’s Theorems
Fermat’s Theorem; Fermat’s Little Theorm

If p is prime and a is a positive integer not divisible by p,
(gcd(a, p)=1), then
ap1  1 (mod p)
Example : a = 7, p = 19(prime)
72 = 49  11 (mod 19); 74 = 121  7 (mod 19);
78 = 49  11 (mod 19); 716 = 121  7 (mod 19);
ap1 = 718 = 716  72 = 7  11  1 (mod 19)
 useful in public key and primality testing
 An alternative form of Fermat’s Theorem:
If p is prime and a is a positive integer, then
ap  a (mod p)
Example : p = 5, a =10; ap = 105  0 (mod 5)  a (mod 5)
208/223
Dept. of Computer Engineering
Information Security Lab.
8.2 Fermat’s and Euler’s Theorems
Euler’s Totient Function

For a positive integer n,
complete set of residues = { 0, 1, , n1}
reduced set of residues = { x | 0 x  n1, gcd(x, n) = 1}
Example : n = 10
complete set of residues = { 0, 1, 2, , 8, 9 }
reduced set of residues = { 1, 3, 7, 9 }

Euler Totient Function (n) = # of elements in reduced
set of residues
Example : n = 10  (n) = (10) = | {1, 3, 7, 9} | = 4

For a prime p, (p) = p – 1
209/223
Dept. of Computer Engineering
Information Security Lab.
8.2 Fermat’s and Euler’s Theorems
Euler’s Totient Function
Table 8.2 Some Values of Euler’s Totient Function (n)
210/223
Dept. of Computer Engineering
Information Security Lab.
8.2 Fermat’s and Euler’s Theorems
Euler’s Totient Function

Suppose that we have two primes p and q, n = pq
(n) = (pq) = (p)  (q) = (p – 1)(q – 1)
Why? The integers that are not relatively prime to n
{ p, 2p, , (q 1)p }, { q, 2q, , ( p – 1)q }
Therefore, (n) = (pq – 1) – [(q – 1) + (p – 1)]
= pq – (p + q) – 1
= (p – 1)(q – 1) = (p)  (q)
Example : (21) = (37) = (3)(7) = (31)(71)= 12
211/223
Dept. of Computer Engineering
Information Security Lab.
8.2 Fermat’s and Euler’s Theorems
Euler’s Theorem

A generalization of Fermat's Theorem
For every a and n such that gcd(a, n) = 1,
a(n)  1 (mod n)
Example : a = 3, n = 10; (10) = 4
a(n) = 34 = 81  1 (mod 10)  1 (mod n)
212/223
Dept. of Computer Engineering
Information Security Lab.
8.3 Testing for Primality

Often need to find large prime numbers

Traditionally sieve using trial division
 divide by all numbers (primes) in turn less than the
square root of the number
 only works for small numbers

Alternatively can use statistical primality tests based on
properties of primes
 for which all primes numbers satisfy property
 but some composite numbers, called pseudo-primes,
also satisfy the property

Can use a slower deterministic primality test
213/223
Dept. of Computer Engineering
Information Security Lab.
8.3 Testing for Primality
Miller-Rabin Algorithm
Two Properties of Prime Numbers
 The first property :
If p is a prime and a is a positive integer less than p, then
a2 mod p = 1  a mod p = 1 or a mod p = 1 = p – 1
 The second property :
Let p be a prime number greater than 2. We can write
p – 1 = 2kq with k > 0, q odd. Let a be any integer in the
range 1< a < p – 1. Then one of the two following
conditions is true:
 aq mod p = 1 i.e. aq  1 (mod p)
 one of the numbers aq, a2q, a4q, …, a2k1q is congruent
to 1 mod p, i.e.  j (1  j  k) a2j–1q = 1 (mod p)
214/223
Dept. of Computer Engineering
Information Security Lab.
8.3 Testing for Primality
Details of the Miller-Rabin Algorithm
 A test based on Fermat’s Theorem
 Algorithm is :
TEST (n)
(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
jq
2
if (a mod n = n 1)
then return(" maybe prime ")
(5) return ("composite")
215/223
Dept. of Computer Engineering
Information Security Lab.
8.3 Testing for Primality
Repeated Use of the Miller-Robin Algorithm
 If Miller-Rabin algorithm returns “composite”
the number is definitely not prime, otherwise is a prime
or a pseudo-prime

Probability it detects a pseudo-prime is < 1/4

Hence, if repeat test with different random a, then chance
n is prime after t tests is:
t
 Pr( n is a prime after t tests ) = 1  4
 eg. for t =10, this probability is > 0.99999
216/223
Dept. of Computer Engineering
Information Security Lab.
8.3 Testing for Primality
A Deterministic Primality Algorithm

AKS (Agrawal, Kayal, Saxena, 2002) algorithm :
relatively simple deterministic algorithm that efficiently
determines whether a given large number is a prime.

The AKS algorithm does not appear to be as efficient as
the Miller-Rabin algorithm
217/223
Dept. of Computer Engineering
Information Security Lab.
8.3 Testing for Primality
Distribution of Primes

The prime number theorem states that primes near n
are spaced on the average one every (ln n) integers, i.e.
the density of prime numbers among the integers in the
neighborhood of n is around 1 in ln n
Let (n) denote the number of primes p  n.
(n)
(n)  n/(ln n – 1 ), lim
1
n  n / ln n
 On average, one would have to test on the order of ln n
integers before a prime is found. Because all even can be
rejected, so in practice need only test 0.5*ln(n) numbers of
size n to locate a prime

218/223
Dept. of Computer Engineering
Information Security Lab.
8.4 Chinese Remainder Theorem





Used to speed up modulo computations: A (mod M)
Let M = m1  m2 … mk where gcd(mi, mj) = 1
Chinese Remainder theorem lets us work in each
moduli mi separately: ai = A mod mi 1  i  k
where A  ZM, ai Zmi
Since computational cost is proportional to size, this is
faster than working in the full modulus M
To compute A (mod M)
 first compute all ai = A mod mi separately
 determine constants ci below, where Mi = M/mi
219/223
Dept. of Computer Engineering
Information Security Lab.
8.5 Discrete Logarithms
The Powers of an Integer, Modulo n
From Euler’s theorem, for gcd(a, n) = 1, aø(n) mod n = 1
where ø(n) Euler’s totient function: # of positive integers
less than n and relatively prime to n.
 Consider am =1 (mod n), gcd(a, n) = 1
 must exist for m = ø(n), least m = order of a
 once powers reach m, cycle will repeat
 If smallest is m = ø(n),
then a is called a primitive root of n
 If p is prime, then successive powers of a "generate" the
group mod p: Zp = { a, a2, …, ap1}
For the prime p = 19, primitive roots = 2, 3,10, 13, 14, 15
Refer to : page 249 Table 8.3

220/223
Dept. of Computer Engineering
Information Security Lab.
8.5 Discrete Logarithms
Logarithms for Modular Arithmetic

The discrete logarithm of a modulo p is to find an
integer x such that y = gx (mod p); written as x = loggy
(mod p)

If g is a primitive root, then it always exists,
otherwise it may not. Table 8.4
x
 x = log34 mod 13 has no answer; 3 = 4 (mod 13)
 x = log23 mod 13 = 4 by trying successive powers

The properties of logarithms :
log x(1) = 0, log x(x) = 1
log x(yz) = log x(y) + log x(z)
log x(y r) = r  log x(y)
221/223
Dept. of Computer Engineering
Information Security Lab.
8.5 Discrete Logarithms
Calculation of Discrete Logarithm

Consider the equation
y = gx mod p
 Given g, x, and p, it is a straightforward matter to
calculate y; just exponentiation

However, given g, y, and p, it is very difficult to
calculate x. Hard problem

The fastest known algorithm for taking DL modulo a
prime number is on the order of
e
((ln p )1/ 3 (ln ln p )2 / 3 )
which is not feasible for large primes.
222/223
Dept. of Computer Engineering
Information Security Lab.
Summary
 have





considered:
prime numbers
Fermat’s and Euler’s Theorems & ø(n)
Primality Testing
Chinese Remainder Theorem
Discrete Logarithms
223/223