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

Challenge-Response Authentication

What users expect these days, is that a session with a server is secured via ‘High Encryption’, so that both the user’s password and his data are truly secure. However sometimes, the server may not have an SSL / TLS certificate, or for some other reason, high encryption may not be available. And in such cases, the need has arisen for the client to prove that it knows the password, without a potential eavesdropper being made aware of it, even if the eavesdropper can capture the entire negotiation.

In such cases, really, the only alternative is challenge-response authentication. I suppose that clear-text password authentication can also be selected on some platforms, but obviously, clear-text solutions are always insecure.

The way challenge-response authentication works in general is, that both the client and the server, have the password or a password-equivalent stored, and that the server next sends a small piece of data to the client, which constitutes ‘the challenge’. This piece of data can most-conveniently be derived from the date and time, so that it never repeats itself, but must be chosen by the server. It is not secret. ( :1 )

What the client is then expected to do, is merely to append this challenge to the password, and to hash the result. The same process is applied by the server, but only the client communicates the result back to the server, the latter of which verifies that the result from the client matches, with what the server obtained internally, when the server also appended the same challenge, to the same password, and hashed the results.

This approach can be so basic, that it can even be implemented in JavaScript! Yet, it should in principle be just as strong, as the password itself (which is not really so strong).

There are a few differences in specific implementations. For example, it may be that the actual password is not stored on the server, but that only the hash-code of the password is stored. Well in that case, after prompting the user for the password, the client must also hash it once, to obtain the equivalent of what’s stored on the server, the client must then append the challenge to it, and the client must hash the result a second time.

(Updated 04/01/2018, 14h00 … )

Continue reading Challenge-Response Authentication