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

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

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

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

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

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

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

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

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

Теорема.

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

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

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

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

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

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

,

,

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

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

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

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

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

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

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) подразумевается число, удовлетворяющее уравнению

(9.1.9)

Такое существует, так как и взаимно просты, и может быть найдено по алгоритму Евклида. Наконец Алиса формирует подписанное сообщение

(9.1.10).

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

(9.1.11)

/*Пример*/

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

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

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