 |
Понятие односторонней функции, общий принцип построения криптографических систем с открытым ключом.
|
|
|
|
Односторонняя функция:
Пусть X и Y дискретные множества. Функция y=f(x), где
xÎX, yÎY называется односторонней (однонаправленной),
если y легко вычисляется по любому x, а обратная функция x=f-1(y) является трудно вычислимой.
Система шифрования Эль-Гамаля, атаки на систему.
КС Эль-Гамаля.
Это некоторая модификация КС РША, стойкость которой не связана непосредственно с проблемой факторизации. Она широко используется в стандартах цифровой подписи и допускает естественное обобщение на случай КС, построенных на основе использования эллиптических кривых, что будет рассмотрено далее.
Генерирование ключей.
Пользователь А проделывает следующие операции для генерирования ключей:
1)генерирует простое число p и примитивный элемент ɑ∈GF(p);
2) выбирает случайное число а такое, что 1<= a<= p-2, и вычисляет число ɑ^a;
3) в качестве открытого ключа выбирает набор: (p, ɑ, ɑ^amodp), а в качестве закрытого ключа – число а.
Шифрование.
Пользователь В выполняет следующие шаги для шифрования сообщения М, предназначенного пользователю А:
1) Получает открытый ключ А;
2) Представляет сообщение М в виде цепочки чисел Мi, каждое из которых не превосходит р-1;
3) Выбирает случайное число k такое, что 1<=k<=p-2;
4) Вычисляет ɣ=(ɑ^k)mod p, б=Мi((ɑ^a)^k) mod p;
5) Посылает криптограмму C=(ɣ,б) пользователю А.
Дешифрование
Пользователь А выполняет следующие шаги для дешифрования сообщения, полученного от пользователя В:
1) используя свой закрытый ключ, вычисляет (ɣ^(- a))mod p
2) восстанавливает сообщение Mi=(ɣ^(-a))* б mod p
Действительно, ɣ^(- a)* б =(ɑ^(- a k))*Mi*(ɑ^(a k))=Mi mod p
Особенностью схемы Эль-Гамаля является то, что она относится к так называемым схемам рандомизационного шифрования, поскольку при шировании в ней используется дополнительная случайность в виде числа k.
|
|
|
Преимущество КС Эль-Гамаля состоит также и в том, что тогда все пользователи в сети могут выбирать одинаковые ɑ и р, что невозможно для КС РША. Кроме того, как будет показано далее, эта схема может быть естественным образом распространена на случай эллиптических кривых.
Существенным недостатком схемы является то, что длина криптограммы в ней в 2 раза больше длины сообщения.
Стойкость КС Эль-Гамаля
Проблема восстановления сообщения М по заданным p, ɑ, ɑ^a, б, ɣ при неизвестном а эквивалентна решению задачи Диффи-Хеллман.
Ясно также, что если будет решена проблема нахождения дискретного логарифма, то криптосистема Эль-Гамаля будет вскрыта. При выборе р с разрядностью 768 бит (для повышенной стойкости-до 1024 бит), стойкость КС Эль-Гамаля будет такой же, как и у КС РША при выборе в последней тех же параметров для модуля.
Важно отметить, что для шифрования различных сообщений Мi, Мj необходимо использовать различные значения чисел k, поскольку в противоположном случае б1/б2=Мi/Мj, и тогда сообщение Мj может быть легко найдено, если известно сообщение Мi.
Система шифрования РША, атаки на систему.
Генерирование ключей.
Случайно выбираются два простых числа p и q. Находится
модуль N=pq. Находится функция Эйлера φ (N)= (p-1)(q-1).
Выбираем число e такое, что НОД(e, φ (N))=1.
Находим d, как обратный элемент к e, de=1(mod φ (N)).
Объявляем d=SK, (e,N)=PK. PK сообщается всем
корреспондентам.
Шифрование.
Корр. А передает зашифрованное сообщение корр.В
(использует открытый ключ корр. В)
E=me(modN)
Расшифрование.
Корр. В расшифровывает принятую криптограмму от
корр.А,используя свой секретный ключ.
m=Ed(modN)
Атаки.
1. Система РША может быть вскрыта, если удастся найти p и q, т. е. факторизовать N.
|
|
|
Исходя из этого факта p и q должны выбираться такой большой разрядности, чтобы факторизация числа n потребовала необозримо большого времени, даже с использованием всех доступных и современных средств вычислительной техники.
В настоящее время задача факторизации чисел не имеет полиномиального решения. Разработаны лишь некоторые алгоритмы, упрощающие факторизацию, но их выполнение для факторизуемых чисел большой разрядности все равно требует необозримо большого времени. Действительно, сложность решения задачи факторизации для наилучшего известного сейчас алгоритма факторизации равна
Так, например ln n = 200, если, то число операций будет приблизительно равно 1,37 ∙ 1014.
При увеличении числа разрядов n до 1000 и более время факторизации становится совершенно необозримым.
2. Другой естественной атакой на КС РША является дискретное логарифмирование. Эта атака (при известном сообщении) выполняется следующим образом: d = log E M mod N. Однако задача дискретного логарифмирования по модулю многоразрядных чисел также относится к трудным в математике, и оказывается, что она имеет почти такую же сложность, как и задача факторизации.
3. Циклическая атака. Будем последовательно возводить полученную криптограмму в степень равную значению открытого ключа т.е. (((((Ee)e)…..)e.
Если при некотором шаге окажется, что Ei=E, то это означает,
что Ei-1=m. Доказывается, что данная атака не лучше атаки факторизации N.
4. Отсутствие шифрования. Этот случай возможен, если в результате шифрования получаем открытое сообщение, т. е. M e mod n = M. Такое условие должно выполниться хотя бы для одного из сообщений, например, для сообщений M = 0, 1, n – 1. На самом деле таких сообщений, которые вообще! не шифруются, существует в точности [1 + gcd (e – 1, p – 1)][1 + gcd (e – 1, q – 1)]. Их число всегда не менее 9. Однако при случайном выборе q и p доля таких сообщений будет ничтожно мала и они почти никогда не встретятся на практике.
5. Атака при малом объеме возможных сообщений
Предположим, что количество сообщений ограничено значениями M1, M2,…, Mr, где r обозримо. (Это могут быть, например, различные команды – вперед, назад, влево, вправо и т. п.). Тогда сообщение может быть легко расшифровано.
|
|
|
Действительно, пусть криптограмма C перехвачена. Тогда необходимо попытаться зашифровать все команды известным открытым ключом и определить ту криптограмму, которая совпадает с принятой C:
Способ борьбы с такой атакой – это «подсаливание» сообщений (т. е. присоединение к ним небольших цепочек бит, полученных с использованием чисто случайного датчика).
|
|
|
