Почему при обмене ключами Диффи-Хеллмана используются простые числа?

Простые числа не разбиваются на более мелкие множители, что значительно усложняет взлом кода или хеш-функции, чем использование, скажем, 12, которое разбивается на /2, /3, /4 или /6. Простое число 7 меньше 12, но имеет только коэффициент 7, поэтому векторов атаки меньше. Это сильное упрощение, но, надеюсь, немного поможет.

Вот конкретный пример:

2^х мод 12

Это имеет только 2 возможных значения для любого x выше 1: 4 или 8. Поскольку это используется для генерации общего ключа аналогичным образом, вы получаете те же две возможности. Другими словами, как только вы узнаете, что база и модификация равны 2 и 12 (которые любой компьютер, прослушивающий разговор, сможет уловить), вы автоматически узнаете, что общий секретный ключ шифрования может быть только одним из двух возможных. Требуется всего две простые операции, чтобы определить, какая из них расшифровывает сообщение. Теперь давайте посмотрим на основной мод:

2^х мод 13

Это имеет 12 различных возможностей для x>1. Он также имеет 12 различных возможных общих ключей, которые можно сгенерировать. Таким образом, для расшифровки сообщения на основе этого простого модуля требуется в 6 раз больше вычислительной мощности, чем в примере с модом 12.

2^x mod 14 имеет 4 возможности.

2^x мод 15 имеет 4

2^x mod 16 полностью превращается в 1 возможность после x=3 (поэтому важно выбрать базу, соответствующую требованиям DH)

2^x mod 17 имеет... как вы уже догадались, 16 возможностей! Разве простые числа не круты? :)

Таким образом, факторизуемость числа модуля напрямую связана с возможностью взлома зашифрованного сообщения.