Module - 02

By,
Krishna Sowjanya K,
Assistant Professor,
Dept. of CSE
Introduction
• An important cryptographic function is the generation of random bit
streams.
• Random bits streams are used in a key generation and encryption.

Two different strategies for generating random bits:

• Pseudorandom Number Generators (PRNGs)
• True Random number Generators (TRNGs)
Introduction

• One strategy computes bits deterministically using an algorithm.

Called as pseudorandom number generators (PRNGs) or deterministic
random bit generators (DRBGs).

• Other strategy is to produce bits non-deterministically using some

physical source that produces some sort of random output called true
random number generators (TRNGs) or non-deterministic random bit
generators (NRBGs).
Pseudorandom Number Generators
Linear Congruential Generators
• Widely used technique for random number generation. Proposed by
Lehmer.
• Algorithm is parameterized with four numbers:
Linear Congruential Generators
• The sequence of random numbers {Xn} is obtained by the formula:

• If m, a, c and X0 are integers, then this technique will produce a

sequence of integers having a range:
Linear Congruential Generators
• Selection of values m, a, c is crucial in developing a good random
numbers.

• Ex 1: a=1, c=1, m=32 X0 =1. What is the sequence?

• Ex 2: a=7, c=0, m=32 X0 =1. What is the sequence?

Linear Congruential Generators
• Selection of values m, a, c is crucial in developing a good random
numbers.

• Ex 1: a=1, c=1, m=32 X0 =1. What is the sequence?

• 1, 2, 3, 4, 5, …

• Ex 2: a=7, c=0, m=32 X0 =1. What is the sequence?

• 7, 17, 23, 1, 7, 17, 23, 1 -> out of 32 only 4 is used. Sequence has a
period of 4.
Linear Congruential Generators
• Ex 3: a=5, c=0, m=32 X0 =1. What is the sequence?
• 5, 25, 29, 17, 21, 9, 13, 1, 5 which increases the period to 8.

• If m is very big, large range of random numbers can be produced.

• The common criteria of m is nearly equal to the maximum

non-negative integer i.e., 231
Linear Congruential Generators

Three tests can be done to evaluate a random number generator:

• T1: Function should be full period generating function. It should
generate all the numbers 0 to n-1.
• T2: The generated sequence should appear random.
• T3: The function should implement efficiently with 32-bit arithmetic.
Linear Congruential Generators

Best values:
• m should be prime
• C should be 0.
• Certain values of a, the period of the generating function is m-1. With
only one value missing i.e., 0.
Linear Congruential Generators
• The convenient prime value of m is:

• Thus, the generating function is:

Linear Congruential Generators
• Of all the 2 billion possible choices of a, only a handful of multipliers
pass all the three tests.
• One such value is:

• Selected to use in the IBM 360 family of computers.

Linear Congruential Generators
• The strength of the linear congruential algorithm is the multiplier and
modulus.

• Only X0 is random.

• Once that value is chosen, the remaining numbers in the sequence

follows deterministically.
Cryptanalysis
• If an opponent knows the parameters are known (e.g., a = 75, c = 0, m
= 231- 1), if single number is known, all subsequent numbers are
known.
• Even if the opponent knows only the algorithm or the knowledge of a
small part of sequence is sufficient to determine the parameters.
• Suppose that the opponent is able to determine values for X0, X1, X2,
and X3.
Cryptanalysis
To make the sequence less predictable, the following techniques can
be used:

Restarting the sequence every N Numbers

• Normally, the PRNG keeps generating from the last numbers.
• Instead of that, after every N numbers, the seed value can be reset
using clock time.
• Ex: If clock value = 35ms then new seed = 35
Cryptanalysis
To make the sequence less predictable, the following techniques can
be used:

Adding the clock value to each number

• Every time a random number is generated; clock time is added to it.
• Ex: Suppose PRNG gives Xn = 42; the clock value = 1003, then:
(42 + 1003) mod m
1045 mod m
This makes the sequence non-producible ; cant guess future numbers.
Blum Blum Shub Generator
• Popular approach for generating secure pseudorandom numbers.
• Named after its developers.

The procedure is:

• Choose two large prime numbers, p and q, that both have a
remainder of 3 when divided by 4.
Blum Blum Shub Generator
• Let n = p * q.
• Next, choose a random number s, such that s is relatively prime to n.
BBS generator procedure of bits Bi is: LSB of each iteration is taken.
Blum Blum Shub
Generator
Cryptanalysis
• The BBS is referred to a cryptographically secure pseudorandom bit
generator (CSPRBG).
• CSPRBG passes the next-bit test.
• Given first k-bits sequence, there is not a practical algorithm that
allows you to guess the next bit.
• It is also based on the difficulty of factoring n.
Principles
• The concept of public-key cryptography evolved to overcome two
major problems in symmetric encryption.
Key Distribution
• Sharing a key among the communication parties.
• Use of a key distribution centre.
Digital Signatures
• Providing the authentication of the communicating parties.
Asymmetric Encryption
• The concept of public-key cryptography evolved to overcome two
major problems in symmetric encryption.
• Public-key cryptography is asymmetric, involving the use of two
separate keys, in contrast to symmetric encryption, which uses only
one key.
• Confidentiality
• Key exchange
• Digital Signatures
Misconception
• Public-key encryption is more secure from cryptanalysis than the
symmetric encryption.
• Depends on key length and the computational work involved in
breaking the cipher.
• Public-key encryption is a general-purpose technique that has made
symmetric encryption obsolete.
• Due to the computational overhead of current public-key
encryption schemes, symmetric algorithms will not be abandoned.
Terminology
• Asymmetric Keys: Public Key, Private key for performing encryption,
decryption, 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
subscriber to a public key.
• Asymmetric (Public Key) Cryptographic Algorithm : Algorithm that
uses the two keys for encryption and decryption.
• Public Key Infrastructure (PKI): A set of policies, processes, used for
administering certificates and public-private key pairs.
Public Key Cryptosystems
• Asymmetric algorithms rely on one key for encryption and a different
but related key for decryption.

These algorithms have following characteristics:

• It is computationally infeasible to determine the decryption key given
only knowledge of the cryptographic algorithm and the encryption
key.
• Either of the two related keys can be used for encryption, with the
other used for decryption.
Public Key Cryptosystems

A public-key encryption scheme has six ingredients:

• Plaintext
• Encryption Algorithm
• Public and private keys
• Cipher text
• Decryption Algorithm
Public Key Cryptosystems
A public-key encryption scheme has six ingredients:
• Plaintext: The message or data that is fed into the algorithm as input.
• Encryption Algorithm: The algorithm that performs various
transformations on the plain text.
• Public and private keys: Pair of keys that have been selected for
encryption and decryption.
• Cipher text: The encrypted message produced as output. Depends on
plain text and key.
• Decryption Algorithm: Accepts the cipher text and key to produce
the plain text
Essential Steps
• Each user generates a pair of keys to be used for encryption and
decryption.
• Each user places one of the two keys in the public register, i.e., public
key.
• If Bob wishes to send a confidential message to Alice, Bob encrypts
the message using Alice’s public key.
• When Alice receives the message, she decrypts it using her private
key.
Essential Steps
• All the participants have access to public keys, and private keys are
generated locally by each participant.
• Private key is not distributed.
• As long as user’s private key remains protected and secret, incoming
communication is secure.
• Any time system can change its private key and publish the public key
to replace the old public key.
Essential Elements
• There is some source A producing the plaintext X.

• The message is intended for the destination B.

• The pair of keys:

Essential Elements
• Using the plaintext and key, the Source A forms ciphertext.

• The Cipher text is given as:

• The plain text is extracted as:

Essential Elements
• Possible to provide authentication and confidentiality can be
provided by the double use of Public-key scheme:
Applications for Public-Key Cryptosystems

The public-key cryptosystems are classified into three categories:

• Encryption/Decryption: Sender encrypts the message with recipient
public key and the recipient decrypts the message with private key.
• Digital Signature: The sender signs a message with private key.
• Key Exchange: Two sides cooperate to exchange a session, which is a
secret key for symmetric encryption.
Requirements for public-key Cryptography
• It is computationally easy for a party B to generate a key pair.

• It is computationally easy for sender to encrypt the message M to

generate cipher text
Requirements for public-key Cryptography
• It is computationally easy for a receiver B to decrypt the message
using private key.

• It is computationally infeasible for attacker knowing the public key

Pub to determine the private key PRb.
Requirements for public-key Cryptography
• It is computationally infeasible for attacker knowing pubic key PUb,
and the ciphertext C, to determine PRb to recover the original
message M.

• Two keys can be applied in either order.

One-Way Function
• Transformation that maps the input data into fixed output in one
direct step without iterative rounds.
• The reverse of it is computationally infeasible.

• With additional information, the inverse can be calculated in

polynomial time.
Trap-door One-Way Function
Public Key Cryptanalysis
• Public key encryption is vulnerable to brute force attack.
• Counter measure is to use large keys.
• Another form of attack is to find private key from public key.
• Probable message attack: If the message is 56-bit DES key encrypted
using RSA.
• The attacker could encrypt all possible 56-bit keys and encrypts using
the public key.
• Then they identify the message by comparing the cipher text.
The RSA Algorithm
• RSA algorithm was developed by Ron Rivest, Adi Shamir, and Len
Adleman at MIT in 1977.
• RSA (Rivest-Shamir-Adleman) is the most widely accepted and
implemented general purpose approach to public key encryption.
• RSA is a cipher in which the plaintext and cipher text are integers
between 0 to n-1 for some n.
• Typical size of n is 1024 bis or 309 decimal digits.
Exponentiation in Modular Arithmetic
• Both encryption and decryption in RSA involve raising an integer to an
integer , mod n.
• If the exponentiation is done over integers, and then reduced modulo
n, the intermediate values would be gargantuan.
• The intermediate results can be reduced using modular arithmetic:
Exponentiation in Modular Arithmetic
• To compute x16 the straight forward approach requires 15
multiplications:
Efficient Operation Using Public Key
• The choice of e is crucial.
• Most common choice is 65537 (216 + 1).
• Other popular choices are 3 and 17.
• Each of these choices has only two bits, so the number of
multiplications required for exponentiation is minimized.
Efficient Operation Using Private Key
• Small value of d gives less complexity but its vulnerable to the
attacks.
Key Generation
• Before the application of public-key cryptosystems, the participant
must generate pair of keys:
• Determining two prime numbers p and q.
• Selecting either e or d and calculating the other.
• Primes chosen must be sufficiently large.
• General method of selecting prime is to select a odd number and
check if its prime or not. If its not prime go for the next number.
(Miller – Rabin Algorithm)
• Euclid’s algorithm for calculating the GCD.
Security of RSA
Five possible approaches to attacking the RSA
• Brute force: This involves trying all possible private keys.
• Mathematical attacks: Factoring the product of two primes.
• Timing attacks: Depends on the running time of the decryption
algorithm.
• Hardware fault-based attack: This involves inducing hardware faults
in the processor that is generating digital signatures.
• Chosen ciphertext attacks: This type of attack exploits properties of
the RSA algorithm.
Factoring Problem
• In 1977, the three inventors of RSA dared Scientific American readers
to decode a cipher.
• In April of 1994, a group working over the Internet claimed the prize
after only eight months of work.
• This challenge used a public key size (length of n) of 129 decimal
digits, or around 428 bits.
• Quadratic Sieve, Generalized number field Sieve (GNFS), special
number field sieve (SNFS).
Timing Attacks
• Paul Kocher, a cryptographic consultant, demonstrated that a
snooper can determine a private key by keeping track of how long a
computer takes to decipher messages.
• Done based on modular multiplication.
• Iteration is slow with a 1 bit, then this bit is assumed to be 1.
Timing Attacks : Counter Measures

• Constant exponentiation time: Ensuring that all exponentiations take

same amount of time.
• Random Delay: Random delay is added to the exponentiation
algorithm to confuse the timing attack.
• Blinding: Multiply the cipher text by a random number before
performing exponentiation. Adds 2 to 10% of performance penalty.
Chosen Ciphertext Attack and Optimal
Asymmetric Encryption Padding
• Attack in which the opponent chooses a number of ciphertexts and is
given the corresponding plain text, decrypted with the target’s
private key.
• Counter measure is to modify the plain text using OAEP.
Diffie-Hellman Key Exchange
• Enables the users to securely exchange a key that can be used for
symmetric encryption.
• Limited to exchange of secret values.
Diffie-Hellman Key Exchange: Primitive Root
• An integer α is called a primitive root or primitive root modulo q
(where q is a prime number), if α can generate all numbers from 1 to
q-1 by taking powers of a modulo q.

• For example, 2 is a primitive root modulo 5

Diffie-Hellman Key Exchange
• User A selects a random integer

• Computes
Diffie-Hellman Key Exchange
• User B selects a random integer

• Computes
Diffie-Hellman Key Exchange
• Each side keep X value private and make Y value public to the other
side.
• Thus,
• XA -> Private Key XB -> Private Key
• YA -> Public Key YB -> Public Key
Diffie-Hellman Key Exchange
• User A computes the key as

• User B computes the key as

These two produce identical results

Diffie-Hellman Key Exchange
Elliptic Curve Cryptography (ECC)

• ECC makes use of Elliptic curves for performing encryption and

decryption.
• Variables and coefficients are all restricted to the elements of the
finite field.
• Offers equal security for smaller key size when compared to RSA
there by reducing the processing overhead.
Key Exchange
• Pick a large integer q.
• q should be either a prime p or an integer in the form of 2m
• Choose the coefficients a, b such that it satisfies the following
equation:

• This defines the elliptic group of points Eq(a, b).

• G be the point on the elliptic curve whose order is a large value of ‘n’
Key Exchange
Encryption and Decryption
• The plain text message to be encrypted is sent as a point Pm(x,y)
• Pm will be encrypted to produce a Cipher text.

• Decryption is done as follows: