Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
В криптосистемах с открытым ключом для шифрования не используется секретный ключ — он необходим только при расшифровке. В работе [97] Диффи и Хеллман кратко описали несколько математических преобразований, названных ими однонаправленными функциями с секретом (one-way trapdoor function).! Они предназначались для реализации криптографии с открытым ключом и обла-' дали следующими свойствами.
Свойство 8.1 (Однонаправленная функция с секретом). Однонаправленную функцию с секретом /((ж) : V TZ легко вычислить для всех х € Т>, но очень( трудно инвертировать для почти всех значений из 7Z. Однако, если используется!
Глава 8. Шифрование — асимметричные методы
291
секретная информация t, то для всех значений у ? 7Z легко вычислить величину хЕТ>, удовлетворяющую условию у = ft(x).
Понятие однонаправленной функции с секретом — основное в криптографии с открытым ключом. Криптосистемы с открытым ключом, использующие однонаправленные функции с секретом, называются асимметричными (asymmetric cryptosystems). В первой работе Диффи и Хеллмана, посвященной криптографии с открытым ключом [97], было рассмотрено несколько однонаправленных функций с секретом. Однако эти функции были недостаточно асимметричными, поэтому вскоре Диффи и Хеллман предложили более удачный вариант: возведение в степень по модулю. Эта функция была использована в знаменитом криптографическом протоколе — протоколе обмена ключами Диффи-Хеллмана (Diffie-Hellman key exchange protocol) [98] (см. раздел 8.3). Эта первая удачная реализация криптографического алгоритма с открытым ключом широко используется до сих пор.
В 1974 году Меркл (Merkle) изобрел механизм согласования криптографического ключа путем явных асимметричных вычислений, получивших название головоломка Меркла [199]. Асимметричность головоломки Меркла заключается в том, что ее вычислительная сложность для законных участников протокола согласования ключа и для перехватчиков совершенно разная: легальные участники легко выполняют вычисления, а нелегальные — нет. Головоломка Меркла представляет собой первую эффективную реализацию однонаправленной функции с секретом. Несмотря на то что головоломка Меркла не подходит для применения в современных криптографических приложениях (мера ее асимметрии колеблется от п до п2), ее влияние на криптосистемы с открытым ключом невозможно переоценить.
В настоящее время стало известно, что Кокс (Cocks), британский криптограф, изобрел первую криптосистему с открытым ключом в 1973 году [277]. Алгоритм шифрования Кокса, получивший название алгоритма с несекретным ключом шифрования, использует сложность разложения целого числа на простые множители и, по существу, совпадает с криптосистемой RSA (раздел 8.5). К сожалению, алгоритм Кокса был засекречен. В декабре 1997 года Группа по электронной защите средств связи (Communications Services Electronic Security Group — CESG) рассекретила алгоритм Кокса.
Несмотря на то что вначале криптосистемы с открытым ключом были достоянием узкого круга лиц, именно благодаря открытым исследованиям они нашли два важнейших применения: 1) цифровые подписи (раздел 10.4) и 2) обмен секретными ключами через открытые каналы связи (раздел 8.3). Эти два приложения лежат в основе электронной коммерции, осуществляемой через Internet.
292
Часть III. Основные методы криптографии
8.1.1 Структурная схема главы
В начале главы вводится понятие стойкости "учебной криптографии", которое сопровождается предупреждением о ее практической уязвимости (раздел 8.2). Затем описываются основные примитивы криптографии с открытым ключом: протокол обмена ключами Диффи-Хеллмана (раздел 8.3), учебный вариант алгоритма RSA (раздел 8.5), а также криптосистемы Рабина (раздел 8.10) и Эль-Гамаля (раздел 8.12). Эти алгоритмы и протоколы сопровождаются теоремами об их формальной стойкости при соответствующих предположениях. В частности, формулируется задача Диффи-Хеллмана и задача дискретного логарифмирования (раздел 8.4), задача RSA (раздел 8.7) и задача о разложении целого числа на простые множители (раздел 8.8). Кроме того, в главе вводятся формальные понятия для описания разнообразных атак на криптосистемы с открытым ключом (раздел 8.6). Нестойкость учебных вариантов криптографических алгоритмов демонстрируется на примере алгоритма RSA (раздел 8.9), Рабина (раздел 8.11) и Эль-Гамаля (раздел 8.13). В разделе 8.14 рассматривается необходимость более строгого понятия стойкости шифрования с открытым ключом. В разделе 8.15 описывается комбинация симметричных и асимметричных криптосистем — гибридная криптосистема.
8.2 Нестойкость "учебных" алгоритмов шифрования
Следует отметить, что алгоритмы шифрования, описанные в этой главе, носят J учебный характер. Их можно найти в любом учебнике по криптографии. К сожалению, эти алгоритмы непригодны для практического применения. Стойкость ¦ "учебного" алгоритма шифрования в криптосистеме с открытым ключом описы- | вается следующим свойством.
Свойство 8.2 (Нестойкость "учебных" алгоритмов шифрования). В рамках этой главы стойкость (секретность) криптосистемы рассматривается с двух точек зрения.
