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 !

And so as I wrote once before, in such schemes, the base must either be coprime with the modulus, or, if inversion is not needed, an equivalent constraint needs to be satisfied, the latter of which happens with Diffie-Hellman Key Exchange.

Dirk

 

Print Friendly, PDF & Email

Leave a Reply

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

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>

This site uses Akismet to reduce spam. Learn how your comment data is processed.