Winsem2017-18 Cse4003 Eth Sjt502 Vl2017185003779 Reference Material II Ecc1-Madhu
Winsem2017-18 Cse4003 Eth Sjt502 Vl2017185003779 Reference Material II Ecc1-Madhu
Winsem2017-18 Cse4003 Eth Sjt502 Vl2017185003779 Reference Material II Ecc1-Madhu
10.19
Figure Three adding cases in an elliptic curve
10.20
Group Law Axioms
•Closure
•Identity:
P+O=O+P=P
•Inverse:
(x, y) + (x, -y) = O
•Associativity
•Commutativity
Group Structures
Recall: Groups
The order of the finite field is the number of elements in the field
Elliptic Curves over Galois Field GF(p)
• P+O = O+P = P
• If P = (x1,y1) then -P = (x1 ,-y1)
and P + (-P) = O.
(0,1) (0,12)
(1,4) (1,9)
(4,2) (4,11)
(5,1) (5,12)
(7,0) (7,0)
(8,1) (8,12)
(10,6) (10,7)
(11,2) (11,11)
• Adding Two points:
Let us add two points in the prevoius example,R=P+Q where
P=(4,2) and Q= (10,6)
a. =(6-2) × (10-4)-1 mod 13=4 × 6-1 mod 13=5 mod 13
b. x=11
c. y=2
R=(11,2) which is a point on the curve
• Multiplying a point by a constant:(Scalar Multiplication)
GF(p) Fields
When n = 1, we have GF(p) field. This field can be the set Zp, {0,
1, …, p − 1}, with two arithmetic operations.
ElGamal cryptosystem
C2
10.42
Key Generation
10.43
10.44
10.45
Proof of ElGamal Cryptosystem
d 1
[C2 (C1 ) ] mod p
rd 1
[(e2 P) (e1 ) ] mod p
r
rd 1
(e1 ) P (e1 ) P
rd
10.46
ECC Elgamal
Generating public and private keys:
1.Bob chooses E(a,b) with an elliptic curve over GF(p) or Gf (2n).
2.Bob chooses a point on the curve,e1(x1,y1)
3.Bob chooses an integer,d
4.Bob calculates e2(x2,y2)=d × e1(x1,y1) //multiple addition of points
5.Bob announces E(a,b),e1(x1,y1) and e2( x2,y2) as his public key;he keeps
d as private key
Encryption:
c1=r× e1 c2=P+r × e1
Decryption:
P= c2-(d × C1) // The minus sign here means adding with the inverse
• ECC is based on elliptic curves. We can defined a group GF(p) or GF(2n) in
which the elements are points on an elliptic curve. ECC simulates the idea
of ElGamal using the above-mentioned groups.
– The public key is (e1, e2, and E) in which e1 and e2 are two points on the
curve E. The private key is d.
b.
P −P
(1, 2) (1, 9)
(2, 1) (2, 10)
(4, 2) (4, 9)
(5, 0) (5, 0)
(6, 2) (6, 9)
(7, 0) (7, 0)
(8, 4) (8, 7)
(9, 5) (9, 6)
(10, 0) (10, 0)
Points
c. Bob chooses e1 = (2, 1) and d = 3, then e2 = 3 × (2, 1) =
(4, 9). Public key is E11(1, 2), e1, and e2. The private key is
d.
d. Assume Alice has the plaintext P = (4, 2) to send to
Bob.
• C1 = r × e1 = 6 × (2, 1) = (8, 7)
• C2 = (4, 2) + 6 × (4, 9) = (4, 2) + (8, 4) = (2, 10)
• f. Bob receives C1 and C2. Bob calculates the
plaintext as to get the P.
P = C2 − (d × C1) = (2, 10) − 3 × (8, 7) = (2, 10) − (8, 4) = (2, 10) + (8, 7) = (4, 2)
In the elliptic curve E(g4 ,1) over the GF(24 ) field:
a.Find the equation of the curve
b.Find all points on the curve
c. Generate public and private keys for B
d.choose a point on the curve as a plain text for A
e. Create ciphertext correponding to the
plaintext in part d for A
f. Decrypt the ciphertext for B to find the
plaintext sent by A
a. E(g4, 1) means that a = g4 and b = 1. The equation of the curve
is
y2 + xy = x3 + g4x2 + 1
(0, 1) (0, 1)
(1, g6) (1, g13)
(g3, g8) (g3, g13)
4.56
Polynomials
4.57
Example
Figure 4.9 show how we can represent the 8-bit word (10011001)
using a polynomials.
4.58
Continued
Example
4.59
Continued
GF(2n) Fields
4.60
Continued
Modulus
For the sets of polynomials in GF(2n), a group of
polynomials of degree n is defined as the modulus. Such
polynomials are referred to as irreducible polynomials.
4.61
Continued
Addition
4.62
Continued
Example
4.63
Continued
Example
4.64
Multliplication
4.65
Example 4.19
Solution
4.67
Example
In GF (24), find the inverse of (x2 + 1) modulo (x4 + x + 1).
4.68
Example
In GF(28), find the inverse of (x5) modulo (x8 + x4 + x3 + x + 1).
Solution
The answer is (x5 + x4 + x3 + x) as shown in Table 4.6.
4.69
Multliplication Using Computer
4.70
Example
4.71
Example
4.72
Example
Repeat Example 4.22 using bit patterns of size 8.
Solution
We have P1 = 000100110, P2 = 10011110, modulus = 100011010
(nine bits). We show the exclusive or operation by .
4.73
Example
4.74
Example Continued
Table 4.9 Addition table for GF(23)
4.75
Example
4.76
Sometimes it is easier to define the elements of the
GF(2n) field using a generator.
4.77
Example
Solution
The elements 0, g0, g1, g2, and g3 can be easily generated, because
they are the 4-bit representations of 0, 1, x2, and x3. Elements g4
through g14, which represent x4 though x14 need to be divided by
the irreducible polynomial. To avoid the polynomial division, the
relation ƒ(g) = g4 + g + 1 = 0 can be used (See next slide).
4.78
Example
4.79
Example
4.80
Example
4.81
Summay
4.82
Elliptic Curves over in GF(Galois
Field GF(2n)
The elements of the set in this field are n-bit words that can be
interpreted as polynomials with coefficients in GF(2).
To define Elliptic curve over GF(2n ),The common equation is
y2 +xy= x3 + ax2 +b
Where b≠0.The values of x,y,a and b are polinomials representing
n-bit words.
• Finding an inverse
If P=(x,y) then –P=(x, x+y)
Finding points on the curve
need to use an algorithm to find the points on the curve using
generators for polynomials
Selecting an Elliptic Curve
• Random method
• Complex multiplication method
• Subfield method
a(x,y)
b(x,y)
Alice, A