DATA SECURITY AND

PRIVACY
BAD703
8.2 Pseudorandom number Generators
(PRNG)
Introduction
Importance of random numbers in cryptography (keys, nonces, session keys)
Difference between TRNG & PRNG
Two types:
1. True Random Number Generators (TRNGs) → based on physical
processes (coin toss, measuring noise, radiation etc).
2. Pseudorandom Number Generators (PRNGs) → deterministic
algorithms/ formula
Which one is faster for computer use?
Deterministic algorithm that generates a sequence of numbers that appear random
(deterministic but “random-looking”)
Based on an initial seed.
Important property to consider : unpredictability .
Repeatability: same seed → same sequence.
Linear Congruential Generators (LCG)
Example 1:

a=5,c=0,m=32, X0=1 → show cycle of 8 numbers

Sequence: 1, 5, 25, 29, … (cycle length 8 starting with X0 ).
Next 4 values ???
Complete Cycle ?
Corresponding Bit sequence?

.
•Example 2: a=c=1,m=10,X0=1.

What is Cycle problem (short periods) ?

a=2,c=0,m=10, X0=1
Sequence: 1, 2, 4, 8, 6, 2, 4, 8, 6 …
The numbers repeat after only 4 steps (cycle length = 4), even though
𝑚 = 10.
This makes the PRNG predictable and less random, which is bad for
cryptography.
Issues with LCG
•Period length: maximum is m,
•Period depends on good choice of parameters.
•Bad choices → short cycles.
•Easy to predict by attacker if some outputs are known
•they can solve equations and recover a,c,m.
•Not secure for cryptography
•Applications: useful in simulations, gaming (because of fastness)
•Adv: Simple, Fast, widely used historically
Blum Blum Shub (BBS) Generator
(secure PRNG based on Number theory)

Both have a
remainder of 3 when
divided by 4
(p mod 4) =
(q mod 4) = 3.
neither p nor q is a factor of s.
The BBS is referred to as a cryptographically secure pseudorandom bit generator (CSPRBG).
Simple Example:
•Choose p=7,q=11,n=77
•Seed s=5
•First 4 iterations: X1, X2, …..
•Output bits : 0,1, ….

Strength:
•Based on hardness of factoring n
•Strong Security: Passes “next-bit test”: impossible to predict next bit
better than random guess.
Security of BBS is based on the difficulty of factoring n. That is, given n, we need to
determine its two prime factors p and q.
Drawback: Very Slow compared to LCG (integer factorization hardness,
not good for simulations)
Applications : Good for providing cryptographic security
Comparison LCG vs BBS:
•LCG → fast, not secure.
•BBS → secure, slow.

•Importance of choosing right PRNG for cryptography.

•Advanced PRNGs (covered in later sections): block cipher–based, hash-
based.
Public Key Cryptography and RSA
Misconception 1: People think public-key encryption is always more secure than
symmetric encryption.
Not true. Security depends mainly on key length and the effort needed to break it,
not on the type.
Misconception 2: People think public-key has replaced symmetric encryption.
Not true. Public-key is slower and heavier to use, so symmetric encryption is still very
important.
Reality: Public-key is mostly used for key exchange and digital signatures, while
symmetric encryption is used for fast data protection.
Misconception 3: Many people think key distribution is easy with public-key
encryption.
But actually, we still need proper protocols and central agents, and it’s not simpler
or faster than symmetric key distribution.
•Asymmetric Keys – Two keys: one public (shared) and one private
(secret). They work together for encryption/decryption or
signing/verification.
•Public Key Certificate – A digital ID card issued by a trusted
authority(digitally signed by the private key of a Certification Authority), linking a person’s
name to their public key.
•Public Key (Asymmetric) Algorithm – Uses the two keys; one can’t
figure out the private key even if one knows the public key.(property : deriving
the private key from the public key is computationally infeasible.)
•Public Key Infrastructure (PKI) – The whole system (policies +
processes + servers+ software + authorities) that manages keys and
certificates (issue, verify, revoke).
9.1 PRINCIPLES OF PUBLIC-KEY CRYPTOSYSTEMS
[Link] with Symmetric Encryption(single key):
1. Secure Key distribution was hard → you needed a pre-shared key or a Key
Distribution Center (KDC), which could be hacked or misused. (No security-
Confidentiality -secrecy if shared)
2. Digital signatures were missing (No Authenticity) → no way to prove who
really sent a digital message, unlike signing paper documents. (Receiver could
pretend to be the sender with the key shared)
[Link] Study / Breakthrough:
1. In 1976, Whitfield Diffie and Martin Hellman (Stanford University) invented
public-key cryptography.
2. Their method solved both problems (secure key exchange + digital
signatures) and was completely new, unlike anything in 4000 years of
cryptography history.
Note: Public-key cryptography was born to solve key distribution and digital
signature problems.
Public-Key Cryptosystems
Asymmetric Algorithm Characteristic
❑Uses two different but related keys: one for encryption and the
other for decryption.
❑It’s impossible to guess the decryption key if you only know the
encryption key & encryption algorithm.
Special Case: RSA Property
➢In RSA, either key can be used to encrypt, and the other key will
decrypt.
➢This makes it useful for both secrecy (confidentiality) and
signatures (authenticity).
6 Ingredients of Public-Key Encryption
Plaintext: The original readable message fed into the algorithm
as input.
Encryption Algorithm: A method that scrambles plaintext using
a key by performing various transformations
Public & Private Keys: A matched pair – one locks, the other
unlocks.
Ciphertext: The scrambled message produced as output. (For a
given message, two different keys will produce two different ciphertexts.)
Decryption Algorithm: Turns ciphertext back into the original
plaintext using the matching key.
Steps:
1) Key Generation
Each user creates two keys: one public, one private.
2) Public & Private Keys
The public key is shared openly (like putting it in a directory).
The private key is kept secret by the owner.
3) Sending a Secure Message
Example: Bob wants to send a message to Alice → he encrypts it with Alice’s public key.
4) Receiving a Secure Message
Alice gets the message and decrypts it with her private key.
Only Alice can read it, because only she has her corresponding private key.
Security Advantage
No need to share private keys → they never travel across the network.
If needed, users can change private keys anytime and publish new public keys.
Note : Public-key cryptography works because everyone shares public keys, but only
private keys can unlock the secrets.
we refer to the key used in symmetric encryption as a secret key.
The two keys used for asymmetric encryption are referred to as the
public key and the private key.
Conventional (Symmetric) Public-Key (Asymmetric) Encryption
Encryption
To Work:
To Work:
Uses a pair of keys: one for
Same key used for both encryption encryption, the other for decryption.
and decryption.
Sender and receiver each hold
Sender & receiver must share the different but related keys.
same secret key.
For Security:
For Security:
At least one key (private key) must
The key must stay secret. stay secret.
Even if someone knows the Knowing one key + algorithm +
algorithm and sees ciphertext, ciphertext should not allow anyone to
they shouldn’t be able to guess the guess the other key.
key.
Confidentiality → achieved when sender uses receiver’s public key, only receiver can open (only the
private key holder can read messages)
How confidentiality is achieved here Fig.9.2 (Public-Key Encryption)
Source A (Sender) has a message X.
Sender encrypts it using Destination B’s public key (PUb).
◦ Encrypted message becomes Y = E(PUb, X).
◦ Since PUb is public, anyone can encrypt, but only B can decrypt.

Destination B (Receiver) uses private key (PRb) to decrypt.

◦ Gets back the original message: X = D(PRb, Y).
Confidentiality is ensured because only the person with PRb (private key) can read the message.
◦ Authentication is not ensured?
◦ Why?
◦ B can not guaranteely say that the message has come from A only because encryption has been done with B’s public key which
can be used by any other person also since everybody can do encryption with others public key. => so no authentication & hence
no digital signature
Why the Cryptanalyst shows 2 values?
The attacker (cryptanalyst) can see the ciphertext Y and knows the public key PUb.
Their possible goals are:
❖Recover X (the plaintext) → They try to guess or calculate the original message (X̂ = estimated
message).
❖Recover PRb (the private key) → If they succeed, they can unlock all future messages (PR̂b =
estimated private key).
So, the figure shows two possible attack outcomes:
Either break just this message (find X̂),
Or break the system entirely (find PR̂b).
•Authentication → achieved when sender uses their own private key, so everyone knows the message truly came from them.
•In authentication, the attacker only cares about the private key of the sender, not the message
How Authentication is Achieved (Private Key Encryption)
Source A (Sender) has a message X.
Instead of using a public key, Source A encrypts the message with its private key (PRa).
◦ Encrypted message becomes: Y = E(PRa, X).

Destination B (Receiver) uses Source A’s public key (PUa) to decrypt.

◦ If decryption works and gives back the original message, then the receiver is sure the message really
came from Source A.
This works because only A has PRa. So if something can be decrypted with PUa, it must have been
created by A.
This is the basis of authentication and digital signatures.
Why the Cryptanalyst Shows Only One Value
In the previous confidentiality diagram, the attacker could try to guess either:
◦ The message (X), or
◦ The private key (PRb).

But here, the attacker just like anybody else can decrypt the message to get back X with the
publicly distributed key of A (PUa).
Their only option is to try to steal or guess the private key (PRa), because that’s the secret part
that proves authenticity.
So the cryptanalyst block shows only PR̂a (estimated private key).
Alice (Source A) wants to send a secret and authentic message to Bob (Destination B).
Step 1: Message creation
•Alice has a message X she wants to send.

Step 2: Alice signs (first Authentication)

•Alice first encrypts X with her private key (PRa).
•This produces Y.
•Why?
•This proves the message came from Alice, because only Alice’s private key could have created
Y.

Step 3: Alice locks (next Secrecy)

Now, to make sure only Bob can read it, Alice encrypts (locks) Y again with Bob’s public key
(PUb).
This gives Z.
Why?
Now only Bob (with his private key PRb) can unlock it.
Step 4: Bob unlocks (Secrecy)
•Bob receives Z.
•First, he uses his private key (PRb) to decrypt it.
•This gives him back Y.
•Why?
•Because Bob’s private key is the only one that can unlock what was locked with his public key.

Step 5: Bob verifies (Authentication)

•Now Bob has Y, which was created using Alice’s private key.
•He uses Alice’s public key (PUa) to decrypt Y.
•This gives him back the original message X.
•Why?
•If the decryption works, Bob is sure the message came from Alice (authentic) and wasn’t changed.
•Alice signs with her private key (authenticity).
•Alice locks with Bob’s public key (secrecy).
•Bob unlocks with his private key, then verifies with Alice’s public
key.

•Secrecy → Only Bob could read the message (since it was locked with PUb).
•Authentication → Bob is sure it came from Alice (since it matches with PUa).
•That’s why two keys (public and private) are used by both Alice and Bob.
Applications for Public-Key Cryptosystems
In public-key cryptosystems, we always have two keys:
❑Public key (everyone can know it).
❑Private key (kept secret).
Depending on the purpose, the sender may use:
❑Receiver’s public key
❑Sender’s private key
❑Or both
Classify the use of public-key cryptosystems into three categories

Encryption/Decryption (Secrecy)
◦ The sender locks the message with the receiver’s public key.
◦ Only the receiver can unlock it with their private key.
Ensures confidentiality (only the receiver can read it).
Digital Signature (Authenticity)
◦ The sender signs a message with their private key.
◦ Anyone can verify it using the sender’s public key.
Ensures authenticity (the message really came from the sender).
Key Exchange (Sharing a temporary key)
◦ Both sides work together to create a session key (a temporary secret key).
◦ This session key is then used for faster symmetric encryption, generated for use for a particular transaction
(or session) and valid for a short period of time.
Ensures secure setup of a shared key for communication.
Requirements for Public-Key Cryptography
•1) Should be Easy to make keys
•It should be simple for a user (say B) to create a key pair:
•A public key (PUb) → shared with everyone.
•A private key (PRb) → kept secret.
2) Should be Easy to encrypt with public key
•If someone (say A) knows the public key (PUb) and the message (M), it should be easy to turn
the message into ciphertext (C).
Formula: C = E(PUb, M)
3) Should be Easy to decrypt with the private key (for the right person)
•The receiver (B), who has the private key (PRb), should be able to easily turn the ciphertext
back into the original message.

•Formula: M = D(PRb, C)
4) Should be Hard for attackers to compute private key from public key
•If an attacker only knows the public key (PUb), it should be impossible (or extremely hard) for
them to figure out the private key (PRb).
5. Hard for attacker to get message:
Even if the attacker knows the public key and the ciphertext, they should not be able to figure out
the original message.
6. Keys can work in either order:
Encrypt with private key, decrypt with public key.
Or encrypt with public key, decrypt with private key.
Main Idea → One-Way Function (Trapdoor Function)
❑Easy to do in one direction (e.g., multiply two big numbers).
❑Very hard to reverse (e.g., factor those big numbers back).
Example:
❑Going forward: Y = f(X) → easy.
❑Going backward: X = f⁻¹(Y) → almost impossible without key. (only the person with the right
“trapdoor” (private key) can reverse it.)
❑Going backward with the key is easy.
Why important?
Cryptography needs problems that are easy for the sender/receiver but impossible for
attackers.
Public-key cryptography works only because such trap-door one-way functions exist — they
allow encryption to be public, but decryption only possible with the private key.
That’s why only a few algorithms (RSA, elliptic curve, Diffie–Hellman, DSS) are used.
Public-Key Cryptanalysis
Brute-force attack
◦ Just like symmetric encryption, hackers can try all possible keys.
◦ Solution: Use very large keys.
◦ Problem: Large keys make encryption/decryption slower.
That’s why public-key is mostly used for key exchange and signatures, not for encrypting big data.

Math-based attack (Public key math)

◦ If someone finds a way to calculate the private key from the public key, the system is broken.
◦ No proof yet that this is impossible (even RSA could be broken one day).

Probable-message attack (special weakness)

◦ If the message is predictable (like just a 56-bit DES key), the attacker can guess all possibilities.
◦ They encrypt all guesses with the public key and match with the real ciphertext.
◦ Solution: Add some random bits to the message to make it unpredictable.
9.2 THE RSA ALGORITHM
Birth of RSA
In 1976, Diffie and Hellman introduced the idea of public-key cryptography and
asked researchers to find real algorithms for it.
Many tried, but most early ideas were broken.
In 1977, three MIT researchers — Rivest, Shamir, and Adleman — created the
RSA algorithm, published in 1978.
Why RSA is important
RSA became the most popular and widely used public-key encryption method.
It’s considered strong and reliable even today.
How RSA works (very basic idea)
In RSA, both plaintext (original message) and ciphertext (encrypted message)
are treated as numbers.
These numbers lie between 0 and n–1, where n is a very large number
(commonly 1024 bits long, which is about 309 decimal digits!).
Security comes from the difficulty of working with such huge numbers.
Description of the Algorithm
Imagine a Secret Lock-and-Key Game
Alice and Bob want to talk secretly.
They use a special kind of lock (RSA) where:
◦ One key locks (encrypts) the message.
◦ A different key unlocks (decrypts) it.
The Math Ingredients
op and q: Alice picks two secret prime numbers (like her two secret spices).
on = p × q: She multiplies them → this becomes part of the lock everyone can
see.
oφ(n) = (p – 1)(q – 1): A hidden calculation using p and q (like a secret recipe).
Making the Keys
Public key (PU = {e, n}): This is like a public lock. Everyone knows it.
◦ e is a number that works well with φ(n) (not sharing any factors with it).

Private key (PR = {d, n}): This is like a private unlock key. Only Alice knows it.
◦ d is chosen so that multiplying d × e has a special property:

𝑑 × 𝑒 mod 𝜙 𝑛 = 1
(Think of it like: turning e clockwise and then d counter-clockwise brings the lock back to its
original state.)
Why It’s Safe
Everyone knows n and e (public).
But only Alice knows d.
Even if someone sees n and e, it’s super hard to figure out d unless they know
the secret primes p and q.

In short:
Public key = Lock (anyone can use to lock a message).
Private key = Key (only the owner can open it).
RSA works because math ensures that locking with e and unlocking with d
always gets back the original message.
1. Select two prime numbers, p = 17 and q = 11.
2. Calculate n = pq = 17 * 11 = 187.
3. Calculate f(n) = (p - 1)(q - 1) = 16 * 10 = 160.
4. Select e such that e is relatively prime to f(n) = 160 and less than f(n); we choose e = 7.
5. Determine d such that de ≡1 (mod 160) and d < 160. The correct value is d = 23, because 23 * 7 =
161 = (1 * 160) + 1; d can be calculated using the extended Euclid’s algorithm (Chapter 2).
The resulting keys are public key PU = {7, 187} and private key PR = {23, 187}.
The example shows the use of these keys for a plaintext input of M = 88.
For encryption, we need to calculate C = 887 mod 187.
compute exponentiation via repeated squaring
p = 61, q = 53 n = 3233 φ = 3120
e = 17, d = 2753
M = 65 C = 65^{17} mod 3233 = 2790
2790^{2753} mod 3233 = 65
Diffie–Hellman (DH) key exchange
❑DH allows two parties to agree on a shared secret over an insecure
channel without sending the secret itself.
❑It relies on the difficulty of the discrete logarithm problem (DLP) in a
chosen group (commonly the multiplicative group modulo a prime).
❑Not an encryption algorithm
❑Used for exchange secret/symmetric key (actually generating
symmetric key at both sides using public key & private keys)
❑This is possible by making use of asymmetric encryption (public key &
private key)
1. Assume prime no. q
2. Select alpha, such that alpha must be primitive root of q & alpha must be less than q
3. Assume Xa (private key of user a ) , Xa <q
4. Calculate Ya (public key of user a)

5. Assume Xb (private key of user b) , Xb <q

6. Calculate Yb (public key of user b)

7.
Man in the middle attack
10.4 Elliptic Curve Cryptography
RSA: for secure encryption & Diffie-Hellman: for secure key
exchange
Elliptic curves (ECC):
❑provides strong security similar to RSA/Diffie-Hellman but with
smaller keys.
❑It is Asymmetric / public key cryptosystem.
❑Efficient in terms of speed, power, and memory.
❑Widely used in modern cryptosystems.
❑Used in Secure web communication using TLS/SSL (HTTPS),
Bitcoin, Blockchain, Mobile security (Apple, Android), IoT devices
 ❑It makes use of Elliptic curves
❑Elliptic curves has some property, curves are defined by some mathematical functions (cubic functions)
Ex: Y2= x3+ax+b (degree 3 Equation)
ECC vs RSA (High-level idea)
❑RSA: Security relies on factoring large primes.
❑ECC: Security relies on elliptic curve discrete logarithm problem
(ECDLP).
❑Both have a “hard problem” foundation.
❑We replace modular exponentiation with elliptic curve point
multiplication.
Hard Problem in ECC :
Equation: Q = kP where Q, P ∈ Base point 𝑃 on the curve,
Eₚ(a,b) and another point 𝑄on the curve
Easy: compute Q given k and P. (where 𝑘 is an integer, and 𝒌𝑷 means
adding 𝑃 to itself 𝑘 times),
Hard: find k given Q and P. (one the problem is to determine the
way function) integer 𝑘, given only 𝑃 and 𝑄.
This is the Elliptic Curve Discrete
Logarithm Problem (ECDLP).
ECDLP is the problem of finding 𝒌 given points 𝑷 and 𝑸 = 𝒌𝑷 on an elliptic curve; it’s computationally
infeasible for large 𝒌.
➢Advantages of ECC ➢Limitations
➢Smaller keys → faster ➢Math is more complex.
computation.
➢Requires careful parameter
➢Less memory → ideal for choice.
constrained devices. ➢Vulnerable if curves are weak
➢Strong security → harder (e.g., poor random number
discrete log problem. generation).
Why Brute Force Fails in Practice ?
Real ECC parameters:
◦ k is very large (e.g., 2¹⁶⁰).

Brute force would take longer than the age of the universe.
Security is equivalent to RSA 1024-bit with ECC 160-bit key.
Analog of Diffie-Hellman key Exchange
Security of Elliptic Curve Cryptography
The security of ECC depends on how difficult it is to determine k
given kP and P.
This is referred to as the elliptic curve logarithm problem.
The fastest known technique for taking the elliptic curve logarithm is
known as the Pollard rho method (that solves the Elliptic Curve
Discrete Logarithm Problem).
Note : Also Refer the notes given during few of
the topic discussions & Text book for more
description.

Refer problems solved during the class.