1
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.2
Public Key Cryptography
2
Diffie-Hellman
? Diffie-Hellman is a public key distribution
scheme
? First public-key type scheme,proposed in
1976,
– W Diffie,M E Hellman,"New directions in
Cryptography",IEEE Trans,Information
Theory,IT-22,pp644-654,Nov 1976
3
4
Diffie-Hellman
? Public-key distribution scheme
? Cannot be used to exchange an arbitrary message
? Exchange only a key,whose value depends on the
participants (and their private and public key
information)
? The algorithm is based on exponentiation in a
finite (Galois) field,either over integers modulo a
prime,or a polynomial field
5
Diffie-Hellman
? Security relies on the difficulty of computing
logarithms in these fields
– discrete logarithms takes O(e log n log log n) operations
? The algorithm,
– two people Alice and Bob who wish to exchange
some key over an insecure communications channel,
– They select a large prime p (~200 digit),such as (p-
1)/2 should also be prime
– They also select g,a primitive root mod p
? g is a primitive if for each n from 0 to p-1,there
exists some a where ga = n mod p,
6
Diffie-Hellman
? The algorithm
– The values of g and p don’t need to be secret
– Alice then chooses a secret number a
– Bob also chooses a secret number b
– Alice and Bob compute yA and yB respectively,
which are then exchanged
? yA = ga mod p yB = gb mod p
– Both Alice and Bob can calculate the key as
? KAB = gab mod p
= yAb mod p (which B can compute)
= yBa mod p (which A can compute)
– The key may then be used in a private-key cipher
to secure communications between A and B
7
Alice ga mod p Bob
gb mod p
The private key is,gab mod p
where p is a prime and g is a generator of Zp
Diffie-Hellman
8
? Knows ga,gb,g,and p
? So we want to find the key,k
– k = gab
– This is believed to be hard,
? If one knows how to compute discrete logs
efficiently,then one can break this scheme
(and other schemes based on public key
cryptography)
Diffie-Hellman
9
Diffie-Hellman
? Can be expanded to be used with many parties
? Can be extended to,
– Finite fields GFp
– Elliptic curves
– Galois field
? Computing discrete logarithms is closely related to
factoring,If you can solve the discrete logarithm
problem,then you can factor,(The converse has
never been proven to be true.)
GF k2
10
El Gamal
? A variant of the Diffie-Hellman key distribution
scheme,allowing secure exchange of messages
? Published in 1985 by ElGamal in
– T,ElGamal,"A Public Key Cryptosystem and a
Signature Scheme Based on Discrete Logarithms",
IEEE Trans,Information Theory,vol IT-31(4),pp469-
472,July 1985,
? Like Diffie-Hellman its security depends on the
difficulty of factoring logarithms
11
The ElGamal encryption scheme
Let p be a prime and g ? Zp* a primitive element,
Let P = Zp*,
C = Zp* x Zp* and
K = {(p,g,x,y),y = gx mod p },
? The values p,g,y are the public key,
? x is the private key,
12
The ElGamal encryption scheme
? Encryption
Let m ? Zp* be a message,
For K = {(p,g,x,y),y = gx mod p },and secret
random number k ? Zp-1,define,eK(m,k) = (s,t),
where
– s = gk mod p
– t = m yk mod p
? Decryption
For s,t ? Zp*,define,dK(s,t) = t (sx)-1mod p
13
An Example
? Let p =2357,g = 2,x = 1751,y ? gx ? 21751 ? 1185
(mod 2357)
? System parameters,(p,g) = (2357,2)
Public key,y = 1185,Private key,x = 1751
? Encryption:say M = 2035
1.Pick a random number k = 1520
2.Computes
s = gk ? 21520 ? 1430 (mod 2357)
t = Myk ? 2035 x 11851520 ? 697 (mod 2357)
– The ciphertext C = (s,t) = (1430,697)
? Decryption,
1.Computes u ? sx ? 14301751 ? 2084 (mod 2357)
2.M ? t u-1 ? 697 x 2084-1 ? 2035 (mod 2357)
14
The security of ElGamal
? The Diffie-Hellman problem,
Given a prime p,g e Zp*,and x,y e Zp*,find xlog gy
mod p,
The security of the ElGamal encryption is reduced to
the difficulty of breaking the Diffie-Hellman
problem,
15
Remarks on El-Gamal Encryption
Scheme
? ElGamal encryption scheme is non-deterministic
? Randomization is introduced to
– increase the effective size of the plaintext space
i.e,one plaintext can map to a large set of possible
ciphertexts
– decrease the effectiveness of chosen-plaintext attack by
means of a one-to-many mapping in the encryption process
? Efficiency,
– encryption requires two exponentiation operations
– exponentiation operations may be very expensive when
implemented on some low-power devices,e.g,low-end
PalmPilots,smart cards and sensors,
– message expansion by two-fold
? Security:depends on the difficulty of solving DLP,
16
Elliptic Curve
? The elliptic curve cryptosystem are modifications
of other systems that work in the domains of
elliptic curve rather than finite fields,
? The elliptic curve cryptosystems appear to remain
secure for smaller keys than other public-key
cryptosystems,
? The use of elliptic curves was first proposed by
Miller (1986) and Koblitz (1987),
? Already,ECC is showing up in standardization
efforts,including IEEE P1363 Standard for
Public-Key Cryptography,
17
RSA Modular Exponentiation y =
xe mod n
512 768 1024 1536 2048
0
60
120
180
240
300
360
R S A k e y s i z e k [ b i t s ]
p
r
o
c
e
s
s
i
n
g
t
i
m
e
t
[
s
]
RSA key size
k [bits]
Processing
time t [s]
512 8
768 22
1024 48
1536 150
2048 335
18
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
y2 = x3 + ax + b
4a3 + 27b2 ? 0
General form,
Condition for distinct
single roots,
Example,
y2 = x3 ? 4x
= x(x ?2)(x +2)
What are Elliptic Curves?
19
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + Q
Group set,
All points P(x,y) lying
on an elliptic curve
Group operation,
Point addition
R'
R P
Q
Points P(x,y) on an Elliptic Curve
form a Group
20
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
Inverse element,
P'(x,-y) = P(x,y)
is mirrored on x-axis
Point addition with
inverse element,
P + P' = O
results in a neutral
element O(x,?) at
infinity P'
O
Neutral element,
P + O = P
P
Neutral and Inverse Elements
21
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + P
Point Doubling,
Form the tangent in
Point P(x,y)
R'
R P
Point Doubling – Adding a point
to itself
22
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
kP = P + P +,.,+ P
Point Iteration,
3P
2P P
Point Iteration – Adding a point
k-1 times to itself
23
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R' (xR,-yR)
R(xR,yR) P(xP,yP)
Q (xQ,yQ)
g
Intersection with curve,
(s? x?y0)2 = x3 +ax+b
Line g,y = s? x?y0
with
s y yx xQ P
Q P
? ??
y y s xP P0 ? ? ?
x s x x
y s x y
R P Q
R R
? ? ?
? ? ? ?
2
0( )
Coordinates of point R,
Mathematical Description of
Geometrical Transform
24
Intersection with curve,
(s? x?y0)2 = x3 +ax+b
x s x
y s x y
R P
R R
? ?
? ? ? ?
2
0
2
( )
Coordinates of point R,
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R' (xR,-yR)
R (xR,yR)
P(xP,yP)
g
Tangent g,y = s? x?y0
s dydx x ayP
P
? ? ?3 2
2
y y s xP P0 ? ? ?
Mathematical Description of
Geometrical Transform
25
How can Geometry be useful for
Cryptography?
Elliptic curves can be defined in a finite or Galois field GFp,
y2 = x3 + ax + b mod p
where the field size p is a prime number and
{0,1,...,p-1} is an abelian group under addition mod p
and
{1,...,p-1} is an abelian group under multiplication mod p,
26
DESCRIPTION
? An elliptic curve is given by F,y2 = x3 + ax + b
and defined for Zp,where Zp represents the set of
integers between 0 and p,includes all pairs of
numbers (x,y)?Zp ? Zp which satisfy,
y2=x3+ax+b(mod p)
? where p is a prime number,p > 3 and a and b are
constants for which
4a3 +27b2 ? 0(mod p),
? the points on F can be found by determining
z = x3 + ax + b(mod p) for every x?Zp,and then
calculating the corresponding y:z = y2 (mod p),
27
Differences
? There are several major differences between elliptic curve groups
over GF(p) and over real numbers,
? Elliptic curve groups over GF(p) have a finite number of points,
which is a desirable property for cryptographic purposes,
? Since these curves consist of a few discrete points,it is not clear
how to "connect the dots" to make their graph look like a curve – it
is not clear how geometric relationships can be applied,
? As a result,the geometry used in elliptic curve groups over real
numbers cannot be used for elliptic curve groups over GF(p),
? However,the algebraic rules for the arithmetic can be adapted for
elliptic curves over GF(p),
? Unlike elliptic curves over real numbers,computations over the
field of GF(p) involve no round off error - an essential property
required for a cryptosystem,
28
Task 1 - Multiplication c = a?b in
GF11
? Compile a multiplication table for c = a ? b mod 11
? Determine the solutions of the equation x2 = 5 mod 11
29
Solution 1 - Multiplication c =
a?b in GF11
0 0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9 10
0 2 4 6 8 10 1 3 5 7 9
0 3 6 9 1 4 7 10 2 5 8
0 4 8 1 5 9 2 6 10 4 7
0 5 10 4 9 3 8 2 7 1 6
0 6 1 7 2 8 3 9 4 10 5
0 7 3 10 6 2 9 5 1 8 4
0 8 5 2 10 7 4 1 9 6 3
0 9 7 5 3 1 10 8 6 4 2
0 10 9 8 7 6 5 4 3 2 1
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
a
b
c
?
x2 = 5 mod 11?
x1 = 4,x2 =
7
30
? Which points P(x,y) with x and y in GF11 fulfill the
elliptic curve equation,
y2 = x3 + x + 6 mod 11
Task 2 – Points on an Elliptic
Curve
31
Solution 2 – Points on an Elliptic
Curve
6 -
8 -
5 4,7 (2,4) (2,7)
3 5,6 (3,5) (3,6)
8 -
4 2,9 (5,2) (5,9)
8 -
4 2,9 (7,2) (7,9)
9 3,8 (8,3) (8,8)
7 -
4 2,9 (10,2) (10,9)
y2 y1,2 P(x,y) P'(x,y)
0
1
2
3
4
5
6
7
8
9
10
x
There are 12 points lying
on the elliptic curve,
Together with the point O at
infinity,the points on the
elliptic curve form a group
with n=13 elements,
n is called the order of the
elliptic curve group and
depends on the choice of the
curve parameters a and b,
32
Points on an Elliptic Curve
An elliptic curve E defined over Zp (P prime,
P>3) will have roughly P points on it,More
precisely,a well-known theorem due to Hasse
asserts that the number of points on E,which
we denote by #E,satisfies the following
inequality
ppEpp 21#21 ??????
33
Task 3 – Iterate a Point on the
Elliptic Curve
? Iterate the point P(2,4) lying on y2 = x3 + x + 6 mod 11,
? Compute 2P = P + P by doubling the point P
x s x
y s x y
R P
R R
? ?
? ? ? ?
2
0
2
( )
s dydx x ayP
P
? ? ?3 2
2
y y s xP P0 ? ? ?
? Compute 3P = P + P + P = 2P + P by point addition
s y yx xQ P
Q P
? ??
y y s xP P0 ? ? ?
x s x x
y s x y
R P Q
R R
? ? ?
? ? ? ?
2
0( )
? All operations are computed in GF11
34
Solution 3 – Iterate a Point on the
Elliptic Curve
? Compute 2P = P + P by doubling the point P(2,4)
x
y
R
R
? ? ? ?
? ? ? ? ? ? ?
9 2 2 5
3 5 9 2 9( )
s ? ? ?? ? ? ? ?3 4 12 4 138 7 2 3
y 0 4 3 2 2 9? ? ? ? ? ?
2P=(5,9)
? Compute 3P = P + P + P = 2P + P by point addition
s ? ?? ? ? ? ?9 45 2 53 4 5 9
y 0 4 9 2 3 8? ? ? ? ? ?
x
y
R
R
? ? ? ?
? ? ? ? ? ? ?
81 2 5 8
9 8 8 3 8( )
3P=(8,8)
35
Elliptic Curve Discrete
Logarithm Problem (ECDLP)
( 2,4) 3 9
( 5,9) 9 8
( 8,8) 8 10
(10,9) 2 0
( 3,5) 1 2
( 7,2) 4 7
( 7,9) 1 2
( 3,6) 2 0
(10,2) 8 10
( 8,3) 9 8
( 5,2) 3 9
( 2,7) ? -
O ? -
kP s y0
1
2
3
4
5
6
7
8
9
10
11
12
13
k
Given an elliptic curve
y2 = x3 + ax + b mod p
and a basis point P,we can compute
Q = kP
through k-1 iterative point additions,
Fast algorithms for this task exist,
Question,Is it possible to compute k
when the point Q is known?
Answer,This is a hard problem known
as the Elliptic Curve Discrete Logarithm,
36
Definition of an Elliptic Curve
Cryptosystem
? version is currently v1
? fieldID identifies the finite field over which curve is defined
? curve coefficients a and b of the elliptic curve
? base specifies the base point P,a point P in the elliptic
curve group defined over GF(p)
? order the order n of the base point
37
Cryptographic Application –
Secret Key Exchange
QA = a P
? Elliptic Curve Cryptosystem,ECC,basis point P and prime p
Secret,
S = bQA = aQB = ab P QB = b P
A = ga mod p
? Diffie-Hellman,Basis g and prime p
B = gb mod p
Secret,
s = Ab = Ba = gab mod p
38
Elliptic Curve Encryption Scheme (ECES)
? Setup,
– let E be an elliptic curve defined over GF(p) and g
be a point of order q in the elliptic curve group such
that ECDLP is intractable,
– randomly chooses x ?R Zq,and computes y ? x P,
1.System Parameters,(E,p,P,q)
2.Public Key, y
3.Private Key,x
39
Elliptic Curve Encryption Scheme (ECES)
? Encryption,
1.Picks randomly an integer k ? Zq,
2.computes
s = k P,t = M ? H(ky)
where M ? {0,1}k is the message of k bits long,H is
some appropriate function which maps a point to a
k-bit binary string (e.g,a hash function),
– The ciphertext C = (s,t),
? Decryption,
1.Computes u = xs from s,
2.M = t ? H(u)
40
ElGamal encryption
? ElGamal encryption,
E,elliptic curve
g,a generator ? E
B’s ―long-term‖ private key x
B’s ―long-term‖ public key y= x P ? E
Encryption,A B
Plaintext M?E
― short-term‖ secret key k
compute s = k P,
t= M +k y
(s,t) is the ciphertext
Decryption,
M = t - xs
Note,M should be a
point in the elliptic
curve,
41
Example
Suppose that P = (2,7) and Bob’s secret ―exponent ‖
is x=7,so y = 7 P =(7,2)
Thus the encryption operation is
e (M,k) = (k(2,7),M+k(7,2)),where M?E and 0? k
? 12,and the decryption operation is
d ( s,t)= t-7s,
Suppose that Alice wishes to encrypt the message
M=(10,9) (which is a point on E),If she chooses the
random value k=3,then she will compute
s= 3(2,7) =(8,3)
and t=(10,9)+3(7,2) = (10,9)+(3,5) = (10,2)
42
Example
(Continue)
Hence,c=((8,3),(10,2)),Now,if Bob receives the
ciphertext c,he decrypts it as follows,
M = (10,2) - 7(8,3)
= (10,2) - (3,5)
= (10,2) + (3,6)
= (10,9)
Hence,the decryption yields the correct plaintext,
43
Equivalent Cryptographic
Strength
Symmetric
RSA n
ECC p
56
512
112
80
1024
161
112
2048
224
128
3072
256
192
7680
384
256
15360
512
Key size ratio 5:1 6:1 9:1 12:1 20:1 30:1
44
0
0, 1
0, 2
0, 3
0, 4
0, 5
0, 6
0, 7
0, 8
0, 9
1
C O M P A R I S O N O F S E C U R I T Y L E V E L S
E C C a n d R S A & D S A
0
1000
2000
3000
4000
5000
6000
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
E
+
1
2
1
E
+
2
0
1
E
+
3
6
T i m e t o B r e a k K e y ( M I P S Y e a r s )
K
e
y
S
i
z
e
(
B
i
t
s
)
E C C
R S A & D S A
Comparison of RSA,ECC,DSA
45
Comparison of PK Systems
? Does breaking the system really require
solving the underlying mathematical
problem?
? Which is the hardest problem?
? IFP and DLP – subexponential
O(exp((c+o(1)))(ln n)1/3(ln ln n)2/3)
? ECDLP – exponential
O(?p)
46
Applications of ECC
? Constrained Channels
- Wireless Devices
- ECC – shorter keys,faster computations
- Reduction in data transmitted – save power
o Smart Cards and Tokens
47
Conclusion
? Usual situations – RSA is good,ECC is
better
? Special systems – constrained or high
security requirements – ECC is currently
the only option
? In the future,computational power will
increase – RSA will soon become
unmanageable,ECC – a viable alternative
48
Public Key Cryptography Standards
? PKCS #1,RSA Cryptography Standard
? PKCS #2,incorporated into PKCS #1
? PKCS #3,Diffie-Hellman Key Agreement Standard
? PKCS #4,incorporated into PKCS #1
? PKCS #5,Password-Based Cryptography Standard
? PKCS #6,Extended-Certificate Syntax Standard
? PKCS #7,Cryptographic Message Syntax Standard
? PKCS #8,Private-Key Information Syntax Standard
? PKCS #9,Selected Attribute Types
? PKCS #10,Certification Request Syntax Standard
? PKCS #11,Cryptographic Token Interface Standard
? PKCS #12,Personal Information Exchange Syntax Standard
? PKCS #13,Elliptic Curve Cryptography Standard
? PKCS #15,Cryptographic Token Information Format Standard
http://www.rsasecurity.com/rsalabs/pkcs/
49
Public Key Cryptography
? In 1988 Whitfield Diffie noted that most public-key
algorithms are based on one of three hard problems
? 1,Knapsack,Given a set of unique numbers,find a
subset whose sum is N,
– 2,Discrete logarithm,If p is a prime and g and m
are integers,find x such that gx ≡ M (mod p),
– 3,Factoring,If N is the product of two primes,either
? a) factor N,
? b) given integers M and C,find d such that Md ≡
C (mod N),
? c) given integers e and C,find M such that Me ≡
C (mod N),or
? d) given an integer x,decide whether there exists
an integer y such that x ≡ y2 (mod N),
50
Public Key Cryptography
? This narrowness in the mathematical foundations
of public-key cryptography is worrisome,
? A breakthrough in either the problem of
factoring or of calculating discrete logarithms
could render whole classes of public-key
algorithms insecure,
51
Public Key Cryptography
? Diffie points out,
? 1,The operations on which public key cryptography
currently depends—multiplying,exponentiating,and
factoring—are all fundamental arithmetic
phenomena,
? 2,Our ability to carry out large arithmetic
computations has grown steadily and now permits us
to implement our systems with numbers sufficient in
size to be vulnerable only to a dramatic breakthrough
in factoring,logarithms,or root extraction,
52
Public Key Cryptography
? As we have seen,not all public-key algorithms
based on these problems are secure,
? The strength of any public-key algorithm
depends on more than the computational
complexity of the problem upon which it is
based; a hard problem does not necessarily
imply a strong algorithm,
53
Public Key Cryptography
? Adi Shamir listed three reasons why this is so,
? 1,Complexity theory usually deals with single
isolated instances of a problem,A cryptanalyst often
has a large collection of statistically related problems
to solve—several ciphertexts encrypted with the
same key,
? 2,The computational complexity of a problem is
typically measured by its worst-case or average-case
behavior,To be useful as a cipher,the problem must
be hard to solve in almost all cases,
? 3,An arbitrarily difficult problem cannot necessarily
be transformed into a cryptosystem,and it must be
possible to insert trapdoor information into the
problem so that a shortcut solution is possible with
this information and only with this information,
54
References
? Diffie,Hellman.,New Directions in
Cryptography”,
? Aleksandar Jurisic,Alfred J,Menezes,Elliptic
Curves and Cryptography
? Certicom’s ECC Tutorial,
http://www.certicom.com/resources/ecc_tutorial/ecc_tutorial.h
tml
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.2
Public Key Cryptography
2
Diffie-Hellman
? Diffie-Hellman is a public key distribution
scheme
? First public-key type scheme,proposed in
1976,
– W Diffie,M E Hellman,"New directions in
Cryptography",IEEE Trans,Information
Theory,IT-22,pp644-654,Nov 1976
3
4
Diffie-Hellman
? Public-key distribution scheme
? Cannot be used to exchange an arbitrary message
? Exchange only a key,whose value depends on the
participants (and their private and public key
information)
? The algorithm is based on exponentiation in a
finite (Galois) field,either over integers modulo a
prime,or a polynomial field
5
Diffie-Hellman
? Security relies on the difficulty of computing
logarithms in these fields
– discrete logarithms takes O(e log n log log n) operations
? The algorithm,
– two people Alice and Bob who wish to exchange
some key over an insecure communications channel,
– They select a large prime p (~200 digit),such as (p-
1)/2 should also be prime
– They also select g,a primitive root mod p
? g is a primitive if for each n from 0 to p-1,there
exists some a where ga = n mod p,
6
Diffie-Hellman
? The algorithm
– The values of g and p don’t need to be secret
– Alice then chooses a secret number a
– Bob also chooses a secret number b
– Alice and Bob compute yA and yB respectively,
which are then exchanged
? yA = ga mod p yB = gb mod p
– Both Alice and Bob can calculate the key as
? KAB = gab mod p
= yAb mod p (which B can compute)
= yBa mod p (which A can compute)
– The key may then be used in a private-key cipher
to secure communications between A and B
7
Alice ga mod p Bob
gb mod p
The private key is,gab mod p
where p is a prime and g is a generator of Zp
Diffie-Hellman
8
? Knows ga,gb,g,and p
? So we want to find the key,k
– k = gab
– This is believed to be hard,
? If one knows how to compute discrete logs
efficiently,then one can break this scheme
(and other schemes based on public key
cryptography)
Diffie-Hellman
9
Diffie-Hellman
? Can be expanded to be used with many parties
? Can be extended to,
– Finite fields GFp
– Elliptic curves
– Galois field
? Computing discrete logarithms is closely related to
factoring,If you can solve the discrete logarithm
problem,then you can factor,(The converse has
never been proven to be true.)
GF k2
10
El Gamal
? A variant of the Diffie-Hellman key distribution
scheme,allowing secure exchange of messages
? Published in 1985 by ElGamal in
– T,ElGamal,"A Public Key Cryptosystem and a
Signature Scheme Based on Discrete Logarithms",
IEEE Trans,Information Theory,vol IT-31(4),pp469-
472,July 1985,
? Like Diffie-Hellman its security depends on the
difficulty of factoring logarithms
11
The ElGamal encryption scheme
Let p be a prime and g ? Zp* a primitive element,
Let P = Zp*,
C = Zp* x Zp* and
K = {(p,g,x,y),y = gx mod p },
? The values p,g,y are the public key,
? x is the private key,
12
The ElGamal encryption scheme
? Encryption
Let m ? Zp* be a message,
For K = {(p,g,x,y),y = gx mod p },and secret
random number k ? Zp-1,define,eK(m,k) = (s,t),
where
– s = gk mod p
– t = m yk mod p
? Decryption
For s,t ? Zp*,define,dK(s,t) = t (sx)-1mod p
13
An Example
? Let p =2357,g = 2,x = 1751,y ? gx ? 21751 ? 1185
(mod 2357)
? System parameters,(p,g) = (2357,2)
Public key,y = 1185,Private key,x = 1751
? Encryption:say M = 2035
1.Pick a random number k = 1520
2.Computes
s = gk ? 21520 ? 1430 (mod 2357)
t = Myk ? 2035 x 11851520 ? 697 (mod 2357)
– The ciphertext C = (s,t) = (1430,697)
? Decryption,
1.Computes u ? sx ? 14301751 ? 2084 (mod 2357)
2.M ? t u-1 ? 697 x 2084-1 ? 2035 (mod 2357)
14
The security of ElGamal
? The Diffie-Hellman problem,
Given a prime p,g e Zp*,and x,y e Zp*,find xlog gy
mod p,
The security of the ElGamal encryption is reduced to
the difficulty of breaking the Diffie-Hellman
problem,
15
Remarks on El-Gamal Encryption
Scheme
? ElGamal encryption scheme is non-deterministic
? Randomization is introduced to
– increase the effective size of the plaintext space
i.e,one plaintext can map to a large set of possible
ciphertexts
– decrease the effectiveness of chosen-plaintext attack by
means of a one-to-many mapping in the encryption process
? Efficiency,
– encryption requires two exponentiation operations
– exponentiation operations may be very expensive when
implemented on some low-power devices,e.g,low-end
PalmPilots,smart cards and sensors,
– message expansion by two-fold
? Security:depends on the difficulty of solving DLP,
16
Elliptic Curve
? The elliptic curve cryptosystem are modifications
of other systems that work in the domains of
elliptic curve rather than finite fields,
? The elliptic curve cryptosystems appear to remain
secure for smaller keys than other public-key
cryptosystems,
? The use of elliptic curves was first proposed by
Miller (1986) and Koblitz (1987),
? Already,ECC is showing up in standardization
efforts,including IEEE P1363 Standard for
Public-Key Cryptography,
17
RSA Modular Exponentiation y =
xe mod n
512 768 1024 1536 2048
0
60
120
180
240
300
360
R S A k e y s i z e k [ b i t s ]
p
r
o
c
e
s
s
i
n
g
t
i
m
e
t
[
s
]
RSA key size
k [bits]
Processing
time t [s]
512 8
768 22
1024 48
1536 150
2048 335
18
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
y2 = x3 + ax + b
4a3 + 27b2 ? 0
General form,
Condition for distinct
single roots,
Example,
y2 = x3 ? 4x
= x(x ?2)(x +2)
What are Elliptic Curves?
19
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + Q
Group set,
All points P(x,y) lying
on an elliptic curve
Group operation,
Point addition
R'
R P
Q
Points P(x,y) on an Elliptic Curve
form a Group
20
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
Inverse element,
P'(x,-y) = P(x,y)
is mirrored on x-axis
Point addition with
inverse element,
P + P' = O
results in a neutral
element O(x,?) at
infinity P'
O
Neutral element,
P + O = P
P
Neutral and Inverse Elements
21
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + P
Point Doubling,
Form the tangent in
Point P(x,y)
R'
R P
Point Doubling – Adding a point
to itself
22
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
kP = P + P +,.,+ P
Point Iteration,
3P
2P P
Point Iteration – Adding a point
k-1 times to itself
23
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R' (xR,-yR)
R(xR,yR) P(xP,yP)
Q (xQ,yQ)
g
Intersection with curve,
(s? x?y0)2 = x3 +ax+b
Line g,y = s? x?y0
with
s y yx xQ P
Q P
? ??
y y s xP P0 ? ? ?
x s x x
y s x y
R P Q
R R
? ? ?
? ? ? ?
2
0( )
Coordinates of point R,
Mathematical Description of
Geometrical Transform
24
Intersection with curve,
(s? x?y0)2 = x3 +ax+b
x s x
y s x y
R P
R R
? ?
? ? ? ?
2
0
2
( )
Coordinates of point R,
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R' (xR,-yR)
R (xR,yR)
P(xP,yP)
g
Tangent g,y = s? x?y0
s dydx x ayP
P
? ? ?3 2
2
y y s xP P0 ? ? ?
Mathematical Description of
Geometrical Transform
25
How can Geometry be useful for
Cryptography?
Elliptic curves can be defined in a finite or Galois field GFp,
y2 = x3 + ax + b mod p
where the field size p is a prime number and
{0,1,...,p-1} is an abelian group under addition mod p
and
{1,...,p-1} is an abelian group under multiplication mod p,
26
DESCRIPTION
? An elliptic curve is given by F,y2 = x3 + ax + b
and defined for Zp,where Zp represents the set of
integers between 0 and p,includes all pairs of
numbers (x,y)?Zp ? Zp which satisfy,
y2=x3+ax+b(mod p)
? where p is a prime number,p > 3 and a and b are
constants for which
4a3 +27b2 ? 0(mod p),
? the points on F can be found by determining
z = x3 + ax + b(mod p) for every x?Zp,and then
calculating the corresponding y:z = y2 (mod p),
27
Differences
? There are several major differences between elliptic curve groups
over GF(p) and over real numbers,
? Elliptic curve groups over GF(p) have a finite number of points,
which is a desirable property for cryptographic purposes,
? Since these curves consist of a few discrete points,it is not clear
how to "connect the dots" to make their graph look like a curve – it
is not clear how geometric relationships can be applied,
? As a result,the geometry used in elliptic curve groups over real
numbers cannot be used for elliptic curve groups over GF(p),
? However,the algebraic rules for the arithmetic can be adapted for
elliptic curves over GF(p),
? Unlike elliptic curves over real numbers,computations over the
field of GF(p) involve no round off error - an essential property
required for a cryptosystem,
28
Task 1 - Multiplication c = a?b in
GF11
? Compile a multiplication table for c = a ? b mod 11
? Determine the solutions of the equation x2 = 5 mod 11
29
Solution 1 - Multiplication c =
a?b in GF11
0 0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9 10
0 2 4 6 8 10 1 3 5 7 9
0 3 6 9 1 4 7 10 2 5 8
0 4 8 1 5 9 2 6 10 4 7
0 5 10 4 9 3 8 2 7 1 6
0 6 1 7 2 8 3 9 4 10 5
0 7 3 10 6 2 9 5 1 8 4
0 8 5 2 10 7 4 1 9 6 3
0 9 7 5 3 1 10 8 6 4 2
0 10 9 8 7 6 5 4 3 2 1
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
a
b
c
?
x2 = 5 mod 11?
x1 = 4,x2 =
7
30
? Which points P(x,y) with x and y in GF11 fulfill the
elliptic curve equation,
y2 = x3 + x + 6 mod 11
Task 2 – Points on an Elliptic
Curve
31
Solution 2 – Points on an Elliptic
Curve
6 -
8 -
5 4,7 (2,4) (2,7)
3 5,6 (3,5) (3,6)
8 -
4 2,9 (5,2) (5,9)
8 -
4 2,9 (7,2) (7,9)
9 3,8 (8,3) (8,8)
7 -
4 2,9 (10,2) (10,9)
y2 y1,2 P(x,y) P'(x,y)
0
1
2
3
4
5
6
7
8
9
10
x
There are 12 points lying
on the elliptic curve,
Together with the point O at
infinity,the points on the
elliptic curve form a group
with n=13 elements,
n is called the order of the
elliptic curve group and
depends on the choice of the
curve parameters a and b,
32
Points on an Elliptic Curve
An elliptic curve E defined over Zp (P prime,
P>3) will have roughly P points on it,More
precisely,a well-known theorem due to Hasse
asserts that the number of points on E,which
we denote by #E,satisfies the following
inequality
ppEpp 21#21 ??????
33
Task 3 – Iterate a Point on the
Elliptic Curve
? Iterate the point P(2,4) lying on y2 = x3 + x + 6 mod 11,
? Compute 2P = P + P by doubling the point P
x s x
y s x y
R P
R R
? ?
? ? ? ?
2
0
2
( )
s dydx x ayP
P
? ? ?3 2
2
y y s xP P0 ? ? ?
? Compute 3P = P + P + P = 2P + P by point addition
s y yx xQ P
Q P
? ??
y y s xP P0 ? ? ?
x s x x
y s x y
R P Q
R R
? ? ?
? ? ? ?
2
0( )
? All operations are computed in GF11
34
Solution 3 – Iterate a Point on the
Elliptic Curve
? Compute 2P = P + P by doubling the point P(2,4)
x
y
R
R
? ? ? ?
? ? ? ? ? ? ?
9 2 2 5
3 5 9 2 9( )
s ? ? ?? ? ? ? ?3 4 12 4 138 7 2 3
y 0 4 3 2 2 9? ? ? ? ? ?
2P=(5,9)
? Compute 3P = P + P + P = 2P + P by point addition
s ? ?? ? ? ? ?9 45 2 53 4 5 9
y 0 4 9 2 3 8? ? ? ? ? ?
x
y
R
R
? ? ? ?
? ? ? ? ? ? ?
81 2 5 8
9 8 8 3 8( )
3P=(8,8)
35
Elliptic Curve Discrete
Logarithm Problem (ECDLP)
( 2,4) 3 9
( 5,9) 9 8
( 8,8) 8 10
(10,9) 2 0
( 3,5) 1 2
( 7,2) 4 7
( 7,9) 1 2
( 3,6) 2 0
(10,2) 8 10
( 8,3) 9 8
( 5,2) 3 9
( 2,7) ? -
O ? -
kP s y0
1
2
3
4
5
6
7
8
9
10
11
12
13
k
Given an elliptic curve
y2 = x3 + ax + b mod p
and a basis point P,we can compute
Q = kP
through k-1 iterative point additions,
Fast algorithms for this task exist,
Question,Is it possible to compute k
when the point Q is known?
Answer,This is a hard problem known
as the Elliptic Curve Discrete Logarithm,
36
Definition of an Elliptic Curve
Cryptosystem
? version is currently v1
? fieldID identifies the finite field over which curve is defined
? curve coefficients a and b of the elliptic curve
? base specifies the base point P,a point P in the elliptic
curve group defined over GF(p)
? order the order n of the base point
37
Cryptographic Application –
Secret Key Exchange
QA = a P
? Elliptic Curve Cryptosystem,ECC,basis point P and prime p
Secret,
S = bQA = aQB = ab P QB = b P
A = ga mod p
? Diffie-Hellman,Basis g and prime p
B = gb mod p
Secret,
s = Ab = Ba = gab mod p
38
Elliptic Curve Encryption Scheme (ECES)
? Setup,
– let E be an elliptic curve defined over GF(p) and g
be a point of order q in the elliptic curve group such
that ECDLP is intractable,
– randomly chooses x ?R Zq,and computes y ? x P,
1.System Parameters,(E,p,P,q)
2.Public Key, y
3.Private Key,x
39
Elliptic Curve Encryption Scheme (ECES)
? Encryption,
1.Picks randomly an integer k ? Zq,
2.computes
s = k P,t = M ? H(ky)
where M ? {0,1}k is the message of k bits long,H is
some appropriate function which maps a point to a
k-bit binary string (e.g,a hash function),
– The ciphertext C = (s,t),
? Decryption,
1.Computes u = xs from s,
2.M = t ? H(u)
40
ElGamal encryption
? ElGamal encryption,
E,elliptic curve
g,a generator ? E
B’s ―long-term‖ private key x
B’s ―long-term‖ public key y= x P ? E
Encryption,A B
Plaintext M?E
― short-term‖ secret key k
compute s = k P,
t= M +k y
(s,t) is the ciphertext
Decryption,
M = t - xs
Note,M should be a
point in the elliptic
curve,
41
Example
Suppose that P = (2,7) and Bob’s secret ―exponent ‖
is x=7,so y = 7 P =(7,2)
Thus the encryption operation is
e (M,k) = (k(2,7),M+k(7,2)),where M?E and 0? k
? 12,and the decryption operation is
d ( s,t)= t-7s,
Suppose that Alice wishes to encrypt the message
M=(10,9) (which is a point on E),If she chooses the
random value k=3,then she will compute
s= 3(2,7) =(8,3)
and t=(10,9)+3(7,2) = (10,9)+(3,5) = (10,2)
42
Example
(Continue)
Hence,c=((8,3),(10,2)),Now,if Bob receives the
ciphertext c,he decrypts it as follows,
M = (10,2) - 7(8,3)
= (10,2) - (3,5)
= (10,2) + (3,6)
= (10,9)
Hence,the decryption yields the correct plaintext,
43
Equivalent Cryptographic
Strength
Symmetric
RSA n
ECC p
56
512
112
80
1024
161
112
2048
224
128
3072
256
192
7680
384
256
15360
512
Key size ratio 5:1 6:1 9:1 12:1 20:1 30:1
44
0
0, 1
0, 2
0, 3
0, 4
0, 5
0, 6
0, 7
0, 8
0, 9
1
C O M P A R I S O N O F S E C U R I T Y L E V E L S
E C C a n d R S A & D S A
0
1000
2000
3000
4000
5000
6000
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
E
+
1
2
1
E
+
2
0
1
E
+
3
6
T i m e t o B r e a k K e y ( M I P S Y e a r s )
K
e
y
S
i
z
e
(
B
i
t
s
)
E C C
R S A & D S A
Comparison of RSA,ECC,DSA
45
Comparison of PK Systems
? Does breaking the system really require
solving the underlying mathematical
problem?
? Which is the hardest problem?
? IFP and DLP – subexponential
O(exp((c+o(1)))(ln n)1/3(ln ln n)2/3)
? ECDLP – exponential
O(?p)
46
Applications of ECC
? Constrained Channels
- Wireless Devices
- ECC – shorter keys,faster computations
- Reduction in data transmitted – save power
o Smart Cards and Tokens
47
Conclusion
? Usual situations – RSA is good,ECC is
better
? Special systems – constrained or high
security requirements – ECC is currently
the only option
? In the future,computational power will
increase – RSA will soon become
unmanageable,ECC – a viable alternative
48
Public Key Cryptography Standards
? PKCS #1,RSA Cryptography Standard
? PKCS #2,incorporated into PKCS #1
? PKCS #3,Diffie-Hellman Key Agreement Standard
? PKCS #4,incorporated into PKCS #1
? PKCS #5,Password-Based Cryptography Standard
? PKCS #6,Extended-Certificate Syntax Standard
? PKCS #7,Cryptographic Message Syntax Standard
? PKCS #8,Private-Key Information Syntax Standard
? PKCS #9,Selected Attribute Types
? PKCS #10,Certification Request Syntax Standard
? PKCS #11,Cryptographic Token Interface Standard
? PKCS #12,Personal Information Exchange Syntax Standard
? PKCS #13,Elliptic Curve Cryptography Standard
? PKCS #15,Cryptographic Token Information Format Standard
http://www.rsasecurity.com/rsalabs/pkcs/
49
Public Key Cryptography
? In 1988 Whitfield Diffie noted that most public-key
algorithms are based on one of three hard problems
? 1,Knapsack,Given a set of unique numbers,find a
subset whose sum is N,
– 2,Discrete logarithm,If p is a prime and g and m
are integers,find x such that gx ≡ M (mod p),
– 3,Factoring,If N is the product of two primes,either
? a) factor N,
? b) given integers M and C,find d such that Md ≡
C (mod N),
? c) given integers e and C,find M such that Me ≡
C (mod N),or
? d) given an integer x,decide whether there exists
an integer y such that x ≡ y2 (mod N),
50
Public Key Cryptography
? This narrowness in the mathematical foundations
of public-key cryptography is worrisome,
? A breakthrough in either the problem of
factoring or of calculating discrete logarithms
could render whole classes of public-key
algorithms insecure,
51
Public Key Cryptography
? Diffie points out,
? 1,The operations on which public key cryptography
currently depends—multiplying,exponentiating,and
factoring—are all fundamental arithmetic
phenomena,
? 2,Our ability to carry out large arithmetic
computations has grown steadily and now permits us
to implement our systems with numbers sufficient in
size to be vulnerable only to a dramatic breakthrough
in factoring,logarithms,or root extraction,
52
Public Key Cryptography
? As we have seen,not all public-key algorithms
based on these problems are secure,
? The strength of any public-key algorithm
depends on more than the computational
complexity of the problem upon which it is
based; a hard problem does not necessarily
imply a strong algorithm,
53
Public Key Cryptography
? Adi Shamir listed three reasons why this is so,
? 1,Complexity theory usually deals with single
isolated instances of a problem,A cryptanalyst often
has a large collection of statistically related problems
to solve—several ciphertexts encrypted with the
same key,
? 2,The computational complexity of a problem is
typically measured by its worst-case or average-case
behavior,To be useful as a cipher,the problem must
be hard to solve in almost all cases,
? 3,An arbitrarily difficult problem cannot necessarily
be transformed into a cryptosystem,and it must be
possible to insert trapdoor information into the
problem so that a shortcut solution is possible with
this information and only with this information,
54
References
? Diffie,Hellman.,New Directions in
Cryptography”,
? Aleksandar Jurisic,Alfred J,Menezes,Elliptic
Curves and Cryptography
? Certicom’s ECC Tutorial,
http://www.certicom.com/resources/ecc_tutorial/ecc_tutorial.h
tml
