0
$\begingroup$

I'm currently reading Paul Garrett's book "Making, Breaking Codes", where he goes through the standard textbook implementations of different crypto-systems (RSA, Elgamal etc).

When he talks about the different attacks that can be performed on these systems, he often uses the extended euclidean algorithm on different numbers to perform these attacks.

For example, when talking about an RSA attack where an actor sends the same cipher text to two different people with the exponent $e$ changed, he talks about how you can calculate the $\mathrm{Ciphertext}^{-1} \mod n$ (along with other operations) to find the plain text message. I understand that using the extended Euclidean algorithm will give you an $a$ and $b$ such that $ax + by = 1$, however I'm unclear as to how this can help one solve different problems in cryptography.

How does finding this $ax + by = 1$ help in the solution to different cryptographic problems?

$\endgroup$
2
$\begingroup$

The significance of the EEA is that it gives an efficient way to compute modular inverses. Since computing modular inverses is an extremely common task in practical cryptography (among many others, you need it to derive the decryption exponent of an RSA keypair from the encryption exponent), the fact that it can be performed efficiently, as demonstrated by the existence of the EEA, is fundamental. If it couldn't, many of the cryptographic schemes in use today just wouldn't work.

$\endgroup$
0
$\begingroup$

Extended euclidean algorithm does not solve cryptographic problems. It is an essential part of many algoritms because it gives basic operation, iversion. You can find such examples in your Garrett's book, see e.g. Chapter 13 Roots Mod Composites. All algorithms from lattice based crypto are in some sense euclidean algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.