5. Второй этап развития криптографии

5.1 Шенноновское понятие секретных систем

По Шеннону существует три общих типа секретных систем:

1. Системы маскировки, которые включают в себя применение таких методов, как невидимые чернила, представление сообщения в форме безобидного текста или маскировки криптограммы, и другие методы, с помощью которых факт наличия сообщения скрывается от противника;

2. Тайные системы (например, инвертирование речи), в которых для раскрытия сообщения требуется специальное оборудование;

3. «Собственно» секретные системы, где смысл сообщения скрывается при помощи шифра, кода и т.д., но само существование сообщения не скрывается и предполагается. Что противник обладает любым специальным оборудованием, необходимым для перехвата и записи переданных сигналов.

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

Оценка секретных систем.

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

1) Количество секретности.

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

2) Объем ключа.

Ключ должен быть передан из передающего пункта в приемный пункт таким способом, чтобы его нельзя было перехватить. Иногда его нужно запомнить. Поэтому желательно иметь ключ настолько малый, насколько это возможно.

3) Сложность операции шифрования и дешифрования.

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

4) Разрастание числа ошибок.

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

5) Увеличение объема сообщения.

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

Совершенная секретность.

Предположим, что имеется конечное число возможных сообщений. с априорными вероятностями и что эти сообщения в возможные криптограммы , так что - отображение, которое приводит сообщение к криптограмме .

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

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

где - априорная вероятность сообщения ;

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

- вероятность получения криптограммы ;

- апостериорная вероятность сообщения при условии, что перехвачена криптограмма .

Для совершенной секретности системы величины и должны быть равны для всех и . Следовательно, должно быть выполнено одно из равенств:

или же , для любых и .

Если , то , и система совершенно секретна.

Теорема.

Необходимое и достаточное условие для совершенной секретности состоит в том, что

для всех и , т.е. не должно зависеть от .

Ненадежность.

Имеется два основных типа ненадежности: ненадежность ключа и ненадежность сообщения.

- ненадежность ключа;

- ненадежность сообщения.

,

,

где , , - криптограмма, сообщение, ключ.

- вероятность ключа и криптограммы .

- апостериорная вероятность ключа , если перехвачена криптограмма .

- вероятность сообщения и криптограммы .

- апостериорная вероятность сообщения , если перехвачена криптограмма .

Для кода подстановки.

6. Третий этап развития криптографии

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

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

6.1 Шифр Ривеста - Шамира - Алдемана

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

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

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

Чтобы восстановить исходный текст, поступает следующим образом:

1. Находит число , такое, что и .Это сравнение разрешимо единственным образом, поскольку .

Для решения сравнения пользователь должен вычислить .

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

Алгоритм применения RSA.

1. Отправитель выбирает два больших простых числа и . Вычисляет два произведения и

2. Затем он выбирает случайное число (целое), взаимно простое с , и вычисляет , удовлетворяющее условию .

3. После этого он публикует и как свой открытый ключ шифрования, сохраняя как закрытый ключ.

4. Если - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале , то она превратится в криптограмму возведением в степень по модулю и отправляется получателю в следующем виде .

5. Получатель сообщения расшифровывает его. Возводя в степень по модулю , так как

Пояснение.

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

Электронная подпись (цифровая подпись).

Если планирует подписывать документ Ц.П., то он должен выбрать параметры RSA. выбирает два простых числа и , вычисляет затем выбирает число ,взаимно простое с , и вычисляет , далее публикует числа и и хранит в секрете . Числа - более не понадобятся.

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

Практически невозможно изменить основной текст , не изменив . Поэтому достаточно снабдить только число подписью, и эта подпись будет относиться ко всему сообщению .

Далее вычисляет число , т.е. она возводит число в свою секретную степень. Число - цифровая подпись.

- вид сообщения с подписью.

Теперь каждый, кто знает открытые параметры , т.е. и , может проверить подлинность его подписи.

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

/*Пример*/ Электронная подпись RSA.

Пусть

(алгоритм Евклида).

(допущение)

вычисляет

- сообщение с подписью

Вычисляем значение хеш-функции, получим

Подпись верна.

Определение Хеш-функции.

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

9. Криптографические алгоритмы

9.1 Шифр Эль-Гамаля

Пусть имеются абоненты , которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищённых каналов связи.

Для всей группы абонентов выбирается некоторое большое простое число и число , такие, что различные степени - различные числа по модулю . Числа и передаются абонентам в открытом виде.

Затем каждый абонент выбирает своё секретное число , , и вычисляет соответствующе ему открытое число ,

()

В результате получаем следующую таблицу ().

Табл(). Ключи пользователей в системе Эль=Гамаля.

Алгоритм передачи сообщения от к выглядит следующим образом: будем считать, что сообщение .

Шаг 1. Алиса формирует случайное число , , вычисляет числа:

(9.1.2)

(9.1.3)

и передаёт пару чисел абоненту Бобу.

Шаг 2. Боб, получив , вычисляет

(9.1.4)

/*Пример*/

Алиса хочет передать Бобу сообщение . Допустим Пусть Боб выбрал для себя секретное число и вычислил по формуле (9.1.1)

Алиса выбирает случайное число , например , и вычисляет по (9.1.2) и (9.1.3):

.

Теперь Алиса посылает Бобу шифрограмму (17,12). Боб вычисляет по формуле (9.1.4):

Боб расшифровал сообщение

Электронная подпись на базе Эль-Гамаля.

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

Затем она вычисляет число

(9.1.5)

Это число Алиса публикует в качестве открытого ключа. Заметим, что при больших , зная , невозможно найти (это задача дискретного логарифмирования).

Теперь Алиса может подписывать сообщения. Допустим, она хочет подписать сообщение . Опишем последовательность действий для построения подписи.

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

(9.1.6)

Далее Алиса вычисляет числа:

(9.1.7)

(9.1.8).

Под в (9.1.8) подразумевается число, удовлетворяющее уравнению

Страницы: 1, 2, 3, 4, 5