Р. Меркле – автор идеи об открытых ключах
Короткая Полина Андреевна
студент гр. ИВС–18, РГАТУ имени П. А. Соловьева
Гусаров Александр Вячеславович
канд. техн. наук, доцент кафедры ВС, РГАТУ имени П. А. Соловьева
Если задать вопрос о том, кто является основоположником несимметричной криптографии (криптографии с открытым ключом), то те, кто знаком с этой областью знаний, конечно же ответят, что это У. Диффи и М. Хеллман. Именно они предложили первый действующий протокол передачи информации, использующий криптографию с открытым ключом, в своей работе «Новые направления в современной криптографии», опубликованной в 1976 г. [1]. В ней был описан метод получения секретного ключа при помощи алгоритма, названного по их фамилиям – протокол Диффи-Хеллмана. Однако они были не первыми в этом вопросе. Сам М. Хеллман в 2002 г. предложил назвать алгоритм, предложенный им вместе с У. Диффи, алгоритмом Диффи-Хеллмана-Меркле [1]. Американский математик и криптограф Р. Меркле предложил свой метод получения секретного ключа в 1974 г., а опубликовал его в 1978 г. [1]. Дело в том, что У. Диффи и М. Хеллман вдохновились идеями Р. Меркле [2] об открытых ключах, хотя принцип, положенный Р. Меркле, в основу защиты, отличался от принципа, предложенного У. Дифии и М. Хеллманом. Они использовали однонаправленную функцию «дискретное логарифмирование в конечном поле», вычисление которое представляет неразрешимую вычислительную проблему.
Р. Меркле предложил метод, основанный на головоломках типа "пазлы", которые легальным пользователям (отправителю А – Алисе (англ. Alice) и получателю B – Бобу (англ. Bob)) решить легче, чем пассивному нарушителю E – Еве (от англ. Eavesdropper – подслушивающий) [3]. Процесс обмена сообщениями между Алисой и Бобом по Р. Меркле выглядит следующим образом [4].
1. Боб создает 220 (1048576) сообщений следующего формата:
"Это головоломка номер x.
В ней секретный ключ номер y. "
Значения x (номер головоломки) и y (значение секретного ключа) выбираются случайным образом.
2. Боб шифрует каждое сообщение собственным 20-битным секретным ключом, используя собственный симметричный криптоалгоритм.
3. Боб отправляет все 220 (1048576) сообщений Алисе.
4. Алиса выбирает любое сообщение из 220 (1048576) и начинает вскрывать его методом "грубой силы", т. е. перебирая все возможные комбинации битов в 20-битном ключе. Через некоторое время (достаточно большое, но приемлемое), ей это удается, и она получает сообщение в формате:
"Это головоломка номер x.
В ней секретный ключ номер y. "
5. Алиса формирует для Боба зашифрованное сообщение, в которое включает свое открытое сообщение. Для шифрования этого сообщения Алиса использует значение y в качестве ключа шифрования для симметричного алгоритма, известного, как минимум, ей и Бобу. К зашифрованному сообщению Алиса добавляет значение x из сообщения, вскрытого методом "грубой силы", не шифруя значение x.
6. Алиса отправляет Бобу зашифрованное сообщение и незашифрованное значение x.
7. Боб получает от Алисы зашифрованное сообщение и незашифрованное значение x.
8. Боб знает, какое значение y соответствует значению x (см. п. 1), а также алгоритм шифрования, используемый Алисой, поэтому легко расшифровывает сообщение от Алисы.
Пассивный взломщик Ева может попытаться взломать систему защиты Р. Меркле, однако ей предстоит гораздо больший объем работы, чем легальным пользователям Алисе и Бобу. Несмотря на то, что она знает значение x, ей в худшем случае придется вскрывать методом «грубой силы» каждое из 1048576 сообщений. В общем случае, вычислительные затраты Евы будут равны возведенным в квадрат вычислительным затратам Алисы. Например, Алиса и Боб могут проверить десять тысяч ключей в секунду, каждому из них потребуется минута для выполнения своих действий и еще одна минута для передачи головоломок от Боба к Алисе. Если вычислительные возможности Евы сравнимы с приведенными возможностями Алисы и Боба, ей потребуется около года для взлома системы.
Таким образом, У. Диффи и М. Хеллман в своем знаменитом алгоритме использовали идею Р. Меркле о том, что для затруднения вскрытия нарушителем секретного ключа необходимо, чтобы затраты его времени многократно превышали затраты времени, необходимые легальным пользователям для того, чтобы установить между собой контакт по каналу связи.
Литература
1. Криптосистема с открытым ключом. Материал из Википедии – свободной энциклопедии [Электронный ресурс]. – URL: https://ru.wikipedia.org/wiki /Криптосистема_с_открытым_ключом (дата обращения 01.02.2020 г.).
2. Меркл, Ральф. Материал из Википедии – свободной энциклопедии [Электронный ресурс]. – URL: https://ru.wikipedia.org/wiki/Меркл,_Ральф (дата обращения 01.02.2020 г.).
3. Алиса и Боб. Материал из Википедии – свободной энциклопедии [Электронный ресурс]. – URL: https://ru.wikipedia.org/wiki /Алиса и Боб (дата обращения 01.02.2020 г.).
4. Головоломки Меркла. Материал из Википедии – свободной энциклопедии [Электронный ресурс]. – URL: https://studopedia.su/3_28191_golovolomki-merkla.html (дата обращения 01.02.2020 г.).