0
$\begingroup$

Say I have Alice and Bob:

Alice has $XA$, $YA = g^{XA} \bmod P$, $RA$ (random number)

Bob has $XB$, $YB = g^{XB} \bmod P$, $RB$ (random number)

Assume they have exchanged their certificates and they perform the following exchange.

\begin{align} A\to B&:y_B^{RA}\\ B\to A&:y_A^{RB} \end{align}

The shared key is $Z_{AB}=g^{RA+RB}$

I am trying to make sense of how they will be able to come to the shared key.

If I am bob I derive the key by:

$(YB^{RA})^{XB^{-1}} = ({g^{XB}}^{RA})^{XB^{-1}} = g^{RA}$

The I issue I am facing is the ${g^{XB}}^{RA}$ is actually ${g^{XB}}^{RA} \bmod P$ so how do I remove the $XB$ from $({g^{XB}}^{RA} \bmod P)$ to get $g^{RA}$

EDIT:

To make it more clear using numbers:

Say: $XB =4 ,g=9,P =23,RA=6$

Alice sends bob: \begin{align} A\to B:&y_B^{RA}\\ &y_B^{RA} \bmod P = 16^{6} \bmod 23 =12 \\ \end{align}

How would bob extract the $RA$ from 12???

Bob can try:

$(YB)^{RA\cdot XB^{-1}} = (16)^{RA \cdot 1/4} mod 23$

As can be seen above how i extract the value of RA?? in terms of $g^{RA}$ and there has to be only one answer if not how would bob know the which answer alice is using? Does it matter which answer alice is using?

$\endgroup$
1
$\begingroup$

First note that by basic power laws:

$$(a^b)^c=a^{b\cdot c}$$

and then note that this here is simply an application of that:

$$\left(y_B^{RA}\right)^{XB^{-1}}=\left(\left(g^{XB}\right)^{RA}\right)^{XB^{-1}}=\left(g^{XB\cdot RA}\right)^{XB^{-1}}=g^{XB\cdot RA\cdot XB^{-1}}=g^{RA}$$

where all equalities hold in all multiplicatively written groups (actually in all monoids), such as $\mathbb Z_P^*$ and $XB^{-1}$ is computed modulo the group's order, e.g. $\varphi(P)$ for $\mathbb Z^*_P$


As for your numerical example, with $g=9, RA=6, XB=4, P=23$, first note that the multiplicative order of $g$ is $11$, which means we need to calculcate $XB^{-1}\bmod 11=3$ and then everything just works:

$$g^{RA}=9^6\bmod 23=3=12^3\bmod 23=(y_B^{RA})^{XB^{-1}}$$

And of course you probably also want to note that $$Z_{AB}=g^{RA+RB}=g^{RA}\cdot g^{RB}$$, so you don't actually need to recover $RA$ nor $RB$ but only $g^{RA}$ and $g^{RB}$, one of which either party can compute directly and the other using the above formulas.


If you want to carry out these computations with realistic numbers yourself, you normally use the little Fermat or the EEA for finding the multiplicative inverses, using also e.g. repeated-square-and-multiply. Finding the order of $g$ can be a bit tricky at times, because you only know that it must divide the group order (by Lagrange's theorem), so you could just pick a safe prime and use a $g$ that has order $q$ for $p=2q+1$ with $p,q$ prime. Finding such an element is quite straightforward in that you check increasing candidate values until you get one that matches the following three conditions: \begin{align} g^1\neq 1\\ g^2\neq 1\\ g^q=1 \end{align}

$\endgroup$
  • $\begingroup$ Hi, slight error it should be: $12^{3} mod 23$ since $XB^{-1} mod 11 = 3$. Also if I may ask, are these calculations feasible when I use large prime numbers? Is there a link where I can learn to find the multiplicative order of different $g$ $\endgroup$ – DENN Aug 19 '18 at 15:54
  • $\begingroup$ @DENN yes, they are feasible and normally you'd use the EEA or the little Fermat for computing these inverses. As for the order, finding it isn't trivial, but if you know the factorization of $P$ you can compute $\varphi(P)=P-1$ and then you know that the order of each element must divide $P-1$ by Lagrange's theorem. "Ideally" you then just pick a prime $P$ such that $(P-1)/2$ is prime and use an element of the small prime order. $\endgroup$ – SEJPM Aug 19 '18 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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