Две формулы работают для этой задачи трехходового обмена, но я не могу понять, почему одна из них работает
Постановка задачи:
"Предположим, что пользователи Алиса и Боб выполняют трехпроходный протокол Диффи-Хеллмана с p = 101. Предположим, что Алиса выбирает 1 = 19, а Боб выбирает b 1 = 13. Если Алиса хочет отправить секретное сообщение m = 5 пользователю Боб, покажи все сообщения, которыми обменивались Алиса и Боб ".
Официальное решение:
$a_2 = {a_1}^{-1}\bmod(p-1)=79$
$b_2=77$
Алиса → Боб: $m^{a_1}\bmod p=37$
Боб → Алиса: $80$
Алиса → Боб: $56$
Боб получает $m$ оценивая $56^{b_2}\bmod p=5$
Решение, которое я сделал, воспользовавшись чьей-то помощью (поскольку я не могу найти в Интернете очень конкретной информации об этом трехпроходном протоколе):
Алиса:
$\begin{align} a_2&={a_1}^{p-2}\bmod(p-1)\\ &=19^{99}\bmod100\\ &=79\end{align}$
Боб:
$\begin{align} b_2&={b_1}^{p-2}\bmod(p-1)\\ &=13^{99}\bmod100\\ &=77\end{align}$
Алиса Бобу №1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Боб Алисе (№1 - №2 нет):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Алиса Бобу # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Боб получает следующее сообщение:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Мой вопрос:
Почему в официальном решении используется $a_2={a_1}^{-1}\bmod(p-1)=79$ вместо $a_2={a_1}^{p-2}\bmod(p-1)=79$, и как можно обосновать эту эквивалентность в контексте проблемы такого типа ? (Я говорю «в контексте проблемы этого типа», потому что, насколько я понимаю, эти два выражения не всегда эквивалентны).
Любой вклад, который мог бы помочь мне прояснить мое замешательство, был бы ОЧЕНЬ благодарен!
PS
- $a_1$ ключ шифрования Алисы
- $a_2$ ключ дешифрования Алисы
- $b_1$ ключ шифрования Боба
- $b_2$ ключ дешифрования Боба
Ответы
TL; DR: второй метод работает только для исчезающей доли простых чисел $p$.
В вопросе используется то же отношение между $a_1$ и $a_2$как в симметричном шифре Поляга-Хеллмана. В этом:
- $p$ является общедоступным основным параметром,
- ключ шифрования - случайное целое число $a_1$ совмещать с$p-1$,
- ключ дешифрования - целое число $a_2$ такой, что $a_1\,a_2=k\,(p-1)+1$ для некоторого целого числа $k$.
- шифрование за $m\mapsto c=m^{a_1}\bmod p$, за $m$ в $[0,p)$,
- расшифровка за $c\mapsto m'=c^{a_2}\bmod p$, и он держит $m'=m$.
Доказательство: $$\begin{align} m'&=c^{a_2}\bmod p&&\text{by construction of $м '$}\\ &=(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 $а_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 $м$ is in $[1, п)$} \end{align}$$
Примечание: маленькая теорема Ферма говорит, что когда$p$ прост и $m$ не является кратным $p$, он держит $m^{p-1}\bmod p=1$.
Одно подходящее целое число $a_2$, и единственный в диапазоне $[0,p-1)\,$, является ${a_1}^{-1}\bmod(p-1)\,$: Мультипликативный обратный из$a_1$ по модулю $p-1$. Это то, что используется в официальном решении вопроса .
Методом из учебника для вычисления этого мультипликативного обратного является Расширенный алгоритм Евклида . Для практических целей я рекомендую этот вариант, в котором используется на две переменных меньше и никогда не используются отрицательные величины.
Другое решение вопроса отличается только вычислением того же $a_2$ используя другую формулу: ${a_1}^{p-2}\bmod(p-1)$. Итак, вопрос сводится к следующему:
Для премьер $p>2$, почему / когда это $a^{-1}\bmod(p-1)$ можно вычислить как $a^{p-2}\bmod(p-1)$ ?
По определению, $a^{-1}\bmod(p-1)$ это целое число $x$ в $[0,p-1)$ с участием $a\,x\bmod(p-1)=1$. Он определяется только тогда, когда$a$ взаимно прост с $p-1$. Отсюда следует, что вопрос эквивалентен:
Для премьер $p>2$, почему / когда это $a^{p-1}\bmod(p-1)=1$ для всех $a$ взаимно простой с $p-1$?
Это для многих $p$ включая вопрос $p=101$, но не всегда. Самый маленький контрпример:$p=11$, $a=3$. Другое это$p=103$, $a=5$. Можно проверить, что использование второго метода для этих$p$ и ключи шифрования приводят к неправильной расшифровке для большинства $m$.
Это простые числа формы A337119 (созданные по случаю), начиная с
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
Это также простые числа $p$ такой, что $p-1$номер Новака-Кармайкла A124240 ; или, что то же самое, простые числа$p$ такой, что $\lambda(p-1)$ разделяет $p-1$ (где $\lambda$- функция Кармайкла ). Они быстро истончаются по мере$p$ растет.
Следовательно , второй метод вопроса в целом неверен , и большинство простых чисел$p$представляют интерес для данного приложения (поскольку они очень большие: тысяча бит). Вероятно, это произошло как неправильное продолжение следующего факта: когда$p$ простое, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ если только $a$ кратно $p$, что следует из малой теоремы Ферма .
В трехпроходном обмене вопроса, $m'$ полученный Бобом в итоге $m$ поскольку $$\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}$$