19CSE331 – Cryptography

Public Key Cryptography

by
KAVITHA C.R.
Asst. Prof.
Dept. of Computer Science and Engineering

Amrita School of Computing, Bengaluru

Amrita Vishwa Vidyapeetham
 Public Key Cryptography or
Asymmetric Key Cryptography
❑ Bob Uses a pair of keys (KE, KD) and
• makes key KE public
• keeps key KD private
❑ Anyone can use the public key KE to encrypt a plaintext into a
ciphertext sent to Bob
❑ Only Bob can decrypt the ciphertext using the private key KD
❑ The most popular encryption scheme is RSA, named after its
inventors Rivest, Shamir, and Adleman (1978)

09-12-2022 2
 Asymmetric Key Cryptography

Different keys are used for encryption and decryption

Note: Different Keys of same user
09-12-2022 3
09-12-2022 4
Encryption and Decryption to prove Confidentiality
Confidentiality ensures that only genuine users can read the original
message.
Each entity has 2 keys:
private key (a secret) and public key (well known).
Using Keys
•Public keys (receiver) are used for encrypting.
•Private keys (receiver) are used for decrypting.

09-12-2022 5
• A public-key crypto system consists of a key with two
parts: a public key and a private key

• Anyone can encrypt a message using the public key

(Ideally) decryption can only be performed using private key

• If both parties setup their own system, two-way

communication is possible
• Full communication can be done using the public-key
system, but usually the public key system is used to
exchange symmetric keys to a block cipher (AES)

• It is possible, but should be infeasible to derive the

private key from the public key
09-12-2022 6
 Transmitting over an insecure channel
Alice wants to send Bob a private message.

Apublic is Alice’s public key.

Aprivate is Alice’s private key.
Bpublic is Bob’s public key.
Bprivate is Bob’s private key.

09-12-2022 7
 Hello Bob,
Wanna get together?

Bob
Alice

encrypt using Bpublic decrypt using Bprivate

•Nobody can read the message from Alice, but anyone could
produce it.
•How does Bob know that the message was really sent from Alice?
•Bob may be comforted to know that only Alice can read his reply.
09-12-2022 8
 OK Alice,
Your place or
mine?
Alice Bob

decrypt using Aprivate encrypt using Apublic

09-12-2022 9
09-12-2022 10
 Digital Signature
•Public key cryptography is also used to provide digital signatures.

signing
plaintext signed message

private key of sender

verification
signed message plaintext

public key of sender

09-12-2022 11
Digital Signature to prove Authentication
Authentication is a proof of identity

09-12-2022 12
 Alice can sign her message!
•Alice can create a digital signature and prove she sent the
message.
•The signature can be a message digest encrypted with Aprivate.
Message Digest
•Also known as “hash function” or “one-way transformation”.
•Transforms a message of any length and computes a fixed
length string.
•We want it to be hard to guess what the message was given only
the digest.
⚫ Guessing is always possible.

09-12-2022 13
 Creating Message Digest for Integrity
Integrity ensures there is no modification.

A → B : Message M // Sign = EKPR(H(M))

09-12-2022 14
 Verifying a Digital Signature

Receiver Computes X = H(M) and Y = DKPU(Sign) and

Compare X with Y. If both are same then no modification
09-12-2022 15
 Alice’s Signature
•Alice feeds her original message through a hash
function and encrypts the message digest with Aprivate
•Bob can decrypt the message digest using Apublic
•Bob can compute the message digest himself.
•If the 2 message digests are identical, Bob knows
Alice sent the message.

09-12-2022 16
 Example: SSL (Secure Socket Layer – simplified version)

Sender: C = EKPU(EKPR(M)) private key of A and public key of B is used

Receiver: M = DKPU(DKPR(C)) private key of B and public key of A is used
09-12-2022 17
 Revised Scheme
Alice Bob

Sign with Aprivate check signature using Apublic

encrypt using Bpublic decrypt using Bprivate

Both Confidentiality and Authentication are proved

09-12-2022 18
 Why the digest?
• Alice could just encrypt her name, and then Bob could
decrypt it with Apublic.
• Why wouldn’t this be sufficient?
Implications
• Suppose Alice denies she sent the message?
• Bob can prove that only someone with Alice’s private key
could have produced the message.

09-12-2022 19
 Another possible problem
•Suppose Bill receives a message from Alice including a digital
signature. “meet me at the library tonight”
•Bill sends the same message to Joe so that it looks like the
message came from Alice.
•Bill includes the digital signature from the message Alice sent to
him.
•Joe is convinced that Alice sent the message!
Solution:
•Always start your messages with:
⚫ Dear Bill,
•Create a digest from the encrypted message and sign that
digest.
•There are many other schemes as well.
09-12-2022 20
09-12-2022 21
09-12-2022 22
 Limitations
1) Speed
•Secret key or symmetric key encryption/decryption algorithms
are much faster than public key algorithms.
•Many times a combination is used:
⚫ use public key cryptography to share a secret key.
⚫ use the secret key to encrypt the bulk of the
communication.
2) Computational cost
• Most public key algorithms are relatively computationally
costly in comparison with many symmetric key algorithms of
apparently equivalent security.
This has important implications for their practical use.
09-12-2022 23
One-way Function
• One-way functions are easy to compute but it is very
difficult to compute their inverse functions.

• Thus, having data x it is easy to calculate f(x) but, on

the other hand, knowing the value of f(x) it is quite
difficult to calculate the value of x.

• There is not a mathematical proof that one-way

functions exist. In practical applications functions that
behave similarly as real one-way functions are used.

• One-way functions are key elements of various tools useful

in modern cryptography. They are used in pseudorandom
generators, authentication of messages and digital
signatures.
Egs: Factoring Problem, Discrete Logarithm mod p problem, Subset
sum problem, Quadratic residue problem
09-12-2022 24
 Trapdoor one-way function
Trapdoor one-way functions are types of one-way functions
that contain a kind of "back door" (trapdoor).

As in the case of ordinary one-way functions it is easy

to compute their values for given data but it is very difficult
to compute their inverse functions.

However, if one has some additional secret information, he

can easily compute the inverse function as well.

An example of such trapdoor one-way functions may be

finding the prime factors of large numbers.
Nowadays, this task is practically infeasible.
On the other hand, knowing one of the factors, it is easy to
compute the other ones.

09-12-2022 25
 Discrete Logarithm

gx ≡ h (mod p) where g is the primitive element in Zp

x is discrete logarithm of h with base g mod p

x = dlogg,p (h)

Eg: 1) dlogg,p (1) = 0

g0 ≡ 1 (mod p)

2) dlogg,p(g) = 1
g1 ≡ g (mod p)

09-12-2022 26
 Diffie Hellman Key Exchange Algorithm
An example is taken to visualize Diffie-Hellman
Key Exchange algorithm.
Let’s say we have two users, Alice and Bob.
•They both agree to use random color which is
known to everyone (e.g. yellow).
•They both have selected a private (secret for
them) color for themselves (red and sea-green)
•Before sharing a color, both mixed their
private color with public color. i.e. Alice mixed
yellow color in red and Bob mixed sea
green color in yellow.
•Both exchange new colors with each other.
•To make sure exchange identity, both mixed their
private color in the new color which they
received.
•After mixing private color both will have
identical color as final color, which identifies the
exchange of color is successful (securely
exchange the keys).
•If a third person has intercepted the color
exchange, it would be difficult to determine the
09-12-2022 secret color.
27
 Diffie-Hellman uses two numbers:
1.A Prime number
[Link] primitive root of the prime number
The Diffie-Hellman Key Exchange is a means for two parties to jointly
establish a shared secret over an unsecure channel

09-12-2022 28
 Example:

09-12-2022 29
 Man-in-the-Middle Attack

09-12-2022 30
09-12-2022 31
RSA (Rivest, Shamir, Adelman) Algorithm
The RSA cryptosystem is the most widely-used public key cryptography algorithm in
the world. It can be used to encrypt a message without the need to exchange a secret
key separately.
The RSA algorithm can be used for both public key encryption and digital signatures.
Its security is based on the difficulty of factoring large integers.
User A can send an encrypted message to User B without any prior exchange of secret
keys. A just uses B's public key to encrypt the message and B decrypts it using the
private key, which only he knows. RSA can also be used to sign a message, so A can
sign a message using their private key and B can verify it using A's public key.

The RSA algorithm holds the following features −

•RSA algorithm is a popular exponentiation in a finite field over
integers including prime numbers.
•The integers used by this method are sufficiently large making it
difficult to solve.
•There are two sets of keys in this algorithm: private key and
public key.
09-12-2022 32
09-12-2022 33
09-12-2022 34
 M =14
Then Encryption process is C = Me mod n = 147 mod 33
= (142)3 * 14 mod 33
= (31)3 * 14 mod 33
= 20
Decryption Process is M = Cd mod n = 203 mod 33
= 14

If M = 19,
Encryption process is C = Me mod n = 197 mod 33
= (31)3 * 19 mod 33
= 13

Decryption Process is M = Cd mod n = 133 mod 33

= 19

09-12-2022 35
Eg: Given p=11 and q =13, plain text M = 7. Use the encryption key as 11.
Find the decryption key. Compute all the steps of RSA algorithm. Perform
Encryption and verify decryption.
M=7
n = 11 * 13 = 143
Փ(n) = 10 * 12 = 120
Encryption key e = 11
Decryption key d = e-1 mod Փ(n) = 11-1 mod 120 = 11
Both encryption and decryption keys are same. So it is not good.
Change the encryption key.

Let Encryption key e = 7

Decryption key d = e-1 mod Փ(n) = 7-1 mod 120 = 103

C = Me mod n = 77 mod 143

=6

M = Cd mod n = 6103 mod 143

= (64)25 * 63 mod 143 = 925 * 73 mod 143
= (94)6 * 9 * 73 mod 143
= (1262)3 * 85 mod 143 = 33 * 85 mod 143 = 7
09-12-2022 36
Eg: Given encryption key e = 31, N =3599. Find the decryption key.

Factorize N
3599 = 59 * 61
p = 59 q =61
Փ(3599) = 58 * 60 = 3480

Decryption key is 31-1 mod 3480 = 3031

09-12-2022 37
 Given g = 7 and p = 11. Private key of User A is 12 and
private key of User B is 14. Find the common secret key
Using Diffie-Hellman Key Exchange algorithm.

XA = 12, XB = 14

Public key of user A is YA = 712 mod 11 = 5

Public key of user B is YB = 714 mod 11 = 3

Ks1 = 312 mod 11 = 9

Ks2 = 514 mod 11 = 9

Ks1 = Ks2
A common secret key is generated using Diffie-Helman Key Exchange
algorithm
09-12-2022 38
09-12-2022 39
09-12-2022 40
09-12-2022 41
09-12-2022 42
09-12-2022 43
09-12-2022 44
Ex: Suppose the receiver selected the primes p=11and q=17, along
with e=3. Find the decryption key. Encrypt the message “HELLO“.
First the sender converts the message into its ASCII code where
ASCII code of A is 65, B is 66 and so on, Z is 90.
Show the Encryption and Decryption of the message using RSA
algorithm.

09-12-2022 45
Ex: p = 61, q=53 and encryption key e = 17. Find the decryption key.
Let the plain text be M = 123. Using RSA algorithm perform encryption
and Verify decryption.

09-12-2022 46
ElGamal Encryption Algorithm

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.

09-12-2022 47
 Elgamal Algorithm

09-12-2022 48
09-12-2022 49
09-12-2022 50
 α is g which is
generator

09-12-2022 51
 g = 11 and p = 23

Private key x = 6

09-12-2022 52
09-12-2022 53
09-12-2022 54
09-12-2022 55
09-12-2022 56
09-12-2022 57