1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Its my bad I mistyped p and q $\endgroup$
    – Kain
    Jul 5 at 8:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jul 5 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.