Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Module 3 - Asymmetric Key Cryptography

CSI3002
Applied Cryptography and Network Security RSA, Elgamal, Elliptic Curve Cryptography (ECC), Diffie-Hellman key
exchange protocol

By,
[Link].N.G.,
Assistant Professor Senior,
Department of Analytics,
School of Computer Science and Engineering,
Vellore Institute of Technology, Vellore.

Email: [Link]@[Link] Mobile: 8903580808 Cabin: PRP 217-16

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Terminology Related to Asymmetric Encryption

Asymmetric Cryptography
• Asymmetric Keys
• Two related keys - a public key and a private key
• Also known as Public Key Cryptography. • Used to perform complementary operations
• Public-key algorithms are based on mathematical functions rather than on • Encryption and Decryption
substitution and permutation. • Signature Generation and Signature Verification

• Public-key cryptography is asymmetric, involving the use of two separate • Public Key Certificate
keys. • A digital document issued and digitally signed by the private key of a Certification
Authority that binds the name of a subscriber to a public key.
• Misconceptions concerning public-key encryption • Public Key (Asymmetric) Cryptographic Algorithm
• Public-key encryption is more secure from cryptanalysis than is symmetric
encryption. • A cryptographic algorithm that uses two related keys, a public key and a private key.
• Public-key encryption is a general-purpose technique that has made symmetric • The two keys have the property that deriving the private key from the public key is
encryption obsolete computationally infeasible.
• Key distribution is trivial when using public-key encryption, compared to the rather • Public Key Infrastructure (PKI)
cumbersome handshaking involved with key distribution centers for symmetric • A set of policies, processes, server platforms, software and workstations used for
encryption. the purpose of administering certificates and public-private key pairs, including the
Prepared by: [Link].N.G., Asst Prof Senior, Dept of ability to issue, maintain,Prepared
and revoke public
by: [Link].N.G., keySenior,
Asst Prof certificates.
Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 1 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Principles Of Public-key Cryptosystems 1. Public Key Cryptosystem

[Link]-Key Cryptosystems
• Asymmetric algorithms rely on one key for encryption and a
different but related key for decryption.
• Characteristic
• It is computationally infeasible to determine the decryption key given only
knowledge of the cryptographic algorithm and the encryption key.
• Either of the two related keys can be used for encryption, with the other
used for decryption.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

1. Public Key Cryptosystem

At any time, a system can change its private key and publish the
companion public key to replace its old public key.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 2 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

2. Essential elements of a public-key encryption 3. Public Key Cryptography and Confidentiality

scheme
• PT : X = [X1, X2, …, XM]
• Message is for Destination B.
• B generates a related pair of keys:
• Public key, PUb → Publicly available
• Private key, PRb → Known only to B
• CT: Y = [Y1, Y2, … , YN]
• Y = E(PUb, X)
• On the receiver end,
• X = D(PRb,Y)

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

3. Public Key Cryptography and Authentication 3. Public Key Cryptography – Confidentiality

and Authentication
• Integrity (Check)
• Authentication
---------------------------------
• Confidentiality is not
maintained.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 3 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

4. Applications for Public-Key Cryptosystems

5.
• We can classify the use of public-key cryptosystems into three Requirements
categories, for Public-Key
• Encryption/decryption Cryptography
• Digital signature
• The sender “signs” a message with its private key.
• Key exchange
• Two sides cooperate to exchange a session key, which is a secret key for symmetric
encryption generated for use for a particular transaction (or session) and valid for a short
period of time.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

5.1 Trapdoor One-Way Function

5.1 Trapdoor One-Way Function
• The main idea behind asymmetric-key cryptography is the concept of
the trapdoor one-way function.
Example:1
• When n is large, n = p × q is a one-way function.
• Given p and q , it is always easy to calculate n ; given n, it is very difficult to
compute p and q. This is the factorization problem.
Example:2
• When n is large, the function y = xk mod n is a trapdoor one-way function.
• Given x, k, and n, it is easy to calculate y.
Trapdoor One-Way Function (TOWF)
• Given y, k, and n, it is very difficult to calculate x. This is the discrete
logarithm problem.
• Given y and a trapdoor, x can be computed • However, if we know the trapdoor, k′ such that k × k ′ = 1 mod f(n), we can
easily. use x = yk′ mod n to find x.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 4 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

6. Public-Key Cryptanalysis RSA Cryptosystem

• Public-key encryption scheme is vulnerable to a brute-force attack. • Proposed by Rivest, Shamir & Adleman of MIT in 1977
• Use large keys.
• The most common public-key algorithm is the RSA cryptosystem
• Tradeoff - Complexity of calculating these mathematical functions may not
scale linearly with the number of bits in the key but grow more rapidly than
that.
• Based on exponentiation in a finite (Galois) field over integers
• Another form of attack is to find some way to compute the private
key given the public key. modulo a prime
• Probable-message attack – Specific to Public Key Cryptosystem • It uses large integers (eg. 1024 bits)
• Message to be sent - 56-bit DES key • Security due to cost of factoring large numbers
• An adversary could encrypt all possible 56-bit DES keys using the public key • factorization is hard
and could discover the encrypted key by matching the transmitted ciphertext.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Introduction - RSA Procedure- RSA

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 5 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Procedure- RSA RSA Key Generation

RSA uses Two Algebraic Structures
• Encryption/Decryption Ring:

R = <Zn , +, × >
• Key-Generation Group:
G = <Z f(n)∗, × >

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Efficient RSA Key Generation RSA En/Decryption

• Users of RSA must: • To encrypt a message
• determine two primes at random - p, q P the sender:
• select either e or d and compute the other • Obtain public key of
• Primes p,q must not be easily derived from modulus n=p.q recipient PU={e,n}
• means must be sufficiently large • Computes: C = Pe
mod n, where 0≤P<n
• typically guess and use probabilistic test
• exponents e,d are inverses, so use Inverse algorithm to compute the other
• To decrypt the
ciphertext C the
owner:
• Uses their private key
PR={d,n}
• Computes: P = Cd
Prepared by: [Link].N.G., Asst Prof Senior, Dept of
mod n Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 6 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Proof of RSA Example of RSA 1

• Alice wants to create a pair of keys so that she can encrypt and
decrypt the messages using RSA. She chooses the values of p and q as
17 and 11. Also, she chooses her public key as 7.
• Show that her choice of public key is justified.
• Calculate her private key.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Example of RSA 1 Example of RSA 2

• Alice wants to create a pair of keys so that she can encrypt and decrypt the messages • Bob want to send the plain text 88 to Alice.
using RSA. She chooses the values of p and q as 17 and 11. Also, she chooses her public
key as 7. • What is the Cipher text received by Alice?
• Show that her choice of public key is justified.
• Calculate her private key. • What is the result of decryption performed at Alice end?
• Use the following keys for encryption and decryption. PUA={7,187} ;
• p=17 & q=11 PRA={23,187}
• n = pq =17 x 11=187
• ø(n)=(p–1)(q-1)=16x10=160
• Public Key:
• gcd(7,160)=1; Also, 1<7<160 → So, her choice of public key is justified.
• PUA={7,187}
• Private Key:
• d = 23
• PRA={23,187}
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 7 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Example of RSA 2 Example RSA 3

• Bob want to send the plain text 88 to Alice. • John want to send the plain text 63 to Bob.
• What is the Cipher text received by Alice? • What is the Cipher text received by Alice?
• What is the result of decryption performed at Alice end? • What is the result of decryption performed at Alice end?
• Use the following keys for encryption and decryption. PUA={7,187} ; • Use the following keys for encryption and decryption. PUB={13,77} ;
PRA={23,187} PRB={37,77}
• Encryption:
• Encryption: • CT = 6313 mod 77
• CT = 887 mod 187 • CT = 28
• CT = 11 • Decryption:
• Decryption: • PT = 2837 mod 77
• PT = 1123 mod 187 • PT = 63
• PT = 88
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Example RSA 4 Example RSA 4

• Jennifer creates a pair of keys for herself.
• She chooses p = 397 and q = 401. She calculates n = 159197.
• She then calculates ∅(n) = 158400.
• She then chooses e = 343 and d = 12007.
• Ted wants to send the message “NO” to Jennifer.
• He changes each character to a number (from 00 to 25), with each
character coded as two digits.
• He then concatenates the two coded characters and gets a four-digit
number.
• The plaintext is 1314
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 8 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Attacks on RSA Attacks on RSA

• Factorization Attack
• If an adversary can find the factors of n it means that the values of p and q are
known.
• If p and q are known computation of ø(n)=(p–1)(q-1) is done and the private
key can be obtained.
• Chosen Cipher Text Attack
• Adversary computes, Y= CT . Xe mod n
• Send this Cipher Text Y for Decryption.
• Z = Yd mod n = (CT . Xe)d mod n = CTd Xed mod n = CTd . X mod n = PT . X mod n
• This Z is intercepted by Adversary.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Attacks on RSA Attack on RSA

• Attacks on Encryption Exponent • Attacks on Decryption Exponent
• There are potential attacks on the low encryption exponent value.
• Recommended e value is 216+1 = 65537 • Revealed Decryption Exponent Attack
• Coppersmith Theorem Attack • If adversary knows d, they can find out p and q (factoring techniques).
• According to the theorem, C = F(P) = Pe mod n, if e=3, 2/3rd of the bits in the PT can be found. • If the owner only changes d and retains p and q, then the adversary will be able to
• Broadcast Attack decrypt all the messages in the future.
• One entity sends the same message to a group of recipients with the same low exponent. • So, if d is compromised, p,q,e,d and n must be regenerated.
• C1 = P3 mod n1 ; C2 = P3 mod n2 ; C3 = P3 mod n3
• Use CRT • Low Decryption Exponent Attack
• Related Message Attack • If the private key is small and q<p<2q , then factors of n can be found out easily.
• Alice encrypts 2 plain text P1, P2 with e=3 and sends C1 and C2 to bob.
• If P1 and P2 are related by a Linear function, then Plain text can be recovered in a feasible
time.
• Short Pad Attack
• M+r1 -> C1 send to Bob. Eve intercepts it.
• M+r2 -> C2 send to Bob. Eve intercepts it.
• If the padded bits are short, Eve
Prepared by: can recoverAsstMProfquickly.
[Link].N.G., Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 9 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Attacks on RSA Attacks on RSA

• Plain Text Attacks • Attacks on the Modulus
• Short Message Attack • Common Modulus Attack
• A community uses a common modulus. If the adversary is also a part of the community, p and
• If Eve knows the sent of possible plain text, she can encrypt all the possible PT until the q values are known.
same CT is obtained and can crack the system. • So, the private key can be easily computed.
• Cycling Attack • Attacks on Implementation
• Continuous encryption of the CT will result eventually in PT. • Timing Attack
• Unconcealed Message Attack • The attacker needs to have the target system compute Cd mod N for several carefully selected
• There are some messages that are encrypted to themselves. values of C.
• So, if the exponent is very low using this vulnerability the RSA system can be cracked. • By precisely measuring the amount of time required and analyzing the timing variations, the
attacker can recover the private key d one bit at a time until the entire exponent is known.
• Power Attack
• Measure the power consumed during decryption, based on the principle discussed for timing
attack, the private key can be recovered bit by bit.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Recommendations for RSA Homework

• Refer text book. • Alice wants to create a pair of keys so that she can encrypt and
decrypt the messages using RSA. She chooses the values of p and q as
7 and 11. Also, she chooses her public key as 13.
• Show that her choice of public key is justified.
• Calculate her private key.
• Bob want to send the plain text 5 to Alice.
• What is the Cipher text received by Alice?
• What is the result of decryption performed at Alice end?
• Use the following keys for encryption and decryption. PUA={13,77} ;
PRA={37,77}

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 10 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

ElGamal Cryptosystem ElGamal Procedure

• Besides RSA and Rabin, another public-key cryptosystem is ElGamal.
• ElGamal is based on the discrete logarithm problem.

Topics discussed in this section:

1. Introduction
2. Procedure
3. Proof
4. Analysis
5. Security of ElGamal C2
6. Application
P=[C2 × C1 p−1−d]
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Key Generation - ElGamal Encryption / Decryption - ElGamal

P=[C2 × C1 p−1−d]

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 11 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Proof Example
−1
• The ElGamal decryption expression 𝐶2 × 𝐶1𝑑 can be verified to • Bob chooses p = 11 and e1 = 2 and d = 3, e2 = e1d = 8.
be P as: • So the public keys are (2, 8, 11) and the private key is 3. Alice chooses
−1 −1 r = 4 and calculates C1 and C2 for the plaintext 7.
• 𝐶2 × 𝐶1𝑑 𝑚𝑜𝑑 𝑝 = 𝑒2𝑟 × 𝑃 × 𝑒1𝑟𝑑 𝑚𝑜𝑑 𝑝
−1
= 𝑒1𝑟𝑑 ×𝑃× 𝑒1𝑟𝑑 =𝑃

• Bob receives the ciphertexts (5 and 6) and calculates the plaintext.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Analysis Example
• Interesting point about ELGamal cryptosystem is that, • Bob uses a random integer of 512 bits. The integer p is a 155-digit
• Alice creates r and keeps it secret and number (the ideal is 300 digits). Bob then chooses e1, d, and
• Bob creates d and keeps it secret. calculates e2, as shown below:
• Alice creates (C1, C2) with r without having any knowledge about d
• 𝐶2 = 𝑒2𝑟 × 𝑃 𝑚𝑜𝑑 𝑝 = 𝑒1𝑟𝑑 × 𝑃 𝑚𝑜𝑑 𝑝 where, 𝑒1𝑟𝑑 acts as
mask that hides P.
• Bob has (C1, C2 and d) but doesn’t have knowledge about r,
• 𝐶1 = 𝑒1𝑟 𝑚𝑜𝑑 𝑝;
• 𝐶1𝑑 = 𝑒1𝑟𝑑 𝑚𝑜𝑑 𝑝
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 12 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Elliptic Curve Arithmetic - Elliptic Curves Over

Example
Zp or GF(p) and GF(2m)
• Alice has the plaintext P = 3200 to send to Bob. She chooses
r = 545131, calculates C1 and C2, and sends them to Bob. • Elliptic curve cryptography uses curves whose variables and coefficients are finite
• Two families of elliptic curves are used in cryptographic applications:

Binary
curves Prime
over curves
GF(2m) over Zp

• Variables and coefficients all take on • Use a cubic equation in which the variables
values in GF(2m) and in calculations and coefficients all take on values in the set
• Bob calculates the plaintext P = C2 × ((C1)d)−1 mod p = 3200 mod p. are performed over GF(2m) of integers from 0 through p-1 and in which
• Best for hardware applications calculations are performed modulo p
Prepared by: [Link].N.G., Asst Prof Senior, Dept of • Best Asst
Prepared by: [Link].N.G., for Prof
software applications
Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Elliptic Curve Arithmetic - Elliptic Curves Over Elliptic Curve Arithmetic - Elliptic Curves Over
Zp or GF(p) Zp or GF(p)
• For elliptic curves over Zp, as with real numbers, we limit ourselves to • Now consider the set EP(a,b)
equations (1), consisting of all pairs of integers
(x,y) that satisfy Equation,

• but in this case with coefficients and variables limited to Zp :

together with a point at infinity .
• The coefficients a and b and the
variables x and y are all elements
of ZP.
• For example, let p = 23, a = 1 and
b = 1, therefore

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 13 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Elliptic Curve Arithmetic - Elliptic Curves Over Elliptic Curve Arithmetic - Elliptic Curves Over
Zp or GF(p) Zp or GF(p)
• It can be shown that a finite abelian group can be defined based on
the set EP(a,b) provided that (x3+ab+b) mod p has no repeated factors

• The rules for addition over EP(a,b). For all points P,Q € EP(a,b)

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Elliptic Curve Arithmetic - Elliptic Curves Over Elliptic Curve Arithmetic - Elliptic Curves Over Zp or
Zp or GF(p) GF(p)

P+Q

6 2P

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 14 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Elliptic Curve Arithmetic - Elliptic Curves Over Elliptic Curve Arithmetic - Elliptic Curves Over
Zp or GF(p) Zp or GF(p)
• Define an elliptic curve E13 (1,1). • Let us add two points in E13 (1,1), R = P + Q, where
• The equation is y2 = x3 + x + 1 P = (4, 2) and Q = (10, 6).
Solution:
• λ = (6 − 2) × (10 − 4)−1 mod 13 = 4 × 6−1 mod 13 = 5 mod 13.
• x = (52 − 4 −10) mod 13 = 11 mod 13.
• y = [5 (4 −11) − 2] mod 13 = 2 mod 13.
• R = (11, 2), which is a point on the curve

8)
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

ECC Simulating ElGamal ECC Simulating ElGamal

Generating Public and Private Keys
• E(a, b) ; e1(x1, y1) ; d → e2(x2, y2) = d × e1(x1, y1)
• Encryption

• Decryption

The security of ECC depends on the difficulty of

solving the elliptic curve logarithm problem.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 15 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

ECC Simulating ElGamal Comparable Key Sizes for Equivalent Security

[Link] selects E67(2, 3) as the elliptic curve over GF(p).
[Link] selects e1 = (2, 22) and d = 4.
[Link] calculates e2 = (13, 45), where e2 = d × e1.
[Link] publicly announces the tuple (E, e1, e2).
[Link] sends the plaintext P = (24, 26) to Bob. She selects r = 2.
[Link] finds the point C1=(35, 1), C2=(21, 44).
[Link] receives C1, C2. He uses 4xC1(35,1) to get (23, 25), inverts the points
(23, 25) to get the points (23, 42).
[Link] adds (23, 42) with CPrepared
2=(21, 44) to get the original one P=(24, 26).
by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Key distribution and Key exchange protocols Symmetric-key Distribution

• Symmetric Key Distribution • Symmetric-key cryptography is more efficient than asymmetric-key
• Session Key cryptography for enciphering large messages.
• Key exchange Protocols • Symmetric-key cryptography, however, needs a shared secret key
• Symmetric Key Agreement between two parties.
• Public Key Distribution - PKI • The distribution of keys is another problem.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 16 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Key-Distribution Center: KDC [Link] Multiple KDCs

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

[Link] Multiple KDCs Session Keys

• A KDC creates a secret key for each member.
• This secret key can be used only between the member and the KDC,
not between two members.
• Session key is the key shared between two end users for the process
of cryptosystem.

A session symmetric key between two parties is used only

once.

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 17 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Key Exchange Protocols Symmetric-key Agreement

• Simple Protocol Using a KDC • Alice and Bob can create a session key between themselves without
• Needham-Schroeder Protocol using a KDC.
• Otway-Rees Protocol • This method of session-key creation is referred to as the symmetric-
key agreement.

• Majorly used techniques:

1. Diffie-Hellman Key Agreement
2. Station-to-Station Key Agreement

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Diffie-Hellman Key Agreement - Example

Diffie- G=<Zp*,X>
Hellman Key Let us give a trivial example to make the procedure clear. Our example uses
small numbers, but note that in a real situation, the numbers are very large.
Agreement Assume that g = 7 and p = 23. The steps are as follows:
1. Alice chooses x = 3 and calculates R1 = 73 mod 23 = 21.
2. Bob chooses y = 6 and calculates R2 = 76 mod 23 = 4.
3. Alice sends the number 21 to Bob.
4. Bob sends the number 4 to Alice.
5. Alice calculates the symmetric key K = 43 mod 23 = 18.
6. Bob calculates the symmetric key K = 216 mod 23 = 18.
7. The value of K is the same for both Alice and Bob;
gxy mod p = 718 mod 23 = 18.
The symmetric (shared) key in the Diffie-Hellman
method
Prepared is K = gxyAsstmod
by: [Link].N.G., [Link] of
Prof Senior,
Analytics, SCOPE, VIT, Vellore.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 18 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Diffie-Hellman Key Agreement – Real Time Diffie-Hellman Key Agreement – Real Time
Example Example
• Let us give a more realistic example. We used a program to create a
random integer of 512 bits (the ideal is 1024 bits).
• The integer p is a 159-digit number.
• We also choose g, x, and y as shown below:

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Analysis of Diffie Hellman Security of Diffie-Hellman

Discrete Logarithm Attack

Man-in-the-Middle Attack

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 19 of 20
 Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Discrete Logarithm Attack Man-in-the-

middle attack
• The security of the key exchange is based on the difficulty of the discrete
logarithm problem.
• Eve can intercept R1 and R2. Also Known as Bucket
• If she can find x from R1 = gx mod p and y from R2 = gy mod p, then she can Brigade Attack.
calculate the symmetric key K = gxy mod p.
• To make Diffie-Hellman safe from the discrete logarithm attack, the
following are recommended.
• The prime p must be very large (more than 300 decimal digits).
• The prime p must be chosen such that p − 1 has at least one large prime factor (more
than 60 decimal digits).
• The generator must be chosen from the group <Zp*, × >.
• Bob and Alice must destroy x and y after they have calculated the symmetric key. The
values of x and y must be used only once.
Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

ECC Simulated ECC Simulated Key Exchange – Diffie Hellman –

Key Exchange – Encryption / Decryption
Diffie Hellman
• Encryption C1 C2

• Decryption

C2 – nB C1

Prepared by: [Link].N.G., Asst Prof Senior, Dept of Prepared by: [Link].N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: [Link].N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 20 of 20