How prime numbers protect your privacy #SoME2

Summary

This script delves into the importance of encryption in securing online communication, illustrating the concept with the story of Alice and Bob. It explains the shift from easily intercepted plain text to the use of asymmetric cryptography, focusing on the RSA cryptosystem. The explanation covers the generation of public and private keys using prime numbers, the encryption and decryption process, and the mathematical underpinnings of RSA, including modular arithmetic and Fermat's Little Theorem. The script concludes by highlighting the broader impact of asymmetric cryptography on internet security, particularly in the HTTPS standard.

Takeaways

• 🌐 The importance of encryption for secure online communication is highlighted, emphasizing that without it, messages could be easily intercepted by malicious entities.
• 🔏 Symmetric encryption is introduced as a method where the same key is used for both encryption and decryption, but it has the drawback of requiring a secure method to share the key between parties.
• 🔑 Asymmetric encryption, specifically the RSA cryptosystem, is explained as a solution to the key exchange problem, using a public key for encryption and a private key for decryption.
• 🔒 The concept of public and private keys is crucial in RSA; public keys can be freely shared and are used to encrypt messages, while private keys are kept secret and are used to decrypt them.
• 🔍 The security of RSA lies in the difficulty of deriving the private key from the public key, which is generated from large prime numbers that are hard to factorize.
• 📜 The process of generating RSA keys involves selecting large prime numbers, calculating their product (n), and using a function (λ) to help compute the private key (d).
• 🔢 Prime numbers are essential in RSA because the product of two primes is unique and difficult to reverse-engineer back into the original primes, providing security for the cryptosystem.
• 🔄 The RSA algorithm relies on modular arithmetic and properties such as Fermat's Little Theorem to ensure the encryption and decryption process works correctly.
• 📊 The script uses a clock analogy to help explain the concept of modular arithmetic, making the abstract mathematical process more relatable.
• 🛡 Despite the explanation of how RSA works, the actual generation of keys and encryption/decryption processes are automated by software, not done manually by users.
• 🌐 The RSA algorithm, while being phased out by more advanced systems, is foundational to the HTTPS standard that secures internet communication by preventing eavesdropping on data exchanged with websites.

Q & A

Why is encryption important for internet communication?

Encryption is crucial for ensuring that messages sent over the internet are only accessible to the intended recipient, preventing unauthorized interception and reading by malicious entities.

What is the main difference between symmetric and asymmetric encryption?

Symmetric encryption uses the same key for both encryption and decryption, whereas asymmetric encryption uses a public key for encryption and a private key for decryption, with the two keys being mathematically related but not directly derivable from one another.

Why can't an attacker use intercepted public keys to decrypt messages?

Public keys are designed to be used for encrypting messages, but they cannot decrypt them. Only the corresponding private key, which is kept secret, can decrypt messages encrypted with the public key.

What is the RSA cryptosystem and how does it relate to asymmetric encryption?

The RSA cryptosystem is a widely used example of asymmetric encryption, named after its inventors Rivest, Shamir, and Adleman. It relies on the mathematical properties of large prime numbers to create a pair of keys: a public key for encryption and a private key for decryption.

How does the concept of congruence work in the context of RSA encryption?

In RSA, congruence is used to describe the relationship between numbers under a certain modulus (n). It allows for the encryption and decryption processes, where raising a number to a certain power and then taking it modulo n results in the original number.

What is the significance of prime numbers in RSA encryption?

Prime numbers are the building blocks of the RSA algorithm. The security of RSA relies on the difficulty of factoring the product of two large prime numbers into its original primes, which is essential for generating the public and private keys.

How are the values of n, e, and d generated in the RSA key generation process?

n is generated by multiplying two large prime numbers p and q. e is chosen as a number coprime with the Carmichael's totient function of n (λ(n)). d is computed using the Extended Euclidean algorithm to satisfy the equation (d * e) ≡ 1 (mod λ(n)).

What is Fermat's Little Theorem and how does it apply to RSA encryption?

Fermat's Little Theorem states that if 'a' is an integer and 'p' is a prime number not dividing 'a', then a^(p-1) ≡ 1 (mod p). This theorem is used in the RSA algorithm to prove that the encryption and decryption processes are inverses of each other modulo p and q.

How does the RSA algorithm ensure the security of private conversations over the internet?

RSA ensures security by allowing users to generate a pair of keys: a public key for encryption and a private key for decryption. Since the private key cannot be derived from the public key, even if an attacker intercepts the public key, they cannot decrypt the messages.

What is the role of asymmetric cryptography in securing internet communications, such as HTTPS?

Asymmetric cryptography, as implemented by RSA and other similar algorithms, secures internet communications by enabling secure key exchange and data encryption. In the case of HTTPS, it ensures that the data exchanged between a user and a website is encrypted and cannot be intercepted or tampered with by attackers.

Outlines

00:00

🔒 The Importance of Encryption in Digital Communication

This paragraph introduces the concept of encryption as a means to ensure the confidentiality of digital communication. It explains the potential vulnerability of messages sent over the internet, which can be intercepted by malicious entities if not encrypted. The narrative uses the hypothetical scenario of Alice and Bob to illustrate the problem of secure communication over an insecure network. It also contrasts the simplicity of symmetric encryption, where the same key is used for both encryption and decryption, with the complexities of asymmetric encryption, which uses a public key for encryption and a private key for decryption, thus preventing unauthorized access to the decryption key.

05:06

🔑 Asymmetric Cryptography and the RSA Algorithm

This paragraph delves into the workings of asymmetric cryptography, specifically the RSA cryptosystem. It explains the process of generating key pairs, where a public key is shared openly and a private key is kept secret. The RSA algorithm is described in terms of mathematical operations involving large prime numbers, modular arithmetic, and the use of Carmichael's totient function. The explanation includes the selection of the public exponent 'e' and the calculation of the private exponent 'd' using the Extended Euclidean algorithm. The paragraph also touches on the practical implementation of RSA in secure messaging applications.

10:08

📚 Mathematical Foundations of RSA and Its Security

The final paragraph discusses the mathematical underpinnings of the RSA algorithm, emphasizing the role of prime numbers and modular arithmetic in ensuring its security. It explains the use of Fermat's Little Theorem and the properties of prime numbers to create a one-way function that is easy to compute in one direction but difficult to reverse. The paragraph also outlines the process of proving the RSA equation's validity using modular arithmetic and provides a brief explanation of how the RSA encryption and decryption process works with the generated keys. It concludes with a reflection on the significance of asymmetric cryptography in securing internet communications, particularly in the HTTPS standard.

Keywords

💡Encryption

Encryption is the process of converting plain text into a coded format that can only be deciphered by someone with the correct key. In the context of the video, encryption is essential for secure communication over the internet, ensuring that messages sent between individuals can't be intercepted and read by unauthorized parties. The script uses the example of Alice and Bob to illustrate how encryption can secure their confidential conversation.

💡Plain Text

Plain text refers to the original, unencrypted form of a message that can be easily read and understood by anyone who has access to it. The video script mentions the risks of transmitting messages in plain text, where a malicious individual could intercept and read the message without difficulty.

💡Asymmetric Cryptography

Asymmetric cryptography is a method of encryption that uses two different keys: a public key for encryption and a private key for decryption. The video explains how this system allows individuals like Alice and Bob to securely exchange messages over the internet without the risk of their private keys being discovered, as the public keys exchanged are not sufficient to decrypt the messages.

💡Public Key

A public key in asymmetric cryptography is a part of a key pair that can be freely shared and is used by others to encrypt messages intended for the key owner. The script explains that even if an attacker intercepts the public key, it cannot be used to decrypt messages encrypted with it.

💡Private Key

A private key is the counterpart to the public key in asymmetric cryptography and is used to decrypt messages that have been encrypted with the public key. The video emphasizes the importance of keeping the private key secret, as it is the only means to decrypt the messages.

💡RSA Cryptosystem

The RSA cryptosystem is a widely used public-key encryption technology named after its inventors, Ron Rivest, Adi Shamir, and Leonard Adleman. The video describes RSA as a method that uses three integers (n, e, and d) to facilitate the encryption and decryption process, ensuring secure communication.

💡Modular Arithmetic

Modular arithmetic, or 'congruence modulo n', is a system of arithmetic for integers where numbers 'wrap around' after they reach a certain value, n. The video uses the analogy of a clock to explain modular arithmetic in the context of RSA, where the encryption and decryption process involves calculations modulo n.

💡Prime Numbers

Prime numbers are natural numbers greater than 1 that have no positive divisors other than 1 and themselves. The script discusses the importance of prime numbers in RSA encryption, where the product of two large prime numbers is used to generate the modulus n for the encryption key.

💡Carmichael's Totient Function

Carmichael's totient function, lambda, is a function used in RSA to calculate a helper number that assists in determining the private key, d. The video explains that lambda of n is the least common multiple of (p-1) and (q-1), where p and q are the prime numbers used to generate n.

💡Extended Euclidean Algorithm

The Extended Euclidean Algorithm is a computational method used to find the integers that satisfy Bézout’s identity, which is essential in computing the private key, d, in RSA. The video mentions this algorithm in the context of finding the multiplicative inverse in modular arithmetic.

💡HTTPS

HTTPS stands for Hypertext Transfer Protocol Secure and is a protocol used to secure communication over the internet. The video script explains that asymmetric cryptography, similar to the principles used in RSA, powers the HTTPS standard, which encrypts data exchanged between users and websites to prevent unauthorized access.

Highlights

The importance of encryption in ensuring that messages are only read by the intended recipient.

The vulnerability of plain text messages to interception and reading by malicious entities.

Introduction to the concept of encryption to prevent unauthorized access to messages.

Explanation of symmetric encryption and its limitations, such as the need for a shared secret key.

The problem of securely sharing the encryption key without the risk of interception.

Introduction to asymmetric cryptography as a solution to the key exchange problem.

Description of public and private keys in asymmetric encryption, with public keys used for encryption and private keys for decryption.

The RSA cryptosystem and its role in secure communication over the internet.

The mathematical basis of RSA involving integers, exponentiation, and modular arithmetic.

The use of prime numbers in generating unique and secure key pairs for RSA encryption.

The process of generating RSA keys using large prime numbers and the totient function.

The selection of the public exponent 'e' and its mathematical requirements for RSA encryption.

Computing the private exponent 'd' using modular arithmetic and Bézout’s identity.

The practical application of RSA in secure messaging and the HTTPS standard.

The explanation of how RSA encryption and decryption work using modular exponentiation.

The proof of the RSA equation's validity using Fermat’s little theorem and properties of modular arithmetic.

The significance of prime numbers in creating a one-way function for secure encryption.

The transition of RSA and the evolution of cryptography towards superior systems while maintaining the core concept of asymmetric encryption.

Transcripts

If you’re like me, you probably communicate more through the internet than by actually

talking with people in real life.

But when doing that, I expect that my messages will only be read by the person I am talking

to, and not by some other random dude on the internet.

But when you think about it, your message has to travel the world to reach the server

of the app you’re using and back to the person you’re writing to.

Is it really that unlikely that somewhere on the way the message could be intercepted

by a malicious entity?

Well yeah, that would definitely happen a lot if these messages weren’t encrypted.

You see, suppose two individuals, Alice and Bob, want to have a confidential conversation

on the internet.

If their messages were transmitted in plain text, meaning, in a way that can be decoded

by anyone who sees it, a malicious individual could intercept and read the message by placing

themselves somewhere on the path followed by the message.

For wireless communications, simply being near one of the two devices could be enough

to catch the radio signal, but there are also many other possible ways.

Now let’s introduce encryption, which you have probably heard a lot about before.

The idea is that before sending a message, Alice, or her device, could modify the message

in a way that could only be reverted by Bob.

A simple but not so secure way is simply to offset the letters of the messages by a specific

number of places in the alphabet, which can be undone by doing the opposite.

The problem is that Alice and Bob would both need to agree on the way they scramble and

unscramble their messages, and as they are both respectable gamers who haven’t touched

grass for six months, meeting in person to discuss this simply isn’t an option.

However, if they just agree on a protocol or key via online communication, the attacker

could also intercept that which would allow them to decrypt all future messages.

The solution: asymmetric cryptography.

Currently, we have only talked about symmetric encryption, where one key is used both for

encryption and decryption.

In our previous example, the key would be the number of places to offset a letter in

the alphabet.

The idea behind asymmetric cryptography is that we have one key to encrypt a message

and one key to decrypt the message.

The key used for encryption is called a public key, and the one used for decryption is the

private key.

The important part is that these two keys should be generated in a pair, where one public

key is always associated with one private key, and there should be no way to retrieve

the private key from the public key.

Okay but how does that help?

Well, now Alice and Bob can both generate their own key pairs, and only exchange their

public keys through the internet.

Even if an attacker intercepts these keys, they would be of no use for them, as they

can’t be used to decrypt messages.

If Bob wants to send a message to Alice, he can now use the public key he received from

her to encrypt it before sending it, knowing that Alice is the only one who has the private

key used to decrypt it.

And if Alice wants to send a message, she does the same, using Bob’s public key to

encrypt it.

This is the idea behind the RSA cryptosystem, publicly described in 1977 by Ron Rivest,

Adi Shamir, and Leonard Adleman.

RSA works by finding three integers, n, e and d such that any integer raised to the

power of e and raised again to the power of d is congruent to that same integer modulo

n.

If you don’t know what that means, imagine a clock with a single hand, like a stopwatch.

Let’s take a number on this clock, for example 3.

If we spin the hand by 5 places, we get 8, which is simply 3+5.

However, if we instead spin the hand by 13 places, we don’t get 16, which would be

3+13, as that is larger than 12.

Instead, we land on 4.

This means that 3 + 13, or 16 and 4 are congruent modulo 12, where 12 is the number of places

on the clock.

If we have a number larger than 12, like 14, we can “place” it on the clock.

In this case, 14 is 12, one full rotation around the clock, plus two, so we land on

2.

Mathematically, we can say that 14 and 2 are congruent, modulo 12.

For those using the 24h time format, this relationship should be familiar, as in this

system, 14 o’clock is 2 pm.

Let’s stop wasting hours talking about time and instead apply this to the RSA equation.

This equation only means that if we were to calculate m to the power of e, then raised

to the power of d, and “place” it on a clock with n places, it would be at the same

spot as m itself, as if the two powers somehow canceled each other out on such a looping

number system.

This is exactly what we need, because it means we can encrypt a message by raising it to

the power of e, and decrypt it again by raising it to the power of d.

There we have it, asymmetric encryption!

That was easy.

Well, finding the equation is the easy part.

The challenge is figuring out a reliable way to generate sets of numbers that actually

work with this equation, and such that you can’t find d, the private key if you know

e and n.

This is where prime numbers come in.

A prime is an integer greater than one that can’t be written as the product of two or

more smaller integers. 8 is not a prime as it can be written as the product of 2 and

4, so is 15, but 2 can’t be written as the product of smaller integers, same for 7, so

these two numbers are primes.

An important property of prime numbers is that if you take the product of two random

ones, you will get a number that can only be factored back into the original two primes.

For example, if we multiply 17, a prime number, by 53, another prime number, we get 901.

And if we try to write 901 as a product of primes, 17 and 53 will be the only possible

combination.

No other prime factorisation exists.

Therefore, the product of two primes is always unique to those two particular primes.

However, no direct way is known to calculate the original two primes from their product.

We have to try out every possible combination of prime numbers until we find the two that

give us the number we had, and if the two prime numbers are really large, it is practically

impossible to retrieve the primes that were used to construct it.

RSA uses this property to create a one way function, where we can easily calculate our

trio of numbers from two random primes, but we can’t reverse the operation to find the

two primes that were used.

Let’s see how we can generate a new keyset using RSA.

First, we choose two very large prime numbers p and q.

It is important that we use a secure and unpredictable random number generator as knowing these primes

is enough to create the private key.

We then multiply p and q to get n.

n will be part of the public key, so we don’t need to keep it private, and as explained

earlier, if p and q are large enough, we can’t retrieve p and q from it.

We can then compute lambda of n, where lambda is known as Carmichael's totient function.

In this case, it is equal to the lowest common multiple of p minus 1 and q minus one.

This number is just a helper number we’ll use to compute the private key, so we of course

need to keep it to ourselves.

We now need to choose e, which is used in the RSA equation to encrypt our message, so

it is part of the public key.

There are actually many possible values for e, it just needs to be an integer greater

than one and coprime with lambda of n.

Coprime just means that the greatest common divisor of e and lambda of n must be 1.

Now comes the tricky part, computing d, our private key.

d is a number satisfying this equation, which once again involves modular congruence, and

there are actually an infinite number of solutions to this equation, however we will simply pick

the smallest integer.

To do that, we can use a property of modular congruence which states that our equation

is equivalent to this one, where k is an integer.

Now, because e and lambda of n are coprime, this equation is actually a form of Bézout’s

identity, which means there always is a solution, and we can compute it using the Extended euclidean

algorithm, feel free to look that up if you’re interested.

There we have it, Alice and Bob can now generate their own key set this way, and exchange their

n and e values, which form the public key, while keeping d, the private key, to themselves.

Now, if Bob wants to send a message to Alice, he first uses an agreed upon encoding scheme

to convert his message to a number, raises it to the power of Alice’s e value, finds

the smallest positive congruent number with Alice’s n value as a modulus and sends that

to her.

She can then raise the number to the power of d, and once again find the smallest positive

congruent number using her n value as a modulus.

If everything was done correctly, she should get the number corresponding to Bob’s message,

which can then be decoded back to text using the chosen encoding scheme.

Finding the smallest positive congruent number can also be done algorithmically using modular

exponentiation, which thankfully doesn’t actually involve calculating the powers themselves,

which would be impossible considering how large these numbers usually are.

And of course, in reality, Alice and Bob don’t follow these steps manually, but rather the

messaging app they are using does so automatically, or at least it should.

Now that we understand how RSA is implemented, let’s discuss why it works.

Before we begin, we need to understand two properties in modular arithmetic.

First, if we prove that the RSA equation works for both mod p and q separately, the equation

is guaranteed to work for n, as it is the product of p and q.

Second, according to Fermat’s little theorem, a to the power of p-1 is congruent to 1 mod

p where a is any integer and p is any prime number that isn’t a divisor of a.

Let’s use these properties to prove that the RSA equation works with the numbers we

generate.

As stated earlier, d satisfies this equation, which we can rewrite like this.

Therefore, ed-1 is a multiple of λ of n, which, by definition, is a multiple of p-1

and q-1.

ed-1 can therefore be written as h multiplied by p-1 and as j multiplied by q-1 where h

and j are positive integers.

So let’s prove the equation modulo p. m raised to the power of e, then raised to the

power of d, which is equal to m to the power of e times d, itself equal to m to the power

of ed-1 times m, and remember that ed-1 can be written as h times p-1.

Here again, we can use the properties of exponents to rewrite the number like this.

Now, because p is a prime number, which should be so large that it can’t be a divisor of

m, we can use Fermat’s little theorem to say that m to the power of p-1 is congruent

to 1 modulo p.

We have now proven that the RSA equation is true with p as the modulus.

We can repeat practically the same proof for q, with the only difference being that we

have to replace h by j, but its value doesn ‘t make a difference.

By proving it works modulo p and q, we have proven that it works modulo n, which means

we’re done.

Mathematically, if we generate n, e and d using the rules we saw earlier, the RSA equation

will always work.

So there you have it.

This is how prime numbers keep the internet secure and let you have private conversations

with people on the other side of the globe.

Although RSA itself is now being replaced by superior cryptosystems, the idea remains

the same.

Asymmetric cryptography is actually what powers the HTTPS standard which prevents attackers

from accessing the information you exchange with websites.

I hope this video, which I made to participate in 3Blue1Brown’s Summer of Math exposition

initiative, taught you something, and feel free to leave questions and feedback in the

comments.

Also please check out some of the other amazing videos made as part of SoME2.

I wish you a great day, and see you in the next video.