1 of 30

��ASYMMETRIC CIPHERS: Principles of Public-Key Cryptosystems, The �RSA algorithm, Diffie - Hellman Key Exchange, Elliptic Curve Arithmetic,�Elliptic Curve Cryptography �(Text 1: Chapter 8, Chapter 9: Section 1, 3, 4)��Text Books:�1. William Stallings , “Cryptography and Network Security Principles and Practice”, � Pearson Education Inc., 6th Edition, 2014, ISBN: 978-93-325-1877-3�2. Bruce Schneier, “Applied Cryptography Protocols, Algorithms, and Source code � in C”, Wiley Publications, 2nd Edition, ISBN: 9971-51-348-X.� � Reference Books: �1. Cryptography and Network Security, Behrouz A. Forouzan, TMH, 2007.�2. Cryptography and Network Security, Atul Kahate, TMH, 2003. ��

MODULE 4

2 of 30

*

2

Asymmetric Key Encryption

Diffie and Hellman

3 of 30

*

3

4 of 30

*

4

Conventional Encryption	Public-Key Encryption
Needed to Work:	Needed to Work:
The same algorithm with the same key is used for encryption and decryption. The sender and receiver must share the algorithm and the key.	One algorithm is used for encryption and decryption with a pair of keys, one for encryption and one for decryption. The sender and receiver must each have one of the matched pair of keys (not the same one).
Needed for Security:	Needed for Security:
The key must be kept secret. It must be impossible or at least impractical to decipher a message if no other information is available. Knowledge of the algorithm plus samples of ciphertext must be insufficient to determine the key.	One of the two keys must be kept secret. It must be impossible or at least impractical to decipher a message if no other information is available. Knowledge of the algorithm plus one of the keys plus samples of ciphertext must be insufficient to determine the other key.

5 of 30

*

5

Y = E(PU_b, X)

X = D(PR_b, Y)

6 of 30

*

6

Y = E(PR_a, X) X = D(PU_a, Y)

7 of 30

*

7

Z = E(PU_b, E(PR_a, X)) X = D(PU_a, E(PR_b, Z))

8 of 30

*

8

9 of 30

*

9

Requirements for Public-Key Cryptography

1. It is computationally easy for a party B to generate a pair (public key PU_b,

private key PR_b).

2. It is computationally easy for a sender A, knowing the public key and the

message to be encrypted, M, to generate the corresponding ciphertext:

C = E(PU_b, M)

3. It is computationally easy for the receiver B to decrypt the resulting

ciphertext using the private key to recover the original message:

M = D(PR_b, C) = D[PR_b, E(PU_b, M)]

4. It is computationally infeasible for an adversary, knowing the public key,

PU_b, to determine the private key, PR_b.

5. It is computationally infeasible for an adversary, knowing the public key,

PU_b, and a ciphertext, C, to recover the original message, M.

We can add a sixth requirement that, although useful, is not necessary for all public-key applications:

6. The two keys can be applied in either order:

M = D[PU_b, E(PR_b, M)] = D[PR_b, E(PU_b, M)]

10 of 30

*

10

The RSA (Ron Rivest, Adi Shamir, and Len Adleman) Algorithm 1977

C = M^e mod n

M = C^d mod n = (M^e)^d mod n = M^ed mod n

For this algorithm to be satisfactory for public-key encryption, the following requirements must be met:

It is possible to find values of e, d, n such that M^ed mod n = M for all M < n.
It is relatively easy to calculate mod M^e mod n and C^d for all values of M < n.
It is infeasible to determine d given e and n.

M^ed mod n = M

The preceding relationship holds if e and d are multiplicative inverses modulo φ(n), where φ(n) is the Euler totient function.

For p, q prime, φ(pq) = (p -1)(q-1) The relationship between e and d can be expressed as

11 of 30

*

11

That is, e and d are multiplicative inverses mod f(n). Note that, according to the rules of modular arithmetic, this is true only if d (and therefore e) is relatively prime to f(n).

Equivalently, gcd(f(n),d) = 1.

12 of 30

*

12

13 of 30

*

13

Two numbers are relatively prime if they have no prime factors in common; that is, their only common divisor is 1. This is equivalent to saying that two numbers are relatively prime if their greatest common divisor is 1.

Select two prime numbers, p = 17 and q = 11.
Calculate n = pq = 17 x 11 = 187.
Calculate f(n) = (p-1)(q-1) = 16 x 10 = 160.
Select e such that e is relatively prime to f(n) = 160 and less than f(n) we choose e = 7.
Determine d such that de 1 (mod 160) and d < 160. The correct value is d = 23, because 23 x 7 = 161 = 10 x 160 + 1; d can be calculated using the extended Euclid's algorithm.

14 of 30

*

14

EXTENDED EUCLID(f(ɸ), e)

(A1, A2, A3) 🡨(1, 0, f(ɸ)); (B1, B2, B3) 🡨 (0, 1, e)
If B3 = 0 return A3 = gcd(f(ɸ), b); no inverse
If B3 = 1 return B3 = gcd(f(ɸ), b); B2 = b¹ mod f(ɸ)

4. Q = A3

B3

5. (T1, T2, T3) 🡨(A1-QB1, A2-QB2, A3-QB3)

6. (A1, A2, A3) 🡨(B1, B2, B3)

7. (B1, B2, B3) 🡨(T1, T2, T3)

8. Goto 2

If gcd(f(ɸ), e) = 1, then e has a multiplicative inverse modulo f(ɸ).

That is, for positive integer b < f(ɸ), there exists a e¹ < f(ɸ) such that ee¹ = 1 mod f(ɸ). The Euclidean algorithm can be extended so that, in addition to finding gcd(f(ɸ), e), if the gcd is 1, the algorithm returns the multiplicative inverse of e.

15 of 30

*

15

Diffie–Hellman key exchange

First, we define a primitive root of a prime number p as one whose powers modulo p generate all the integers from 1 to p-1. That is, if a is a primitive root of the prime number p, then the numbers

a mod p, a² mod p,..., a^p-1 mod p

are distinct and consist of the integers from 1 through p-1 in some permutation.

For any integer b and a primitive root a of prime number p, we can find a unique exponent i such that

Used for sharing a secret key

16 of 30

*

16

The number 3 is a primitive root modulo 7 because

17 of 30

*

17

The Algorithm

18 of 30

*

18

19 of 30

*

19

K	= (Y_B)^XA mod q
	= (a^XB mod q)^XA mod q
	= (a^XB)^XA mod q	by the rules of modular arithmetic
	= (a^{XB XA} mod q
	= (a^XA)^XB mod q
	= (a^XA mod q)
	= (a^XA mod q)^XB mod q
	= (Y_A)^XB mod q

20 of 30

*

20

Alice and Bob agree to use a prime number q=23 and base a=5.
Alice chooses a secret integer Xa=6, then sends Bob Ya= a^Xa mod q

Ya = 5⁶ mod 23
Ya = 15,625 mod 23
Ya = 8

Bob chooses a secret integer Xb=15, then sends Alice Yb = a^Xb mod q

Yb = 5¹⁵ mod 23
Yb = 30,517,578,125 mod 23
Yb = 19

Alice computes s = Yb ^Xa mod q

s = 19⁶ mod 23
s = 47,045,881 mod 23
s = 2

21 of 30

*

21

Bob computes s = Ya ^Xb mod q

s = 8¹⁵ mod 23
s = 35,184,372,088,832 mod 23
s = 2

Alice and Bob now share a secret: s = 2. This is because 6*15 is the same as 15*6. So somebody who had known both these private integers might also have calculated s as follows:

s = 5^6*15 mod 23
s = 5^15*6 mod 23
s = 5⁹⁰ mod 23
s = 807,793,566,946,316,088,741,610,050,849,573,099,185,363,389,551,639,556,884,765,625 mod 23
s = 2

22 of 30

Elliptic Curve Cryptography

majority of public-key crypto (RSA, D-H) use either integer or polynomial arithmetic with very large numbers/polynomials
imposes a significant load in storing and processing keys and messages
an alternative is to use elliptic curves
offers same security with smaller bit sizes
newer, but not as well analysed

A major issue with the use of Public-Key Cryptography, is the size of numbers used, and hence keys being stored. Recently, an alternate approach has emerged, elliptic curve cryptography (ECC), which performs the computations using elliptic curve arithmetic instead of integer or polynomial arithmetic. Already, ECC is showing up in standardization efforts, including the IEEE P1363 Standard for Public-Key Cryptography. The principal attraction of ECC, compared to RSA, is that it appears to offer equal security for a far smaller key size, thereby reducing processing overhead. Although the theory of ECC has been around for some time, it is only recently that products have begun to appear and that there has been sustained cryptanalytic interest in probing for weaknesses. Accordingly, the confidence level in ECC is not yet as high as that in RSA.

23 of 30

Real Elliptic Curves

an elliptic curve is defined by an equation in two variables x & y, with coefficients
consider a cubic elliptic curve of form

y² = x³ + ax + b
where x,y,a,b are all real numbers
also define zero point O

consider set of points E(a,b) that satisfy
have addition operation for elliptic curve

geometrically sum of P+Q is reflection of the intersection R

An elliptic curve is defined by an equation in two variables, with coefficients. For cryptography, the variables and coefficients are restricted to elements in a finite field, which results in the definition of a finite abelian group (see Ch 4 for details of an abelian group). Before looking at this, we first look at elliptic curves in which the variables and coefficients are real numbers. This case is perhaps easier to visualize. Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar to those used for calculating the circumference of an ellipse. For our purpose, we can consider cubic equations for elliptic curves of the form shown here. Also included in the definition of an elliptic curve is a single element denoted O and called the point at infinity or the zero point. Now, consider the set of points E(a, b) consisting of all of the points (x, y) that satisfy this equation together with the element O. Using a different value of the pair (a, b) results in a different set E(a, b). See text for detailed rules of addition and relation to zero point O. Can derive an algebraic interpretation of addition, based on computing gradient of tangent and then solving for intersection with curve. There is also an algebraic description of additions over elliptic curves, see text.

24 of 30

Real Elliptic Curve Example

Stallings Figure 10.4b “Example of Elliptic Curves”, illustrates the geometric interpretation of elliptic curve addition, as follows: If three points on an elliptic curve lie on a straight line, their sum is O. hence define addition as:

O serves as the additive identity. Thus O = –O; for any point P on the elliptic curve, P + O = P. In what follows, we assume P <> O and Q <> O.
The negative of a point P is the point with the same x coordinate but the negative of the y coordinate; that is, if P = (x, y), then –P = (x, –y). These two points can be joined by a vertical line & that P + (–P) = P – P = O.
To add two points P and Q with different x coordinates, draw a straight line between them and find the third point of intersection R. There is a unique point R that is the point of intersection (unless the line is tangent to the curve at either P or Q, in which case we take R = P or R = Q, respectively). To form a group structure, we need to define addition on these three points as follows: P + Q = –R. ie. P + Q to be the mirror image (with respect to the x axis) of the third point of intersection as shown on slide.
The geometric interpretation of the preceding item also applies to two points, P and –P, with the same x coordinate. The points are joined by a vertical line, which can be viewed as also intersecting the curve at the infinity point. We therefore have P + (–P) = O, consistent with item (2).
To double a point Q, draw the tangent line and find the other point of intersection S. Then Q + Q = 2Q = –S.

With the preceding list of rules, it can be shown that the set E(a, b) is an abelian group.

25 of 30

Finite Elliptic Curves

Elliptic curve cryptography uses curves whose variables & coefficients are finite
have two families commonly used:

prime curves E_p(a,b) defined over Z_p

use integers modulo a prime
best in software

binary curves E_2m(a,b) defined over GF(2ⁿ)

use polynomials with binary coefficients
best in hardware

26 of 30

Elliptic Curve Cryptography

ECC addition is analog of modulo multiply
ECC repeated addition is analog of modulo exponentiation
need “hard” problem equiv to discrete log

Q=kP, where Q,P belong to a prime curve
is “easy” to compute Q given k,P
but “hard” to find k given Q,P
known as the elliptic curve logarithm problem

Certicom example: E₂₃(9,17)

Elliptic Curve Cryptography uses addition as an analog of modulo multiply, and repeated addition as an analog of modulo exponentiation. The “hard” problem is the elliptic curve logarithm problem. We give an example taken from the Certicom Web site (www.certicom.com). Consider the group E₂₃(9, 17). This is the group defined by the equation y² mod 23 = (x³ + 9x + 17) mod 23. What is the discrete logarithm k of Q = (4, 5) to the base P = (16, 5)? The brute-force method is to compute multiples of P until Q is found. Thus P = (16, 5); 2P = (20, 20); 3P = (14, 14); 4P = (19, 20); 5P = (13, 10); 6P = (7, 3); 7P = (8, 7); 8P = (12, 17) ; 9P = (4, 5). Because 9P = (4, 5) = Q, the discrete logarithm Q = (4, 5) to the base P = (16, 5) is k = 9. In a real application, k would be so large as to make the brute-force approach infeasible.

27 of 30

ECC Diffie-Hellman

can do key exchange analogous to D-H
users select a suitable curve E_q(a,b)
select base point G=(x₁,y₁)

with large order n s.t. nG=O

A & B select private keys n_A<n, n_B<n
compute public keys: P_A=n_AG, P_B=n_BG
compute shared key: K=n_AP_B,K=n_BP_A

same since K=n_An_BG

attacker would need to find k, hard

Illustrate here the elliptic curve analog of Diffie-Hellman key exchange, which is a close analogy given elliptic curve multiplication equates to modulo exponentiation. Key exchange using elliptic curves can be done in the following manner. First pick a large integer q, which is either a prime number p or an integer of the form 2^m and elliptic curve parameters a and b for Equation (10.5) or Equation (10.7). This defines the elliptic group of points E_q(a, b). Next, pick a base point G = (x₁, y₁) in E_q(a, b) whose order is a very large value n. The order n of a point G on an elliptic curve is the smallest positive integer n such that nG = O. So E_q(a, b) and G are parameters of the cryptosystem known to all participants. A key exchange between users A and B can then be accomplished as shown. To break this scheme, an attacker would need to be able to compute k given G and kG, which is assumed hard.

28 of 30

ECC Encryption/Decryption

several alternatives, will consider simplest
must first encode any message M as a point on the elliptic curve P_m
select suitable curve & point G as in D-H
each user chooses private key n_A<n
and computes public key P_A=n_AG
to encrypt P_m : C_m={kG, P_m+kP_b}, k random
decrypt C_m compute:

P_m+kP_b–n_B(kG) = P_m+k(n_BG)–n_B(kG) = P_m

29 of 30

ECC Security

relies on elliptic curve logarithm problem
fastest method is “Pollard rho method”
compared to factoring, can use much smaller key sizes than with RSA etc
for equivalent key lengths computations are roughly equivalent
hence for similar security ECC offers significant computational advantages

30 of 30

Comparable Key Sizes for Equivalent Security

Symmetric scheme (key size in bits)	ECC-based scheme (size of n in bits)	RSA/DSA (modulus size in bits)
56	112	512
80	160	1024
112	224	2048
128	256	3072
192	384	7680
256	512	15360