CRYPTOGRAPHY & NETWORK
SECURITY(BCS703)
MODULE-2
MODULE-2
Pseudorandom number Generators: Linear Congruential
Generators, Blum Blum Shub Generator.
Public key cryptography and RSA: Principles of public key
cryptosystems-Public key cryptosystems, Applications for
public key cryptosystems, Requirements for public key
cryptography, Public key Cryptanalysis, The RSA algorithm:
Description of the Algorithm, Computational aspects, The
Security of RSA.
Diffie-Hellman key exchange: The Algorithm, Key exchange
Protocols, Man-in-the-middle Attack
Elliptic Curve Cryptography: Analog of Diffie-Hellman key
Exchange, Elliptic Curve Encryption/Decryption, Security of
Elliptic Curve Cryptography.
Pseudorandom number Generators(PRNG)
• An important cryptographic function is the generation of random bit
streams.
• Random bits streams are used in a wide variety of contexts, including
key generation and encryption.
• There are two fundamentally different strategies for generating
random bits or random numbers.
• One strategy, which until recently dominated in cryptographic
applications, computes bits deterministically using an algorithm.
This class of random bit generators is known as pseudorandom
number generators (PRNGs) or deterministic random bit generators
(DRBGs).
• The other strategy is to produce bits non-deterministically using
some physical source that produces some sort of random output.
This class of random bit generators is known as true random number
generators (TRNGs) or non-deterministic random bit generators
(NRBGs).
• Random numbers play an important role in the use
o f e n c r y p t i o n fo r va r i o u s n e t w o r k s e c u r i t y
applications.
• A number of network security algorithms and
protocols based on cryptography make use of
random binary numbers.
• Cryptographic applications typically make use of
a l g o r i t h m i c te c h n i q u e s fo r ra n d o m n u m b e r
generation. These algorithms are deterministic and
therefore produce sequences of numbers that are
not statistically random. However, if the algorithm is
good, the resulting sequences will pass many tests of
randomness. Such numbers are referred to as
pseudorandom numbers.
TRNG = real randomness (nature-driven, unpredictable).
PRNG = fake randomness (algorithm-driven, looks random but predictable).
Pseudorandom number Generators:
Linear Congruential Generators
• Linear Congruential Method is a class of Pseudo Random Number
Generator (PRNG) algorithms used for generating sequences of
random-like numbers in a specific range.
• This method can be defined as:
For a = 1, it will be the additive congruence method.
Steps of the method
Example
Blum Blum Shub Generator
• The Blum Blum Shub (BBS) generator is a
cryptographically secure pseudorandom number
generator (CSPRNG).
Unlike simple generators like the LCG or additive
congruence method, BBS is designed to be
unpredictable and secure because it is based on hard
number theory problems.
• It was developed by Lenore Blum, Manuel Blum, and
Michael Shub in 1986.
Steps:
Ex:
Public key cryptography
• The development of public-key cryptography is the
greatest and perhaps the only true revolution in the
entire history of cryptography.
• Earlier all cryptographic systems have been based on
the elementary tools of substitution and permutation.
• Public key algorithms are based on mathematical
functions rather than on substitution and permutation.
• More important, public-key cryptography is asymmetric,
involving the use of two separate keys, in contrast to
symmetric encryption, which uses only one key.
• The use of two keys has profound consequences in the
areas of confidentiality, key distribution, and
authentication.
Terminology Related to Asymmetric Encryption
• Asymmetric Keys :
Two related keys, a public key and a private key, that are used to perform complementary
operations, such as encryption and decryption or signature generation and signature
verification.
• Public Key Certificate
A digital document issued and digitally signed by the private key of a Certification Authority
that binds the name of a subscriber to a public key. The certificate indicates that the
subscriber identified in the certificate has sole control and access to the corresponding
private key.
• Public Key (Asymmetric) Cryptographic Algorithm
A cryptographic algorithm that uses two related keys, a public key and a private key. The
two keys have the property that deriving the private key from the public key is
computationally infeasible.
• Public Key Infrastructure (PKI)
A set of policies, processes, server platforms, software and workstations used for the
purpose of administering certificates and public-private key pairs, including the ability to
issue, maintain, and revoke public key certificates.
Principles of Public key Cryptosystems
• Asymmetric algorithms rely on one key for encryption and a different but
related key for decryption.
• Plaintext: This is the readable message or data that is fed into the algorithm as
input.
• Encryption algorithm: The encryption algorithm performs
varioustransformations on the plaintext.
• Public and private keys: This is a pair of keys that have been selected so that
one is used for encryption, the other is used for decryption. The exact
transformations performed by the algorithm depend on the public or private
key that is provided as input.
• Ciphertext: This is the scrambled message produced as output. It depends on
the plaintext and the key. For a given message, two different keys will produce
two different ciphertexts.
• Decryption algorithm: This algorithm accepts the ciphertext and the matching
key and produces the original plaintext.
The essential steps are the following
1. Each user generates a pair of keys to be used for the
encryption and decryption of messages.
2. Each user places one of the two keys in a public register or
other accessible file. This is the public key. The companion key is
kept private. Each user maintains a collection of public keys
obtained from others.
3. If Bob wishes to send a confidential message to Alice, Bob
encrypts the message using Alice's public key.
4. When Alice receives the message, she decrypts it using her
private key. No other recipient can decrypt the message because
only Alice knows Alice's private key.
Keys
• To discriminate between symmetric and
public-key encryption, 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.
Public-Key Cryptosystems: Secrecy and
Authentication
• Public-key schemes can be used for either secrecy or authentication,
or both (as shown in the figure).There is some source A that produces
a message in plaintext X. The message is intended for destination B.
• B generates a related pair of keys: a public key, PUb, and a private key,
PR b . PR b is known only to B, whereas PU b is publicly available and
therefore accessible by A.
• With the message X and the encryption key PUb as input, A forms the
ciphertext Y = E(PUb, X)
• The intended receiver, in possession of the matching private key, is
able to invert the transformation: X = D(PRb, Y).
• An adversary, observing Y and having access to PUb, but not having access to PRb or
X, must attempt to recover X and/or PRb. This provides confidentiality.
• Public-key encryption can also provide authentication:Y = E(PRa, X); X
= D(PUa, Y)
• To provide both the authentication function and confidentiality have a
double use of the public_x0002_key scheme :Z = E(PUb, E(PRa, X))
X = D(PUa, D(PRb, Z))
Applications for Public-Key Cryptosystems
We can classify the use of public-key cryptosystems into
three categories:
• Encryption/decryption: The sender encrypts a
message with the recipient's public key.
• Digital signature: The sender "signs" a message with
its private key. Signing is achieved by a cryptographic
algorithm applied to the message or to a small block of
data that is a function of the message.
• Key exchange: Two sides cooperate to exchange a
session key. Several different approaches are possible,
involving the private key(s) of one or both parties.
The RSA Algorithm
• RSA(Rivest-Shamir-Adleman) Algorithm is
an asymmetric or public-key cryptography algorithm
which means it works on two different keys: Public
Key and Private Key.
• The Public Key is used for encryption and is known to
everyone, while the Private Key is used
for decryption and must be kept secret by the
receiver.
• RSA Algorithm is named after Ron Rivest, Adi Shamir
and Leonard Adleman, who published the algorithm
in 1977.
• The RSA scheme is a block cipher in which the
plaintext and ciphertext are integers between 0 and
n-1 for some n. A typical size for n is 1024 bits, or 309
decimal digits. That is, n is less than 21024
RSA Algorithm/Description of
Algorithm
• RSA Algorithm is based on factorization of large
number and modular arithmetic for encrypting
and decrypting data.
It consists of three main stages:
• Key Generation: Creating Public and Private Keys
• Encryption: Sender encrypts the data using Public
Key to get cipher text.
• Decryption: Decrypting the cipher text using
Private Key to get the original data.
Example
A number is said to be coprime (or relatively prime) to another if their greatest
common divisor (GCD) is 1.
Perform encryption using RSA algorithm following P = 3, Q = 11, e = 3
and M =9
• n=P×Q=3×11=33
• φ(n)=(P−1)(Q−1)
=(3−1)(11−1)
=2×10=20
• Given:
• e=3 (must be coprime with 20 → yes, valid)
• Public key = (e,n)=(3,33)
• Message M=9.
• C = M^e mod n
= 9^3 mod 33
=9^3 = 729
= 729mod 33
=3
Ciphertext = 3
What is the cipher text if the plain text is 63 and the
p u b l i c k e y i s 1 3 ? U s e
the RSA algorithm.
• Assume p=17,q=11
then n=187
In a public key system using RSA ,Cipher text C=10 is
sent to user where n=[Link] is the plain text?
• n=221=13×17
p =13,Q=17
φ(n)=(p−1)(q−1)=12×16=192
Find Public Key Exponent � ,In many
exam/assignment problems, a common choice is �
=5 or � =3 (must be coprime with 192).
check gcd(5,192)=1
gcd(3,192)3(not valid)
e=5
We need � such that:
• d×e≡1(mod192)
• If � =5
Solve 5� ≡1(mod192)
• d=77
Example
Alice generates a public/private key pair; Bob encrypts using
Alice’s public key;and Alice decrypts using her private key.
For this example, the keys were generated as follows:
Computational Aspects
• We now turn to the issue of the complexity of the computation required
to useRSA. There are actually two issues to consider:
encryption/decryption and key generation.
• To perform the modular exponentiations, you can use the “Square and
MultiplyAlgorithm”, a fast, efficient algorithm for doing exponentiation.
• The idea is to repeatedly square the base, and multiply in the ones that
are neededto compute the result, as found by examining the binary
representation of the exponent.
⚫ Eg. 7 = 7 .7 = 3.7 = 10 mod 11
⚫ eg. 3
129 = 3128.31 = 5.3 = 4 mod 11
• The RSA algorithm requires that during key generation, the user selects a
value ofe that is relatively prime to ø (n). Thus, if a value if e is selected
first, and the primes p and q are generated, it may turn out that gcd(ø(n),
e) ≠ 1. In that case, the user must reject the p, q values and generate a
new p,q pair.
RSA Key Generation
• • Before the application of the public-key cryptosystem, each
participant must generatea pair of keys, which requires
finding primes and computing inverses.
• • Both the prime generation and the derivation of a suitable
pair of inverse exponentsmay involve trying a number of
alternatives.
• • Typically make random guesses for a possible p or q, and
check using a probabalistic primality test whether the guessed
number is indeed prime. If not, try again.
• • Note that the prime number theorem shows that the
average number of guesses needed is not too large.
• Then compute decryption exponent d using Euclid’s Inverse
Algorithm, which is quite efficient.
The Security of RSA
Four possible approaches to attacking the RSA
algorithm are as follows:
• Brute force: This involves trying all possible private
keys.
• Mathematical attacks: There are several approaches,
all equivalent in effort to factoring the product of two
primes.
• Timing attacks: These depend on the running time
of the decryption algorithm.
• Chosen ciphertext attacks: This type of attack
exploits properties of the RSAalgorithm.
• Brute force:
• The defense against the brute-force approach
is the same for RSA as for other cryptosystems,
namely, use a large key space. Thus, the larger
the number of bits in d, the better.
• However, because the calculations involved,
both in key generation and in
encryption/decryption, are complex, the
larger the size of the key, the slower the
systemwill run.
• Timing Attacks:
• Timing Attacks demonstrated that a snooper
can determine a private key bykeeping track of
how long a computer takes to decipher
messages.
• Timing Attacks are based on observing how
long it takes to compute the cryptographic
operations. Timing attacks are applicable not
just to RSA, but to other public-key cryptography
systems
Diffie–Hellman Key Exchange/Agreement
Algorithm
• The Diffie–Hellman algorithm (proposed by Whitfield Diffie &
Martin Hellman in 1976) is one of the earliest public key exchange
protocols.
• The Diffie-Hellman key exchange algorithm is a cryptographic
protocol that enables two parties to establish a shared secret key
over an insecure communication channel.
• This shared secret can then be used for symmetric encryption to
secure subsequent communications.
• The security of the algorithm relies on the computational difficulty
of the discrete logarithm problem.
Steps:
• Publicly Agreed Parameters:
Two parties, typically referred to as Alice and Bob, agree
upon a large prime number p and a generator g (a
primitive root modulo p). These values are public and do
not need to be kept secret.
• Private Key Generation:
Alice secretly chooses a random integer a as her private key.
Bob secretly chooses a random integer b as his private key.
Neither a nor b are ever revealed to the other party.
• Public Key Calculation and Exchange:
Alice calculates her public key A = ga mod p and
sends A to Bob.
Bob calculates his public key B = gb mod p and sends
B to Alice.
• Shared Secret Key Calculation:
Alice computes the shared secret key S = Ba mod p.
Bob computes the shared secret key S = Ab mod p.
Example
Let p = 23 and g = 5.
• Alice:
Chooses private key a = 6.
Calculates public key A = 56 mod 23 = 15,625 mod 23 = 8.
Sends A = 8 to Bob.
• Bob:
Chooses private key b = 15.
Calculates public key B = 515 mod 23 = 30,517,578,125 mod 23 = 19.
Sends B = 19 to Alice.
• Alice
Calculates shared secret S = Ba mod p = 196 mod 23 = 47,045,881 mod 23 = 2.
• Bob:
Calculates shared secret S = Ab mod p = 815 mod 23 = 35,184,372,088,832
mod 23 = 2.
• Both Alice and Bob successfully derive the shared secret key S = 2.
Both Secret Keys should be same...
Let q=353 and g=3. Xa=97, Xb=233. Use Diffie Hellman Key
e x c h a n g e
algorithm to find Ya, Yb and Secret key K
• 1. Calculate Public Keys (Ya and Yb)
User A (Alice):
Ya = gXa mod q
Ya = 397 mod 353
Ya = 40
User B (Bob):
Yb = gXb mod q
Yb = 3233 mod 353
Yb = 248
• 2. Exchange Public Keys Alice sends Ya (40) to Bob
and Bob sends Yb (248) to Alice.
• 3. Calculate the Shared Secret Key (K)
User A (Alice) calculates K:
K = (Yb)Xa mod q
K = 24897 mod 353
K = 160
User B (Bob) calculates K:
K = (Ya)Xb mod q
K = 40233 mod 353
K = 160
YA=51
YB=4
Shared Secret key=30
Xa=6,
Xb=8
Secret key= 3
Man-in-the-Middle Attack:
• At this point, Bob and Alice think that they
share a secret key, but instead Bob and Darth
share secret key K1 and Alice and Darth share
secret key K2 .All futurecommunication
between Bob and Alice is compromised in the
following way(Next Slide)
• The key exchange protocol is vulnerable to
such an attack because it does not
authenticate the participants. This
vulnerability can be overcome with the use of
digital signatures and public-key certificates.
Elliptic Curve Cryptography:
• We studied DES -widely used algorithm for
secret key cryptography.
• RSA- widely used algorithm for public key
cryptography.
• Here we study Elliptic Curve
Cryptography(ECC)- a stronger competitor to
RSA.
Take the coordinates (x,y) and simplify
using formula .points should satisfy the
equation .
FInd many points that satisfy the
condition that becomes [Link]
numbers can be used for x,y
Elliptic curve over Finite fields
• THis is the curve used in crytography
Adding two points inthe curve
Here P!=Q,
but need to add P+Q
Just project a line that passes through two points
and this line will interset the curve in another
[Link] find the reflection of the new point on the
x axis and point is called R. hereR=P+Q, R also lies on
the curve.
• Elliptic Curve Cryptography (ECC) is an approach to public-key
cryptography that uses the mathematical properties of elliptic curves
over finite fields to create secure encryption and digital signatures,
offering higher security with smaller key sizes compared to other
algorithms like RSA.
• ECC, is an asymmetric key cryptography that employs the algebraic
architecture of elliptic curves with finite fields.
• Neal Koblitz and Victor S. Miller independently proposed the use of
elliptic curves in encryption in 1985.
• Elliptic Curve Cryptography (ECC) is a public-key cryptography
approach that provides the same level of security as traditional
algorithms (like RSA or Diffie–Hellman) but with much smaller key
sizes/No. of bits . This makes ECC highly efficient and widely used in
modern systems such as SSL/TLS, cryptocurrencies (Bitcoin, Ethereum),
and secure messaging.
• Provides high level of security .
• by reducing number of keys(n)
ECC RSA/DSA
112 512
256 3072 etc
General formula (cubic equation)for EC is
y2=x3+ax+b
• Adding a Point P with P :
p+p =2p
2p+p=3p
Lets consider the point P(x,y) in the elliptic group Ep(a,b)
The rules for addition of P with P over the elliptic roup Ep(a,b) is
Let A=(2,4) and B=(8,5) be the two points on the EC
y2=x3+2x+4 over F13
Compute A+B , 2A
Compute A+B
Point Doubling Formula(2A)
Check curve validity
So both are valid points.
• COmpute P+Q
Compute 2P
Components of Elliptic Curve Cryptography
1. ECC keys:
• Private key: ECC cryptography's private key creation is as simple
as safely producing a random integer in a specific range, making
it highly quick. Any integer in the field represents a valid ECC
private key.
• Public keys: Public keys within ECC are EC points, which are pairs
of integer coordinates x, and y that lie on a curve. Because of its
unique features, EC points can be compressed to a single
coordinate + 1 bit (odd or even). As a result, the compressed
public key corresponds to a 256-bit ECC.
Elliptic Curve Diffie-Hellman (ECDH)
algorithm
• The Elliptic Curve Diffie-Hellman (ECDH) algorithm is a key
agreement protocol that allows two parties to establish a
shared secret key over an insecure channel using elliptic curve
cryptography (ECC).
The ECDH process involves the following steps:
1. Agreement on Public Parameters:
• Both parties (Alice and Bob) agree on a publicly known
elliptic curve and a base point (generator point, G) on that
curve.
2. Private Key Generation:
• Each party generates a private key, which is a random
integer. Alice chooses a, and Bob chooses b.
3. Public Key Calculation:
• Each party calculates their public key by multiplying their
private key by the base point G:
• Alice's public key: A = a * G
• Bob's public key: B = b * G
4. Public Key Exchange:
• Alice sends her public key A to Bob, and Bob sends his
public key B to Alice.
5. Shared Secret Calculation:
• Each party computes the shared secret using their own
private key and the other party's public key:
• Alice calculates s = a * B = a * (b * G)
• Bob calculates s = b * A = b * (a * G)
6. Shared Secret:
• Because multiplication of points on an elliptic curve is
associative and commutative, a * (b * G) is equal to b * (a
* G), resulting in the same shared secret s for both Alice
and Bob.
Analog of Diffie-Hellman key Exchange
Elliptic Curve Encryption/Decryption
• The first task in this system is to encode the plaintext
message m to be sent as an (x, y)
point Pm.
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.
• Analysis (Next slide) indicates that for equal
key lengths, the computational effort
re quired for ECC and RSA is comparable