# Diffie-Hellman key exchange for $n + 1$ parties

Suppose that there are $$n+1$$ parties - $$B,A_1,A_2,...,A_n$$ that want to share a secret key

The protocol of exchanging is roughly the same as Diffe-Hellman

Chose a group $$G$$ with an order of $$p$$ - a prime number and a generator element $$g$$

• Each $$A_i$$ generates a random number $$a_i \in \{1,...,p\}$$ and send $$B$$ the value $$X_i \leftarrow g^{a_i}$$
• B generates a random number $$b \in \{1,...,p\}$$ and send each $$A_i$$ the value $$Y_i \leftarrow X_i^b$$

The shared key of the group is $$g^b$$

It is obvious that $$B$$ can calculate this key.

How can each $$A_i$$ calculate the shared key ?

I tried finding the inverse $$a_i^{-1}$$ of $$a_i$$ in mod $$p$$ and then taking both sides of $$Y_i=g^{a_ib}$$ to the power of $$a_i^{-1}$$ but when I plug in real numbers, it does not seem right.

The method in the (revised) question is (mostly†) OK. That is, $$A_i$$ calculates the shared key as $$Y_i^{a_i^{-1}\bmod p}$$, where the exponentiation is in the group $$G$$ of order $$p$$. And (assuming no alteration of messages) every party including $$B$$ gets the same shared key, because \begin{align} Y_i^{a_i^{-1}\bmod p}&={X_i}^{b\,(a_i^{-1}\bmod p)}\\ &=g^{a_i\,(b\,(a_i^{-1}\bmod p))}\\ &=g^{b\,(a_i\,(a_i^{-1}\bmod p))}\\ &=g^{b\,(k\,p+1)}&&\text{for some }k\in\mathbb Z\\ &=g^{p\,k\,b+b}\\ &=(g^p)^{k\,b}\,g^b\\ &=1^{k\,b}\,g^b&&\text{because the order of }g\text{ is }p\\ &=g^b \end{align}

Given that the initial question used two primes, it's possible that a confusion is made between a prime modulus $$n$$ used to compute in the group $$G$$, and the prime order $$p$$ (formerly $$q$$) of group $$G$$ and it's generator $$g$$. That would explain why numerical experiments fail.

Among many others, our options include:

1. Making $$G$$ an unspecified abstract group of order $$p$$, and not making numerical experiments.
2. Making $$G$$ the subgroup of quadratic residues of $$\mathbb Z_n^*$$ for $$n$$ a safe prime, which has prime order $$p$$ the matching Sophie Germain prime with $$p=(n-1)/2$$. A toy (unsafe) example is $$n=83$$, $$p=41$$. An actual example of such group is the 2048-bit MODP group of RFC 3526.
3. Making $$G$$ a Schnorr group, that is a subgroup $$G$$ of prime order $$p$$ of $$\mathbb Z_n^*$$. Then $$p$$ must be a prime divisor of $$n-1$$. This extends the above, allowing smaller $$p$$ thus faster operation. An actual example of such group is the 2048-bit MODP group with 256-bit prime order subgroup of RFC 5114.
4. Using an elliptic curve of prime order $$n$$ on the prime field $$\mathbb F_n$$. An actual example would be secp256r1 (except using the $$p$$ there as our $$n$$ and the $$n$$ there as our $$p$$), with the group operation described in sec1.

It fails when one of the $$a_i$$ is $$p$$, but that has vanishing probability $$1-(1-1/p)^n$$.

• Its my bad I mistyped p and q
– Kain
Commented Jul 5, 2023 at 8:33
• @Kain: I have updated the answer to match the modified question and detail the computation in a proof of correctness. Make sure to refresh the page.
– fgrieu
Commented Jul 5, 2023 at 8:53