Главная Статьи Криптография

В основу одной из наиболее ранних криптосистем с открытым ключом была заложена задача о рюкзаке, которая считалась трудной при общем выборе начальных данных. Фактически, она принадлежит классу-полных задач, однако, можно показать, что криптосистема, основанная на ней, не является стойкой.

Ранее (см. стр. 393) мы ввели понятие проблемы выбора как задачи с односложным ответом: «да» или «нет». Мы показали, что некоторые другие задачи, например, задача о рюкзаке, сводится к такой проблеме. Аналогичная ситуация возникает в криптографии, где хотелось бы знать, является ли задача вычисления одного бита сообщения столь же сложной, как и задача вычисления всего сообщения. Предположим, что используется RSA-функция

Пусть А — конечная абелева группа простого порядка Q, порожденная элементом G. Рассмотрим предикат

: х → х (mod 2)

и докажем следующую теорему.

Теорема 16.6. Предикатявляется сильным для функции х

Задача RSA, а именно, уравнение С = (mod N), обладает следующими сильными предикатами:

- (m) = m (mod 2); - (m) = 0, если m <,(m) = 1 в противном случае; - (m) = m (mod), где k = O(ln ln N).

Мы уже отмечали, что недостатки криптографической схемы Меркля - Хеллмана и других криптосистем, основанных на теории сложности, возникают ввиду того, что эти схемы ассоциированы с трудными в общем случае, но легкими при средних значениях параметров проблемами. Возникает естественный вопрос: откуда мы знаем, что задача RSA или проблема выбора Диффи-Хеллмана избавлены от этого недостатка? Не может ли так оказаться, что при известных модуле N и шифрующей экспоненте Е уравнение

1. 16.5. Рандомизированные алгоритмы
2. Доказуемая стойкость со случайным оракулом
3. 17.2. Стойкость алгоритмов подписи
4. 17.2.1.1. Схема подписи Шнорра.
5. 17.2.1.2. DSA-noдnucu.
6. 17.2.1.3. EC-DSA-noдnиcи.
7. 17.2.2. Активный противник
8. 17.2.2.1. Схема подписи Шнорра.
9. 17.2.3. RSA-FDH
10. 17.2.4. RSA-PSS
11. 17.3. Стойкость шифрующих алгоритмов
12. 17.3.1. Иммунизация криптосистем, основанных на Эль-Гамаль
13. 17.3.1.1. Схема Женга-Себерри 1.
14. 17.3.1.2. Схема Женга-Себерри 2.
15. 17.3.1.3. Схема Женга-Себерри 3.
16. 17.3.2. RSA-OAEP
17. 17.3.3. Преобразование схем СРА в схемы ССА2
18. Доказуемая стойкость без случайного оракула
19. 18.2.1. Сильные RSA-предположения
20. 18.2.2. Интерактивные хэш-предположения Диффи - Хеллмана
21. 18.3. Схемы подписи
22. 18.3.1. Схема подписи Дженнаро-Галеви-Рабина
23. 18.3.2. Схема подписи Крамера-Шоупа
24. 18.4. Алгоритмы шифрования
25. 18.4.1. Схема шифрования Крамера-Шоупа
26. 18.4.2. Схема шифрования DHIES
27. А. 1. Множества
28. А.2. Отношения
29. А.З. Функции
30. А.4. Перестановки
31. A.5. Операции
32. А.6. Группы
33. А.6.1. Нормальные подгруппы и классы смежности
34. А.6.2. Факторгруппы
35. А.6.3. Гомоморфизмы
36. A.7. Кольца
37. А.8. Поля
38. А.9. Векторные пространства
39. А.9.1. Подпространства
40. А.9.2. Свойства векторов
41. А.9.3. Размерность и базисы
42. Приложение Б
43. Примеры на языке Java
44. Б. 1. Блочные шифры
45. Б.2. Шифрование с открытым ключом
46. Б.З. Хэш-функции
47. Б.4. Цифровые подписи
48. Б.5. Доказательства с нулевым разглашением и обязательства
49. Б.5.1. Parameters .Java
50. Б.5.2. Private_Commitment.java