Due formule funzionano per questo problema di scambio a tre passaggi, ma non riesco a capire perché una di esse funzioni
Dichiarazione problema:
"Supponiamo che gli utenti Alice e Bob eseguano il protocollo Diffie-Hellman a 3 passaggi con p = 101. Supponiamo che Alice scelga a 1 = 19 e Bob scelga b 1 = 13. Se Alice vuole inviare il messaggio segreto m = 5 a Bob, mostra tutti i messaggi scambiati tra Alice e Bob. "
Soluzione ufficiale:
$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 ottiene $m$ valutando $56^{b_2}\bmod p=5$
Soluzione che ho fatto usando l'aiuto di qualcuno (poiché non riesco a trovare informazioni molto specifiche su questo protocollo a tre passaggi 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 a Bob # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob ad Alice (# 1 - non c'è # 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 ottiene il messaggio come segue:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
La mia domanda:
Perché la soluzione ufficiale usa $a_2={a_1}^{-1}\bmod(p-1)=79$ invece di $a_2={a_1}^{p-2}\bmod(p-1)=79$, e come può essere giustificata tale equivalenza nel contesto di questo tipo di problema ? (Dico "nel contesto di questo tipo di problema" perché, a quanto mi risulta, le due espressioni non sono sempre equivalenti).
Qualsiasi input che potrebbe aiutarmi a chiarire la mia confusione sarebbe molto apprezzato!
PS
- $a_1$ è la chiave di crittografia di Alice
- $a_2$ è la chiave di decrittazione di Alice
- $b_1$ è la chiave di crittografia di Bob
- $b_2$ è la chiave di decrittazione di Bob
Risposte
TL; DR: il secondo metodo funziona solo per una proporzione evanescente di numeri primi $p$.
La domanda utilizza la stessa relazione tra $a_1$ e $a_2$come nel cifrario simmetrico di Pohlig-Hellman. In questo:
- $p$ è un parametro primario pubblico,
- la chiave di crittografia è un numero intero casuale $a_1$ coprimo con$p-1$,
- la chiave di decrittazione è un numero intero $a_2$ tale che $a_1\,a_2=k\,(p-1)+1$ per un numero intero $k$.
- la crittografia è per $m\mapsto c=m^{a_1}\bmod p$, per $m$ in $[0,p)$,
- la decrittazione è per $c\mapsto m'=c^{a_2}\bmod p$e tiene $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: il piccolo teorema di Fermat dice che quando$p$ è primo e $m$ non è un multiplo di $p$, Tiene $m^{p-1}\bmod p=1$.
Un numero intero adatto $a_2$e l'unico nel raggio d'azione $[0,p-1)\,$, è ${a_1}^{-1}\bmod(p-1)\,$: l' inverso moltiplicativo di$a_1$ modulo $p-1$. Questo è ciò che viene utilizzato nella soluzione ufficiale della domanda .
Il metodo da manuale per calcolare quell'inverso moltiplicativo è l' algoritmo euclideo esteso . Per implementazioni pratiche, consiglio questa variante che utilizza due variabili in meno e non manipola mai quantità negative.
L'altra soluzione della domanda differisce solo calcolando lo stesso $a_2$ utilizzando una formula diversa: ${a_1}^{p-2}\bmod(p-1)$. Quindi la domanda si riduce a:
Per primo $p>2$, perché / quando è così $a^{-1}\bmod(p-1)$ può essere calcolato come $a^{p-2}\bmod(p-1)$ ?
Per definizione, $a^{-1}\bmod(p-1)$ è il numero intero $x$ in $[0,p-1)$ con $a\,x\bmod(p-1)=1$. È definito solo quando$a$ è coprimo con $p-1$. Ne consegue che la domanda è equivalente a:
Per primo $p>2$, perché / quando è così $a^{p-1}\bmod(p-1)=1$ per tutti $a$ coprime a $p-1$?
Questo è per molti $p$ compresa la domanda $p=101$, ma non sempre. Il più piccolo controesempio è$p=11$, $a=3$. Un altro esso$p=103$, $a=5$. Si può verificare che utilizzando il secondo metodo per questi$p$ e le chiavi di crittografia portano alla decrittazione errata per la maggior parte $m$.
Questi sono i numeri primi del modulo A337119 (creato per l'occasione), a cominciare da
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
Anche questi sono i numeri primi $p$ tale che $p-1$è un numero Novák-Carmichael A124240 ; o equivalentemente i numeri primi$p$ tale che $\lambda(p-1)$ divide $p-1$ (dove $\lambda$è la funzione di Carmichael ). Si diradano rapidamente come$p$ cresce.
Quindi il secondo metodo della domanda è sbagliato in generale e la maggior parte dei numeri primi$p$di interesse per l'applicazione a portata di mano (poiché sono poltiglia grandi: mille bit). Probabilmente è stata un'estensione errata del fatto seguente: quando$p$ è il primo, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ salvo che $a$ è un multiplo di $p$, che segue dal piccolo teorema di Fermat .
Nello scambio in tre passaggi della domanda, $m'$ ottenuto da Bob alla fine è $m$ da $$\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}$$