Pseudorandom Number Generator (PRNG)

Summary

This presentation delves into the concept of pseudo random number generators (PRNGs), emphasizing their importance in generating sequences that appear random but are deterministic. It explains that true randomness can only be found in the physical world, whereas PRNGs produce predictable, repeatable sequences. The session covers how PRNGs are used in stream ciphers for secure communication, with Alice and Bob exemplifying the process of encryption and decryption using a shared key or seed. The lecture also touches on the theoretical aspects of stream ciphers and the Shannon notion of perfect secrecy, highlighting the practical challenges of achieving true randomness and the role of pseudo randomness in enhancing security.

Takeaways

• 🔑 The presentation discusses the concept of Pseudo Random Number Generators (PRNGs) and their importance in generating random sequences.
• 📚 By the end of the session, learners will understand the necessity of pseudo random sequences and how they are generated using PRNGs.
• 🌱 A keystream generator is introduced as a device that takes a seed or key to produce a sequence of bits, which are expected to be random in nature.
• 🎲 The script clarifies that true randomness can only be achieved through physical phenomena, such as natural fluctuations or noise, which are unpredictable and non-deterministic.
• 💻 In contrast, PRNGs generate numbers that are deterministic and predictable, hence they produce pseudo-randomness rather than true randomness.
• 🔄 Pseudo-randomness is characterized by repeating patterns after a certain period, which distinguishes it from true randomness.
• 🔑 The size of the key or seed used in the keystream generator affects the length and quality of the pseudo-random sequence generated.
• 🔐 The script uses the example of a stream cipher to illustrate how Alice and Bob can use a PRNG to securely exchange messages, with the key being the output from the keystream generator.
• 🔒 For secure communication, both sender and receiver must use the same seed or key to ensure they generate the same pseudo-random sequence.
• 🎯 The script emphasizes the theoretical aspects of stream ciphers and the conditions under which a sequence can be considered truly random, highlighting the impracticality of generating truly random sequences with machines.
• 📈 The concept of perfect secrecy, as per Shannon's notion, is tied to the use of one-time pads, which rely on truly random sequences for maximum security.

Q & A

What is the main focus of the presentation?

The presentation focuses on the concept of the Pseudo Random Number Generator (PRNG), explaining its necessity and how it generates pseudo random numbers.

What are the two main outcomes the learner is expected to achieve after the session?

The learner will understand the need for having a pseudo random sequence and will know how pseudo random numbers can be generated using a PRNG.

What is a keystream generator and what role does it play in generating pseudo random numbers?

A keystream generator is an algorithm that takes a seed or key as input and generates a sequence of bits that are expected to be random in nature, which are used as a keystream.

Why are the numbers generated by a keystream generator not truly random?

The numbers generated by a keystream generator are not truly random because they are predictable and deterministic, unlike the non-deterministic randomness found in the physical world.

How can truly random numbers be generated?

Truly random numbers can be generated by measuring random fluctuations or noise in the physical world, such as from a tree, forest, sky, or the universe.

What is the difference between truly random and pseudo random numbers?

Truly random numbers are unpredictable and non-deterministic, generated by natural phenomena, while pseudo random numbers are generated by algorithms and are deterministic and repeatable.

Why is the size of the key or seed important in PRNGs?

The size of the key or seed is important because it affects the length and quality of the pseudo random sequence generated. A larger key size results in a longer and more complex sequence.

What is a stream cipher and how does it relate to PRNGs?

A stream cipher is a method of encryption where a pseudo random binary sequence (generated by a PRNG) is combined with plaintext to produce ciphertext, ensuring security in communication.

Can you explain the process of encryption and decryption using a stream cipher?

In encryption, plaintext bits are XORed with pseudo random keystream bits to produce ciphertext. In decryption, the ciphertext is XORed with the same keystream to retrieve the original plaintext.

What is the significance of the one-time pad in the context of PRNGs?

The one-time pad is a theoretical encryption technique where a truly random key is used only once. It is considered to provide perfect secrecy, but in practice, PRNGs are used to approximate this level of security.

How can the randomness of a sequence generated by a PRNG be measured?

The randomness of a sequence can be measured by assessing its unpredictability, lack of pattern, and the equal probability of zeros and ones. This will be covered in more detail in a subsequent lecture.

What is the practical implication of using pseudo random numbers in security?

Pseudo random numbers are used to achieve security by creating a level of unpredictability that is close to true randomness. This helps protect against certain types of attacks and ensures the confidentiality of communications.

Outlines

00:00

🔐 Introduction to Pseudo Random Number Generators

This paragraph introduces the concept of Pseudo Random Number Generators (PRNGs) and sets the stage for the session's learning outcomes. It explains that by the end of the session, learners will understand the necessity of pseudo random sequences and learn how to generate pseudo random numbers using PRNGs. The paragraph begins with an example of a keystream generator, which takes a seed or key to produce a sequence of bits that appear random but are not truly so, as they are predictable and deterministic. The distinction between true randomness found in the physical world and pseudo randomness generated by machines is highlighted, emphasizing the need for pseudo randomness in achieving perfect secrecy in cryptographic applications.

05:00

🔑 Stream Ciphers and Pseudo Randomness in Cryptography

This paragraph delves into the practical application of pseudo randomness in stream ciphers, a cryptographic method where a plaintext is combined with a keystream to produce ciphertext. It describes the process where Alice, as the sender, uses a keystream generator with a given seed to create a ciphertext stream, which she then sends to Bob. Bob, upon receiving the ciphertext, uses the same keystream generator with the same seed to regenerate the keystream and decrypt the message back to plaintext. The paragraph underscores the importance of both parties having the same seed to ensure the security of the communication. It also touches on the theoretical aspects of stream ciphers, the concept of perfect secrecy as per Shannon's notion, and the difference between truly random and pseudo random sequences in achieving this level of security.

10:01

📊 Measuring Pseudo Randomness and Achieving Security

In this final paragraph, the focus shifts to the measurement of randomness and the role of pseudo random number generators in ensuring security. It raises the question of how to confirm the completeness of randomness in a sequence generated by a PRNG. The paragraph concludes the session by summarizing the importance of pseudo random sequences in achieving security and the mutual agreement on a common key or seed between the sender and receiver. It also reiterates the inevitability of randomness in security, as per Shannon's notion of perfect secrecy, and leaves the audience with the understanding that while true randomness may be impractical, a good pseudo random sequence can be close enough for effective security measures.

Keywords

💡Pseudo Random Number Generator (PRNG)

A Pseudo Random Number Generator (PRNG) is an algorithm that produces a sequence of numbers that approximate the properties of random numbers, but are actually deterministic. In the context of the video, PRNGs are used to generate sequences that, while not truly random, are sufficiently unpredictable for various applications, including security and cryptography. The script discusses the importance of PRNGs in creating pseudo random sequences for achieving security, emphasizing that while they are not truly random, they are close enough for practical purposes.

💡Randomness

Randomness refers to the lack of pattern or predictability in events. In the video, true randomness is contrasted with pseudo randomness. True randomness is found in the physical world, where events are non-deterministic and unpredictable, such as fluctuations in nature. Pseudo randomness, on the other hand, is generated by machines and algorithms and can be predictable. The script explains that while true randomness is desirable for perfect secrecy in cryptography, pseudo randomness is often used because it is practical and can be made to appear sufficiently random for most applications.

💡Keystream Generator

A keystream generator is a component of a stream cipher that generates a keystream, which is a sequence of bits used to encrypt data. In the video, the keystream generator is described as taking a seed or key as input and producing a sequence of bits that are expected to be random. However, since this randomness is generated by a deterministic machine, it is actually pseudo random. The script uses the keystream generator to illustrate how pseudo random sequences are created and used in encryption.

💡Seed

In the context of PRNGs and keystream generators, a seed is an initial value provided as input to the algorithm to produce a sequence of numbers. The script mentions that the seed is used to initiate the keystream generator, which then produces a sequence of bits that appear random. The importance of the seed is highlighted in ensuring that the same sequence can be regenerated by both the sender and receiver when using a stream cipher for secure communication.

💡Stream Cipher

A stream cipher is a method of encryption where plaintext bits are combined with a pseudo random keystream bit-by-bit to produce ciphertext. The video explains that stream ciphers use a keystream generator to create a sequence of bits that are XORed with plaintext bits to generate ciphertext. The security of the cipher depends on the unpredictability of the keystream, which is why PRNGs and the concept of pseudo randomness are crucial.

💡XOR Operation

The XOR (exclusive OR) operation is a binary operation used in the context of the video to combine bits from the plaintext and the keystream to produce ciphertext. The script describes how Alice uses the XOR operation to encrypt her message by combining plaintext bits with keystream bits generated by the keystream generator. Bob can then decrypt the message by applying the XOR operation again using the same keystream, demonstrating the importance of the shared seed or key for secure communication.

💡Perfect Secrecy

Perfect secrecy is a concept in cryptography where the ciphertext provides no information about the plaintext to an unauthorized party. The video references the notion of perfect secrecy by Shannon and explains that it can be achieved with a one-time pad, which uses a truly random keystream that is as long as the message itself. The script contrasts this with pseudo random sequences, which are used in practice because generating truly random sequences is impractical.

💡One-Time Pad

A one-time pad is a type of encryption technique that is theoretically unbreakable if used correctly. The video explains that a one-time pad uses a truly random key that is as long as the message and is used only once. The script mentions that when a truly random keystream is used in a stream cipher, it can achieve perfect secrecy, which is the ideal scenario in cryptography.

💡Ciphertext

Ciphertext is the result of encrypting plaintext using an encryption algorithm. In the video, ciphertext is generated by Alice through the XOR operation between her plaintext bits and the keystream bits produced by the keystream generator. The script illustrates that the ciphertext is then sent to Bob, who uses the same keystream generator with the same seed to decrypt the message back into plaintext.

💡Plaintext

Plaintext refers to the original message or data before it has been encrypted. The video script describes how Alice has a plaintext message that she wishes to send securely to Bob. She encrypts this plaintext using a keystream generated by a PRNG to produce ciphertext. The plaintext is then securely transmitted, and Bob is able to decrypt it back into its original form using the same keystream sequence.

Highlights

The presentation focuses on the concept and application of Pseudo Random Number Generators (PRNGs).

Learners will understand the necessity of pseudo random sequences and how they are generated by PRNGs.

A keystream generator is introduced as a device that produces a sequence of bits from a given seed or key.

The generated keystream is expected to be random but is not truly random due to its predictability.

Truly random numbers can only be obtained from the physical world's random fluctuations.

Pseudo randomness is defined as a sequence that repeats itself after a certain period.

The size of the key or seed influences the length and quality of the pseudo random sequence.

Stream ciphers use keystream generators to produce sequences expected to be random but are actually pseudo random.

Alice and Bob are used as examples to demonstrate the use of stream ciphers in secure communication.

The importance of both sender and receiver knowing the same seed for generating the same pseudo random sequence is emphasized.

The concept of perfect secrecy in cryptography is linked to the use of truly random sequences.

A one-time pad, which uses truly random sequences, is mentioned as an example of perfect secrecy.

The impracticality of generating truly random sequences from machines is discussed.

The expectation that a good stream cipher should closely approximate true randomness for better security is highlighted.

The theoretical aspects of stream ciphers, including the probability of zeros and ones being equal, are covered.

The session concludes with the understanding that pseudo random sequences are essential for security and achieving the notion of perfect secrecy.

Transcripts

hello everyone welcome back in this

presentation we are going to focus on

the pseudo random number generator P RNG

let's start the session with the

outcomes upon the completion of the

session the learner will be able to

outcome number one we will understand

the need for having Pudo random sequence

and outcome number two we will know how

pseudo random numbers can be generated

using pseudo random number generator

let's dive into the topic of the day the

pseudo random number generator before

understanding about Randomness let's

take a scenario let's say there is a

keystream generator where this keystream

generator is going to Generate random

numbers for example if we are giving an

input this input that we are giving to

the keystream generator is referred as a

seed or key let's assume this is a key

that is given as an input to to this

keystream generator now what the

keystream generator is going to do it is

going to generate a key stream now what

this key stream is going to contain this

key stream is going to generate a

sequence of bits obviously they are

going to be zeros and once now what has

actually happened is the keyst stream

generator has taken a key or a seed and

it has generated a sequence of bids

which are expected to be random in

nature I'll put my question this way is

it truly random I mean is the numbers

are completely random for this the

answer is no because only physical world

can have complete Randomness or truly

Randomness say if you take an entity in

the physical world it may be a tree or

forest or sky or universe or whatever

entity you want to take but take the

example from the physical world only in

physical world we can witness random

fluctuations everywhere and we can

generate truly random numbers by

measuring these random fluctuations

known as noise when we sample this noise

then we can get some numbers and these

numbers are truly random why because the

next value will be unpredictable because

this Randomness that is generated by the

physical world is

non-deterministic the next value or the

next move is unpredictable and that is

why we refer this Randomness that is

generated by the physical world is not

deterministic and it is truly random but

this key stream generator that we are

talking about in computers they are

actually generated by machines and the

numbers or random numbers that are

generated by this machines or the

keystream generator performed by the

machine they are predictable and they

are deterministic we need truly random

numbers in order to achieve perfect

secrecy isn't it now it's clear that

what we generate from the machines are

not truly random then then what kind of

Randomness it is it should be close

enough to the truly Randomness then we

call it as pseudo Randomness because

this Randomness will be repeating itself

there will be a period the length of the

randomness will be repeated for example

if we have 1,000 bits that are random

and if the next 1,000 bits are the same

as that of the previous 1,000 bits then

it means the randomness is repeated and

we cannot call this as truly random and

we need to call it as Pudo random

so what we understood from this is that

when we input a seed or a key then this

is accepted by the keyst stream

generator and it produces a key stream

which is expected to be random to be

precise they are pseudo random now how

far they are random it is actually

depending on the size of the key if you

give a bigger key size or a larger key

size then the randomness is also a

larger Randomness the larger the key

size or the seed size the randomness

will be larger let's see the the

theoretical aspects now basically we are

talking about stream ciphers basically

it's going to contain a binary sequence

which contain zeros and ones so we are

talking about stream Cipher in stream

Cipher we are going to use the key

stream generator and what this keyst

stream generator is going to do that's

what we have seen previously it's going

to take a key or a seed as an input and

it is going to generate a sequence of

output which is expected to be random

but is it truly random no we cannot say

that it will be a truly random sequence

because there will be repetion of the

sequence and that is why we cannot

guarantee that the key stream that is

generated by the machines are truly

random then what kind of Randomness it

is it is pseudo random we will

understand things with an example let's

bring in our popular characters let's

say we have Alice here and we have Bob

here now what Alice and Bob are going to

do is that they are going to use a

stream Cipher and they they are going to

exchange the messages obviously if it is

a stream Cipher then exort operation is

going to be carried out and they will

have the plain text which is exal with

the key and we get the cipher text now

what is the key here the key is the

output they get from the keyst stream

generator what we have discussed

recently let's say Alice is actually

wanted to send Cipher text to Bob

because she doesn't want to send the

plain text so what she is doing is that

she's taking the plain text sequence

let's say X1 X2 X3 X for all these are

bits this may be 0 1 0 1 1 0 1 1 so some

sequence of zeros and ones as the

playing text now what she's going to do

is she's going to generate the key

stream how she will be doing that she

will be taking a keyst stream generator

she will be giving the input seed to the

keystream generator and that keystream

generator will be giving the random

sequence now all the random sequence

bits are placed here and she's going to

perform an exort operation between X1

and and K1 the exor between X1 and K1

will be y1 this is a binary bit likewise

when she performs the exor operation for

all the BDS she will be getting a

sequence of bits which we call as the

cipher text stream now this Cipher text

stream is actually generated by Alys and

it is then given to Bob now how Bob will

get the plain text back now Bob is going

to adopt the same method he's also

bringing the same keystream generator

that was used by Alice and Bob needs to

give the same key or the seed that Alice

has fed into the machine in order to

generate this sequence this K1 K2 K3

isn't it so please be noted that Bob is

using the same Key Street generator he's

going to give the same input key or the

seed what Alice has given in order to

generate the same sequence because he

also needs the same sequence in order to

get the playing text back how Bob will

be getting the playing text he received

the cipher text stream isn't it so y1 Y2

Y3 up to YN he he has received all the

cipher text streams he is going to

generate the key streams with the help

of the key stream generator by inputting

the seed or the key the same key which

is used by both Alice and Bob and he

will be getting the playing text back

how a simple Exar operation again

because when you exert the cipher text

with the keyst stream it gives back the

playing text isn't it so this is

actually now done by Bob now Bob is able

to generate the playing text back even

though we are using the randomness as

the key this is Possible only when the

input key or the seed is known to both

Alice and Bob when the input or seed is

given to the key stream generator it

gives the same random sequence and this

random sequence cannot be truly random

it is pseudo random because this random

sequence will be repeatable after the

period ends so the next period will be

having the same set of sequence as the

previous period let's come to the

theoretical points what operation we did

previously we are taking making the

plain text bit XI this XI is exor with

the keystream bit Ki in order to

generate the cipher text bit Yi so what

happened in the encryption the xib bit

is exort with the Ki bit in order to

generate Yi and what is the decryption

part we will be getting XI by merely

exhorting this Yi with the keybard Ki

when we generate this key stream which

is non repeatable then only we will call

this Ki as a truly random bit when we

have such kind of truly random sequence

in our algorithm then this kind of

stream Cipher is referred to as a

onetime pad which is referred to as

perfect secrecy I hope you can recollect

the things which we have dealt in the

chapter one the shenon notion of perfect

secrecy and this one time pad that what

we are getting using this kind of

algorithm is referred as perfect secrecy

but remember in reality we need to

understand whether what we are getting

is truly random or pseudo random random

let's see the theoretical points now so

we have already seen about the stream

Cipher the key stream generator and the

truly random sequence when we will call

this as a truly random sequence

obviously we are going to have only two

bits in our sequence one is zero and

other one is one so the probability of

the number of zeros is equal to the

probability of number of ones so this

should be one of the important criterias

for being a truly random sequence

because the number of zeros and number

of ones are used equally

at the same time when we have such

concept then our algorithm is actually

following the shanon's notion of perfect

secrecy but do you think it is

practically possible to generate a truly

random sequence generating a truly

random sequence is Impractical we are

getting this Randomness from machines

where machines are predictable and

deterministic we want truly random

sequence but we are ending up with the

pseudo random sequence but what we

expect is this pseudo random sequence or

a good stream Cipher should be close to

the truly random sequence though we are

not able to get the exact truly random

sequence so when we get such kind of

Randomness then this is good enough for

achieving better security let's say we

have generated a random sequence through

a pseudo random generator now the

important question is how to measure

this Randomness how to confirm that

there is complete Randomness with the

sequence that we have obtained from the

pseudo random number generator so that's

what we are going to see in the next

lecture so anyway from this lecture we

understood that pseudo random number

generator generates a random sequence

and this is going to be used for

achieving security and this pseudo

random number generator is going to be

used by both sender and the receiver the

only thing is they need to mutually

agree upon the common key or the seed

only when they use the same seed they

will be getting the same random sequence

and also we confirmed that Randomness is

inevitable as far as security is

concerned in order to achieve the

shanon's notion of perfect secrecy no

other goal we need Randomness but the

thing is whether it is truly random or

pseudo random and that's it guys I hope

now you understood the need for having

pseudo random sequence and we also have

come to know how pseudo random numbers

can be generated using pseudo random

number generator I hope the session is

informative and thank you for

[Music]

[Applause]

watching

[Music]