How Do Properties of Modulus Algebra Apply to RSA and Diffie-Hellman?

[FrankJ777]

I'm trying to better understand RSA and Diffie-Hellman exchange and the modulus math that they are base on, there are some questions I have about there properties for which I am unable to find concise explanations about. I'm generally interested in how the commutative, associative, distributive, etc.. properties apply.
Questions 1. About Fermat's Little Theorem.

M^P-1 ≡ 1 (mod P) which I'm told implies that...
M^P ≡ M (mod P)

Is this essentially multiplying by M on both sides?? So if X ≡ Y ( mod P) then aX ≡ aY (mod P) ?

Does. a⋅[ X (mod P)] = aX (mod P) is it a⋅[ X (mod P)] = the remainder of X/P times a ?

Also in the Diffie Hellman exchange I'm told that...

(g^a mod p)^b (mod p) = g^ab (mod p)

which i think means in general that...

[ g (mod p)]^a (mod p)= g^a ( mod p )

but I'm not sure what property that uses. Can that be derived from the multiplication property where...

ab ( mod p ) = [ a (mod p) ⋅ b (mod p) ] (mod p)

Thanks a lot for any explanation you can give to point me on the right track.

 

[fresh_42]

The answer to your questions is basically the homomorphism property of modulo.
Let $φ(a) = r$ if $a = k \cdot M +r$, i.e. $φ =\mod(M)$. Then if $b = l \cdot M + q$ we get

$φ(ab) =$
$= ab\mod(M)$
$= ((k \cdot M + r) \cdot (l \cdot M+q))\mod(M)$
$= ((klM + rl +qk) \cdot M + rq)\mod (M)$
$= rq$
$= (a\mod(M)) \cdot (b\mod(M))$
$= φ(a) \cdot φ(b)$

 

[jbriggs444]

Does. a⋅[ X (mod P)] = aX (mod P) is it a⋅[ X (mod P)] = the remainder of X/P times a ?

In computing, the modulus operator takes the remainder after division. In mathematics it is something quite different. The modulus notation modifies the equality test.

When we write "a = b (mod P)" that should be understood to mean that a and b are equivalent modulo p. That is to say that they have the same remainder when divided by p.

When the (mod P) notation appears to the left of the equal sign, it amounts to mathematical nonsense.

 

[FrankJ777]

Fresh, sorry I haven't taken abstract algebra. Please tell me if I'm understanding you correctly.

The answer to your questions is basically the homomorphism property of modulo.
Let $φ(a) = r$ if $a = k \cdot M +r$, i.e. $φ =\mod(M)$. Then if $b = l \cdot M + q$ we get

$φ(ab) =$
$= ab\mod(M)$
...
$= (a\mod(M)) \cdot (b\mod(M))$
$= φ(a) \cdot φ(b)$

You are saying that φ(a) is the function a (mod M). ?
And that..

ab (mod M) = a (mod M) ⋅ b (mod M)

from most other things I've read the identity is...

ab (mod M) = ( a (mod M) ⋅ b (mod M) ) (mod M)

Am I understanding you correctly?

 

[FrankJ777]

In computing, the modulus operator takes the remainder after division. In mathematics it is something quite different. The modulus notation modifies the equality test.

When we write "a = b (mod P)" that should be understood to mean that a and b are equivalent modulo p. That is to say that they have the same remainder when divided by p.

When the (mod P) notation appears to the left of the equal sign, it amounts to mathematical nonsense.

OK. How do I interpret the expression?
If i multiply a number time a modular expression such as...
a⋅[ X (mod P)]
is it the same thing as saying...
= aX (mod P)
or is it a⋅[ X (mod P)] = the remainder of X/P times a

 

[fresh_42]

Fresh, sorry I haven't taken abstract algebra. Please tell me if I'm understanding you correctly.

You are saying that φ(a) is the function a (mod M). ?
And that.

Yes.

ab (mod M) = a (mod M) ⋅ b (mod M)

Correct.

from most other things I've read the identity is...

ab (mod M) = ( a (mod M) ⋅ b (mod M) ) (mod M)

Am I understanding you correctly?

Yes. The first three mod's here mean to take the remainder and the last isn't really necessary (only if programming). The last one only tells in which number area the second multiplication took place, namely in the domain of possible remainders of (division by) $M.$

I does not matter how often or where you take the remainder. And $\mod M$ is simply that: the remainder if divided by $M$.
As jbriggs444 has said: $a ≡ b \mod M$ means just that $a$ and $b$ have the same remainder when divided by $M$, or $(a-b)$ is divisible by $M.$
Your notation with the many mod's in between is somehow computer language to keep the numbers short. It makes not really a difference.

 

[fresh_42]

OK. How do I interpret the expression?
If i multiply a number time a modular expression such as...
a⋅[ X (mod P)]

This doesn't make much mathematical sense, because one doesn't know where you multiply.
If you multiply integers and take the remainder afterwards, ok, like $3 \cdot 6 = 18 = 6 \mod 12$. But this is a different multiplication from what you do on the remainders. E.g. $3 \cdot 4 = 0 \mod 12$. You don't get zero on the integers, only after passing to the remainders. So in your expression it's not clear where you want to multiply, even if you might get the same result as intended. It's simply a dirty notation.
If you want to be precise you could use $≡$ instead of $=$ to signal that all arithmetic operations are performed on the remainders only.

 

[FrankJ777]

OK. At this page explaining the math behind Diffie-Hellman they state:

(ga mod p)^b mod p = g^ab mod p
(gb mod p)^a mod p = g^ba mod p

I believe in this example they intend the ' = ' to mean exactly equal, not equivalent congruent. Also I think the additional (mod p)'s in red make the remainder on both sides exactly equal. Does this make mathematical sense in this context?

So is it a general rule that...

(g mod p)^b mod p = g^b mod p
or that...
(g mod p)^b ≡ g^b mod p

Can this be derived from the multiplication property?
Thanks.

 

[Stephen Tashi]

The modulus notation modifies the equality test.

Should we say that the modulus notation also modifies the meaning of everything in an equation?

For example, does the expression: (3)(4) mod(5) use "3" to denote an integer or does it use "3" to denote an equivalence class of integers, in which case "3" denotes a set ? Or perhaps "3" denotes an integer, but the integer is a "representative" for a set ?

 

[jbriggs444]

Should we say that the modulus notation also modifies the meaning of everything in an equation?

Perhaps so. I've never worried about it much since things works out the same under either interpretation.

 

[fresh_42]

Should we say that the modulus notation also modifies the meaning of everything in an equation?

For example, does the expression: (3)(4) mod(5) use "3" to denote an integer or does it use "3" to denote an equivalence class of integers, in which case "3" denotes a set ? Or perhaps "3" denotes an integer, but the integer is a "representative" for a set ?

I think it is all about the where. Where do you calculate in? You can do all arithmetic in $ℤ$ and project the result onto $ℤ/nℤ$ or you can forget about $ℤ$ and the cosets and consider $ℤ/nℤ$ as the ring to perform the calculations in: no more cosets, representatives or integers, simply different rules. Confusion only arises if one messes up the two concepts and switch between them. As $ℤ → ℤ/nℤ$ is a ring homomorphism it doesn't really matter concerning the results. However, it is kind of dirty.

 

[Stephen Tashi]

OK. At this page explaining the math behind Diffie-Hellman they state:

(ga mod p)^b mod p = g^ab mod p

Is it (g^a\ mod\ p)^b\ mod\ p ?

 

[FrankJ777]

Is it (g^a\ mod\ p)^b\ mod\ p ?

Yes Stephen. My bad. Let me repost this.

(g^a mod p)^b mod p = g^ab mod p
(g^b mod p)^a mod p = g^ba mod p

Thanks