Трудные задачи. Необратимые функции. Эллиптические кривые
Криптосистемы открытого ключа основаны на задаче, которую трудно решить. Понятие «трудно» в данном случае подразумевает высокую слож-ность вычислений для поиска решения, но не концепцию задачи. Такие задачи называются трудными, или трудноразрешимыми. Наиболее известные примеры таких задач — поиск сомножителей (факторинг), доказательство теорем и проблема коммивояжера.
Существуют два главных класса задач, которые представляют интерес для криптографии: полиномиальные (Polynomial, Р) — если задача решается за количество времени (или действий), которое можно выразить полиномом, и неполиномиальные (NonPolynomial, NP) — если за время или за количество действий, описываемое полиномом, можно лишь оценить правильность предложенного решения.
Односторонней функцией называется такая математическая функция, которая значительно легче вычисляется в одном направлении (прямом), чем в противоположном (обратном). Например, для вычисления функции в прямом направлении требуются секунды, а для вычисления в обратном направлении — месяцы и годы, если обратное вычисление вообще возможно.
Криптосистемы открытого ключа основаны на односторонних функциях (точнее, известных как односторонние), имеющих «лазейку», которой является частный ключ. Тот, кому известна «лазейка» (частный ключ асимметричной криптосистемы), может легко вычислить функцию в обоих направлениях, но, не зная «лазейки», можно рассчитать функцию только в прямом направлении. Прямое направление используется для проверки подписи и для шифрования информации, обратное же — для создания подписи и расшифровывания.
Эллиптические кривые — это математические конструкции теории чисел и алгебраической геометрии, которые в недавние годы нашли многочисленные применения в криптографии.
Эллиптическая кривая состоит из всех элементов (х; у), удовлетворяющих уравнению
У2 = х3 + ах+ b,
и отдельного элемента, обозначаемого О и называемого «точка в бесконечности», который является точками вверху и в основании каждой вертикальной линии.
-
Содержание
- Оглавление
- Понятие защиты информации. Цели защиты информации
- Предметные области защиты информации
- Классификация средств защиты информации
- История развития криптологии
- 1949 – 1976. Классическая криптология. (с закрытым ключом)
- 1976 Года. Криптография с открытым ключом
- Отрасли криптологии. Основные понятия криптологии
- Симметричные криптосистемы
- Криптосистемы с открытым ключом.
- Криптографические методы защиты информации
- Классификация методов криптографического преобразования данных
- 2. Кодирование
- Шифрование. Шифры замены и перестановки. Схема шифрования Виженера
- Шифрование методом аналитических преобразований
- Гаммирование и комбинированные методы шифрования
- Кодирование
- Блочное и поточное шифрование. Шифры Фейстеля. Режимы шифрования
- Симметричные криптосистемы
- Криптосистемы с открытым ключом
- Алгоритмы des и aes. Достоинства и недостатки
- Алгоритмы rsa и dsa. Достоинства и недостатки
- Трудные задачи. Необратимые функции. Эллиптические кривые
- Хэширование и хэш-функции. Коллизии хэш-функций
- Алгоритм md5
- Стеганография
- Криптоанализ и его задачи
- Основные и дополнительные типы криптоаналитических атак
- Атака на основе подобранного ключа
- Условия эффективности криптоанализа
- Законы и нормативные акты рб в области защиты информации
- Международное регулирование в криптографии.