Однонаправленные функции

Вся концепция криптосистем с открытым ключом основана на применении однонаправленных функций (one way functions). Однако, точное определение этого класса функций с математической точки зрения дать достаточно сложно. Неформально однонаправленную функцию можно определить следующим образом.

Пусть X и Y - произвольные множества. Функция f(X) -> Y,
является однонаправленной, если для всех х, входящих в Х, легко вычислить функцию f(x), и в то же время для большинства y, входящих в Y, получить любое значение x, входящее в X, такое что f(x) = y достаточно сложно (при этом полагают, что существует, по крайней мере, одно такое значение x).

К сожалению, в настящее время математика не в состоянии дать нам ответ на вопрос, существуют ли таковые функции вообще или же это только красивая гипотеза. Тем не менее пытливым умам удалось обнаружить несколько зависимостей, которые могут быть использованы (и используются!) в качестве однонаправленных. Основной критерий причисления функции к классу однонаправленных очень прост - отсутствие эффективных алгоритмов обратного преобразования.

Простейший пример однонаправленной функции - целочисленное умножение. В самом деле, вычислить произведение двух очень больших целых чисел (имеется в виду, с помощью ЭВМ, а не вручную) достаточно легко, но даже самый мощный компьютер с наилучшими известными на сегодняшний день алгоритмами не в состоянии факторизовать (разделить на сомножители) двухсотзначное число, которое является произведением двух сопоставимых по длине простых чисел.

Вторым важным классом функций, используемых в практике построения систем с открытым ключом, являются так называемые однонаправленные функции с черным ходом (trap door one way function). Для порядка введем определение.

Функция f(X) -> Y относится к классу однонаправленных функций с черным ходом в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление инверсной функции, если известен "черный ход" (или, говоря по-русски, секретная строка, число или другая информация, ассоциирующаяся с данной функцией).

В двухключевых системах (несимметричные криптосистемы) каждым адресатом генерируются два ключа, связанные между собой по определенному правилу, но которые не возможно вычислить один из другого. Один ключ объявляется открытым, а другой закрытым. Открытый ключ публикуется и доступен любому, кто желает послать сообщение адресату. Секретный ключ сохраняется в тайне.

Исходный текст шифруется открытым ключом адресата и передается ему. Зашифрованный текст в принципе не может быть расшифрован тем же открытым ключом. Дешифрование сообщения возможно только с использованием закрытого ключа, который известен только самому адресату. Так как один из ключей является открытым, то эти системы называют криптосистемами с открытым ключом.

Криптографические системы с открытым ключом используют так называемые необратимые или односторонние функции, которые обладают следующим свойством: при заданном значении хотноси-тельно просто вычислить значение у =f(x), однако если известно у, то нет простого пути для вычисления значения х.

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

♦ разложение больших чисел на простые множители;

♦ вычисление дискретного логарифма;

♦ алгоритмы на основе задачи об укладки ранца;

♦ криптосистемы на эллиптических кривых.

Здесь же следует отметить, что двухключевые криптосистемы имеют многоцелевое назначение:

1) как состоятельные средства шифрации передаваемых и хранимых данных;

2) как средства для распределения ключей;

3) как средства аутентификации пользователей, включая создание электронной цифровой подписи.

БИЛЕТ №5

Криптографические системы защиты информации. Основные понятия криптографии.

Криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа.

Некоторые основные понятия и определения:

Алфавит - конечное множество используемых для кодирования информации знаков.

Текст -упорядоченный набор из элементов алфавита.

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

· алфавит Z₃₃ - 32 буквы русского алфавита и пробел;

· алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

· бинарный алфавит - Z₂ = {0,1};

· восьмеричный алфавит или шестнадцатеричный алфавит;

Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом.

Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляет собой семейство T преобразований открытого текста. xлены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптосистемы разделяются на симметричные и с открытым ключом (или асимметричесские).

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

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

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

Электронной (цифровой) подписью называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения.

Криптостойкостью называется характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. криптоанализу). Имеется несколько показателей криптостойкости, среди которых:

· количество всех возможных ключей;

· среднее время, необходимое для криптоанализа.

Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:

· зашифрованное сообщение должно поддаваться чтению только при наличии ключа;

· число операций, необходимых для определения использованного ключа шифрования по фрагменту шифрованного сообщения и соответствующего ему открытого текста,

· должно быть не меньше общего числа возможных ключей;

· знание алгоритма шифрования не должно влиять на надежность защиты;

· незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа; и т.д.

Криптографические методы являются наиболее эффективными средствами защиты информации в автоматизированных системах (АС).

Любой криптографический метод характеризуется такими показателями, как стойкость и трудоемкость:

· Стойкость метода - это тот минимальный объем зашифрованного текста, статистическим анализом которого можно вскрыть исходный текст.

· Трудоемкость метода - определяется числом элементарных операций, необходимых для шифрования одного символа исходного текста.

Поиск по сайту: