Two formulas work for this three-pass exchange problem, but I can't figure out why one of them works

Question

Problem statement:

"Suppose that users Alice and Bob carry out the 3-pass Diffie-Hellman protocol with p = 101. Suppose that Alice chooses a 1 = 19 and Bob chooses b 1 = 13. If Alice wants to send the secret message m=5 to Bob, show all the messages exchanged between Alice and Bob."

Official solution:

$a_2 = {a_1}^{-1}\bmod(p-1)=79$
$b_2=77$
Alice → Bob: $m^{a_1}\bmod p=37$
Bob → Alice: $80$
Alice → Bob: $56$
Bob obtains $m$ by evaluating $56^{b_2}\bmod p=5$

Solution I made using someone's help (since I can't find very specific information about this three-pass protocol online):

Alice:
$\begin{align} a_2&={a_1}^{p-2}\bmod(p-1)\\ &=19^{99}\bmod100\\ &=79\end{align}$

Bob:
$\begin{align} b_2&={b_1}^{p-2}\bmod(p-1)\\ &=13^{99}\bmod100\\ &=77\end{align}$

Alice to Bob #1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$

Bob to Alice (#1 - there is no #2):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$

Alice to Bob #2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$

Bob obtains the message as follows:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$

My question:

Why does the official solution use $a_2={a_1}^{-1}\bmod(p-1)=79$ instead of $a_2={a_1}^{p-2}\bmod(p-1)=79$, and how can that equivalence in the context of this type of problem be justified? (I say "in the context of this type of problem" because, to my understanding, the two expressions are not always equivalent).

Any input that could help me clarify my confusion would be GREATLY appreciated!

P.S.

• $a_1$ is Alice's encryption key
• $a_2$ is Alice's decryption key
• $b_1$ is Bob's encryption key
• $b_2$ is Bob's decryption key

Answer 1

TL;DR: the second method works only for a vanishing proportion of primes $p$.

---

The question uses the same relation between $a_1$ and $a_2$ as in the Pohlig-Hellman symmetric cipher. In this:

• $p$ is a public prime parameter,
• the encryption key is a random integer $a_1$ coprime with $p-1$,
• the decryption key is an integer $a_2$ such that $a_1\,a_2=k\,(p-1)+1$ for some integer $k$.
• encryption is per $m\mapsto c=m^{a_1}\bmod p$, for $m$ in $[0,p)$,
• decryption is per $c\mapsto m'=c^{a_2}\bmod p$, and it holds $m'=m$.

Proof: $$\begin{align} m'&=c^{a_2}\bmod p&&\text{by construction of $m'$}\\ &=(m^{a_1}\bmod p)^{a_2}\bmod p&&\text{since $c=m^{a_1}\bmod p$}\\ &=m^{a_1\,a_2}\bmod p\\ &=m^{k\,(p-1)+1}\bmod p&&\text{by construction of $a_2$}\\ &=m^{(p-1)\,k}\,m^1\bmod p\\ &=(m^{p-1})^k\,m\bmod p\\ &=(m^{p-1}\bmod p)^k\,m\bmod p\\ &=1^k\,m\bmod p&&\text{per Fermat's little theorem}\\ &=m\bmod p\\ &=m&&\text{since $m$ is in $[1,p)$} \end{align}$$

Note: Fermat's little theorem tells that when $p$ is prime and $m$ is not a multiple of $p$, it holds $m^{p-1}\bmod p=1$.

One suitable integer $a_2$, and the only one in range $[0,p-1)\,$, is ${a_1}^{-1}\bmod(p-1)\,$: the multiplicative inverse of $a_1$ modulo $p-1$. That's what's used in the question's official solution.

The textbook method to compute that multiplicative inverse is the Extended Euclidean algorithm. For practical implementations, I recommend this variant which uses two less variables and never manipulates negative quantities.

---

The question's other solution differs only by computing the same $a_2$ using a different formula: ${a_1}^{p-2}\bmod(p-1)$. So the question boils down to:

For prime $p>2$, why/when is it that $a^{-1}\bmod(p-1)$ can be computed as $a^{p-2}\bmod(p-1)$ ?

By definition, $a^{-1}\bmod(p-1)$ is the integer $x$ in $[0,p-1)$ with $a\,x\bmod(p-1)=1$. It is defined only when $a$ is coprime with $p-1$. It follows that the question is equivalent to:

For prime $p>2$, why/when is it that $a^{p-1}\bmod(p-1)=1$ for all $a$ coprime to $p-1$?

That's for many $p$ including the question's $p=101$, but not always. The smallest counterexample is $p=11$, $a=3$. Another it $p=103$, $a=5$. It can be verified that using the second method for these $p$ and encryption keys leads to incorrect decryption for most $m$.

These are the primes form A337119 (created for the occasion), starting with

2 3 5 7 13 17 19 37 41 43 61 73 97 101 109 127 157 163 181 193 241 257 313 337 379 401 421 433 487 541 577 601 641 661 673 757 769 881 883 937 1009 1093 1153 1201 1249 1297 1321 1361 1459 1601 1621 1801 1861 1873

These also are the primes $p$ such that $p-1$ is a Novák-Carmichael number A124240; or equivalently the primes $p$ such that $\lambda(p-1)$ divides $p-1$ (where $\lambda$ is the Carmichael function). They quickly thin out as $p$ grows.

Therefore the question's second method is wrong in general, and most primes $p$ of interest for the application at hand (since they mush be large: thousand bits). Likely it came as an incorrect extension of the following fact: when $p$ is prime, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ unless $a$ is a multiple of $p$, which follows from Fermat's little theorem.

---

In the question's three-pass exchange, $m'$ obtained by Bob in the end is $m$ since $$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &={({m_\text{BobToAlice}}^{a_2}\bmod p)}^{b_2}\bmod p\\ &={m_\text{BobToAlice}}^{a_2\,b_2}\bmod p\\ &={({m_\text{AliceToBob1}}^{b_1}\bmod p)}^{a_2\,b_2}\bmod p\\ &={m_\text{AliceToBob1}}^{b_1\,a_2\,b_2}\bmod p\\ &={(m^{a_1}\bmod p)}^{b_1\,a_2\,b_2}\bmod p\\ &=m^{a_1\,b_1\,a_2\,b_2}\bmod p\\ &=m^{(a_1\,b_1)\,(a_2\,b_2)}\bmod p\\ &=(m^{a_1\,a_2}\bmod p)^{b_1\,b_2}\bmod p\\ &=m^{b_1\,b_2}\bmod p\\ &=m \end{align}$$