# Need help with notation used in McCallum-Relyea key exchange explanation

I want to better understand the McCallum-Relyea (MR) key exchange used in software called Clevis and Tang. (I'm an IT person, please excuse me for being mathematically not very precise.)

It is related to the Diffie-Hellman (DH) key exchange that I understand in its simplest form using the function (A**B mod P) with fixed prime P. I know that other operation may be used if it satisfy certain conditions.

The document I found uses a "multiplicative notation" (google find that for me). Link is: https://people.redhat.com/pladd/NYRHUG_NBDE_2020-02.pdf pages 23 and 25.

The DH key exchange is written there using AB instead of e.g. (A**B mod P).

1. Alice chooses secret C and sends c=gC to Bob.
2. Bob chooses secret S and sends s=gS to Alice.
3. Alice computes K=sC=gSC; Bob computes K=cS=gCS

Keeping in mind that gX is a notation for (g**X) mod P I can follow that and I see why gSC == gCS. So far so good.

However the MR description introduces addition and substraction and computes for instance:

x = c + e
y = xS

and the explanation in the document makes sense to me only if y = cS + eS. My question is what that plus operation (and also the minus elsehwere in the document) are in reality. It canot be the regular addition, because (c+e)**S mod P != c**S mod P + e**S mod P).

UPDATE: with the help of @R_Marche and after studying the slide #31 in this presentation I could wrote a quick&dirty program in Python that does the computation step by step and comes to the correct answer. That answers the question to me. I'm a guest here, don't know if it is OK, but I'm attaching the program.

import random

class ModGrp:
def __init__(self, g, p):
self.gen = g
self.p = p
def rnd(self):
return random.randrange(1, self.p)
return (a*b) % self.p
def sub(self, a, b):
def mul(self, a, b):
return pow(a, b, self.p)
def inv(self, x):
return pow(x, self.p-2, self.p)

mg = ModGrp(17,443)

# -- provisioning --
# on server
SS = mg.rnd()
s = mg.mul(mg.gen, SS)
# on client
CC = mg.rnd()
c = mg.mul(mg.gen, CC)
K1 = mg.mul(s, CC)
del CC

# -- recovery --
# on client
EE = mg.rnd()
e = mg.mul(mg.gen, EE)
# on server
y = mg.mul(x, SS)
# back on client
K2 = mg.sub(y, mg.mul(s, EE))

print(f"created={K1} recovered={K2}")

In the Diffie-Helmann key exchange (and in algorithms derived from it) you are dealing with a group. A group $$G$$ consists of a set of elements and of an operation that combines them.

Your doubts are probably caused by the fact that there are two main ways to denote the group operation: one additive and one multiplicative.

Assume $$x,y$$ are elements in $$G$$, and that the operation in $$G$$ is $$\circ$$.

In the additive notation you'd write $$x + y$$ instead of $$x \circ y$$, and $$n\cdot x$$ instead of repeating $$x\circ x \circ \cdots \circ x$$ for $$n$$ times.

In the multiplicative notation (which seems to be the one you're more used to), you instead write $$x\cdot y$$ instead of $$x \circ y$$ and $$x^n$$ instead of repeating $$x\circ x \circ \cdots \circ x$$ for $$n$$ times.

Now, to answer you actual question. In the notation used by the slides the set you are working with is the set $$\mathbb{Z}_p$$, the integers modulo $$p$$. The operation $$\circ$$ is the modular addition, so it is denoted in additive notation, with a + . It follows that the repeated addition is denoted by a multiplication $$n\cdot x$$. The reason you may find this confusing is that when you learned the DH algorithm, you saw it written with the multiplicative notation. I suggest you to try and rewrite the DH algorithm you already know by swapping all $$\cdot$$ with $$+$$ and all exponentiations with multiplications. The same thing seen from two different perspective might help you to make the "jump" to the new version of the key exchange.

• It helped me to advance in the right direction. Thank you, accepted. (and I added an UPDATE to the question)
– VPfB
Jun 10, 2022 at 16:10