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

Question

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)
    def add(self, a, b):
        return (a*b) % self.p
    def sub(self, a, b):
        return self.add(a, self.inv(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) 
x = mg.add(c, e)
# on server
y = mg.mul(x, SS) 
# back on client
K2 = mg.sub(y, mg.mul(s, EE))

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

Answer 1

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.