Интернет магазин китайских планшетных компьютеров

Компьютеры - Ранцевая криптосистема Меркля-Хеллмана - Математическое описание алгоритма

Генерация ключа

Чтобы зашифровать n-битное сообщение, выберем супервозрастающую последовательность из n ненулевых натуральных чисел

w =.

Далее случайным образом выберем целые взаимно простые числа q и r такие, что

.

Число q выбирается таким образом, чтобы гарантировать единственность шифротекста. В случае, если оно будет хотя бы чуть меньше, может возникнуть ситуация, что одному шифротексту будут соответствовать несколько исходных текстов. r должно быть взаимно просто с q, в противном случае оно не будет иметь мультипликативного обратного по модулю q, существование которого необходимо для расшифровки.

Теперь построим последовательность

β =,

где каждый элемент вычисляется по следующей формуле

β_i = rw_i mod q.

β будет открытым ключом, в то время как закрытый ключ образует последовательность.

Шифрование

Чтобы зашифровать n-битное сообщение

α =,

где α_i - это i-ый бит, т.е. {0, 1}, вычислим число c, которое и будет шифротекстом.

Расшифровка

Чтобы прочитать исходный текст, получатель должен определить биты сообщения α_i, которые удовлетворяли бы формуле

Такая задача имела бы полиномиальную сложность в случае, если бы β_i были случайно выбранными значениями. Однако значения β_i были выбраны таким образом, что расшифровка сводится к простой задаче при условии, что открытый ключ известен.

Ключ к определению исходного текста заключается в том, чтобы найти целое число s, которое является мультипликативным обратным r по модулю q. Это значит, что s удовлетворяет уравнению sr mod q = 1, что эквивалентно существованию целого числа k такого, что sr = kq + 1. Поскольку r взаимно просто с q, найти s и k возможно с использованием расширенного алгоритма Евклида. Далее получатель шифротекста вычисляет

Отсюда

Из того, что rs mod q = 1 и β_i= rwi mod q, следует

Тогда

Сумма всех w_i меньше, чем q. Отсюда значение также находится в интервале. Таким образом, получатель должен определить α_i из условия, что

.

А это уже простая задача, поскольку w - супервозрастающая последовательность. Пусть w_k – наибольший элемент в w. Если w_k > c' , то α_k = 0; если w_k ≤c' , то α_k = 1. Далее вычитаем произведение w_k×α_k из c' и повторяем эти шаги до тех пор, пока не вычислим α.