# Finding the Multiplicative Inverse within a Modulus

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?

(Corrected 09/27/2018, 15h15 … )

(Update 09/11/2018, 9h55 : )

I have just found out today, that a generalized way to compute this multiplicative inverse has always existed, which is known as The Extended Euclidean Algorithm. This algorithm can find the required inverse in relatively short time, even if (E) happens to be large enough to approach the modulus. However, a concept which is held to be true, is that the modulus itself must be known, within which (D) is supposed to be this inverse of (E).

For reference purposes, I have copied and pasted the algorithm below:

http://dirkmittler.homeip.net/Extended_Euclid.pdf

What the reader should know, is that I can accept that this algorithm works, ‘because the WiKiPedia says so’, but that I do not understand why it works. This was not, something I had invented myself.

But what I had done in years gone by, was to reinvent the wheel, so to speak, and to develop an algorithm, which is only capable of doing so, when (E) happens to be a small number, in cryptographic terms.

I now think that the real reason for which such a small number is chosen for (E), is just to make it easy enough to encrypt data, even for appliances and computers with weak CPUs, which in turn can be decrypted by powerful servers, that use 2048-bit exponents for (D).

(As of 06/06/14/2017 : )

Well, if we can say that the modulus (p-1)(q-1) is also called (m), then any multiple of (m) must be the modulus-equivalent of zero! Hence, it would follow that

im  mod m == 0  mod m

Where i is any integer.

It would seem to follow, that

E D  mod m  ==  im + 1  mod m

Where D < m

Hence,

D = (im + 1) / E  mod m

If we may imagine that division exists for modulus integers – It really does not. But multiplicative inverses are supposed to emulate division

D = (im + 1) / E – jm

Where j is an integer, 0 <= j < ∞ ,

dependent on i .

D = (im – jEm +1) / E

D = ((ijE)m + 1) / E

(Edit 06/15/2017 : Even though the values of i and j were irrelevant to the exactitude of the modulus-equations, only one combination needs to be computable without the modulus expressions. Below, I maintain that i is in fact in the modulus of E. )

D = (im + 1) / E

Hence, if E is just a 17-bit number, and D is a 2048-bit number, it would follow that

(im + 1)

is itself only a 2065-bit number. Therefore, If we can assume that D exists, there is no reason why i would need to be greater than 65537 (our assumed value of E).

This would also be the maximum number of trials necessary, before a division does not leave a remainder, and D has been found.

(m) must be kept an absolute secret, which it would not be, if (p)(q) could be factorized.

(Erratum 09/27/2018, 15h15 : )

An additional constraint exists, by which (E) and (m) must be coprime. But (E) is already prime, which means that (m) just cannot be divisible by (E). The way to make sure of that is to make sure that the prime numbers chosen, (p) or (q), are not such, that (p-1) or (q-1) are divisible by (E). They might be, because if (p) is prime, then (p-1) by definition is not, and is thus divisible by something.

Hence, an attempt is made to divide each prime number generated, by (E), to see whether it can be used or not. And if it is divisible, it cannot, and yet another prime is generated.

Dirk

(Edit 06/15/2017 : )

One idea which some people might have, to find a multiplicative inverse of E in the modulus of (p-1)(q-1), would be to use the exponent function, to raise E to the power of (-1) in that modulus. But This thought is an error, because we’d need to raise E to that power, in a modulus, which would be the Totient Product of (p-1)(q-1).

(p-1)(q-1) is already the Totient Product of (p)(q). It can be computed easily, as long as (p)(q) only has two known, prime factors. If the original modulus had many prime factors, then its Totient Product would form, in a more-complex way.

And a phenomenon exists by which, if (p) is a large prime number, as such it is already rarefied, and (p-1) will often tend to be a very symmetrical number, that has many prime-factors. And then, to compute the Totient Product, of the Totient Product, again requires that a large modulus be prime-factorized, and becomes intractable.

However, if our goal were simply to find the multiplicative inverse of a large value, in the modulus of the single prime number (p), then the Totient Product of the modulus of the base would become (p-1), and the exponent (-1) would then easily be expressed as (p-2). This can be important in El-Gamal Encryption, which is not RSA Encryption.

For academic purposes, if the modulus of the base were (p)(q), then the corresponding exponent would be ((p-1)(q-1) – 1). But with RSA Encryption – and the need to compute the multiplicative inverse during key-generation – If an attempt was made to raise (E) itself to an exponent, this base would correspond to what was originally the exponent, and would therefore already be in the modulus (p-1)(q-1).

Dirk

## 5 thoughts on “Finding the Multiplicative Inverse within a Modulus”

1. François Dionne says:

Your notation is ambiguous: is it T^(E^D) or (T^E)^D ?
The two are not equivalent or even equal; exponents are traditionally evaluated from right to left but here, only (T^E)^D is correct. The expression then becomes T^(E*D) .

1. Dirk Mittler says:

As you have suggested, I have corrected the notation. Thank you for pointing it out.

Dirk