Dos fórmulas funcionan para este problema de intercambio de tres pasos, pero no puedo entender por qué funciona una de ellas
Planteamiento del problema:
"Suponga que los usuarios Alice y Bob llevan a cabo el protocolo Diffie-Hellman de 3 pasos con p = 101. Suponga que Alice elige a 1 = 19 y Bob elige b 1 = 13. Si Alice quiere enviar el mensaje secreto m = 5 a Bob, muestra todos los mensajes intercambiados entre Alice y Bob ".
Solución oficial:
$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 obtiene $m$ evaluando $56^{b_2}\bmod p=5$
Solución que hice usando la ayuda de alguien (ya que no puedo encontrar información muy específica sobre este protocolo de tres pasos en línea):
Alicia:
$\begin{align} a_2&={a_1}^{p-2}\bmod(p-1)\\ &=19^{99}\bmod100\\ &=79\end{align}$
Beto:
$\begin{align} b_2&={b_1}^{p-2}\bmod(p-1)\\ &=13^{99}\bmod100\\ &=77\end{align}$
Alice a Bob # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob a Alice (# 1 - no hay # 2):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Alice a Bob # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Bob obtiene el mensaje de la siguiente manera:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Mi pregunta:
¿Por qué utiliza la solución oficial $a_2={a_1}^{-1}\bmod(p-1)=79$ en vez de $a_2={a_1}^{p-2}\bmod(p-1)=79$y ¿cómo se puede justificar esa equivalencia en el contexto de este tipo de problemas ? (Digo "en el contexto de este tipo de problema" porque, a mi entender, las dos expresiones no siempre son equivalentes).
¡Cualquier aportación que pueda ayudarme a aclarar mi confusión será GRANDEMENTE apreciada!
PD
- $a_1$ es la clave de cifrado de Alice
- $a_2$ es la clave de descifrado de Alice
- $b_1$ es la clave de cifrado de Bob
- $b_2$ es la clave de descifrado de Bob
Respuestas
TL; DR: el segundo método funciona solo para una proporción de primos que desaparece $p$.
La pregunta usa la misma relación entre $a_1$ y $a_2$como en el cifrado simétrico de Pohlig-Hellman. En esto:
- $p$ es un parámetro principal público,
- la clave de cifrado es un número entero aleatorio $a_1$ coprime con$p-1$,
- la clave de descifrado es un número entero $a_2$ tal que $a_1\,a_2=k\,(p-1)+1$ por algún entero $k$.
- el cifrado es por $m\mapsto c=m^{a_1}\bmod p$, para $m$ en $[0,p)$,
- el descifrado es por $c\mapsto m'=c^{a_2}\bmod p$y tiene $m'=m$.
Prueba: $$\begin{align} m'&=c^{a_2}\bmod p&&\text{by construction of $metro'$}\\ &=(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 $metro$ is in $[1, p)$} \end{align}$$
Nota: el pequeño teorema de Fermat dice que cuando$p$ es primo y $m$ no es un múltiplo de $p$, se mantiene $m^{p-1}\bmod p=1$.
Un entero adecuado $a_2$, y el único en el rango $[0,p-1)\,$, es ${a_1}^{-1}\bmod(p-1)\,$: el inverso multiplicativo de$a_1$ modulo $p-1$. Eso es lo que se usa en la solución oficial de la pregunta .
El método de libro de texto para calcular ese inverso multiplicativo es el algoritmo euclidiano extendido . Para implementaciones prácticas, recomiendo esta variante que usa dos variables menos y nunca manipula cantidades negativas.
La otra solución de la pregunta solo difiere al calcular el mismo $a_2$ usando una fórmula diferente: ${a_1}^{p-2}\bmod(p-1)$. Entonces la pregunta se reduce a:
Para prima $p>2$, por que / cuando es que $a^{-1}\bmod(p-1)$ se puede calcular como $a^{p-2}\bmod(p-1)$ ?
Por definición, $a^{-1}\bmod(p-1)$ es el entero $x$ en $[0,p-1)$ con $a\,x\bmod(p-1)=1$. Se define solo cuando$a$ es coprime con $p-1$. De ello se deduce que la pregunta es equivalente a:
Para prima $p>2$, por que / cuando es que $a^{p-1}\bmod(p-1)=1$ para todos $a$ coprime a $p-1$?
Eso es para muchos $p$ incluyendo la pregunta $p=101$, pero no siempre. El contraejemplo más pequeño es$p=11$, $a=3$. Otro es$p=103$, $a=5$. Se puede verificar que utilizando el segundo método para estos$p$ y las claves de cifrado conducen a un descifrado incorrecto para la mayoría $m$.
Estos son los números primos de A337119 (creados para la ocasión), comenzando con
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
Estos también son los números primos $p$ tal que $p-1$es un número Novák-Carmichael A124240 ; o equivalentemente los primos$p$ tal que $\lambda(p-1)$ divide $p-1$ (dónde $\lambda$es la función de Carmichael ). Rápidamente se adelgazan como$p$ crece.
Por lo tanto, el segundo método de la pregunta es incorrecto en general, y la mayoría de los números primos$p$de interés para la aplicación en cuestión (ya que deben ser grandes: miles de bits). Probablemente vino como una extensión incorrecta del siguiente hecho: cuando$p$ es primo, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ a no ser que $a$ es un múltiplo de $p$, que se sigue del pequeño teorema de Fermat .
En el intercambio de tres pasos de la pregunta, $m'$ obtenido por Bob al final es $m$ ya que $$\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}$$