How do i generate the shared key from this question?

Question

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?

Answer 1

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}