Алгоритм шифрования. Деление по модулю

Читаю как работает аглоритм шифрования с открытым ключем

Алгоритм Диффи-Хеллмана работает следующим образом.

Предположим, что двум абонентам ( P1 и P2 ) требуется установить между собой безопасное соединение, для которого необходимо согласовать ключ шифрования.
1. P1 и P2 принимают к использованию два больших целых числа a и b, причем 1 < a < b.
2. P1 выбирает случайное число i и вычисляет I = a^i mod b. P1 передает I абоненту P2.
3. P2 выбирает случайное число j и вычисляет J = a^j mod b. P2 передает J абоненту P1.
4. P1 вычисляет k1 = J^i mod b.
5. P2 вычисляет k2 = I^j mod b.
6. Имеем k1 = k2 = a^ (i*j) mod b, следовательно, k1 и k2 являются секретными ключами, предназначенными для использования при передаче других данных.

Вроде все понятно, но на шаге 4 вычисляется k1: k1 = J^i mod b, где J = a^j mod b,
следовательно есть какое-то правило, по которому (a^j mod b)^i mod b = a^ (i*j) mod b?

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
следовательно есть какое-то по которому

Какое-то что? Правило? Теорема?

(a^j mod b)^i mod b = a^ (i*j) mod b

Ну да, так и есть. Во-первых, (a^i)^j == a^(i*j), практически по определению возведения в степень. Во-вторых, утверждение в вопросе доказывается банально, если представить себе результат каждого шага как (p*b+q) (p, q конкретные именно для данного шага). В какую бы степень i не возвели это, ясно (хотя бы по биному Ньютона из школы), что результат будет состоять из кучи слагаемых, кратных b (нам неинтересных) и одного q^i. То есть, если вы возводите части в степень по модулю, неважно, каждое из умножений при этом возведении в степень отдельно делается по модулю (берётся остаток) или нет, итоговый результат идентичен. Если ещё непонятно, объясню примером: если натуральное число заканчивается на 2, его куб будет заканчиваться на 8, независимо от старших цифр; то же самое можно сказать для любого другого количества цифр (например, если число заканчивается на 12, его куб будет заканчиваться на 28).
В криптоматематике возведение в степень по модулю — отдельная операция, которая по-своему оптимизируется.

Спасибо за ответ. Буду детально вчитываться и разбираться

Какое-то что? Правило? Теорема?
Исправил


Отпишите здесь, если это видео не поможет.

Кстати, на youtu.be/vFjq9pID4-E?t=275 происходит совсем неочевидное для обывателя преобразование. А так да, все круто.

Да смотрел его — доходчиво объясняет, но опять же тот же вопрос преобразования там по умолчанию дается

Підписатись на коментарі