Криптосистема Эль-Гамаля.

Простейший алгоритм шифрования, основывающийся на дискретном логарифмировании, — это криптосистема Эль-Гамаль. В отличие от RSA, в алгоритме Эль-Гамаль существуют некоторые открытые параметры, которые могут быть использованы большим числом пользователей. Они называются параметрами домена и выглядят следующим образом:

- Р — «большое простое число», т. е. число, насчитывающее около 1024 битов, такое, что Р — 1 делится на другое, «среднее простое число» Q, лежащее неподалеку от

- G — элемент мультипликативной группы поля порядок которой, как мы знаем, делится на Q, причем

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

После выбора параметров домена определяют открытый и секретный ключи. Секретным ключом может априори быть любое натуральное число x, а открытый ключ получается по следующей формуле:Н = (mod P).

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

Сообщение в этой системе представляется ненулевым элементом поля m Для его шифрования поступают следующим образом:

- генерируют случайный эфемерный ключ k,

- вычисляют =

- находят = m •

- выдают получившийся шифротекст в виде пары С =

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

Чтобы расшифровать пару данных С = производят следующие преобразования:

Разберем небольшой пример, выбрав сначала параметры домена. Пусть

Q = 101, Р = 809 и G = 3.

Легко проверить, что Q действительно делит число Р — 1, а порядок элемента G в группе делится на Q. Порядок элемента G равен 808, поскольку

= 1 (mod P),

и ни при каких меньших степенях такого равенства не получается. В качестве пары открытого и секретного ключа выберем

х = 68 и Н= = =65(modP).

Допустим, нам нужно зашифровать сообщение, численное представление которого равно m = 100. Поступаем следующим образом.

- Генерируем случайный эфемерный ключ k = 89.

- Находим = = = 345 (mod P).

- Получаем = m · — 100 • = 517 (mod P).

- Отправляем шифротекст С = (345,517).

Партнер сможет восстановить текст, делая также вычисления:

Последнее равенство получается чуть более сложно, чем в вещественных числах: сначала число 345 возводится в степень 68 по модулю 809, вычисляется мультипликативный обратный к результату по этому же модулю, а затем найденный обратный умножается на 517. Позже мы увидим, что система Эль-Гамаль в том виде, о котором только что было рассказано, беззащитна против атак с выбором шифротекста. Поэтому обычно применяют модифицированные схемы шифрования. Тем не менее, Эль-Гамаль сможет выстоять против атаки с выбором открытого текста, если считать, что задача Диф-фи-Хеллмана трудна для решения. Опять-таки, здесь мы используем наивное понятие криптостойкости алгоритма, считая, что система защищена, если противник не сможет обратить шифрующую функцию.

Лемма 7.8. Если задача Диффи - Хеллмана трудноразрешима, то система Эль-Гамаль защищена против атак с выбором открытого текста, где защищенность означает, что нападающий не может восстановить открытый текст по перехваченной шифрограмме за разумное время.

Доказательство. Чтобы показать защищенность системы Эль-Гамаль от атак с выбором открытого текста в предположении о сложности задачи Диффи - Хеллмана, будем считать, что у нас есть оракул вскрывающий шифр Эль-Гамаль. На вход оракула подается открытый ключ Н и шифротекст а выходными данными служит дешифрованный открытый текст. Покажем теперь, как с помощью оракула решается задача Диффи - Хеллмана, т.е. даны

и

и требуется вычислить

Выберем открытый ключ в системе Эль-Гамаль в соответствии с поставленной задачей, т. е. положим

Н =

Заметим, что мы не знаем секретного ключа х. Теперь выписываем «шифротекст»:

С =

где а случайный элемент поля Вводим этот ши-

фротекст в оракул, взламывающий Эль-Гамаль, и получаем соответствующий открытый текст М = который по расшифровывающей процедуре Эль-Гамаль должен получаться в виде отношения М = Используя полученные данные, мож;но решить исходную задачу Диффи-Хеллмана, вычисляя

Дата добавления: 2015-12-01