Hovedinnhold
Kurs: (Informatikk > Enhet 2
Leksjon 4: Moderne kryptografi- Den grunnleggende aritmetiske læresetning
- Felles kryptograf nøkkel: Hva er det?
- Diskret logaritmen problem
- Diffie-hellman-nøkkelutveksling
- RSA kryptering: trinn 1
- RSA kryptering: trinn 2
- RSA kryptering: trinn 3
- Tid kompleksitet (Utforskning)
- Eulers totient funksjon
- Euler Totient Exploration
- RSA kryptering: trinn 4
- Hva er det neste vi bør lære?
© 2024 Khan AcademyBrukervilkårPersonvernVarsel om informasjonskapsler
RSA kryptering: trinn 2
Setting up a trapdoor one-way function. Opprettet av Brit Cruise.
Ønsker du å delta i samtalen?
Ingen innlegg enda.
Videotranskripsjon
- [Voiceover] The solution
was found by another British mathematician and
cryptographer, Clifford Cocks. Cocks needed to construct a
special kind of one-way function called a trapdoor one-way function. This is a function that is easy
to compute in one direction, yet difficult to reverse, unless you have special
information, called the trapdoor. For this, he turned to
modular exponentiation, which we introduced as clock arithmetic, in the Diffie–Hellman
key exchange, as follows. Take a number, raise it to some exponent, divide by the modulus
and output the remainder. This can be used to encrypt
a message as follows: Imagine Bob has a message, which is converted into a number, m. He then multiplies his number by itself, e times, where e is a public exponent, then he divides the result
by a random number, N, and outputs the remainder of the division. This results in some number, c. This calculation is easy to perform, however, given only c, e, and N, it is much more difficult to
determine which m was used, because we'd have to resort to some form of trial and error. So, this is our one-way
function that we can apply to m, easy to perform, but difficult to reverse. It is our mathematical lock. Now, what about the key? The key is the trapdoor, some piece of information that makes it easy to reverse the encryption. We need to raise c to some
other exponent, say d, which will undo the initial
operation applied to m and return the original message m. So, both operations
together, is the same as m to the power of e, all
raised to the power of d, which is the same as, m
to the power of e times d, e is the encryption, d is the decryption. Therefore, we need a way for
Alice to construct e and d, which makes it difficult
for anyone else to find d This requires a second one-way function which is used for generating d, and for this, he looked back to Euclid.