liveBook · Manning

Extended Euclidean algorithm

As explained in Hacking Cryptography

The extended Euclidean algorithm computes greatest common divisors and coefficients expressing them as linear combinations of integers.

The extended Euclidean algorithm (EEA) efficiently computes the greatest common divisor of two integers while expressing that divisor as a linear combination of them. In RSA key generation, it finds the private exponent d, the modular inverse of the public exponent e modulo φ(n). section 8.3.2

Use the EEA in RSA key generation to:

RSA key-generation calculation

For p = 193 and q = 727, φ(n) = 139392. Choosing e = 17653, the EEA produces d = 77533. Verification gives 17653 × 77533 ≡ 1 mod 139392. section 8.3.2

How Hacking Cryptography covers it

How deep it goes
Defines the EEA’s GCD role and demonstrates its RSA result, but does not detail the algorithm’s iterative steps.
Examples
Uses p = 193, q = 727, e = 17653, φ(n) = 139392, and d = 77533.
What it assumes
Assumes familiarity with GCD, coprimality, modular arithmetic, and Euler’s theorem.
What you can do after
Evaluate RSA key generation by computing and verifying a modular inverse with the EEA.
How it connects
Connects greatest common divisor, modular inverse, Euler’s theorem, and RSA key generation.
Cover of Hacking Cryptography
liveBookmanning.com
Read Hacking Cryptography on liveBook Get the book at manning.com

Also explained in

Compare how 2 books explain extended Euclidean algorithm →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.