Cryptography & Network

Security: Overview
BCS703, 7th Sem
22-08-2025 New (A)
Discussion on Module : Doubts & Quiz

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network
Security: Overview
BCS703, 7th Sem
23-08-2025 New (A)
09:30AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

 Cryptography & Network Security
Random Numbers in Cryptography & Security

• What is Random Number

• In cryptography, random numbers are used everywhere
• Key distribution & authentication:
• Like when two people (say Alice and Bob) want to talk securely, they exchange messages to
share keys and authenticate each other.

• They use nonces (numbers used once) to prevent replay attacks.

• If the nonce is random, an attacker cannot guess or reuse it.
• Session key generation:
• Every new secure session (like your online banking login) uses a fresh key valid for a short time.
• That session key must be generated randomly.
 Cryptography & Network Security
Random Numbers in Cryptography & Security

• What is Random Number

RSA key generation
• RSA requires large prime numbers.
• Random numbers are used to nd these primes.

Stream ciphers
• Encryption methods that encrypt data bit by bit (instead of block by block)
need a random bitstream
fi
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Random: Two important properties
Two important properties:
[Link] Distribution
◦ The 0s and 1s should occur about equally often.
◦ Example: Tossing a fair coin many times → about half heads, half tails.
[Link]
◦ Knowing some part of the sequence should not help in predicting the rest.
◦ Example: If the sequence so far is 01010101, you can guess the next bit → that’s not
independent.
👉 Random numbers for cryptography must pass randomness tests to prove they’re
uniform and independent.
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• What Makes a Sequence Random?
Randomization in Cryptography
• In cryptography, some problems are too big and hard to solve exactly.
• Example: Checking if a very large number (like 10^150) is prime.
◦ Brute force = dividing by all smaller numbers → impossible (takes forever).

Instead of checking everything, we use randomness:

• Pick some random test numbers.
• Run quick tests with them.
• If the tests succeed many times → we can be very con dent the number is prime (even if we
didn’t check everything).
• This trick of using randomness as a shortcut is called randomization.
fi
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• How numbers become random.
Randomization in Cryptography
• In cryptography, some problems are too big and hard to solve exactly.
• Example: Checking if a very large number (like 10^150) is prime.
◦ Brute force = dividing by all smaller numbers → impossible (takes forever).

Instead of checking everything, we use randomness:

• Pick some random test numbers.
• Run quick tests with them.
• If the tests succeed many times → we can be very con dent the number is prime (even if we
didn’t check everything).
• Example: Tasting Watermelon fi
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• What makes number a truly Random / Unpredictable
Randomness vs. Unpredictability
Very important distinction:
• Randomness = passes statistical tests (uniform, independent).
• Unpredictability = no one should be able to guess future numbers, even knowing the past
numbers.
Example:
• If a generator always alternates 0 and 1 (010101…), it’s random-looking at rst (equal 0s
and 1s), but fully predictable → bad for cryptography.
• For secure systems (authentication, session keys, stream ciphers):
we need both randomness AND unpredictability

fi
Cryptography & Network
Security: Overview
BCS703, 7th Sem
23-08-2025 (New A Sec)
11:30AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network
Security: Overview
BCS703, 7th Sem
25-08-2025 New (A)
10:25AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Requirements of a Cryptographic PRNG (or PRF)
The main rule:
If the seed is secret, then nobody should be able to guess or predict the
pseudorandom sequence.
Why?
• If a PRNG is used in a stream cipher, and an attacker learns the PRNG sequence and
can recover the plaintext.
• If a PRF is used to generate a secret key → a weak PRF could make brute-force
attacks easier.
So, cryptographic PRNGs must meet three main requirements
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Requirements of a Cryptographic PRNG (or PRF)
1. Randomness
Even though a PRNG is just a formula, its output should look like real random numbers.
• Uniformity → 0s and 1s should come with equal chance (like tossing a fair coin).
• Scalability → Even if you take a small part of the sequence, it should also look random.
• Consistency → No matter which seed you use, the generator should behave the same way.
To check this, statisticians run tests:
• Frequency Test → checks if 0s and 1s are balanced.
• Runs Test → checks if you don’t get too many repeated 0s or 1s in a row.
• Maurer’s Test → checks if the sequence can be compressed (if it can, then it’s not random
enough).
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Requirements of a Cryptographic PRNG (or PRF)
2. Unpredictability
A good cryptographic PRNG must be impossible to guess.
• Forward unpredictability → Even if you know many past outputs, you cannot predict the
next number.
• Backward unpredictability → Even if you know some outputs, you cannot go backwards
and nd the secret seed.
In short: The sequence should look so random that no shortcut exists for guessing.
fi
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Requirements of a Cryptographic PRNG (or PRF)
3. Seed Requirements
The seed is the starting value of the PRNG.
• If the attacker knows the seed, they can reproduce the entire sequence.
• So, the seed must itself be random and secret.
• Usually, a TRNG (true random generator) is used to create the seed, then fed into the
PRNG.
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Algorithm Design Approaches
There are two ways to design a PRNG:
[Link]-built PRNGs → specially designed only for generating pseudorandom numbers.
◦ Example: RC4 (used both as PRNG and stream cipher).
[Link]-algorithm–based PRNGs → reusing existing crypto algorithms that already
look random.
◦ Block ciphers (AES in CTR mode).
◦ Asymmetric ciphers (based on number theory).
◦ Hash functions / MACs (outputs look random).
Modern systems usually reuse crypto algorithms (like AES, SHA) since they’re already
available and strong.
Cryptography & Network
Security: Overview
BCS703, 7th Sem
26-08-2025 New (A)
10:25AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network
Security: Overview
BCS703, 7th Sem
08-09-2025 New (A) | 11-09-2025 (New B Sec)
10:25AM | 10:25AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

 Cryptography & Network Security
Random Numbers in Cryptography & Security

• What is Random Number

• In cryptography, random numbers are used everywhere
• Key distribution & authentication:
• Like when two people (say Alice and Bob) want to talk securely, they exchange messages to
share keys and authenticate each other.

• They use nonces (numbers used once) to prevent replay attacks.

• If the nonce is random, an attacker cannot guess or reuse it.
• Session key generation:
• Every new secure session (like your online banking login) uses a fresh key valid for a short time.
• That session key must be generated randomly.
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Random: Two important properties
Two important properties:
[Link] Distribution
◦ The 0s and 1s should occur about equally often.
◦ Example: Tossing a fair coin many times → about half heads, half tails.
[Link]
◦ Knowing some part of the sequence should not help in predicting the rest.
◦ Example: If the sequence so far is 01010101, you can guess the next bit → that’s not
independent.
Random numbers for cryptography must pass randomness tests to prove they’re uniform
and independent.
Cryptography & Network
Security: Overview
BCS703, 7th Sem
13-09-2025 (New B Sec)
10:25AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

 Cryptography & Network Security
Random Numbers in Cryptography & Security
• What makes number a truly Random / Unpredictable
TRNG – True Random Number Generator PRNG – Pseudorandom Number Generator
• Gets randomness from the real world • Uses a mathematical formula (algorithm).
(nature, computer hardware). • Needs a seed (a starting number, often
• Example: given by TRNG).
◦ How you move your mouse, • Generates a long sequence of numbers
◦ The time you press keys, that look random.
◦ Tiny uctuations in your computer clock. • If someone knows the seed + algorithm →
• These are unpredictable → converted into they can recreate the sequence.
random bits. • Very fast → widely used in cryptography
• Very secure, but slow. (like generating keystreams).
fl
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• What makes number a truly Random / Unpredictable
PRF – Pseudorandom Function
• Works like PRNG, but instead of unlimited numbers, it gives a xed-size output.
• Example: generate exactly 128 random bits for a key or nonce.
• Uses seed + some extra info (like user ID, session ID).

fi
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Pseudorandom Number Generators (PRNGs)
PRNGs are algorithms that generate sequences of numbers that look random but are actually deterministic
(completely determined by initial values and formulas).

1. Linear Congruential Generators (LCGs)

One of the oldest and most widely used PRNG methods, introduced by Lehmer (1951).

General Formula
Xn+1 =(aXn + c)mod m
Where:
•m → modulus (m>0)
•a → multiplier (0<a<m)
•c → increment (0≤c<m)
•X0 → seed (starting value)
Each new number depends only on the previous one → deterministic process.
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Pseudorandom Number Generators (PRNGs)
2. Example
• a=7, c=0, m=32, X0=1
Sequence: {7, 17, 23, 1, 7, …} → Period = 4 (bad generator)
• If we change a=5, sequence: {5, 25, 29, 17, 21, 9, 13, 1, …} → Period = 8
• A “good” generator should have a long period, ideally close to m.

3. Criteria for a Good PRNG (Park & Miller, 1988)

1.T1 – Full period: It should generate all possible numbers (0 … m-1) before repeating.
2.T2 – Randomness: Sequence should appear random (no obvious patterns).
3.T3 – Ef ciency: Should be ef cient with 32-bit arithmetic.
fi
fi
 Cryptography & Network Security
Random Numbers in Cryptography & Security
• Pseudorandom Number Generators (PRNGs)
4. Choosing Parameters 5. Strengths of LCG
•If m is prime and c = 0, then for certain values of •Simple and fast
a, the period is m – 1. •If parameters chosen correctly → sequence
•A common choice: passes statistical randomness tests.
•Xn+1 =(a Xn)mod(231−1) •Widely used in simulation, statistics, Monte
•where m=231−1 (a large prime). Carlo experiments
6. Weaknesses of LCG
•Best-known parameters:
◦ a=16807 (=75) •Not truly random → sequence is deterministic
◦ c=0 •If seed + parameters are known → entire
◦ m=231−1 sequence predictable
This generator was used in IBM 360 and is still •Even if only a few values of the sequence are
widely recommended known → one can solve equations to nd a,c,m.
•Security risk → Not suitable for cryptography.
fi
Cryptography & Network
Security: Overview
BCS703, 7th Sem
08-09-2025 New (A)
12:25PM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network Security
Random Numbers in Cryptography & Security
Blum Blum Shub (BBS) Generator
• Blum Blum Shub (BBS) is a cryptographically secure pseudorandom number generator (CSPRNG).
• It was proposed by Blum, Blum, and Shub in 1986.
• Its main strength: it is unpredictable and has a strong mathematical proof of security.
• In simple words: It produces random-looking bits (0s and 1s) that are impossible to guess ahead
of time, unless you know some secret information.
• Why do we need BBS?
• Many older random number generators (like Linear Congruential Generators) are fast but
predictable → not good for cryptography.
• In cryptography, if someone can predict the random numbers, they can break keys, sessions,
or messages.
• BBS solves this problem because its randomness is based on a hard math problem: factoring
large numbers.
Cryptography & Network Security
Random Numbers in Cryptography & Security
Blum Blum Shub (BBS) Generator
• The Mathematics Behind BBS.
• Choose two special prime numbers p and q:
• Both must satisfy:
• p≡3 (mod 4), q≡3 (mod 4)
• Example: p=383, q=503.
• Compute their product:n=p×q
• This just means when you divide each prime by 4, the remainder must be 3.
• Quick check: 383 % 4 = 3 and 503 % 4 = 3 both satisfy it.
• Example: n=383×503=192649.
• Pick a seed value s: A random number such that s
• s is relatively prime to n
• (means s should not share any factors with p or q).
• i.e ==> gcd(s, n) = 1
• Example: s=101355
Cryptography & Network Security
Random Numbers in Cryptography & Security
Blum Blum Shub (BBS) Generator : The BBS Algorithm

• Step 1: Compute the rst state : X0 =s2 (mod n)

• Step 2: Generate sequence using: Xi =(Xi−1)2 (mod n)
• Step 3: Output the least signi cant bit (LSB) of each Xi :
• Bi =Xi (mod 2)
• If Xi is even, Bi =0.
• If Xi is odd, Bi =1.
fi
fi
Cryptography & Network Security
Random Numbers in Cryptography & Security
Blum Blum Shub (BBS) Generator : The BBS Algorithm
Cryptography & Network Security
Random Numbers in Cryptography & Security
Blum Blum Shub (BBS) Generator
Example Walkthrough
p=383,q=503,
n=192649
Seed s=101355
Step 1: Initialization
X0 =s2 mod 192649 = 20749
Cryptography & Network Security
Random Numbers in Cryptography & Security
Blum Blum Shub (BBS) Generator
Why is BBS Secure?

• Security is based on the dif culty of factoring n into its prime factors p and q.
• If an attacker does not know p and q, predicting the sequence is as hard as solving the factoring
problem.

• Next-Bit Test:
◦ Even if you know the rst k bits, there’s no practical way to predict the (k+1)-th bit better than 50%.
• This makes BBS a Cryptographically Secure PRNG (CSPRNG).
fi
fi
Cryptography & Network
Security: Overview
BCS703, 7th Sem
10-09-2025 New (A)
12:25PM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

 Cryptography & Network Security
Public key cryptography and RSA

PUBLIC-KEY CRYPTOSYSTEMS

• Public-key cryptography (also called asymmetric cryptography) is a modern method of

securing digital communication.

• Unlike traditional symmetric cryptography, which uses the same secret key for both
encryption and decryption, public-key cryptography uses a pair of keys:

• Public key – openly shared with everyone.

• Private key – kept secret by the owner.
Cryptography & Network Security
Public key cryptography and RSA
The Two Big Problems with Symmetric Encryption
Symmetric encryption uses the same key for both encryption and decryption. This raised two major
challenges:

[Link] Distribution Problem

◦ Communicating parties must share a secret key in advance.
◦ This can be done either:
▪ By physically distributing keys (impractical on large scale).
▪ Or by using a Key Distribution Center (KDC).
◦ KDC means trusting a third party, which could be compromised.
◦ Whit eld Dif e argued this defeats the purpose of secrecy if a central authority has access to
everyone’s keys.
fi
fi
 Cryptography & Network Security
Public key cryptography and RSA
The Breakthrough by Dif e and Hellman (1976)
• Dif e and Martin Hellman proposed public-key cryptography.
• Their system used two different but related keys:
◦ A public key (shared openly).
◦ A private key (kept secret).
• This approach solved:
◦ The key distribution problem (anyone can share a public key safely).
◦ The digital signature problem (messages can be signed with a private key and veri ed
with a public key).
fi
fi
fi
Cryptography & Network Security
Public key cryptography and RSA
The Breakthrough by Dif e and Hellman (1976)
Basics of Public-Key Cryptosystems

Public-key (asymmetric) algorithms work with a key pair:

• Encryption key ≠ Decryption key

• It’s computationally infeasible to derive the private key from the public key.
• Some algorithms (like RSA) allow either key to be used for encryption and the other for
decryption.
fi
Cryptography & Network Security
Public key cryptography and RSA
Components of a Public-Key System
Every system has six ingredients:

[Link] → the original readable message.

[Link] Algorithm → transforms plaintext into

ciphertext.

[Link] & Private Keys → a key pair (one for

encryption, one for decryption).

[Link] → the scrambled, unreadable output.

[Link] Algorithm → reverses the process using

the matching key.

Cryptography & Network Security
Public key cryptography and RSA
Public-Key System : Decryption algorithm:
This algorithm accepts the ciphertext and the matching key and produces the original plaintext.
Following steps to follow
[Link] user generates a public/private key pair.
[Link] public key is shared openly (posted in a directory, etc.).
[Link] send a con dential message to Alice:
◦ Bob encrypts it with Alice’s public key.
[Link] Alice receives the ciphertext:
◦ She decrypts it with her private key.
◦ Only Alice can decrypt it, since only she has her private key.
fi
Cryptography & Network Security
Public key cryptography and RSA
Public-Key System : Decryption algorithm:

Conventional (Symmetric) Encryption Public-Key (Asymmetric) Encryption

Same key is used for both encryption and These use a pair of keys (public key & private
decryption. key).

At least one of the keys (the private key)

The key must be kept secret.
must be kept secret.

Knowledge of the algorithm + ciphertext Knowledge of the algorithm + one key +

samples should not be enough to discover the ciphertext samples should not allow someone
key. to determine the other key.
Cryptography & Network
Security: Overview
BCS703, 7th Sem
11-09-2025 New (A)
12:25PM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network Security
Public key cryptography and RSA
Public-Key Cryptosystem for Con dentiality
Goal: Ensure that only the intended receiver (Destination B) can read the message.
Steps:
[Link] Source (X): Source A generates a message X.
Encryption:
• The message is encrypted using Destination B’s public key (PUb).
• Encryption produces ciphertext: Y=E(PUb ,X)
Decryption:
• At Destination B, the ciphertext is decrypted using B’s private key (PRb).
• Decryption recovers the original message:
Transmission:
• The ciphertext Y is sent over the channel.
• Even if a cryptanalyst intercepts Y, they cannot decrypt it because they don’t have the private key.
fi
Cryptography & Network Security
Public key cryptography and RSA
Public-Key Cryptosystem for Con dentiality
Decryption:
At Destination B, the ciphertext is decrypted using B’s private key (PRb).
Decryption recovers the original message: X=D(PRb ,Y)
Result: Only B (who owns PRb ) can read the message → Con dentiality is achieved.

fi
fi
Cryptography & Network Security
Public key cryptography and RSA
Public-Key Cryptosystem for Authentication
 Cryptography & Network Security
Public key cryptography and RSA
Public-Key Cryptosystem for Authentication

• Key Difference: Con dentiality vs Authentication

• For con dentiality, encryption is done with the receiver’s public key and decryption with
the receiver’s private key.

• For authentication, encryption (or signing) is done with the sender’s private key, and
veri cation is done with the sender’s public key.
fi
fi
fi
 Cryptography & Network Security
Public key cryptography and RSA
Public-Key System : Authentication and Secrecy

• Message Source (Plaintext X):

• Source A starts with the original message X.
• First Encryption (using A’s private key PRa)
• The message is rst encrypted using Source
A’ s private key.
• Result = Y.
• Purpose → Authentication: Because only A
knows PRa, the receiver can later verify that
the message truly came from A.
fi
 Cryptography & Network Security
Public key cryptography and RSA
Public-Key System : Authentication and Secrecy

• Second Encryption (using B’s public key PUb)

• Now, Y is encrypted again using Destination B’s
public key.
• Result = Z.
• Purpose → Secrecy: Only B can decrypt this
(using PRb), so con dentiality is ensured.
fi
Cryptography & Network Security
Public key cryptography and RSA
Public-Key System : Authentication and Secrecy
• Transmission (Z):
• Encrypted message Z is sent across the insecure channel.
• Even if intercepted, no attacker can decrypt it (since they don’t have B’s private key PRb).
• First Decryption (using B’s private key PRb):
• At Destination B, the rst decryption step is performed with B’s private key.
• This removes the second layer of encryption.
• Output = Y.
• Second Decryption (using A’s public key PUa):
• Next, Y is decrypted using A’s public key.
• If decryption succeeds, B knows the message was encrypted with PRa → veri es A’s
identity.
• Output = original plaintext X.
fi
fi
Cryptography & Network
Security: Overview
BCS703, 7th Sem
12-09-2025 New (A)
11:30AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network
Security: Overview
BCS703, 7th Sem
16-09-2025 New (B)
09:30AM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network Security
Public key cryptography and RSA
Public-Key Cryptosystems : Applications
Public-key cryptosystems rely on a pair of keys: [Link] Signatures
• Public key → openly available. ◦ Sender “signs” the message using their
• Private key → kept secret by the owner. private key (PRa).

Depending on the goal, either the sender’s ◦ Receiver veri es authenticity using the
private key or the receiver’s public key (or sender’s public key (PUa).
both) is used. ◦ Ensures Authentication + Integrity.
Main Applications [Link] Exchange
[Link]/Decryption ◦ Both parties cooperate to establish a session
◦ Sender encrypts the message with the key (temporary secret key).
recipient’s public key (PUb). ◦ Used for symmetric encryption during one
◦ Receiver decrypts with their private key session/transaction.
(PRb). ◦ Different methods exist (e.g., Dif e–Hellman)
◦ Ensures Con dentiality.
fi
fi
fi
Cryptography & Network Security
Public key cryptography and RSA
Requirements for Public-Key Cryptography
For a cryptosystem to work securely, the underlying algorithm must satisfy strict requirements
(as rst proposed by Dif e & Hellman, 1976):

[Link] Key Generation

◦ It must be computationally simple for a user (e.g., B) to generate a public-private key pair
(PUb, PRb).

[Link] Encryption
◦ For sender A, given PUb and message M, computing ciphertext must be straightforward:
C=E(PUb,M)

[Link] Decryption
◦ For receiver B, using PRb to recover the message should be ef cient:
M=D(PRb,C)=D[PRb,E(PUb,M)]
fi
fi
fi
Cryptography & Network Security
Public key cryptography and RSA
Requirements for Public-Key Cryptography

[Link] to Derive Private Key

◦ Given PUb, it should be computationally infeasible to determine PRb.
[Link] to Recover Message
◦ Given PUb and ciphertext C, it must be infeasible for an attacker to recover message M.
[Link] Work in Either Order (Optional)
◦ In some schemes, encryption can be done with either key and decrypted with the other:
M=D[PUb,E(PRa,M)]=D[PRa,E(PUb,M)]

◦ Useful for digital signatures.

Cryptography & Network Security
Public key cryptography and RSA
What is RSA?
• RSA stands for Rivest–Shamir–Adleman, the three inventors who introduced it in 1977.
• It is the most widely used public-key cryptosystem.
• RSA is based on the mathematics of prime numbers and modular arithmetic.
CORE IDEA

• RSA uses two different keys:

• Public Key (PU = {e, n}) → used for encryption (anyone can use this).
• Private Key (PR = {d, n}) → used for decryption (only the receiver knows this).
• If someone wants to send a secure message to you:
• They use your public key to encrypt.
• You use your private key to decrypt.
Cryptography & Network Security
Public key cryptography and RSA
RSA Key Generation
[Link] two prime numbers p, q.
[Link] n=p×q.
(This n is part of both public and private keys).
[Link] φ(n)=(p−1)(q−1).
[Link] e such that 1< e < φ(n) and gcd(e,φ(n))=1.
(This is the public exponent).
[Link] d, the modular inverse of e modulo φ(n):
de=1 mod φ(n) => d≡e−1(modφ(n))
• Public Key = {e, n}
• Private Key = {d, n}
Cryptography & Network
Security: Overview
BCS703, 7th Sem
16-09-2025 New (B)
12:25PM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network
Security: Overview
BCS703, 7th Sem
17-09-2025 New (A)
12:25PM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network Security
Public key cryptography and RSA
RSA Encryption & Decryption
RSA Encryption

If plaintext = C=Me mod n

where C is the ciphertext.

RSA Decryption

To recover plaintext:

M=Cd mod n
Cryptography & Network Security
Public key cryptography and RSA
RSA Encryption & Decryption
[Link] primes: p=17,q=11.
[Link] n=17×11=187.
[Link] φ(n)=(16×10)=160.
[Link] e=7 (gcd(7, 160) = 1).
[Link] d such that 7d≡1(mod160).
1.d=23.
Public Key = {7, 187}
Private Key = {23, 187}
Encrypt message M=88:
C=887mod187=11
Decrypt ciphertext - C=11:
M=1123mod187=88
Cryptography & Network Security
Public key cryptography and RSA
Example Key Generation
Cryptography & Network Security
Public key cryptography and RSA
Cryptography & Network Security
Public key cryptography and RSA
Cryptography & Network
Security: Overview
BCS703, 7th Sem
17-09-2025 New (B)
10:25PM

Mr. Roopanand M K, Assistant Professor, Department of CS&E, PDIT, Hosapete

Cryptography & Network Security
Public key cryptography and RSA
Cryptography & Network Security
Public key cryptography and RSA

[Link] force: try all possible private keys — prevented by using large key sizes.
[Link] attacks: mainly about factoring n
[Link] attacks: exploit differences in computation time.
[Link] faults: induce errors in the device.
[Link] ciphertext attacks: exploit RSA properties.

The main defense: large key sizes (e.g., 1024, 2048, 4096 bits).
Cryptography & Network Security
Public key cryptography and RSA
Dif e–Hellman
• In RSA, we use two primes p and q (multiply them to get n).
• Dif e-Hellman is not an encryption/decryption algorithm but it’s a Key Exchange
• In Dif e–Hellman, we do not use both p and q. We only use one big prime number, usually written
as q.

• So: in DH, q is the main prime modulus.

• Once we choose the big prime q ==> choose a base ‘a’ that is a primitive root modulo q.
• Each party privately picks a random secret:
• Alice picks XA (private), ==> YA is Public
• Bob picks XB (private). ==> YB is Public
fi
fi
fi
Cryptography & Network Security
Public key cryptography and RSA
Dif e–Hellman
• Consider a Prime number ‘q’.
• Let q=7
• Select ‘a’ or (Alpha) such that ‘a’<q and ‘a’ is prime root of ‘q’.
• a1 mod q

• a2 mod q

• a3 mod q and so on…

• Here a would be 1,2,3,….(q-1) such that it should repeat all the numbers from 1 to
(q-1) ==> Called as ‘a’ is primitive root of ‘q’.
fi
Cryptography & Network Security
Public key cryptography and RSA
Dif e–Hellman
The protocol (math)
[Link] computes YA =aXA mod q and sends YA to Bob.
[Link] computes YB =aXB mod q and sends YB to Alice.

So both sides get the same K.

fi
Cryptography & Network Security
Public key cryptography and RSA
Dif e–Hellman
fi
Cryptography & Network Security
Public key cryptography and RSA
Why an eavesdropper can’t easily get K.
An eavesdropper (Eve) sees only:

To get K eavesdropper would need either XA or XB . That means solving for x in:
ax≡Y (modq) which is the discrete logarithm problem (DLP).
For large primes q, computing discrete logs is believed to be computationally infeasible
with current classical algorithms.
Cryptography & Network Security
Public key cryptography and RSA
Diagrammatic Representation