Transcript Why Cryptography?

Number Theory and
Advanced Cryptography
2. Primes and Discrete Logarithms
Part I: Introduction to Number Theory
Part II: Advanced Cryptography
Chih-Hung Wang
Feb. 2011
1
The distribution of primes

The natural way of measuring the density of
primes is to count the number of primes up to a
bound x, where x is a real number. For a real
number x ¸ 0, the function (x) is defined to be
the number of primes up to x. Thus, (1) = 0,
(2) = 1, (7.5) = 4, and so on.
2
Some values of (x)
3
The Sieve of Eratosthenes

This is an algorithm for generating all the primes up
to a given bound k.
4
The prime number theorem
5
The error term in the prime number
theory (1)
6
The error term in the prime number
theory (2)
7
Sophie Germain primes
8
Probabilistic primality testing
 Trial
Division
9
Trial division
10
The Miller-Rabin test
11
Error parameter (1)
12
Error parameter (2)
13
Carmichael numbers
14
Good Primality testing (1)
15
Good Primality testing (2)
16
Error parameter
17
Generating random primes using
the Miller-Rabin Test
18
Sieving up to a small bound
19
Generating a random k-bit prime
20
Perfect power testing (1)
21
Perfect power testing (2)
22
Perfect power testing (3)
23
Deterministic Primality Testing

The basic idea
24
AKS algorithm
25
Running time
26
Notes
27
Primality testing in Java


Public BigInteger ( int bitLength，int certainty，
Random rnd )
Public boolean isProbablePrime (int certainty)
28
Cyclic groups

Order of group element
29
Order of group element
30
(Example)Powers of Integers, Modulo
19
31
Cyclic group & Group generator
32
Example of Cyclic Group
33
Theorem of Cyclic Group
34
Prime Order group
35
The Multiplicative Group Zn*
36
The Multiplicative Group Zn*
37
Example of The Multiplicative
Group
38
Finding Primitive Root
Page 166
39
Application 1: Diffie-Hellman Key
Exchange
Diffie and Hellman 1976
 A number of commercial products employ this
key exchange technique
 This algorithm enables two users to exchange
key securely

40
The Diffie-Hellman Key Exchange
Protocol
41
Example of D-H Key Exchange (1)
q=97

=5
XA = 36
XB=58
YA=536=50 mod 97
YB=558=44 mod 97
K=(YB)XA mod 97 = 4436 = 75 nod 97
K=(YA)XB mod 97 = 5058 = 75 nod 97
42
Example of D-H Key Exchange (2)


43
Hybrid Encryption

Diffie-Hellman based hybrid encryption
system
A
K=(YB)xA
=(YA)xB
Mod q
SK=h(K)
128 – 256 bits
YA
B
YB
ESK(M)
SK can be a key of the
AES symmetric cryptosystem
44
The Man-in-the-Middle Attack (1)
45
The Man-in-the-Middle Attack (2)
46
The DH Problem and DL Problem
(1)
47
The DH Problem and DL Problem
(2)
Example: a = loggh = log3 5 mod 19 = 4
48
Importance of Arbitrary Instances for
Intractability Assumptions
CRT
riai=ria (mod qi)
=
h(p-1)/qi
mod p
a=kiqi+ai
ri= g(p-1)/qi mod p
49
Chinese Remainder Theorem (1)
50
Chinese Remainder Theorem (2)
51
Chinese Remainder Theorem (3)
52
Example of CRT
x  3 mod 4
x  0 mod 5
x  0 mod 7
x  8 mod 9
M / m1  1260 / 4  315
M / m2  1260 / 5  252
M / m3  1260 / 7  180
M / m4  1260 / 9  140
y1  3
y2  3
y3  3
y4  2
x  y1 ( M / m1 )c1  y2 ( M / m2 )c2  y3 ( M / m3 )c3  y4 ( M / m4 )c4
 3  315  3  3  252  0  3 180  0  2 140  8
 5075 mod 1260
 35
53
ElGamal (1)
54
ElGamal (2)
55
Meet-in-the-middle attack &
Active attack of ElGamal




See Page 277 Example 8.8
Malice select r U Fp*
Malice sends (c1, c2’=rc2) to Alice
Alice returns rm to Malice
56