Разложение числа на простые сомножители. Вычислить произведение двух простых чисел очень просто. Однако для решения обратной задачи эффективного алгоритма в настоящее время не существует.
В качестве примеров задач, приводящих к односторонним функциям, можно привести следующие.
Функцией-ловушкой называется односторонняя функция, для которой обратную функцию вычислить просто, если имеется некоторая дополнительная информация, и сложно, если такая информация отсутствует.
Неформально под односторонней функцией понимается эффективно вычислимая функция, для обращения которой (т.е. нахождения хотя бы одного значения аргумента по известному значению функции) не существует эффективных алгоритмов. Заметим, что обратная функция может не существовать.
Центральным понятием в теории ассиметричных криптосистем является понятие односторонней функции.
Ассимметричные криптосистемы
Еще одним обширным классом криптосистем являются так называемые ассиметричные, или двухключевые криптосистемы .
Рис. 5.2
Эти системы характеризуются тем, что для шифрования и расшифрования используются разные ключи, связанные между собой некоторой зависимостью. При этом данная зависимость такова, что установить один ключ, зная другой, с вычислительной точки очень трудно.
Один из ключей, например, ключ шифрования, можно сделать общедоступным (открытым). Тогда любой пользователь может послать зашифрованное сообщение данному абоненту, которое он расшифрует с помощью второго (секретного) ключа. Если сделать общедоступным ключ расшифрования, то на базе полученной системы можно построить систему аутентификации передаваемых сообщений, так как любой абонент, получивший послание, может проверить его подпись с помощью ключа расшифрования. Поскольку один из пары ключей общедоступен, то такие системы получили название криптосистем с открытым ключом.
Криптосистема с открытым ключом определяется темя алгоритмами: генерации ключей, шифрования и расшифрования. Алгоритм генерации ключей открыт, всякий может подать на вход генератора ключей случайную строку и получить пару ключей (k1, k2). Один из ключей публикуется, он называется открытым, а второй, называемый секретным, хранится в тайне.
Односторонние функции и функции-ловушки
2. Дискретное логарифмирование в конечном простом поле (проблема Диффи-Хелмана). Допустим, задано большое простое число p и пусть g – примитивный элемент поля GF (p). Тогда для любого a вычислить ga (mod p) просто, а вычислить a по заданным k = ga (mod p) и p оказывается затруднительным.
Криптосистемы с открытым ключом основываются на одностронних функциях-ловушках. При этом открытый ключ определяет конкретную реализацию функции, а секретный ключ дает информацию о ловушке. Любой, знающий ловушку, может легко вычислять функцию в обоих направлениях, но тот, у кого такой информации нет, может производить вычисления только в одном направлении. Прямое направление используется для шифрования и верификации цифровых подписей, а обратное – для расшифровки и выработки цифровой подписи.
Во всех криптосистемах с окрытым ключом чем больше длина ключа, тем выше различия между усилиями, необходимыми для вычисления функции в прямом и обратном направлениях (для того, кто не обладает информацией о ловушке).
Пример
Пусть абоненты А и В решили наладить секретную переписку с открытым ключом. Тогда каждый из них независимо от другого выбирает два больших простых числа, находит их произведение, находит функцию Эйлера от этого произведения и выбирает случайное число, меньшее этого вычисленного значения. Функция Эйлера φ(p) равна количеству чисел, меньших p и взаимнопростых с p, т.е. не имеющих с числом p общих делителей кроме единицы; при этом если p – простое число, то φ(p) = p-1.
Итак:
A: p1, p2 , rA = p1∙ p2 , φ(rA), (a, φ(rA)) = 1, 0 < a < φ(rA)
Затем печатается телефонная книга, доступная всем желающим, которая имеет вид:
Абонент
А
В
Открытые ключи
rA, a
rB, b
Здесь rA – произведение двух простых чисел p1, p2, известных только абоненту А; а – открытый ключ, доступный каждому, кто хочет передать сообщение А;
rB – произведение двух простых чисел q1, q2, известных только абоненту B; b – открытый ключ, доступный каждому, кто хочет передать сообщение B.
Каждый из абонентов находит свой секретный ключ из сравнений:
A: α: αa ≡ 1(mod φ(rA)), 0 < α < φ(rA)
B: β: βb ≡ 1(mod φ(rB)), 0 < β < φ(rB)
Получаем следующую таблицу ключей:
Абонент
Открытые ключи
Секретные ключи
А
rA, a
α
В
rB, b
β
Пусть абонент А решает послать сообщение m абоненту В:
А: m→ B и пусть 0 < m < rB, иначе текст делят на куски длиной rB.
Далее абонент А шифрует свое сообщение m открытым ключом абонента В и находит
m1 = mb (mod rB), 0 < m1 < rB
Абонент В расшифровывает это сообщение своим секретным ключом:
m2 = m1β (mod rB), 0 < m2 < rB
и получает m2 = m.
Опустим формальное доказательства тождественности этих преобразований и проверим метод на конкретных числовых данных.
Пусть
p1 = 7 p2 = 23 - простые числа А
rA = p1∙ p2 =161 φ(rA) = 132
q1 = 11 q2 = 17 - простые числа В
rB = q1∙ pq2 = 187 φ(rB) = 160
a = 7 b = 9 – случайные числа, выбранные А и В соответственно.
Телефонная книга:
А: 161, 7
В: 187, 9
Каждый из абонентов находит свой секретный ключ:
А: 7∙α ≡ 1 (mod 132) → α = 19
B: 9∙β ≡ 1 (mod 160) → β = 89
Пусть абонент А решает послать абоненту В сообщение m =3.
Тогда он шифрует свое сообщение открытым ключом абонента В:
m1 ≡ 39≡ 48 (mod 187)
Абонент расшифровывает это сообщение своим секретным ключом:
m2 ≡ 4889≡ 3 (mod 187)
Следовательно m2 = m =3.
Способы и методы сокрытия секретных сообщений известны с давних времен, причем данная сфера получила название “стеганография”. Слово происходит от греческих слов steganos – секрет, тайна и graphy – запись, т.е. означает буквально “тайнопись”.
Стеганография в отличие от криптографии имеет другую задачу; ее цель – скрыть сам факт существования секретного сообщения. При этом оба способа могут быть объединены и использованы для повышения эффективности защиты информации.
Методы стеганографии известны с древности. Хорошо известны различные способы скрытого письма между строк обычного, незащищенного письма – для этого используются специальные “невидимые” чернила. Другие способы включают в себя использование микрофотоснимков, незначительные различия в написании рукописных символов, маленькие проколы определенных символов в сообщении множество других приемов сокрытия сообщения.
Компьютерные технологии придали новый импульс развитию и совершенствованию стеганографии, появилось новое направление в области защиты информации – компьютерная стеганография (КС). Методы КС, используя естественные неточности устройств оцифровки и избыточность аналогового видео- и аудиосигналов, позволяют скрывать сообщения в компьютерных файлах.
В современной КС существует два типа файлов: сообщение – файл, который необходимо скрыть, и контейнер – файл, который используется для скрытия в нем сообщения. Контейнеры бывают двух типов: контейнер-оригинал (“пустой” контейнер) - это контейнер, который не содержит скрытой информации, и контейнер-результат – это контейнер, содержащий скрытую информацию. Под ключом в КС понимается секретный элемент, который определяет порядок занесения сообщения в контейнер.
Основные положения КС:
1. Методы скрытия должны обеспечивать аутентичность и целостность файла.
2. Предполагается, что противнику полностью известны возможные стеганографические методы.
3. Безопасность методов основывается на сохранении стеганографическим преобразованием основных свойств открыто передаваемого файла при внесениив него секретного сообщения и некоторой неизвестной противнику информации – ключа.
4. Даже если факт скрытия сообщения стал известен противнику, извлечение секретного сообщения представляет собой сложную вычислительную задачу.
В связи с распространением глобальных компьютерных сетей значение стеганографии все более возрастает. В настоящее время стеганографические системы активно используются для решения следующих задача:
- защита конфиденциальной информации от НСД;
- камуфлирование программного обеспечения;
- защита авторского права на некоторые виды интеллектуальной собственности;
- преодоление систем мониторинга и управления сетевыми ресурсами.
Рассмотрим, какими способами можно скрыть сообщение в файлах.
Можно использовать зарезервированные для рашсширения поля компьютерных форматов данных – такие поля в обычном состоянии заполнены нулевой информацией и не учитываются программами.
Для сокрытия информации в текстовых файлах используется специальное форматирование файлов, вставка дополнительных пробелов между словами, предложениями и абзацами, выбор определенных позиций букв в тексте (акростих – один из этих методов).
Информацию можно скрыть в неиспользуемых местах накопителей информации на магнитных дисках (например, на нулевой дорожке или в блоках, помеченных как поврежденные).
Наконец, для сокрытия информации (и это главный метод) используется избыточность цифровых видео-, аудио- и фотоданных. Младшие разряды цифровых отсчетов содержат очень мало полезной информации, и их заполнение дополнительной информацией практически не влияет на качество восприятия мультимедийных файлов.
