The general concept in RSA Cryptography is, there exists a product of two prime numbers, call them (p) and (q), such that
T ^ E ^ D mod (p)(q) = T
where,
T is an original plaintext document,
E is an encryption key,
D is the corresponding decryption key,
E and D are successively-applied exponents, of T,
(p)(q) is the original modulus.
A famous Mathematician named Euler found, that in order for exponent operations on T to be consistent in the modulus (p)(q), the exponents’ product itself must be consistent in the modulus (p-1)(q-1). This latter value is also known as Euler’s Totient Product of (p)(q).
There is a little trick to this form of encryption, which I do not see explained often, but which is important. Since E is also the public key, a relatively small prime number is used in practice, that being (2^16 + 1), or 65537. D could be a 2048 or a 4096-bit exponent. The public key consists of the exponent E and the modulus (p)(q) packaged together.
Thus, when the key-pair is created, (p) and (q) must be known separately, so that D can be computed, and then (p-1)(q-1), which hopefully never touched the hard-drive, can be discarded, after D is saved, along with (p)(q) again, this time forming the private key.
Therefore, D must be the multiplicative inverse of E, in the modulus of (p-1)(q-1). But how does one compute that?
Continue reading Finding the Multiplicative Inverse within a Modulus