Module 2-Ch2

1. Introduction to Public Key Cryptosystems

A Public Key Cryptosystem is a type of cryptographic system that uses two

different keys:

1. Public Key
2. Private Key

Unlike symmetric encryption, where the same key is used for encryption and
decryption, public key cryptography uses two mathematically related keys.

Key Idea

 Public Key → Known to everyone

 Private Key → Secret

If a message is encrypted using one key, it can only be decrypted using the
other key.

2. Principle of Public Key Cryptosystems

Public key cryptography works based on mathematical functions that are

easy to compute but hard to reverse.

These are called Trapdoor One-Way Functions.

One-Way Function

Easy to compute:

y = f(x)

But very difficult to compute:

x = f⁻¹(y)

Example:

Multiplying two large prime numbers is easy, but factoring them back is very
difficult.

3. Key Pair Concept

Each user generates a pair of keys.

Public Key (PU)

Private Key (PR)

These keys are mathematically related.

Important Property

M = D(PR, E(PU, M))

Where

 M = Plaintext
 E = Encryption
 D = Decryption

This means:

Encryption with Public Key

Decryption with Private Key

4. Basic Operation of Public Key Cryptosystem

Step-by-Step Process

Sender → Encrypt message using receiver's public key

Receiver → Decrypt message using private key
Simple Diagram

Mathematical Representation

Encryption:

C = E(PU , M)

Decryption:

M = D(PR , C)

Where

 PU = Public Key
 PR = Private Key
 M = Message
 C = Ciphertext

Key Distribution in Public Key Cryptosystems

Public keys can be openly distributed.

Example:

A user publishes their public key in

  Public directories
 Certificate authorities
 Digital certificates

But the private key must be kept secret.

Example of Public Key Communication

Suppose:

Sender = Alice
Receiver = Bob

Bob generates keys:

Public Key → PU_B

Private Key → PR_B

Bob publishes PU_B.

Communication Process

Step 1

Alice gets Bob's Public Key

Step 2

Alice encrypts message

C = E(PU_B , M)

Step 3

Ciphertext is sent.

Step 4

Bob decrypts

M = D(PR_B , C)
Only Bob can read the message.

2. Properties of Public Key Cryptosystems

a public key system must satisfy the following properties.

1. Easy Key Generation

It should be easy to generate a pair of keys.

(PU , PR)

2. Easy Encryption

Encryption using the public key must be computationally efficient.

C = E(PU , M)

3. Easy Decryption

Decryption using the private key must be easy.

M = D(PR , C)

4. Difficult to Derive Private Key

It must be computationally infeasible to derive the private key from the public
key.

PR ≠ f(PU)

5. Encryption and Decryption are Inverses

M = D(PR , E(PU , M))
 3. Two Important Uses of Public Key Systems

Public key systems can be used in two different ways.

1. Confidentiality (Encryption)

Purpose: Secure communication

Process:

Encryption → Public Key

Decryption → Private Key

Example:

C = E(PU_B , M)
M = D(PR_B , C)

2. Authentication (Digital Signature)

Purpose: Verify sender identity

Process:

Encryption → Private Key

Decryption → Public Key

Example:

Signature = E(PR_A , M)
M = D(PU_A , Signature)

If decryption works correctly → message came from sender.

Advantages of Public Key Cryptography

1. Solves key distribution problem

2. Supports digital signatures
3. Enables secure communication over open networks
4. Provides authentication and confidentiality
Limitations of Public Key Cryptography

1. Slower than symmetric encryption

2. Requires large computational power
3. Vulnerable to mathematical attacks if algorithm is weak

Therefore, in practice:

Public Key → Used for Key Exchange

Symmetric Key → Used for Data Encryption

Example:

 HTTPS
 SSL/TLS

Examples of Public Key Algorithms

Some commonly used public key algorithms are:

Algorithm Use

RSA Encryption and Digital Signatures

Diffie–Hellman Key Exchange

ElGamal Encryption

ECC (Elliptic Curve Cryptography) Modern secure communication

Real World Applications

Public key cryptography is used in:

 HTTPS secure websites

 Digital signatures
 Online banking
 Secure email
  Cryptocurrency
 VPN communication

4 Requirements for Public Key Cryptography

 For a public key cryptosystem to be secure and practical, it must
satisfy several important requirements.

1: Easy Key Pair Generation

It should be computationally easy to generate a pair of keys:

 Public Key (PU)

 Private Key (PR)

Easy Encryption

The encryption process should be simple and computationally efficient.

Mathematically:

C = E(PU , M)

Where:

 M = Plaintext
 PU = Public Key
 C = Ciphertext

Easy Decryption

 The receiver should be able to decrypt the message easily using the
private key.
 Mathematically:
 M = D(PR , C)

Infeasible to Derive Private Key from Public Key

It must be computationally infeasible to determine the private key using the

public key.
Meaning:

PR cannot be easily calculated from PU

Infeasible to Recover Plaintext from Ciphertext

Even if an attacker knows:

 Public key
 Ciphertext

They should not be able to recover the plaintext.

Encryption and Decryption Are Inverses

The encryption and decryption operations must satisfy:

M = D(PR , E(PU , M))

Meaning:

1. Encrypt with Public Key

2. Decrypt with Private Key

The original message must be recovered.

II RSA
RSA was proposed by Ron Rivest, Adi Shamir, and Leonard Adleman in
1977.

RSA has 3 main phases

1 Key Generation
2 Encryption
3 Decryption

RSA Key Generation Algorithm

 1. Select two prime numbers p and q
2. Compute

n=p×q

3. Compute

φ(n) = (p−1)(q−1)

4. Choose e such that

gcd(e, φ(n)) = 1

5. Compute d such that

d × e ≡ 1 mod φ(n)

6. Public key = (e, n)

7. Private key = (d, n)

RSA Encryption Algorithm

Input : Message M
Output: Ciphertext C

1. Obtain public key (e,n)

2. Compute

C = M^e mod n

3. Send ciphertext C

RSA Decryption Algorithm

Input : Ciphertext C
Output: Message M

1. Use private key (d,n)

2. Compute

M = C^d mod n

3. Recover plaintext
RSA Key Generation (Step-by-Step)

Step 1: Choose Two Prime Numbers

Choose two large prime numbers.

Example:

p=3
q = 11

Step 2: Compute n

n=p×q
n = 3 × 11 = 33

n is used as the modulus.

Step 3: Compute Euler’s Totient Function

φ(n) = (p − 1)(q − 1)
φ(n) = (3 − 1)(11 − 1)
φ(n) = 2 × 10 = 20

Step 4: Choose Public Key (e)

Select e such that:

1 < e < φ(n)

gcd(e, φ(n)) = 1

Choose:

e=3

Because

gcd(3,20) = 1
Step 5: Compute Private Key (d)

Find d such that

d × e ≡ 1 mod φ(n)
d × 3 ≡ 1 mod 20

Solution:

d=7

because

7 × 3 = 21
21 mod 20 = 1

RSA Encryption Process

Formula

C = M^e mod n

Where

M = plaintext
C = ciphertext
e = public key
n = modulus

Example Encryption

Let plaintext be

M=4

Compute

C = 4^3 mod 33

Step calculation

4^3 = 64
64 mod 33 = 31
Ciphertext

C = 31

3 RSA Decryption Process

Formula

M = C^d mod n

Where

d = private key

Example Decryption

Ciphertext

C = 31

Compute

M = 31^7 mod 33

Step calculation

31 mod 33 = 31
31^2 mod 33 = 4
31^4 mod 33 = 16

Then

31^7 = 31^(4+2+1)
= (16 × 4 × 31) mod 33
= 1984 mod 33
=4

Recovered message

M=4

✅Decryption successful.
 Final Keys

Public Key

(e, n) = (3, 33)

Private Key

(d, n) = (7, 33)

RSA Process Flow (Simple Diagram)

Key Generation
↓
(p , q chosen)
↓
n = pq
φ(n) = (p−1)(q−1)
↓
Choose e
↓
Compute d
↓
Public Key (e,n)
Private Key (d,n)

Encryption
M → C = M^e mod n

Decryption
C → M = C^d mod n
Computational Aspects of RSA
The computational aspect of RSA refers to the mathematical calculations
required to generate keys, encrypt data, and decrypt data efficiently.

RSA mainly uses:

• Prime numbers
• Modular arithmetic
• Modular exponentiation

The algorithm was proposed by Ron Rivest, Adi Shamir, and Leonard
Adleman.

Computational Technique

RSA uses modular exponentiation to efficiently compute large powers.

Example:

Instead of directly computing

4¹³

it is calculated using square and multiply method, which reduces

computation time.

This makes RSA practical even for very large numbers (2048-bit keys).

Security of RSA
The security of RSA is based on the difficulty of factoring large composite
numbers.

In RSA:

n=p×q

where

p and q are large prime numbers.

The public key contains n, but p and q are secret.

Why RSA is Secure

Multiplying two large primes is easy.

Example

17 × 19 = 323

But factoring a large number back into its primes is very difficult.

Example

323 → 17 × 19

For very large numbers (hundreds of digits), factorization becomes

computationally infeasible.

Example

Public key

(e , n) = (3 , 33)

Attacker knows

n = 33

If attacker factors

33 = 3 × 11

Then

φ(n) = (3 − 1)(11 − 1) = 20

They can compute the private key

d=7

Then they can decrypt messages.

This is why small numbers are insecure.

Possible Attacks on RSA

1. Factorization Attack

Attacker attempts to factor n into p and q.

2. Brute Force Attack

Trying all possible private keys (practically impossible for large keys).

3. Timing Attack

Attacker measures the time taken during decryption to infer key information.

4. Chosen Ciphertext Attack

Attacker sends special ciphertexts to obtain information about the private key.

Methods to Improve RSA Security

1. Use very large prime numbers

2. Use 2048-bit or larger keys
3. Use secure padding schemes
4. Protect private keys carefully