CS8792

CRYPTOGRAPHY AND NETWORK

SECURITY

UNIT 3 NOTES

Downloaded from: annauniversityedu.blogspot.com

UNIT III PUBLIC KEY CRYPTOGRAPHY

MATHEMATICS OF ASYMMETRIC KEY CRYPTOGRAPHY: Primes – Primality Testing –

Factorization – Euler‘s totient function, Fermat‘s and Euler‘s Theorem – Chinese Remainder
Theorem – Exponentiation and logarithm – ASYMMETRIC KEY CIPHERS: RSA cryptosystem
– Key distribution – Key management – Diffie Hellman key exchange -ElGamal cryptosystem –
Elliptic curve arithmetic-Elliptic curve cryptography.

Downloaded from: annauniversityedu.blogspot.com

TWO ASSERTION OF CRT

Downloaded from: annauniversityedu.blogspot.com

Downloaded from: annauniversityedu.blogspot.com
Downloaded from: annauniversityedu.blogspot.com
Example
Prime Number
An integer p > 1 is a prime number if and only if its only divisors are ±1
and ±p.
Fermat’s Theorem
If p is prime and a is a positive integer not divisible by p, then
ap-1 ≡ 1 (mod p).

Example:
a = 7, p = 19
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)

If p is prime and a is a positive integer, then ap ≡ a(mod p)

Euler’s Totient Function

The number of positive integers less than n and relatively prime to n. ø(1)=1
ø(p) = p - 1
suppose that we have two prime numbers p and q with p ≠ q. Then we can
show that, for n = pq,
ø(n) = ø(pq) = ø(p) * ø(q) = (p - 1) * (q - 1)

Example:
ø(21) = ø(3) * ø(7) = (3 - 1) * (7 - 1) = 2 * 6 = 12
where the 12 integers are {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}.

Euler’s Theorem
Euler’s theorem states that for every a and n that are relatively prime:
aø(n) ≡ 1(mod n)

Downloaded from: annauniversityedu.blogspot.com

Example:
a = 3; n = 10; ø(10) = 4 aø(n) = 34 = 81 = 1 (mod 10) = 1 (mod n)
a = 2; n = 11; ø(11) = 10 aø(n) = 210 = 1024 = 1 (mod 11) = 1 (mod n)

Testing for Primality

Used to determine whether a given number is prime number or not.

Miller-Rabin Algorithm
any positive odd integer n ≥3 can be expressed as
n - 1 = 2kq with k > 0, q odd
n - 1 is an even integer. Then, divide (n - 1) by 2 until the result is an odd number q, for a total of k divisions.
If n is expressed as a binary number, then the result is achieved by shifting the number to the right until the
rightmost digit is a 1, for a total of k shifts.

Properties of Prime Numbers:

First Property:
If p is prime and a is a positive integer less than p, then a2 mod p = 1 if and only if either a mod p = 1 or a
mod p = -1 mod p = p - 1.
By the rules of modular arithmetic (a mod p) (a mod p) = a2 mod p.
Thus, if either a mod p = 1 or a mod p = -1, then a2 mod p = 1.
Conversely, if a2 mod p = 1, then (a mod p)2 = 1, which is true only for
a mod p = 1 or a mod p = -1.

Second Property:
Let p be a prime number greater than 2.
n -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.

1. aq is congruent to 1 modulo p. That is, aq mod p = 1, or equivalently,

aq = 1(mod p).
2. One of the numbers aq, a2q, a4q, ......., a2k - 1q is congruent to -1 modulo p.
That is, there is some number j in the range (1≤ j≤k) such that a2j - 1q
mod p = -1 mod p = p - 1 or equivalently, a2j - 1q = -1 (mod p).

Downloaded from: annauniversityedu.blogspot.com

3.5 DISCRETE LOGARITHMS

Downloaded from: annauniversityedu.blogspot.com

Downloaded from: annauniversityedu.blogspot.com
3.6 ASYMMETRIC KEY CIPHERS:
RSA cryptosystem
The best known and widely regarded as most practical public-key scheme was proposed by
Rivest, Shamir & Adleman in 1977:
It is a public-key scheme which may be used for encrypting messages, exchanging keys, and
creating digital signatures
RSA is a public key encryption algorithm based on exponentiation using modular arithmetic
to use the scheme, first generate keys:
Key-Generation by each user consists of:
 selecting two large primes at random (~100 digit), p, q
 calculating the system modulus R=p.q p, q primes
 selecting at random the encryption key e,
 e < R, gcd(e, F(R)) = 1
 solving the congruence to find the decryption key d,
 e.d [[equivalence]] 1 mod [[phi]](R) 0 <= d <= R
 publishing the public encryption key: K1={e,R}
 securing the private decryption key: K2={d,p,q}

Encryption of a message M to obtain ciphertext C is:

C = Me mod R 0 <= d <= R

Decryption of a ciphertext C to recover the message M is:

M = Cd = Me.d = M1+n.[[phi]](R) = M mod R

The RSA Algorithm

Key Generation

Select p, q p and q both prime, p ≠ q

Calculate n = p * q
Calcuate f(n) = (p - 1)(q - 1)
Select integer e gcd (ø(n), e) = 1; 1<e<ø(n)
Calculate d d ≡e-1 (mod ø(n))
Public key PU = {e, n}
Private key PR = {d, n}

Encryption
Plaintext: M<n
Ciphertext: C =Me mod n

Downloaded from: annauniversityedu.blogspot.com

Decryption
Ciphertext: C
Plaintext: M =Cd mod n

Example:
P=17 q=11 e=7 M=88

1. Select two prime numbers, p = 17 and q = 11.

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

The resulting keys are public key PU={7,187} and private key PR={23,187}.
Plaintext input of M = 88.

For encryption,
calculate C = 887 mod 187.
887 mod 187 = [(884 mod 187) * (882 mod 187) * (881 mod 187)] mod 187
881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 59,969,536 mod 187 = 132
887 mod 187 = (88 * 77 * 132) mod 187 = 894,432 mod 187 = 11

For decryption,
calculate M = 1123 mod 187
1123 mod 187 = [(111 mod 187) * (112 mod 187) * (114 mod 187) *
(118 mod 187) * (118 mod 187)] mod 187
1
11 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 14,641 mod 187 = 55
118 mod 187 = 214,358,881 mod 187 = 33
1123 mod 187=(11* 121 * 55 * 33 * 33) mod 187 =79,720,245 mod 187= 88

The Security of RSA

Brute force: This involves trying all possible private keys.

Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of
two primes.
Timing attacks: These depend on the running time of the decryption algorithm.
Hardware fault-based attack: This involves inducing hardware faults in the processor that is generating
digital signatures.
Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm.

Solve:
a. p = 3; q = 11, e = 7; M = 5
b. p = 5; q = 11, e = 3; M = 9
c. p = 7; q = 11, e = 17; M = 8

Downloaded from: annauniversityedu.blogspot.com

d. p = 11; q = 13, e = 11; M = 7

3.7 KEY MANAGEMET AND KEY DISTRIBUTION

For symmetric encryption to work, the two parties to an exchange must share the same key, and that key
must be protected from access by others. For symmetric encryption to work, the two parties to an exchange
must share the same key, and that key must be protected from access by others.

For two parties A and B, key distribution can be achieved in a number of ways, as follows:

1. A can select a key and physically deliver it to B.

2. A third party can select the key and physically deliver it to A and B.
3. If A and B have previously and recently used a key, one party can transmit the new key to the other,
encrypted using the old key.
4. If A and B each has an encrypted connection to a third party C, C can deliver a key on the encrypted
links to A and B.

A Key Distribution Scenario

User A wishes to establish a logical connection with B and requires a one-time session key to protect the
data transmitted over the connection. A has a master key, Ka, known only to itself and the KDC; similarly,
B shares the
master key Kb with the KDC. The following steps occur.

1. A issues a request to the KDC for a session key to protect a logical connection to B. The message includes
the identity of A and B and a unique identifier, N1, for this transaction, which we refer to as a nonce. The
nonce may be a timestamp, a counter, or a random number; the minimum requirement is that it differs with
each request. Also, to prevent masquerade, it should be difficult for an opponent to guess the nonce. Thus,
a random number is a good choice for a nonce.

2. The KDC responds with a message encrypted using Ka. Thus, A is the only one who can successfully
read the message, and A knows that it originated at the KDC. The message includes two items intended for
A:

• The one-time session key, Ks, to be used for the session

• The original request message, including the nonce, to enable A to match

this response with the appropriate request Thus, A can verify that its original request was not altered before
reception by the KDC and, because of the nonce, that this is not a replay of some previous request.

In addition, the message includes two items intended for B:

• The one-time session key, Ks, to be used for the session

• An identifier of A (e.g., its network address), IDA

These last two items are encrypted with Kb (the master key that the KDC
shares with B). They are to be sent to B to establish the connection and prove A’s identity.

Downloaded from: annauniversityedu.blogspot.com

3. A stores the session key for use in the upcoming session and forwards to B the information that originated
at the KDC for B, namely, E(Kb,[Ks || IDA]).

Because this information is encrypted with Kb, it is protected from eavesdropping. B now knows the session
key (Ks), knows that the other party is A (from IDA), and knows that the information originated at the KDC
(because it is encrypted using Kb).
4. Using the newly minted session key for encryption, B sends a nonce, N2, to A.
5. Also, using Ks, A responds with f(N2), where f is a function that performs
some transformation on N2

Hierarchical Key Control

It is not necessary to limit the key distribution function to a single KDC.

A hierarchical scheme minimizes the effort involved in master key distribution, because most master keys
are those shared by a local KDC with its local entities.

Session Key Lifetime

The more frequently session keys are exchanged, the more secure they are, because the opponent has less
ciphertext to work with for any given session key. On the other hand, the distribution of session keys delays
the start of any exchange and places a burden on network capacity. A security manager must try to balance
these competing considerations in determining the lifetime of a particular session key.

Downloaded from: annauniversityedu.blogspot.com

For connection-oriented protocols, one obvious choice is to use the same session key for the length of time
that the connection is open, using a new session key for each new session. If a logical connection has a very
long lifetime, then it would be prudent to change the session key periodically, perhaps every time the PDU
(protocol data unit) sequence number cycles.

For a connectionless protocol, such as a transaction-oriented protocol, there

is no explicit connection initiation or termination. Thus, it is not obvious how often one needs to change
the session key. The most secure approach is to use a new session key for each exchange. However, this
negates one of the principal benefits of connectionless protocols, which is minimum overhead and delay
for each transaction. A better strategy is to use a given session key for a certain fixed period only or for a
certain number of transactions.

Decentralized Key Control

The use of a key distribution center imposes the requirement that the KDC be trusted and be protected from
subversion. This requirement can be avoided if key distribution is fully decentralized.
A decentralized approach requires that each end system be able to communicate in a secure manner with
all potential partner end systems for purposes of session key distribution. Thus, there may need to be as
many as [n(n - 1)]/2 master keys for a configuration with n end systems.

A session key may be established with the following sequence of steps

1. A issues a request to B for a session key and includes a nonce, N1.

2. B responds with a message that is encrypted using the shared master key. The response includes the
session key selected by B, an identifier of B, the value f(N1), and another nonce, N2.
3. Using the new session key, A returns f(N2) to B.

Symmetric Key Distribution using Asymmetric Encryption

Simple Secret Key Distribution

1. A generates a public/private key pair {PUa, PRa} and transmits a message to B consisting of PUa and an
identifier of A, IDA.
2. B generates a secret key, Ks, and transmits it to A, which is encrypted with A’s public key.
3. A computes D(PRa, E(PUa, Ks)) to recover the secret key. Because only A
can decrypt the message, only A and B will know the identity of Ks.
4. A discards PUa and PRa and B discards PUa.

Downloaded from: annauniversityedu.blogspot.com

Public-Key Distribution of Secret Keys

1. A uses B’s public key to encrypt a message to B containing an identifier of A(IDA) and a nonce (N1),
which is used to identify this transaction uniquely.
2. B sends a message to A encrypted with PUa and containing A’s nonce (N1) as well as a new nonce
generated by B (N2). Because only B could have decrypted message (1), the presence of N1 in message (2)
assures A that the correspondent is B.
3. A returns N2, encrypted using B’s public key, to assure B that its correspondent is A.
4. A selects a secret key Ks and sends M = E(PUb, E(PRa, Ks)) to B. Encryption of this message with B’s
public key ensures that only B can read it; encryption with A’s private key ensures that only A could have
sent it.
5. B computes D(PUa, D(PRb, M)) to recover the secret key.

Distribution of Public Keys

• Public announcement
• Publicly available directory
• Public-key authority
• Public-key certificates

Downloaded from: annauniversityedu.blogspot.com

Public Announcement of Public Keys

Publicly Available Directory

1. The authority maintains a directory with a {name, public key} entry for each participant.
2. Each participant registers a public key with the directory authority.
Registration would have to be in person or by some form of secure authenticated communication.
3. A participant may replace the existing key with a new one at any time, either because of the desire to
replace a public key that has already been used for a large amount of data, or because the corresponding
private key has been compromised in some way.
4. Participants could also access the directory electronically. For this purpose, secure, authenticated
communication from the authority to the participant is mandatory.

Public-Key Authority

1. A sends a timestamped message to the public-key authority containing a

Request for the current public key of B.
2. The authority responds with a message that is encrypted using the authority’s private key, PRauth. Thus,
A is able to decrypt the message using the authority’s public key. Therefore, A is assured that the message
originated with the authority. The message includes the following:

• B’s public key, PUb, which A can use to encrypt messages destined for B
• The original request used to enable A to match this response with the corresponding earlier request and to
verify that the original request was not
altered before reception by the authority
• The original timestamp given so A can determine that this is not an old
message from the authority containing a key other than B’s current public key.

Downloaded from: annauniversityedu.blogspot.com

3. A stores B’s public key and also uses it to encrypt a message to B containing an identifier of A (IDA) and
a nonce (N1), which is used to identify this transaction uniquely.
4, 5. B retrieves A’s public key from the authority in the same manner as A
Retrieved B’s public key.
At this point, public keys have been securely delivered to A and B, and they
may begin their protected exchange. However, two additional steps are desirable:
6. B sends a message to A encrypted with PUa and containing A’s nonce (N1) as well as a new nonce
generated by B (N2). Because only B could have decrypted message (3), the presence of N1 in message (6)
assures A that the correspondent is B.
7. A returns N2, which is encrypted using B’s public key, to assure B that its
Correspondent is A.

Public-Key Certificates

1. Any participant can read a certificate to determine the name and public key of the certificate’s owner.
2. Any participant can verify that the certificate originated from the certificate authority and is not
counterfeit.
3. Only the certificate authority can create and update certificates.
4. Any participant can verify the currency of the certificate.

Downloaded from: annauniversityedu.blogspot.com

For participant A, the authority provides a certificate of the form
CA = E(PRauth, [T || IDA || PUa])

where PRauth is the private key used by the authority and T is a timestamp.
D(PUauth, CA) = D(PUauth, E(PRauth, [T || IDA ||PUa])) = (T || IDA ||PUa)

3.8 DIFFIE HELLMAN KEY EXCHANGE

The purpose of the algorithm is to enable two users to securely exchange a key that can then be
used for subsequent encryption of messages.The algorithm itself is limited to the exchange of
secret values.
The Diffie-Hellman algorithm depends for its effectiveness on the difficulty of computing discrete
logarithms.

Downloaded from: annauniversityedu.blogspot.com

Diffie Hellman key exchange as follows:

There are publicly known numbers: a prime number „q‟ and an integer α that is

primitive root of q.

suppose users A and B wish to exchange a key. User A selects a random integer XA

< q and computes

YA = α XA mod q. Similarly, user B independently selects a random

integer XB < q and computes YB = α XB mod q. Each side keeps the X value private

and

makes the Y value available publicly to the other side. User A computes the key as

K = (YB)XA mod q and

User B computes the key as

K = (YA)XB mod q

These two calculations produce identical results.

K = (YB)XA mod q

= (α XB mod q)XA mod q

= (α XB)XA mod q

= (α XA)XB mod q

= (α XA mod q)XB mod q

= (YA)XB mod q

Downloaded from: annauniversityedu.blogspot.com

The result is that two sides have exchanged a secret key.

The security of the algorithm lies in the fact that, while it is relatively easy to

calculate Exponentials

modulo a prime, it is very difficult to calculate discrete logarithms. For large primes,

the latter task is considered infeasible.

Diffie-Hellman Key Exchange

Global Public Elements

q prime number
α α<q, and α is a primitive root of q

User A Key Generation

Select private XA XA < q
Calculate public YA YA = αXA mod q

User B Key Generation

Select private XB XB < q
Calculate public YB YB = αXB mod q

Calculation of Secret Key by User A

K = (YB )XA mod q

Calculation of Secret Key by User B

K = (YA)XB mod q

Example:
Key exchange is based on the use of the prime number
q = 353 and a primitive root of 353, in this case α = 3. A and B select private keys
XA = 97 and XB = 233, respectively.

A computes YA = 397 mod 353 = 40.

B computes YB = 3233 mod 353 = 248.

After they exchange public keys, each can compute the common secret key:
A computes K = (YB)X mod 353 = 24897 mod 353 = 160.
A

B computes K = (YA)X mod 353 = 40233 mod 353 = 160.

B

Key Exchange Protocols

Downloaded from: annauniversityedu.blogspot.com

Man-in-the-Middle Attack

Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack proceeds as
follows.

1. Darth prepares for the attack by generating two random private keys XD1
and XD2 and then computing the corresponding public keys YD1 and YD2.
2. Alice transmits YA to Bob.
3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates
K2 = (YA)XD2 mod q.
4. Bob receives YD1 and calculates K1 = (YD1)XB mod q.
5. Bob transmits YB to Alice.
6. Darth intercepts YB and transmits YD2 to Alice. Darth calculates
K1 = (YB)XD1 mod q.
7. Alice receives YD2 and calculates K2 = (YD2)XA mod q.

Downloaded from: annauniversityedu.blogspot.com

Bob and Darth share secret key K1 and Alice and Darth share secret key K2. All future communication
between Bob and Alice is compromised in the following way.

1. Alice sends an encrypted message M: E(K2, M).

2. Darth intercepts the encrypted message and decrypts it to recover M.
3. Darth sends Bob E(K1, M) or E(K1, M′), where M′ is any message. In the
first case, Darth simply wants to eavesdrop on the communication without
altering it. In the second case, Darth wants to modify the message going to Bob.

Downloaded from: annauniversityedu.blogspot.com

3.9 The Elgamal Cryptosystem

The 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",
Like Diffie-Hellman its security depends on the difficulty of factoring logarithms

Key Generation
 select a large prime p (~200 digit), and
 [[alpha]] a primitive element mod p
 A has a secret number xA
 B has a secret number xB
 A and B compute yA and yB respectively, which are then made public
yA = [[alpha]]xA mod p
yB = [[alpha]]xB mod p

to encrypt a message M into ciphertext C,

 selects a random number k, 0 <= k <= p-1
 computes the message key K

K = yB
k mod p
 computes the ciphertext pair: C = {c1,c2}

C1 = [[alpha]]k mod p C2 = K.M mod p

to decrypt the message

 extracts the message key K
K = C1
xB mod p = [[alpha]]k.xB mod p
 extracts M by solving for M in the following equation:
C2 = K.M mod p

Algorithm

Global Public Elements

q prime number
α α<q, and α is a primitive root of q

Key Generation by Alice

Select private XA XA < q - 1

Downloaded from: annauniversityedu.blogspot.com

Calculate YA YA = αXA mod q
Public key {q, a, YA}
Private key XA

Encryption by Bob with Alice’s Public Key

Plaintext: M<q
Select random integer k k<q
Calculate K K = (YA)k mod q
Calculate C1 C1 = αk mod q
Calculate C2 C2 = KM mod q
Ciphertext: (C1, C2)

Decryption by Alice with Alice’s Private Key

Ciphertext: (C1, C2)
Calculate K K = (C1)XA mod q
Plaintext: M = (C2K-1) mod q

1. Bob generates a random integer k.

2. Bob generates a one-time key K using Alice’s public-key components
YA, q, and k.
3. Bob encrypts k using the public-key component a, yielding C1. C1
provides sufficient information for Alice to recover K.
4. Bob encrypts the plaintext message M using K.
5. Alice recovers K from C1 using her private key.
6. Alice uses K-1 to recover the plaintext message from C2.

Thus, K functions as a one-time key, used to encrypt and decrypt the message.

Example:
let us start with the prime field GF(19); that is, q = 19.
It has primitive roots {2, 3, 10, 13, 14, 15}. choose α = 10.

1. Alice chooses XA = 5.
2. Then YA = αXA mod q = α5 mod 19 = 3.
3. Alice’s private key is 5 and Alice’s public key is {q, a, YA} = {19, 10, 3}.

Suppose Bob wants to send the message with the value M = 17. Then,

1. Bob chooses k = 6.
2. Then K = (YA)k mod q = 36 mod 19 = 729 mod 19 = 7.
3. C1 = αk mod q = α6 mod 19 = 11
C2 = KM mod q = 7 * 17 mod 19 = 119 mod 19 = 5
4. Bob sends the ciphertext (11, 5).

For decryption:
1. Alice calculates K = (C1)XA mod q = 115 mod 19 = 161051 mod 19 = 7.
2. Then K-1 in GF(19) is 7-1 mod 19 = 11.
3. Finally, M = (C2K-1) mod q = 5 * 11 mod 19 = 55 mod 19 = 17.

Downloaded from: annauniversityedu.blogspot.com

If a message must be broken up into blocks and sent as a sequence of encrypted blocks, a unique value of
k should be used for each block. If k is used for more than one block, knowledge of one block M1 of the
message enables the user to compute other blocks as follows.
Let
C1,1 = αk mod q; C2,1 = KM1 mod q
C1,2 = αk mod q; C2,2 = KM2 mod q
Then,
C2,1/C2,2 = (KM1 mod q / KM2 mod q) = (M1 mod q / M2 mod q )
If M1 is known, then M2 is easily computed as
M2 = (C2,1)-1 C2,2 M1 mod q

3.10 Elliptic Curve Cryptography (ECC)

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.

Abelian Group:
an abelian group G, sometimes denoted by {G, • }, is a set of elements with a binary operation, denoted by
• , that associates to each ordered pair (a, b) of elements in G an element (a • b) in G

(A1) Closure: If a and b belong to G, then a • b is also in G.

(A2) Associative: a • (b • c) = (a • b) • c for all a, b, c in G.
(A3) Identity element: There is an element e in G such that a • e = e • a = a
for all a in G.
(A4) Inverse element: For each a in G there is an element a′ in G such that
a • a′ = a′ • a = e.
(A5) Commutative: a•b = b•a for all a, b in G.

Elliptic Curves over Real Numbers

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. In general, cubic equations for elliptic curves
take the following form, known as a Weierstrass equation:
y2 + axy + by = x3 + cx2 + dx + e
where a, b, c, d, e are real numbers and x and y take on values in the real numbers.
y2 = x3 + ax + b
Such equations are said to be cubic, or of degree 3, because the highest exponent they contain is a 3. 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
y = √x3+ax+b

1. 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.
2. 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).
Note that these two points can be joined by a vertical line.
Note that P + (-P) = P - P = O.
3. 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. It is easily seen that there is a unique point R that is the point of intersection

Downloaded from: annauniversityedu.blogspot.com

(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: P + Q = -R. That is, we define
P + Q to be the mirror image (with respect to the x axis) of the third point of intersection.
4. 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, which is consistent with item (2).
5. To double a point Q, draw the tangent line and find the other point of intersection S. Then Q + Q = 2Q =
-S.

Algebraic Description of Addition

P = (xP, yP) and Q = (xQ, yQ), that are not negatives of each other, the slope of the line l that joins them is Δ
= (yQ - yP)/(xQ - xP). There is exactly one other point where l intersects the elliptic curve, and that is the
negative of the sum of P and Q.
After some algebraic manipulation, we can express the sum R = P + Q as
xR = Δ2 - xP - xQ
yR = -yP + Δ(xP - xR)

P + P = 2P = R. When yP ≠ 0

Downloaded from: annauniversityedu.blogspot.com

ECC Diffie-Hellman Key Exchange

Global Public Elements

Eq(a, b) elliptic curve with parameters a, b, and q, where q is a prime or an integer
of the form 2m
G point on elliptic curve whose order is large
value n

User A Key Generation

Select private nA nA < n
Calculate public PA PA = nA * G

User B Key Generation

Select private nB nB < n
Calculate public PB PB = nB * G

Calculation of Secret Key by User A

K = nA * PB

Calculation of Secret Key by User B

K = nB * PA

Downloaded from: annauniversityedu.blogspot.com