ВУЗ:
Составители:
М
1
= (16
3
) mod 33 = 4096 mod 33 = 4,
М
2
= (1
3
) mod 33 = 1 mod 33 = 1,
М
3
= (15
3
) mod 33 = 3375 mod 33 = 9.
Таким образом, в результате расшифрования сообщения получено ис-
ходное сообщение "ГАЗ".
Криптостойкость алгоритма RSA основывается на предположении, что
исключительно трудно определить секретный ключ по известному, по-
скольку для этого необходимо решить задачу о существовании делителей
целого числа. Данная задача является NР – полной и, как следствие этого
факта, не допускает в настоящее время эффективного (полиномиального)
решения. Более того, сам вопрос существования эффективных алгоритмов
решения NР – полных задач является до настоящего времени открытым. В
связи с этим для чисел, состоящих из 200 цифр (а именно такие числа ре-
комендуется использовать), традиционные методы требуют выполнения
огромного числа операций (около 10
23
). Время выполнения наилучших из
известных алгоритмов разложения при п > 10
145
на сегодняшний день вы-
ходит за пределы современных технологических возможностей.
Существует вариант криптосистемы RSA, в которой вместо функции
Эйлера используется функция Кармайкла λ, где λ(n) – наименьшее целое t,
такое что для любого целого х, взаимно простого с п, выполняется х
t
= 1
mod п. Если п выбирается так, как описано выше, то λ(n) = НОК(р – 1, q –
1).
3.3.4. КРИПТОСИСТЕМЫ МЕРКЛЯ-ХЕЛЛМАНА И ХОРА-РИВЕСТА
Криптосистемы Меркля-Хеллмана и Хора-Ривеста основаны на ис-
пользовании односторонней функции, известной под названием "задача
укладки рюкзака".
Пусть имеется п объектов, так что можно составить п-компонентный
вектор f, в котором i-й компонент f представляет собой место, занимаемое
i-м объектом. Имеется рюкзак общим объемом K.
Тогда задачу укладки рюкзака можно сформулировать следующим
образом: даны f и K, и требуется найти битовый вектор х, такой что fx = K.
Доказано, что не существует эффективного алгоритма вычисления х по f и
K в общем случае. Таким образом, можно использовать вектор f для шиф-
рования n-битового сообщения х путем вычисления произведения K = f x.
Важно отметить, что выбор f является критическим. Предположим,
что f выбирается в виде супервозрастающей последовательности, тогда для
любого i
1
1
i
ij
j
f
f
−
=
>
∑
.
В этом случае при данных f и K вычислить х очень просто. Проверим,
является ли K большим, чем последний элемент f, и если да, то делаем по-
следний элемент х равным 1, вычитаем это значение из K и рекурсивно ре-
шаем меньшую проблему. Этот метод работает, поскольку когда K больше
последнего элемента f, даже если выбрать х = (1 1 1 ... 1 0), то произведение
fx все равно будет слишком маленьким, благодаря тому, что последова-
тельность супервозрастающая. Таким образом, необходимо выбирать еди-
ницу в последней позиции х.
Ясно, что выбор f очень важен: можно получить, а можно и не полу-
чить одностороннюю функцию. Однако, именно существование этого про-
стого случая позволяет создать функцию-ловушку, которую можно исполь-
зовать для построения криптосистемы с открытым ключом.
Пользователь А получает свой открытый ключ следующим образом:
1. Выбирает супервозрастающую последовательность f’, примерно,
из 100 элементов.
2. Выбирает случайное целое т, большее суммы элементов f’.
3. Выбирает другое случайное целое w, взаимно простое с т.
4. Теперь вычисляется f' умножением каждого компонента f на w по
модулю т; f' = f w (mod m).
5. Проводится случайная перестановка Р элементов f’ для получения
открытого ключа f.
Теперь А раскрывает ключ f и держит в секрете f’, m, w и P.
Когда пользователь В хочет послать А сообщение (битовый вектор) х,
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
