Primitive Root of a Prime Integer

Loading...

En provenance du cours de University of Colorado System

Asymmetric Cryptography and Key Management

37 notes

University of Colorado System

Asymmetric Cryptography and Key Management

37 notes

Cours 3 sur 4 dans Specialization Applied Cryptography

Welcome to Asymmetric Cryptography and Key Management! In asymmetric cryptography or public-key cryptography, the sender and the receiver use a pair of public-private keys, as opposed to the same symmetric key, and therefore their cryptographic operations are asymmetric. This course will first review the principles of asymmetric cryptography and describe how the use of the pair of keys can provide different security properties. Then, we will study the popular asymmetric schemes in the RSA cipher algorithm and the Diffie-Hellman Key Exchange protocol and learn how and why they work to secure communications/access. Lastly, we will discuss the key distribution and management for both symmetric keys and public keys and describe the important concepts in public-key distribution such as public-key authority, digital certificate, and public-key infrastructure. This course also describes some mathematical concepts, e.g., prime factorization and discrete logarithm, which become the bases for the security of asymmetric primitives, and working knowledge of discrete mathematics will be helpful for taking this course; the Symmetric Cryptography course (recommended to be taken before this course) also discusses modulo arithmetic. This course is cross-listed and is a part of the two specializations, the Applied Cryptography specialization and the Introduction to Applied Cryptography specialization.

À partir de la leçon

Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange is an asymmetric cryptographic protocol for key exchange and its security is based on the computational hardness of solving a discrete logarithm problem. This module explains the discrete logarithm problem and describes the Diffie-Hellman Key Exchange protocol and its security issues, for example, against a man-in-the-middle attack.

Discrete Logarithm2:08

Primitive Root of a Prime Integer3:56

Discrete Logarithm Problem1:22

Rencontrer les enseignants

Sang-Yoon Chang
Assistant Professor
Computer Science

Let's discuss more about primitive root with an example.

Given our modulus of five,

which is a prime number,

let's look at how different bases A mod P behave when taking exponents.

When the base, base A is equal to one taking the exponents,

produces the same value as one,

because one raised to the power of any exponent is equal to one.

When the bases A is A equals to two,

then A to the second power mod five is equal to four,

because two squared is equal to four.

When the exponent is three,

A to the third power mod five is three,

because two to the third power is equal to eight and eight mod five is three.

When the exponent is four,

eight to the fourth power mod P is equal to one,

because two to the fourth power is equal to 16,

and 16 mod five is equal to one.

What would happen with eight to the fifth power mod P?

This is equal to eight to the fourth power mod P times

A mod P. So this is one times two mod P,

which is equal to two, and since,

eight to the sixth power mod P is equal to eight the fifth power mod P times eight mod P,

which is equal to four,

we now have a repetition.

When A is equal to two,

taking the exponent where the exponents increase,

will generate a sequence that repeats 2-4-3-1.

Therefore, there is no need to continue populating the table to

the right after the exponent four.

We can continue populating the table with the base of A is equal to three,

and A is equal to four.

Now, let's study the table that we populated.

When A is equal to one,

one value of one repeats itself with a period of one.

So this is the only value,

regardless of the value of the exponent,

or which column it is in the table.

When A is equal to four,

the sequence of four and one repeats itself,

and the values of two and three never appear when varying the exponents.

What we want are the base As that yields

all possible values when taking the exponent mod P, except for zero.

In other words, the primitive root is a number whose power

successively generate all the elements mod P, except for zero.

Because it generates all the elements mod P,

such base is appropriate for cryptographic applications.

When the modulus is P equals five,

A is equal to two, and A is equal to three, accomplishes this feature.

And these values of As are called,

the primitive root of P. In other words, in this example,

two is a primitive root of five,

and three is also a primitive root of five,

but one and four are not primitive roots of five.

Such numbers, two and three in this case,

are also called the generators,

when used in cryptography.

When a modulus P is used,

where P is a prime number,

and A is the primitive root of that P,

then the discrete logarithm,

base A mod P of Y,

exists and is unique.

In this table, the discrete log corresponds to the exponent.

For example, focusing on the four in the second column,

and the third row, the discrete log base three mod five of four is equal to two.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play