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?

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

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.


 

An additional constraint exists, by which D and E must be coprime. But E is already prime, which means that D just cannot be divisible by E in the modulus (m). 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, because (p)(q) only has two known, prime factors. If the original modulus had many prime factors, then its Totient Product would form, by subtracting 1 from each of them.

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, of (p), becomes intractable.

However, if our goal were simply to find the multiplicative inverse of a large value of E, 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 – the base would correspond to what was originally the exponent, and would therefore already be in the modulus (p-1)(q-1).

 

Leave a Reply

Your email address will not be published. Required fields are marked *

Please Prove You Are Not A Robot * Time limit is exhausted. Please reload the CAPTCHA.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>