Finding the Purpose of Multiplicative Groups, within a Modulus

There exists a WiKiPedia article, which defines what a Multiplicative Group of Integers is, Modulo n. But even though the article is about 10 pages long (in my browser), it fails to explain in a common-sense way – at least that I can find at a glance – why the existence of these groups is important on a practical level.

I would paraphrase that the Multiplicative Group, consists of Integers within the Modulus, which have Multiplicative Inverses, and which are therefore also Coprime with the Modulus. While these two properties are equivalent, they are not in fact exactly the same property. But why is this combination of properties finally important, let’s say If we wanted to implement an encryption scheme, in which a base – representing a message – is to be raised to a 2048-bit long exponent, and if to do so a second time, is to reproduce the original message?

Essentially, we can multiply one integer by another, assuming they are both in the same modulus, and arrive at some numerical result when applying the remainder function on the product, even though one of the original integers was not coprime with the modulus. This is trivial, because of the way the remainder function has been defined. In other words, we could compute this:

(2 * 5) mod 10 = 0

There is a sticking point with this operation. Once the value zero has been computed, any further multiplication with zero, yield zero again. There is no magical reason why this would not be the case with modular multiplication. But there was once a (2) and a (5), which will never be recoverable in any specific way, from ( 0 mod 10 ). Not only that, but this loss of information does not take place all at once; this happens cumulatively. We could start with (7), which is coprime with the modulus, we could multiply it once by (2), and we could then multiply it again by (5), and again, we’d get zero:

C1 = (7 * 2) mod 10 = 4

T1 = (C1 * 5) mod 10 = 0 !

We can also observe, that just to perform a multiplication in which one parameter was not coprime, results in a product which is not so – in the above case, in ( 4 mod 10 ). Similarly:

C2 = (7 * 5) mod 10 = 5  (No obvious problem yet.)

T2 = (C2 * 2) mod 10 = 0  (Problem.)

Well, when we are exponentiating a number, we are essentially performing many multiplications on it. And then the cumulative result can easily be, that we cannot reproduce the original message, or even, that the message becomes zero !

Continue reading Finding the Purpose of Multiplicative Groups, within a Modulus

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


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 … )

Continue reading Finding the Multiplicative Inverse within a Modulus