Duas fórmulas funcionam para este problema de troca de três passos, mas não consigo descobrir por que uma delas funciona
Declaração do problema:
"Suponha que os usuários Alice e Bob realizem o protocolo Diffie-Hellman de 3 passagens com p = 101. Suponha que Alice escolha a 1 = 19 e Bob escolha b 1 = 13. Se Alice quiser enviar a mensagem secreta m = 5 para Bob, mostre todas as mensagens trocadas entre Alice e Bob. "
Solução 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 obtém $m$ avaliando $56^{b_2}\bmod p=5$
Solução que fiz com a ajuda de alguém (já que não consigo encontrar informações muito específicas sobre este protocolo de três passagens online):
Alice:
$\begin{align} a_2&={a_1}^{p-2}\bmod(p-1)\\ &=19^{99}\bmod100\\ &=79\end{align}$
Prumo:
$\begin{align} b_2&={b_1}^{p-2}\bmod(p-1)\\ &=13^{99}\bmod100\\ &=77\end{align}$
Alice para Bob # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob para Alice (# 1 - não há # 2):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Alice para Bob # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Bob obtém a mensagem da seguinte maneira:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Minha pergunta:
Por que a solução oficial usa $a_2={a_1}^{-1}\bmod(p-1)=79$ ao invés de $a_2={a_1}^{p-2}\bmod(p-1)=79$, e como pode essa equivalência no contexto deste tipo de problema ser justificada? (Digo "no contexto deste tipo de problema" porque, a meu ver, as duas expressões nem sempre são equivalentes).
Qualquer contribuição que pudesse me ajudar a esclarecer minha confusão seria MUITO apreciada!
PS
- $a_1$ é a chave de criptografia de Alice
- $a_2$ é a chave de descriptografia de Alice
- $b_1$ é a chave de criptografia de Bob
- $b_2$ é a chave de descriptografia de Bob
Respostas
TL; DR: o segundo método funciona apenas para uma proporção crescente de primos $p$.
A questão usa a mesma relação entre $a_1$ e $a_2$como na cifra simétrica Pohlig-Hellman. Nisso:
- $p$ é um parâmetro público primário,
- a chave de criptografia é um número inteiro aleatório $a_1$ coprime com$p-1$,
- a chave de descriptografia é um inteiro $a_2$ de tal modo que $a_1\,a_2=k\,(p-1)+1$ para algum inteiro $k$.
- criptografia é por $m\mapsto c=m^{a_1}\bmod p$, para $m$ dentro $[0,p)$,
- a descriptografia é por $c\mapsto m'=c^{a_2}\bmod p$, e mantém $m'=m$.
Prova: $$\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}$$
Nota: O pequeno teorema de Fermat diz que quando$p$ é primo e $m$ não é um múltiplo de $p$, segura $m^{p-1}\bmod p=1$.
Um inteiro adequado $a_2$, e o único no alcance $[0,p-1)\,$, é ${a_1}^{-1}\bmod(p-1)\,$: o inverso multiplicativo de$a_1$ modulo $p-1$. Isso é o que é usado na solução oficial da questão .
O método clássico para calcular esse inverso multiplicativo é o algoritmo Euclidiano estendido . Para implementações práticas, eu recomendo esta variante que usa duas variáveis a menos e nunca manipula quantidades negativas.
A outra solução da questão difere apenas por computar o mesmo $a_2$ usando uma fórmula diferente: ${a_1}^{p-2}\bmod(p-1)$. Portanto, a questão se resume a:
Para prime $p>2$, por que / quando é isso $a^{-1}\bmod(p-1)$ pode ser calculado como $a^{p-2}\bmod(p-1)$ ?
Por definição, $a^{-1}\bmod(p-1)$ é o inteiro $x$ dentro $[0,p-1)$ com $a\,x\bmod(p-1)=1$. É definido apenas quando$a$ é coprime com $p-1$. Conclui-se que a pergunta é equivalente a:
Para prime $p>2$, por que / quando é isso $a^{p-1}\bmod(p-1)=1$ para todos $a$ coprime para $p-1$?
Isso é para muitos $p$ incluindo a questão $p=101$, Mas não sempre. O menor contra-exemplo é$p=11$, $a=3$. Outro isso$p=103$, $a=5$. Pode-se verificar que usando o segundo método para estes$p$ e as chaves de criptografia levam à descriptografia incorreta para a maioria $m$.
Estes são os primos do formulário A337119 (criado para a ocasião), começando com
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
Estes também são os primos $p$ de tal modo que $p-1$é um número Novák-Carmichael A124240 ; ou equivalentemente os primos$p$ de tal modo que $\lambda(p-1)$ divide $p-1$ (Onde $\lambda$é a função Carmichael ). Eles rapidamente diminuem como$p$ cresce.
Portanto, o segundo método da pergunta está errado em geral, e a maioria dos números primos$p$de interesse para o aplicativo em questão (já que podem ser grandes: mil bits). Provavelmente veio como uma extensão incorreta do seguinte fato: quando$p$ é principal, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ a menos que $a$ é um múltiplo de $p$, que segue do pequeno teorema de Fermat .
Na troca de três passagens da pergunta, $m'$ obtido por Bob no final é $m$ Desde a $$\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}$$