Public Key Cryptosystems

Module 3
Mathematics for PKC
Watch the following to refresh the mathematical
concepts needed for PKC

[Link]
Principles of PKC
Private-Key Cryptography (Symmetric key)

• traditional private/secret/single key cryptography uses

one key
• shared by both sender and receiver
• if this key is disclosed communications are compromised
• also is symmetric, parties are equal
• hence does not protect sender from receiver forging a
message & claiming is sent by sender
Public-Key Cryptography (Assymetric key)

• probably most significant advance in the 3000 year

history of cryptography
• uses two keys – a public & a private key
• asymmetric since parties are not equal
• uses clever application of number theoretic
concepts to function
• complements rather than replaces private key
cryptosystems
Why Public-Key Cryptography?

• developed to address two key issues:

– key distribution – how to have secure
communications in general without having to trust a
KDC with your key
– digital signatures – how to verify a message comes
intact from the claimed sender
• public invention due to Whitfield Diffie & Martin Hellman
at Stanford Uni in 1976
– known earlier in classified community
 Public-Key Cryptography
• public-key/two-key/asymmetric cryptography involves
the use of two keys:
– a public-key, which may be known by anybody, and
can be used to encrypt messages, and verify
signatures
– a private-key, known only to the recipient, used to
decrypt messages, and sign (create) signatures
• is asymmetric because
– those who encrypt messages or verify signatures
cannot decrypt messages or create signatures
Public-Key Secrecy
Public-Key Authentication
Public-Key Authentication & Secrecy
 Public-Key Applications
• can classify uses into 3 categories:
– encryption/decryption (provide secrecy)
– digital signatures (provide authentication)
– key exchange (of session keys)
• some algorithms are suitable for all uses,
others are specific to one
 Security of Public Key Schemes
• like private key schemes brute force exhaustive search
attack is always theoretically possible
• but keys used are too large (>512bits)
• security relies on a large enough difference in difficulty
between easy (en/decrypt) and hard (cryptanalyse)
problems
• more generally the hard problem is known, but is made
hard enough to be impractical to break
• requires the use of very large numbers
• hence is slow compared to private key schemes
RSA
 RSA mathematics
• Modular Arithmetic
[Link]
 RSA
• by Rivest, Shamir & Adleman of MIT in 1977
• best known & widely used public-key scheme
• based on exponentiation in a finite (Galois) field over integers
modulo a prime
– exponentiation takes O((log n)3) operations (easy)
• RSA uses large integers (eg. 1024 bits)
• security is due to the cost of factoring large numbers
– factorization takes O(e log n log log n) operations -> (hard problem)
 RSA Algorithm
• 1) Key generation; PU={e,n} and PR={d,n}
• 2) Encryption
d
• 3) Decryption
• Both sender and receiver have n. The sender has e and only the
receiver has d.
 RSA Key Setup
• each user generates a public/private key pair by:
• selecting two large primes at random - p,q
• computing their system modulus n=p.q
– note ø(n)=(p-1)(q-1)
• selecting at random the encryption key e
• where 1<e<ø(n), gcd(e,ø(n))=1
• solve following equation to find decryption key d
– e.d=1 mod ø(n) and 0≤d≤n
• publish their public encryption key: PU={e,n}
• keep secret private decryption key: PR={d,n}
 The RSA Algorithm – Key Generation

1. Select p,q p and q both prime

2. Calculate n=pxq
3. Calculate
4. Select integer e
5. Calculate d
6. Public Key KU = {e,n}
7. Private key KR = {d,n}
 The RSA Algorithm - Encryption

• Plaintext: M<n

• Ciphertext: C = Me (mod n)
 The RSA Algorithm - Decryption

• Ciphertext: C

• Plaintext: M = Cd (mod n)
 RSA Use
• to encrypt a message M the sender:
– obtains public key of recipient PU={e,n}
– computes: C = Me mod n, where 0≤M<n
• to decrypt the ciphertext C the owner:
– uses their private key PR={d,n}
– computes: M = Cd mod n
• note that the message M must be smaller than the modulus n
(block if needed)
 Why RSA Works
• because of Euler's Theorem:
– aø(n)mod n = 1 where gcd(a,n)=1
• in RSA have:
– n=p.q
– ø(n)=(p-1)(q-1)
– carefully chose e & d to be inverses mod ø(n)
– hence e.d=1+k.ø(n) for some k
• hence :
Cd = Me.d = M1+k.ø(n) = M1.(Mø(n))k
= M1.(1)k = M1 = M mod n
 RSA Example - Key Setup
1. Select primes: p=17 & q=11
2. Compute n = pq =17 x 11=187
3. Compute ø(n)=(p–1)(q-1)=16 x 10=160
4. Select e: gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160 Value is d=23
since 23x7=161= 10x160+1
6. Publish public key PU={7,187}
7. Keep secret private key PR={23,187}
 RSA Example - En/Decryption
• sample RSA encryption/decryption is:
• given message M = 88 (nb. 88<187)
• encryption:
C = 887 mod 187 = 11
• decryption:
M = 1123 mod 187 = 88
Example of RSA Algorithm
 Fast Exponentiation
• can use the Square and Multiply Algorithm
– a fast, efficient algorithm for exponentiation
– concept is based on repeated squaring of base
– and multiplying in the one bit positions that are needed to
compute the result
– looking at binary representation of exponent
• only takes O(log2 n) multiples for number n
Ex: 75
Binary of 5 = 101 (here onwards exponents are in binary)
71.71 = 710 (always square the base first, here we have the first 2 bits of
exponent right.)
Since third bit is 1 do a square and a multiply with the base
710.710=7100
7100.71=7101
Ex: 3129
Binary of 129 = 10000001 (here onwards exponents are in binary)
31.31 = 310 (always square the base first, here we have the first 2 bits of
exponent right.)
310.310=3100 (Since 3rd bit is 0, do a square)
3100.3100=31000 (Since 4th bit is 0, do a square)
31000.31000=310000 (Since 5th bit is 0, do a square)
310000.310000=3100000(Since 6th bit is 0, do a square)
3100000.3100000=31000000(Since 7th bit is 0, do a square)
31000000.31000000=310000000(Since 8th bit is 1, do a square and multiply with
base)
310000000.31=310000001
 Exponentiation
c = 0; f = 1
for i = k downto 0
do c = 2 x c
f = (f x f) mod n
if bi == 1 then
c = c + 1
f = (f x a) mod n
return f
 RSA - Efficient Encryption
• encryption uses exponentiation to power e
• hence if e small, this will be faster
– often choose e=65537 (216-1)
• but if e too small (eg e=3) can attack
– using Chinese remainder theorem & 3 messages with different
moduli
• if e is fixed must ensure gcd(e,ø(n))=1
– ie reject any p or q not relatively prime to e
 RSA - Efficient Decryption
• decryption uses exponentiation to power d
– this is likely large, insecure if not
• can use the Chinese Remainder Theorem (CRT) to compute mod p
& q separately. then combine to get desired answer
– approx 4 times faster than doing directly
• only owner of private key who knows values of p & q can use this
technique
 RSA Key Generation
• users of RSA must:
– determine two relative primes at random - p,q
– select either e or d and compute the other
• primes p,q must not be easily derived from modulus n=p.q
– means must be sufficiently large
– typically guess and use probabilistic test
• exponents e, d are inverses, so use Inverse algorithm (Extended
Euclidean Algorithm) to compute the other
 RSA Security
• possible approaches to attacking RSA are:
– brute force key search (infeasible given size of numbers)
– mathematical attacks (based on difficulty of computing ø(n), by
factoring modulus n, hard problems)
– timing attacks (on running of decryption)
– chosen ciphertext attacks (given properties of RSA)
RSA attacks
Elgamal Cryptographic Algorithm
Elgamal encryption

● ElGamal encryption is a public-key cryptosystem.

● It uses asymmetric key encryption for communicating between
two parties and encrypting the message.
● This cryptosystem is based on the difficulty of finding
discrete logarithm in a cyclic group that is even if we know
ga and gk, it is extremely difficult to compute gak.
Steps of Elgamal cryptosystem

Suppose Alice wants to communicate with Bob.

1. Bob generates public and private keys:
● Bob chooses a very large number q and a cyclic group Fq.
● From the cyclic group Fq, he choose any element g and
an element a such that gcd(a, q) = 1.
● Then he computes h = ga.
● Bob publishes (F, h = ga, q) and g as his public key and retains
a as private key.
Steps of Elgamal cryptosystem (Contd.)

Suppose Alice wants to communicate with Bob.

2. Alice encrypts data using Bob’s public key :
● Alice selects an element k from cyclic group F such that
gcd(k, q) = 1.
● Then she computes p = gk and s = hk = gak.
● She multiples s with M.
● Then she sends (p, M*s) = (gk, M*s).
Steps of Elgamal cryptosystem (Contd.)

Suppose Alice wants to communicate with Bob.

3. Bob decrypts the message :
● Bob calculates s′ = pa = gak.
● He divides M*s by s′ to obtain M as s = s′.
 Ex:

Original Message : encryption In this cryptosystem, the original

g: 5860696954522417707188952371547944035333315907890 message M is masked by multiplying
ga: 4711309755639364289552454834506215144653958055252 gak to it. To remove the mask, a clue is
gk:12475188089503227615789015740709091911412567126782
given in form of gk. Unless someone
knows a, he will not be able to retrieve
gak:39448787632167136161153337226654906357756740068295
M. This is because finding discrete log
Decrypted Message : encryption
in a cyclic group is difficult and
simplifying knowing ga and gk is not
good enough to compute gak.
 Advantages

● Security: ElGamal is based on the discrete logarithm problem, which

is considered to be a hard problem to solve. This makes it secure
against attacks from hackers.
● Key distribution: The encryption and decryption keys are different,
making it easier to distribute keys securely. This allows for secure
communication between multiple parties.
● Digital signatures: ElGamal can also be used for digital signatures,
which allows for secure authentication of messages.
 Disadvantages

● Slow processing: ElGamal is slower compared to other encryption algorithms,

especially when used with long keys. This can make it impractical for certain
applications that require fast processing speeds.
● Key size: ElGamal requires larger key sizes to achieve the same level of
security as other algorithms. This can make it more difficult to use in some
applications.
● Vulnerability to certain attacks: ElGamal is vulnerable to attacks based on the
discrete logarithm problem, such as the index calculus algorithm. This can
reduce the security of the algorithm in certain situations.
Knapsack Algorithm
Diffie Hellman Key Exchange
Algorithm
 Diffie/Hellman Key Exchange
• Securely exchange a key
– Without previously sharing any secrets
• Alice and Bob agree on a large prime n and a number g
– g should be primitive mod n
• n and g don’t need to be secrets
Exchanging a Key in Diffie/Hellman
• Alice and Bob want to set up a session key
– How can they learn the key without anyone else knowing
it?
• Protocol assumes authentication
• Alice chooses a large random integer x and sends Bob
X = gxmod n
 Exchanging the Key, Contd.
• Bob chooses a random large integer y and sends Alice Y = gy
mod n
• Alice computes k = Yx mod n
• Bob computes k’ = Xy mod n
• k and k’ are both equal to gxymod n
• But nobody else can compute k or k’
 Why Can’t Others Get the Secret?
• What do they know?
– n, g, X, and Y
– Not x or y
• Knowing X and y gets you k
• Knowing Y and x gets you k’
• Knowing X and Y gets you nothing
– Unless you compute the discrete logarithm to obtain x or y
Elliptic Curve Cryptography

These slides were prepared by Tim Güneysu, Christof Paar and Jan Pelzl
< Motivation
▪ Problem:
Asymmetric schemes like RSA and Elgamal require exponentiations in integer rings and
fields with parameters of more than 1000 bits.
▪ High computational effort on CPUs with 32-bit or 64-bit arithmetic
▪ Large parameter sizes critical for storage on small and embedded systems
▪ Motivation:
Smaller field sizes providing equivalent security are desirable
▪ Solution:
Elliptic Curve Cryptography uses a group of points (instead of integers) for cryptographic
schemes with coefficient sizes of 160-256 bits, reducing significantly the computational
effort.

Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

< Computations on Elliptic Curves
• Elliptic curves are polynomials that define points based on
the (simplified) Weierstraß equation:

y2 = x3 + ax + b

for parameters a,b that specify the exact shape

of the curve

• On the real numbers and with parameters

a, b ∈ R, an elliptic curve looks like this

• Elliptic curves can not just be defined over the real

Example: y2 = x3 −3x+3 over R
numbers R but over many other types of finite fields.

Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

< Computations on Elliptic Curves (ctd.)
▪ In cryptography, we are interested in elliptic curves
module a prime p:
Definition: Elliptic Curves over prime fields

The elliptic curve over Zp, p>3 is the set of all

pairs (x,y)∈ Zp which fulfill
y2 = x3 + ax + b mod p
together with an imaginary point of infinity θ,
where a,b∈ Zp and the condition
4a3+27b2 ≠ 0 mod p.

▪ Note that Zp = {0,1,…, p -1} is a set of integers

with modulo p arithmetic

Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

< Computations on Elliptic Curves (ctd.)
▪ Some special considerations are required to convert
elliptic curves into a group of points
▪ In any group, a special element is required to
allow for the identity operation, i.e.,
given P ∈ E: P + θ = P = θ + P
P
▪ This identity point (which is not on the curve) is point at
infinity
additionally added to the group definition θ
▪ This (infinite) identity point is denoted by θ
▪ Elliptic Curve are symmetric along the x-axis
-P
▪ Up to two solutions y and -y exist for each
quadratic residue x of the elliptic curve
▪ For each point P =(x,y), the inverse or negative
point is defined as -P =(x,-y)
Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl
 < Computations on Elliptic Curves (ctd.)
▪ Generating a group of points on elliptic curves based on point addition
operation P+Q = R, i.e., (xP,yP)+(xQ,yQ) = (xR,yR)
Point Addition
▪ Geometric Interpretation of point addition operation
▪ Draw straight line through P and Q; if P=Q use tangent line instead
▪ Mirror third intersection point of drawn line with the elliptic curve
along the x-axis
▪ Elliptic Curve Point Addition and Doubling Formulas
x3 = s2 −x1−x2 mod p and y3 = s(x1 −x3)−y1 mod p Point Doubling

where
; if P ≠ Q (point addition)
s= ; if P = Q (point doubling)

Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

 < Computations on Elliptic Curves (ctd.)

▪ Example: Given E: y2 = x3+2x+2 mod 17 and point P=(5,1)

Goal: Compute 2P = P+P = (5,1)+(5,1)= (x3,y3)

s= = (2 · 1)−1(3 · 52 + 2) = 2−1 · 9 ≡ 9 · 9 ≡ 13 mod 17

x3 = s2 − x1 − x2 = 132 − 5 − 5 = 159 ≡ 6 mod 17
y3 = s(x1−x3) − y1 = 13(5 − 6) − 1= −14 ≡ 3 mod 17

Finally 2P = (5,1) + (5,1) = (6,3)

69/24 Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

< Computations on Elliptic Curves (ctd.)

▪ The points on an elliptic curve and the point at infinity θ form cyclic subgroups
2P = (5,1)+(5,1) = (6,3) 11P = (13,10)
3P = 2P+P = (10,6) 12P = (0,11)
4P = (3,1) 13P = (16,4)
5P = (9,16) 14P = (9,1)
6P = (16,13) 15P = (3,16)
7P = (0,6) 16P = (10,11)
8P = (13,7) 17P = (6,14)
9P = (7,6) 18P = (5,16)
10P = (7,11) 19P = θ
▪ This elliptic curve has order #E = |E| = 19 since it contains 19 points in its cyclic
group.
 < Number of Points on an Elliptic Curve
• How many points can be on an arbitrary elliptic curve?
• Consider previous example: E: y2 = x3+2x+2 mod 17 has 19 points
• However, determining the point count on elliptic curves in general is hard
• But Hasse‘s theorem bounds the number of points to a restricted interval

• Interpretation: The number of points is “close to” the prime p

• Example: To generate a curve with about 2160 points, a prime with a length of about
160 bits is required
71/24 Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl
 < Elliptic Curve Discrete Logarithm Problem
▪ Cryptosystems rely on the hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP)

▪ Cryptosystems are based on the idea that d is large and kept secret and attackers cannot compute it
easily

▪ If d is known, an efficient method to compute the point multiplication dP is required to create a

reasonable cryptosystem
▪ Known Square-and-Multiply Method can be adapted to Elliptic Curves
▪ The method for efficient point multiplication on elliptic curves: Double-and-Add Algorithm

72/24 Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

73/24 Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl
Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl
Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl
 < Security Aspects
▪ Why are parameters significantly smaller for elliptic curves (160-256 bit) than for RSA (1024-3076 bit)?
▪ Attacks on groups of elliptic curves are weaker than available factoring algorithms or integer DL
attacks
▪ Best known attacks on elliptic curves (chosen according to cryptographic criterions)
are the Baby-Step Giant-Step and Pollard-Rho method
▪ Complexity of these methods: on average, roughly steps are required before the ECDLP can be
successfully solved

▪ Implications to practical parameter sizes for elliptic curves:

▪ An elliptic curve using a prime p with 160 bit (and roughly 2160 points) provides a security of 280 steps
that required by an attacker (on average)
▪ An elliptic curve using a prime p with 256 bit (roughly 2256 points) provides a security of 2128 steps on
average

76/24 Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

 < Implementations in Hardware and Software
▪ Elliptic curve computations usually regarded as consisting of four layers:
▪ Basic modular arithmetic operations are computationally most
expensive
▪ Group operation implements point doubling
and point addition
▪ Point multiplication can be implemented using the Double-and-Add
method
▪ Upper layer protocols like ECDH and ECDSA
▪ Most efforts should go in optimizations of the modular arithmetic
operations, such as
▪ Modular addition and subtraction
▪ Modular multiplication
▪ Modular inversion

77/24 Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

 < Implementations in Hardware and Software
▪ Software implementations
▪ Optimized 256-bit ECC implementation on 3GHz 64-bit CPU
requires about 2 ms per point multiplication H
▪ Less powerful microprocessors (e.g, on SmartCards or cell W
phones) may take significantly longer (>10 ms)
▪ Hardware implementations
▪ High-performance implementations with 256-bit special
primes can compute a point multiplication in a few hundred
microseconds on reconfigurable hardware S
W
▪ Dedicated chips for ECC can compute a point multiplication
in as few as ten microseconds

78/24 Chapter 9 of Understanding Cryptography by Christof Paar and Jan Pelzl

End of Module 3