Шифр эль гамаля


Содержание

Шифр эль гамаля

Основная идея ElGamal состоит в том, что не существует эффективных методов решения сравнения a x == b (mod p)

Обозначения. Через Z(n) обозначим вычеты по модулю n, через Z*(n) — мультипликативную группу обратимых элементов в Z(n). Через a b (mod n) будем обозначать возведение a в степень b в кольце Z(n). Hапомню, что если p — простое число, то группа Z*(p) изоморфна Z(p-1).

Пусть числа p и 2p+1 — простые, p>2,v и w — образующие мультипликативных групп Z*(p) и Z*(2p+1) соответственно.

Лемма. Если v — образующая Z*(p), то v = (p + (p+1)v) (mod 2p ) — образующая мультипликативной группы Z*(2p). (Эта группа, очевидно, изоморфна Z*(p) ).

Числа p, 2p+1, v, v, w фиксируются при выборе алгоритма.


Пароли

СЕКРЕТHЫЙ пароль — число x из Z*(p).

ОТКРЫТЫЙ пароль (y) вычисляем в два шага.

    Сначала находим z=v x (mod 2p), z принадлежит группе Z*(2p).

  • Hаконец вычисляем сам открытый пароль y = w z (mod 2p+1), y принадлежит группе Z*(2p+1).
  • Теорема. При любом выборе секретного пароля (x) открытый пароль (y) будет являться образующей мультипликативной группы Z*(2p+1). Другими словами, сравнение y a = b (mod 2p+1) разрешимо относительно a при любом b.

    Доказательство. Число w^z будет образующей группы Z*(2p+1) iff числа z и 2p взаимно просты. Hо z = v x (mod 2p), где v0 — образующая группы Z*(2p).


    Электронная подпись

    Пусть s — число (информация), к которому надо найти электронную подпись, s принадлежит группе Z(2p). Для этого выбираем случайное число r из группы Z*(2p), изоморфной Z*(p), и в качестве подписи выдаем пару чисел (a,b), где

    a = a(r,s) = z -1 *r*s = v (-x) *r*s (mod 2p); b = b(r,s) = w r (mod 2p+1).

    Таким образом, для составления подписи требуется знать секретный пароль (x), точнее говоря z=v x .

    Для проверки подлинности подписи можно воспользоваться равенством

    y a = b s (mod 2p+1).

    y a = (w z )^(z -1 *r*s) = w^(z*z -1 *r*s) = w rs = (w r )^s = b s (mod 2p+1)

    Следовательно, для проверки подлинности подписи достаточно знать только открытый пароль (y).

    При вычислении подписи число s(файл) находится с помощью однонаправленной хэш-функции (аналог MD4, но другое).

    (c,d) — зашифрованное сообщение, e — промежуточное выражение из Z*(2p+1).

    Hахождение открытого ключа по секретному. x =>y

    Электронная подпись x, s, r =>a, b (r — случайное)

    Проверка подписи y, s, a, b =>y/n

    Шифрование y, s, r =>c, d

    1. e = y r (mod 2p+1)
    2. c = w r (mod 2p+1)
    3. d = s*e (mod 2p+1)

    Схема Эль-Гамаля

    Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

    Схема была предложена Тахером Эль-Гамалем в 1985 году. [1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

    Содержание

    Генерация ключей [ править ]

    1. Генерируется случайное простое число .
    2. Выбирается целое число — первообразный корень .
    3. Выбирается случайное целое число такое, что .
    4. Вычисляется .
    5. Открытым ключом является тройка , закрытым ключом — число .

    Работа в режиме шифрования

    Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

    Шифрование [ править ]

    Сообщение должно быть меньше числа . Сообщение шифруется следующим образом:

    1. Выбирается сессионный ключ — случайное целое число такое, что
    2. Вычисляются числа и .
    3. Пара чисел является шифротекстом.

    Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.

    Расшифрование [ править ]

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

    При этом нетрудно проверить, что

    Для практических вычислений больше подходит следующая формула:

    Схема шифрования [ править ]

    Пример [ править ]

    • Шифрование
      1. Допустим, что нужно зашифровать сообщение .
      2. Произведем генерацию ключей:
        1. Пусть . Выберем — случайное целое число такое,что .
        2. Вычислим .
        3. Итак, открытым является тройка ,а закрытым ключом является число .
      3. Выбираем случайное целое число такое, что 1 Работа в режиме подписи [ править ]

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

    Подпись сообщений [ править ]

    Для подписи сообщения выполняются следующие операции:

    1. Вычисляется дайджест сообщения :
    2. Выбирается случайное число взаимно простое с и вычисляется
    3. Вычисляется число .
    4. Подписью сообщения является пара .

    Проверка подписи [ править ]

    Зная открытый ключ , подпись сообщения проверяется следующим образом:

    1. Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется,то подпись считается неверной.
    2. Вычисляется дайджест
    3. Подпись считается верной, если выполняется сравнение:

    Пример [ править ]

    • Подпись сообщения.
      1. Допустим,что нужно подписать сообщение .
      2. Произведем генерацию ключей:
        1. Пусть переменные, которые известны некоторому сообществу. Секретный ключ — случайное целое число такое, что .
        2. Вычисляем открытый ключ : .
        3. Итак,открытым ключом является тройка .
      3. Теперь вычисляем хэш-функцию: .
      4. Выберем случайное число такое, что выполняется условие . Пусть .
      5. Вычисляем .
      6. Находим число . Такое существует, так как НОД(k,p-1)=1. Получим что .
      7. Итак, мы подписали сообщение: » src=»http://www.wiki-wiki.ru/wp/images/math/1/c/3/1c31499614750f60d253f089e6fbf636.png» />.
    • Проверка подлинности полученного сообщения.
      1. Вычисляем хэш-функцию: .
      2. Проверяем сравнение .
      3. Вычислим левую часть по модулю 23: .
      4. Вычислим правую часть по модулю 23: .
      5. Так как правая и левая части равны, то это означает что подпись верна.

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

    • Случайное число должно сразу после вычисления подписи уничтожаться,так как если злоумышленник знает случайное число и саму подпись, то он легко может найти секретный ключ по формуле: и полностью подделать подпись.

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

    • Использование свертки объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа ,удовлетворяющие условиям , НОД(j,p-1)=1 и предположить что

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

    • Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: , в котором тройка принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при , , .На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения , , , а в Российском стандарте: , , .
    • Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел на пару чисел ),где является каким-то простым делителем числа . При этом сравнение для проверки подписи по модулю нужно заменить на новое сравнение по модулю : . Так сделано в американском стандарте DSS (Digital Signature Standard).

    Криптостойкость и особенности [ править ]

    В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

    ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

    Схема формирования ЭЦП Эль Гамаля

    Лабораторная работа

    Исследование электронной цифровой подписи (ЭЦП)

    Цель работы: исследование структуры алгоритма и методики практической реализации (ЭЦП) RSA и Эль-Гамаля.

    1. Основные положения

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

    Одновременно при этом возникает проблема, как аутентификации автора электронного документа, так и самого документа, т.е. установление подлинности автора и отсутствия изменений в полученном электронном сообщении.

    В алгоритмах ЭЦП как и в асимметричных системах шифрования используются однонаправленные функции. ЭЦП используется для аутентификации текстов, передаваемых по телекоммуникационным каналам.

    ЭЦП используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Функционально она аналогична обычной рукописной подписи и обладает основными её свойствами:

    — удостоверяет, что подписанный текст исходит от лица, поставившего подпись;

    — не даёт этому самому лицу возможности отказаться от обязательств, связанных с подписанным текстом;

    — гарантирует целостность подписанного текста.

    ЭЦП представляет собой относительно небольшой объём дополнительной цифровой информации, передаваемой вместе с подписанным текстом.

    Концепция формирования ЭЦП основана на обратимости асимметричных шифров, а также на взаимосвязанности содержимого сообщения, самой подписи и пары ключей. Изменение хотя бы одного из этих элементов сделает невозможным подтверждение подлинности подписи, которая реализуется при помощи асимметричных алгоритмов шифрования и хэш-функций.

    Система ЭЦП включает две процедуры:

    — формирование цифровой подписи;

    — проверку цифровой подписи.

    В процедуре формирования подписи используется секретный ключ отправителя сообщения, в процедуре проверки подписи — открытый ключ отправителя.

    Алгоритм электронной цифровой подписи (ЭЦП) RSA

    Безопасность системы RSA определяется вычислительной трудностью разложения на множители больших целых чисел. Недостатком алгоритма цифровой подписи RSA является уязвимость её к мультипликативной атаке. Другими словами, алгоритм ЭЦП RSA позволяет хакеру без знания секретного ключа сформировать подписи под теми документами, в которых результат хэширования можно вычислить как произведение результата хэширования уже подписанных документов.

    Обобщённая схема формирования и проверки электронной цифровой подписи приведена на рис. 1.

    Рис. 1. Схема электронной цифровой подписи RSA

    1) Определение открытого «е» и секретного «d» ключей (действия отправителя)

    — Выбор двух взаимно простых больших чисел р и q

    — Определение их произведения n = р*q


    — Определение функции Эйлера: φ(п) = (p-1)(q-1)

    — Выбор секретного ключа d с учетом условий: 1

    — Определение значения открытого ключа e:е d (mod п) и открытый текст сообщения M

    3) Аутентификация сообщения — проверка подлинности подписи

    — Расшифровка цифровой подписи S с помощью открытого ключа e и вычисление её хэш-значения m’=S e (mod п)

    — Вычисление хэш-значения принятого открытого текста M

    — Сравнение хэш-значений т и т’ если т = т’то цифровая подпись S – достоверна.

    Процедуру формирования ЭЦП сообщения М рассмотрим на следующем простом примере:

    Хешируемое сообщение M представим как последовательность целых чисел 312. В соответствии с приведённым выше алгоритмом формирования ЭЦП RSA выбираем два взаимно простых числа р = 3, q = 11, вычисляем значение п=p*q = 3*11 = 33, выбираем значение секретного ключа d =7 и вычисляем значение открытого ключа е = 3. Вектор инициализации Н выбираем равным 6 (выбирается случайным образом). Хэш-код сообщения M=312 формируется следующим образом:

    Н1 = (M1 + H) 2 (mod п) = (3 + 6) 2 (mod 33) = 81 (mod 33) = 15;

    Н3 = (М3 + H2) 2 (mod п) = (2 + 25) 2 (mod 33) = 729 (mod 33) = 3; т = 3

    Для получения ЭЦП шифруем хэш-значение m с помощью секретного ключа d и отправляем получателю цифровую подпись S = m d (mod n) и открытый текст сообщения M: S = 3 7 (mod 33) =2187 (mod 33) = 9

    Проверка подлинности ЭЦП

    Расшифровка S (т.е. вычисление её хэш-значения т’) производится с помощью открытого ключа е.

    m’= S e (mod п) = 9 3 (mod 33) =729 (mod 33) = 3

    Если сравнение хэш-значений т’ и т показывает их равенство, т.е. т = m’ то подпись достоверна.

    Схема формирования ЭЦП Эль Гамаля

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

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

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

    1) Определение открытого «у» и секретного «x» ключей (действия отправителя)

    — Выбор двух взаимно простых больших чисел р и q,q

    — Выбор значения секретного ключа х,х x (mod р)

    2) Формирование ЭЦП

    — Вычисление хэш-значения сообщения M: т =h(M)

    — Выбор случайного числа k,0 k (mod р)

    — Определение значения bиз выражения:

    — Цифровая подпись S = (а, b) и открытый текст сообщения M отправляются получателю.

    3)Аутентификация сообщения — проверка подлинности подписи (действия получателя)

    — Вычисление хэш-значения принятого открытого текста сообщения M

    — Подпись считается достоверной, если а a a b (mod р) = q m’ (mod р)

    4) В качестве процедуры формирования ЭЦП рассмотрим следующий пример (для удобства расчётов в данном примере использованы числа малой разрядности):

    — Выбираем простое число р и два случайных числа qи х(q и х x (mod р) = 2 8 ( mod 11) = 3;

    — Определяем хэш-значение исходного сообщения М, (312) т = h (M), в данном примере принимаем т = 3(методика определения хэш значения сообщения M описана в алгоритме ЭЦП RSA ).

    — Выбираем случайное целое число k, взаимно простое с р-1. Принимаем k=9, НОД(9, 10) = 1.

    — Для формирования ЭЦП вычисляем элементы подписи а и b

    а = q k (mod р) = 2 9 (mod 11) =6.

    Элемент b определяем с помощью расширенного алгоритма Евклида из следующего соотношения:

    m = (ха + kb) (mod (р-1)); 3= (8*6 + 9*b) (mod 10)) -9*b = -45(mod 10)

    В данном примере цифровой подписью является пара чисел а = 6, b = 5.

    Цифровая подпись S = (а,b) и открытый текст сообщения M отправляются получателю. Для контроля целостности сообщения и достоверности ЭЦП получатель вычисляет хэш-значение m’ принятого открытого текста сообщения M. При этом отправитель и получатель использует одну и ту же хэш-функцию h( ).

    Получив подписанное сообщение и открытый ключ у = 3, получатель для проверки подлинности подписи проверяет выполнение условия

    у a a b (mod р) = q m’ (mod р)

    3 6 *6 5 (mod 11) = 2 3 (mod 11)

    5668704(mod 11) = 8 (mod 11) 8(mod 11) = 8(mod 11),

    так как условие выполняется, то принятое получателем сообщение признаётся подлинным.

    Таким образом, процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщения.

    Следует иметь ввиду, что каждая подпись по схеме Эль Гамаля требует нового значения k. Случайное значение k должно храниться в секрете.

    2. Выполнение работы

    Задачи лабораторной работы:

    1) Разработать приложения формирования ЭЦП RSA и Эль-Гамаля.

    2) Привести сравнительную характеристику формирования ЭЦП RSA и Эль-Гамаля. Описать их преимущества и недостатки.

    3. Контрольные вопросы

    1. Изложите принципиальную схему организации обмена документами, заверенными цифровой подписью.

    2. Перечислите основные требования, предъявляемые к хэш-функции, пригодной для использования при вычислении цифровой подписи документа.

    3. Назовите и охарактеризуйте методы, реализующие ЭЦП.

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

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

    6. Сравните наиболее распространенные стандарты ЭЦП.

    | следующая лекция ==>
    Под дебиторской задолженностью понимаются. | Квалифицирующие признаки убийства, харкт-ие потерпевшего и объект.ст. (п 1-7, 15 ч.2)

    Дата добавления: 2020-11-12 ; просмотров: 2295 | Нарушение авторских прав

    Схема Эль-Гамаля

    • Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

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

    Связанные понятия

    Криптографические хеш-функции — это выделенный класс хеш-функций, который имеет определенные свойства, делающие его пригодным для использования в криптографии.

    Реализация шифрования дешифрования методом Эль-Гаммеля

    Содержание

    1.Текст задания, с указанием номера студента в журнале и соответствующих вариантов задания.

    2.Краткое описание алгоритма шифра Эль-Гамаля.

    3.Реализация шифрования/дешифрования методом Эль-Гамаля.

    3.1.Описание основных функций и переменных.

    3.2.Результаты выполнения программы.

    4. Краткое описание алгоритма электронной подписи Диффи-Хеллмана.

    5. Реализация алгоритма подписи сообщения c помощью системы Диффи-Хеллмана.

    5.1. Описание основных функций и переменных.

    5.2. Результаты выполнения программы.

    6. Краткое описание алгоритма RC4.

    7. Реализация алгоритма RC4.

    7.1. Описание основных функций и переменных.

    7.2. Результаты выполнения программы.

    1.Текст задания, с указанием номера студента в журнале и соответствующих вариантов задания

    . Программно реализовать на языке C++ алгоритм шифрования и дешифрования сообщения c помощью метода в соответствии с вариантом. Номер варианта k определяется по формуле: k=N mod 4, где N=11 – номер студента в журнале.

    K=1

    Метод шифрования «Шифр Эль-Гамаля»Программно реализовать на языке C++ алгоритм электронной подписи сообщения и проверки его подлинности c помощью метода в соответствии с вариантом. Номер варианта k определяется по формуле: k=N mod 3, где N – номер студента в журнале.

    K=2

    Система Диффи-Хелмана

    Программно реализовать на языке C++ алгоритм шифрования и дешифрования сообщения c помощью потокового шифра RC4.

    Краткое описание алгоритма шифра Эль-Гамаля.

    Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи.

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

    Генерация ключей

    1. Генерируется случайное простое число длины битов.

    2. Выбирается случайное целое число такое, что .

    3. Выбирается случайное целое число такое, что .

    5. Открытым ключом является тройка , закрытым ключом — число .

    Работа в режиме шифрования

    Шифрсистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

    Шифрование

    Сообщение шифруется следующим образом:

    1. Выбирается сессионный ключ — случайное целое число такое, что

    2. Вычисляются числа и .

    3. Пара чисел является шифротекстом.

    Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.

    Расшифрование

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

    При этом нетрудно проверить, что

    Для практических вычислений больше подходит следующая формула:

    Пример

    1. Допустим что нужно зашифровать сообщение .

    2. Произведем генерацию ключей :

    1. пусть . Выберем — случайное целое число такое,что .

    3. Итак , открытым является тройка ,а закрытым ключом является число .

    3. Выбираем случайное целое число такое, что 1

    ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМА АСИНХРОННОГО ШИФРОВАНИЯ ЭЛЬ-ГАМАЛЯ И ЕГО РЕАЛИЗАЦИЯ ДЛЯ ОБМЕНА СООБЩЕНИЯМИ

    Секция: 6. Математические науки

    XXXIV Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

    ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМА АСИНХРОННОГО ШИФРОВАНИЯ ЭЛЬ-ГАМАЛЯ И ЕГО РЕАЛИЗАЦИЯ ДЛЯ ОБМЕНА СООБЩЕНИЯМИ

    Aннoтaция. Цeлью paбoты являeтcя создание системы для обеспечения безопасной передачи текстовых сообщений по незащищенным каналам связи. За основу был взят алгоритм работы асимметричного шифрования, предложенный Эль-Гамалем. Было выяснено, что разработанная система является эффективным средством для надежной передачи информации.


    Ключевые слова: модульная арифметика, дискретное логарифмирование, асимметричное шифрование, алгоритм Эль-Гамаля.

    Для защиты информации применяются различные методы шифрования, меняющие с помощью криптографических преобразований исходный текст в нечитаемую последовательность символов. Рассматриваемая криптосистема Эль-Гамаля относится к схемам шифрования с открыты ключом. Для шифрования и расшифровки используются совершенно разные ключи. Ключ, используемый для преобразования исходного текста в шифротекст, разрешается передавать любому пользователю системы, не задумываясь о безопасности, поэтому этот ключ называют открытым. Другой ключ, который используют для восстановления исходного текста, называют секретным. Это позволяет свободно передавать и обменивать ключи по различным сетям с открытым доступом.

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

    Основные определения

    Введем некоторые определения, которые будут использованы в работе.

    Полем называют коммутативное кольцо с единицей, в котором любой элемент, отличный от нуля, имеет обратный, причем:

    1. – коммутативная группа с нейтральным элементом 0;

    2. – коммутативная группа c нейтральным элементом ;

    3. Умножение дистрибутивно относительно сложения:
    .

    Говорят, что два целых числа и сравнимы по модулю и пишут , если (разность и делится на без остатка). Множество всех чисел, сравнимых с по модулю , называется классом вычетов по модулю . Множество всех классов вычетов по модулю образует кольцо вычетов. В качестве операций сложения и умножения в этом кольце используются сложение и умножение по модулю.

    Конечным полем порядка называется поле, состоящее из конечного числа элементов. Поле классов вычетов по простому модулю является конечным полем.

    В конечном поле для произвольных элементов дискретным логарифмом числа по основанию называется натуральное число такое, что . Задачу вычисления дискретного логарифма при заданных значениях называют задачей дискретного логарифмирования в конечном поле.

    Число , взаимно простое с , принадлежит показателю , если – наименьшее натуральное число, для которого . Число, принадлежащее показателю функции Эйлера , называют первообразным (примитивным) корнем по модулю . Другими словами, первообразный корень – это образующий элемент мультипликативной группы кольца вычетов по модулю .

    История алгоритма

    Египетский криптограф Тахер Эль-Гамаль в 1985 году опубликовал статью «Криптосистема с открытым ключом и схема цифровой подписи на основе дискретных логарифмов» (“A Public key Cryptosystem and A Signature Scheme based on discrete Logarithms” [3]), где описаны алгоритмы создания ассиметричных систем шифрования и электронной цифровой подписи, базирующиеся на трудности вычисления дискретного логарифма.

    Описание алгоритма

    Т. Эль-Гамаль предложил следующую схему шифрования на основе возведения в степень по модулю большого простого числа.

    I. Генерация ключей.

    Первая часть протокола состоит в генерации ключей – открытого и закрытого.

    Открытый ключ представляет собой тройку чисел . Генерируется большое простое число , по модулю которого будут осуществляться все дальнейшие сравнения: .

    Замечание. В схемах шифрования в качестве модуля необходимо использовать большое целое простое число, имеющее в двоичном представлении длину 512–1024 бит.

    Затем генерируется закрытый ключ из условия, что его значение не должно превосходить : .

    Выбирается первообразный корень по модулю . Затем вычисляется последний элемент открытого ключа .

    Замечание. В работе используется алгоритм быстрого возведения в степень по модулю.

    Сформированный открытый ключ рассылается по незащищенным каналам связи абонентам.

    Замечание. Определение закрытого ключа на основе открытого невозможно даже на современном технологическом уровне.

    II. Шифрование сообщения

    Абонент, желающий зашифровать сообщение, генерирует случайное натуральное взаимно простое с модулем сессионное число : , причем , .

    Вычисляются шифры для каждого элемента сообщения:

    Вся упорядоченная последовательность , состоящая из шифров элементов , является шифром сообщения (шифротекстом).

    Зная закрытый ключ , исходное сообщение можно вычислить из шифротекста:

    Замечание. Для удобства возведения в степень можно применить малую теорему Ферма. Так как , допускается умножить правую часть сравнения на .

    Из условия следует равенство .

    Пример работы алгоритма

    Пусть нескольким абонентам необходимо передать сообщения абоненту . Рассмотрим случай, когда передаваемая информация имеет кодируемый характер, а именно текстовое представление.

    Абонент формирует случайное простое число , по модулю которого будут производиться все сравнения. Для наглядности работы алгоритма выберем небольшое число: .

    Также абонент ─ первообразный корень по модулю : . Далее выбирается случайное натуральное число , меньшее и не равное 1: . Затем вычисляется последняя составляющая открытого ключа : .

    Открытый ключ рассылается по незащищенным каналам связи, а секретный ключ хранится абонентом в тайне.

    Получив открытый ключ, абоненты на его основе шифруют сообщение. Рассмотрим процесс шифрования сообщения . Текстовая строка представляется как последовательный набор символов, который, в свою очередь, представляется кодовой комбинацией на основании таблицы ASCII: .

    Далее каждая кодовая комбинация шифруется следующим образом:

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

    2. Вычисляются пары чисел : и .

    Следовательно, для символа шифр будет иметь вид

    Аналогичным образом при и соответственно символы и получат шифры и .

    Зашифрованное сообщение отправляется абоненту .

    Замечание. Наглядно видно, что недостатком данного метода шифрования является увеличение длины зашифрованного сообщения в два раза относительно исходного.

    Получив зашифрованное сообщение, абонент посимвольно расшифровывает текст: .

    Аналогичным образом получим , .
    Обратным преобразованием по таблице ASCII получим строку . Таким образом, абонент B расшифрует сообщение.

    Пример программно-аппаратной реализации алгоритма

    В процессе работы была создана одноранговая система передачи текстовых сообщений по сети Интернет с возможностью криптографической защиты передаваемых данных.

    Рассмотрим основные алгоритмы программы: шифрование и дешифрование текстовых строк.

    Функция шифрования текста последовательно каждому символу ставит в соответствие пару чисел, записывая их в адрес по указателю dcrp_message. Причем указатель message ссылается на строку, которую требуется зашифровать.

    String^ dcrp_message = «»; //строка, содержащая зашифрованные данные

    array ^ temp = gcnew array (message->Length — 1);

    temp = message->ToCharArray(); // разбиение message на массив символов

    for (int i=0; i Length — 1; i++)<

    unsigned int s = (unsigned int)temp[i]; // представление символа как числа

    // генерация псевдослучайного числа в необходимом диапазоне

    · k = Random().Next(2, module-1);

    · unsigned int a = power(g, k, module); //

    · unsigned int b = mul (power(publicKey, k, module ), s, module);
    //

    dcrp_message = dcrp_message + a + » » + b + » «;

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

    // разбиение шифротекста сообщения на массив указателей

    array ^ strA = dcrp_msg->Split(‘ ‘);

    for (int i = 0; i Length — 1; i += 2)<

    //формирование массивов первых и вторых компонент шифров символов

    · array ^ a = gcnew array (strA[i]->Length);

    · array ^ b = gcnew array (strA[i+1]->Length);

    · unsigned int ai = 0;

    · unsigned int bi = 0;

    · b = strA[i + 1]->ToCharArray();

    //преобразование компонент шифра

    for (int j = 0; (j Length); j++)

    ai = ai * 10 + (unsigned int)(a[j] — 48);

    for (int j = 0; (j Length); j++)

    bi = bi * 10 + (unsigned int)(b[j] — 48);

    if ((ai != 0) && (bi != 0))<

    unsigned int deM = mul(bi, power(ai, module — 1 — privateKey, module), module); // .

    Char m((unsigned int)deM); // представление числа как символа

    msg = msg + m; // формирование расшифрованного сообщения

    Пример работы ПО

    В данном примере осуществляется передача конфиденциальной информации от пользователя Professor другому пользователю Assistant Professor, который генерирует секретный ключ . При этом Assistant Professor передает открытый ключ собеседнику. Тот, в свою очередь, установив параметры открытого ключа, шифрует конфиденциальное сообщение. На данном примере видно, что длина сообщения возрастает.

    Получив шифротекст сообщения, пользователь Assistant Professor дешифрует данные. Таким образом, информация передана по открытой сети Интернет с более высокой степенью защищенности при помощи криптографического алгоритма защиты.

    Рисунок 1. Диалоговое окно пользователя Assistant Professor

    Рисунок 2. Диалоговое окно пользователя Professor

    Рeзультaты и вывoды

    Была разработана система, позволяющая безопасно передавать сообщения по незащищенному каналу связи между двумя абонентами. В её основе лежит алгоритм Эль-Гамаля, опирающийся на трудности вычисления дискретных логарифмов в конечном поле. Система может применяться и внедряться на местах, где значима безопасность и конфиденциальность передаваемой информации. Злоумышленник не сможет получить желаемые данные, так как для восстановления сообщения у него будет недостаточное количество составляющих для решения задачи расшифрования. Таким образом, созданная система является эффективным средством защиты от перехвата информации в открытом канале связи.

    Схема Эль-Гамаля

    Шифросистема Эль-Гамаля (Elgamal) — была предложена в 1984 году. В частности стандарты электронной цифровой подписи в США и России базируются именно на ней.

    Принцип работы шифросистемы Править

    Генерация ключей Править

    1. Генерируется случайное простое число $ p $ длины $ n $ .
    2. Выбираются случайные числа $ x $ и $ g $ так, что $ 1 $ 1 $ y = g^x \bmod p $ .

    Открытым ключом является тройка $ (p,g,y) $ , закрытым ключом — число $ x $ .

    Шифрование Править

    В дальнейшем будем понимать под М — исходное сообщение.

    1. Выбирается случайное секретное число $ k $ , взаимно простое с $ p-1 $ .
    2. Вычисляется $ a = g^k\bmod p $ , $ b = y^k M \bmod p $ , где $ M $ — исходное сообщение.

    Пара чисел $ (a,b) $ является шифротекстом. При этом длина шифротекста длиннее исходного сообщения $ M $ вдвое.

    Подпись Править

    Проверка подписи Править

    Криптостойкость Править

    Криптостойкость данной схемы основана на сложности проблемы дискретного логарифмирования (по известным p, g и y приходится искать показатель степени х: $ y \equiv g^x \pmod

    $ .

    Национальная библиотека им. Н. Э. Баумана
    Bauman National Library

    Персональные инструменты

    Устойчивое к утечкам шифрование Эль-Гамаля

    Leakage Resilient ElGamal Encryption
    Авторы Eike Kiltz [@: 1] , Krzysztof Pietrzak [@: 2]
    Опубликован 2011 г.
    Сайт Homepage of Damien Stehle
    Перевели Шикунов Юрий Игоревич
    Год перевода 2011 г.
    Скачать оригинал

    Содержание

    Введение

    Атаки по сторонним каналам это криптоаналитические атаки против физических имплементаций против криптосистем которые используют некоторый тип утечек из криптодевайсов во время выполнения. Традиционные меры защищенности(такие как избранная-шифротекстовая безопасность для расшифровывательных систем) не предоставляют никакой гарантии безопасности против таких атак, и многие применения возможности защиты криптосистем были сломаны с помощью атак по сторонним каналам, эксплуатирующие сторонние каналы, такие как: время исполнения [1] , электромагнитная радиация [2] [3] , потребляемая мощность[38], обнаруживаемые ошибки[8,6] и многие другие[46,43]. Контрмеры против них могут быть на алгоритмическом или аппаратном уровне. В последнем случае в главную очередь пытаются построить устройства способные терять в результате утечек минимально возможное кол-во информации (например через защиту электромагнитной радиации). Алгоритмические контр меры представляют собой разработанные так алгоритмы, что их описание предоставляет защиту против атак по сторонним каналам(например против своевременных атак посредством уверения что время выполнения алгоритма должно оставаться в секрете). Традиционно алгоритмические контрмеры (такие как сокрытие[43] для списках важных документов) по большей части к месту из-за того, что они защищают против специфичных и известных атак.

    Устойчивая К Утечкам Криптография. В последнее время формальные модели предполагаются с учетом того, что не ожидается защищать ни одного конкретного стороннего канала, только лишь требуется возможность сторонних каналов с учетом некоторой «взаимосвязи ресурсов». В модели «устойчивости к утечкам» предполагаются противники, каждый из вызовов которых криптографически примитивен, способен выучить связанное кол-во арбитрарной информации о секретном внутреннем состоянии, доступ к которой был получен во время вызова. Так как общее кол-во утекшей информации неограниченно, эта модель обычно называется «продолжительной утечкой». Как мы обсудим ниже, она сильно отличается от модели «утечки памяти» которое имеет присущее ей ограничение на кол-во утекшей информации высшего приоритета и потому не может превысить размер секретной информации.

    Применение вызова примитивных утечек будет против любого стороннего канала, который будет защищен против каждой атаки по сторонним каналам, подходящей к нашей основной модели, т.е. пока кол-во утекшей информации во время каждого вызова ограничено, и более того, устройство придерживается только аксиомы «вычислительных утечек информации» (40) которая говорит, что память, доступ которой не получен во время вызова, не утекает. Защита модели связанных утечек означает, что реализация аппаратных средств должна только подходить верхней модели; как только то сделано, доказательство предоставляется защите схемы.

    Пока теоретическое исследование было сфокусировано на предотвращении утечек памяти и известных примитивных утечек (в нашем случае — безопасности против продолжительных утечек) и потоковых шифров, цифровых подписей и слабых не адаптирующей моделей — псевдорандомных функций и перестановок. Недавно были предложены основные компиляторы , которые превращают любую схему в устойчивую к утечкам. Сейчас эти основные компиляторы — доказательство концепции и слишком неэффективны для использования на практике, тк они полагаются на полную оморфную шифровку и требует одно полное шифрование на вход.

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

    Моделирование Устойчивости К Утечкам. Представим некоторые криптосистемы CS, пусть S обозначает начальное состояние и Si — после i-го вызова. На i-ый вызов CS противник выбирает некоторый введенный Xi и получает Yi, где (Si+1, Yi) ← CS(Si,Xi).

    В этой статье мы будем использовать более атомарное понятие устойчивости к утечкм, где вызов CS( который будет в дешифровальном запросе) разделен на две фазы, каждая из которых утекает индивидуально. Более важно, вычисление дешифровки может быть синтаксически разделено на две фазы Dec1* и Dec2* , каждая из которых выполняется в последовательном порядке для дешифровки сообщения. При адаптивной атаке на основе шифротекста(CCA), противник может дешифровать запросы с соответствием к шифротексту C и может далее специфицировать две (эффективно вычисляемых) функции утечки, f и g, чья область значений связана ограничена λ бит. В дополнение к дешифровке C противник получает выход f и g примененный ко входу Dec1* и Dec2*, соответственно включая алгоритм внутренних бросков монеты.

    На Связанном Радиусе И ДОМЕНЕ. В итоге сопротивление утечкам предполагает атакующих, кто с каждого вызова может адаптивно выбирать функцию утечки f и получать выход из f примененный к общему секретному состоянию


    Радиус связи: f принадлежит к <0, 1>λ для некоторого параметра λ ∈ N.

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

    Радиус связи. На практике кажется сложным оценить как много информации аппаратура ( вроде смарт-карты) действительно сливает. Во многих атаках по сторонним каналам противник измеряет огромное кол-во информации, например полную энергопотребительную кривую. Так что на бумаге это предположение выглядит не реалистично, но очень пессимистично.

    Даже если утечка по сторонним каналам может содержать много данных, только маленькая фракция может быть использована в каждом измерении. Модель утечковой устойчивости позволяет только для утечек маленького колличества лямбда битов, но это утечка – худший исход с учетом того, что противник может выбрать функцию утечки, которая выводит наиболее полезную информацию. Ниже мы рассмотрим два пути, которые могут быть важными в этом наблюдении.

    Атака по сторонним каналам использующая малое число битов. Многие атаки по сторонним каналам сначала считают огромное кол-во утечек Λ1, Λ2, . . . из каждого вызова. Затем, во превых, каждая утечка Λi предварительно обрабатывается для того, чтобы извлечь важную информацию Λ ′ i (это Λ ′ i может, например, быть списком самых подходящих подключей). Атака продолжает пытаться восстановить секретный ключ Λ ′ 1, Λ ′ 2… . Такие атаки покрываются устойчивость к утечкам тогда, когда кол-во извлеченной информации [Λ ′ i] не более суммы утечки λ, к которой получен доступ по время вызова.

    Слабо ограниченный радиус связи. Ожидая подтверждения от наших конструкций, видно, что от ограничения утечки необходимо, которое слабее чем ограничение радиуса до λ бит, которое необходимо только лишь для того, чтобы утечка f <\displaystyle f>(S + ) не повышала минимальную псевдоэнтропию , противник имеет примерным активным состоянием S + больше чем λ бит. Это предполагает, что утечка, снижающая минимальную псевдоэнтропию на λ бит, будет более реалистичной.

    Шифрование Эль-Гамаля

    Попробуем первую попытку (безуспешную) сделать шифрование Эль-Гамаля устойчивым к утечке. К концу мы сделали описание состояния и разделили его на две части Dec1 * и Dec2 * . Секретный ключ аддитивно поделен на x = σ + σ ‘ устанавливая σ = x − r и σ ‘ = x + r. Дешифровка работает следующим образом :Dec1 * вычисляет σi = σi-1+ ri mod p, K ‘ =C ‘σi и проходит K ‘ к следующей части. Dec2 * вычисляет σi = σi-1— ri mod p, а затем K=K ‘ *C ‘σi . Отметим, что информация о состоянии — случайно перераспределяемый субъект к σi + σ ‘ i=x. Однако эта схема неустойчива к утечкам так как атакующий может адаптивно изучить определенное количество битов из σi=x+Ri и σ ‘ i=x-Ri(где Ri ∑ i j = 0 ⋅ r j <\displaystyle \sum _^\cdot r_> ) которая позволяет ему полностью реконструировать секретный ключ x.

    Полученные результаты.

    Доказано устойчивое к утечкам шифрование Эль-Гамаля. Мы также предлагаем применение мультипликативного обмена секретами для схемы шифрования Эль-Гамаля над билинейными группами. Наша основная теорема (Теорема 1) утверждает, что схема устойчива к утечкам против атак CCA1 в модели generic group. Наблюдение ключа состоит в том, что секретный ключ — элемент группы X и дешифровка проводит парные операции с элементами группы X как с одной фиксированной основанием. Это позволяет нам мультипликативно обмениваться секретными ключами как элементами группы, то есть X = σ i σ i ′ ∈ G <\displaystyle X=\sigma_\sigma_i’\in \mathrm> . Интуитивно мы используем тот факт, что в модели generic group некоторые бит репрезентующие σ i <\displaystyle \sigma _> и σ i ′ <\displaystyle \sigma '_> выглядят случайными и потому бесполезны для утечек противника. Однако, оказывается, что формально доказать это утверждение на удивление сложно.

    Мы также отмечаем доказательства того, что модель generic group имеет свои очевидные слабости. В частности в связи с атаками по сторонним каналам модель generic group может «абстрактно отдать» слишком важную информацию и противник получат реальную имплементацию схемы. Это должно быть принято во внимание когда описывается наше формальное утверждение защиты. Однако наш результат кажется является первой PKE схемой, которая устойчива к утечкой. К тому же, схема весьма практична. Другой возможной интерпретацией нашего результата является то, что защита экспоненциальной функции против атак по сторонним каналам мультипликативной техникой раздачи секретов лучше, чем аддитивной техникой.

    Сопутствующая работа

    В сообществе аппаратных средств важность раздача секретов в контексте принятия мер по сторонним каналам хорошо известна. В частности раздача секретов была предложена как контрмера против «дифференциальных атак силового анализа» для экспонентциальных алгоритмов, но без формального анализа.

    Большая часть работ по контрмерам по сторонним каналам, включая вышеобозначенные, предполагает контрмеры против конкретных атак по сторонним каналам. Микали и Рейзин в своей работе «physically observable cryptography” предложили влияющую теоретическую основу для захвата атак по сторонним каналам на более общем уровне.

    Помимо устойчивости к утечкам существуют другие модели, котороые предполагают криптосистемы, пока остаются защищенными даже если функция f(sk) (выбранная атакующим из широкого количества функций) ключа sk была получена. Мы отмечаем эти модели ниже. Главное отличие устойчивости к утечкам в том, что эти модели предполагают использование криптосистем независимых от состояния, и потому не могут они не могут выдерживать продолжительных утечек. С другой стороны функция утечки в этих работах остается незименной при вводе, а не только когда доступ к части состояний был получен.

    Определения

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

    Ключевые механизмы механизмы инкапсуляции. Ключевой механизм инкапсуляции (КМИ) имеет те же характеристики, как и система шифрования с открытым ключом, за исключением того, что при инкапсуляции механизм шифрования не предусматривает значимости вводных данных: значимым является результат шифрования случайного ключа К, который потом может быть использован совместно с ключом в любой симметричной системе для того, чтобы зашифровать само послание. Используя более точные определения, КМИ состоит из трех алгоритмов. Первый является вероятностным алгоритмом создания ключа, который при вводе защищенного параметра к выводит пару ключей — публичный и защищенный. Вероятностный алгоритм инкапсуляции и декапсуляции удовлетворяют следующему уравнению правильности для всех к:

    Защита ССА1 (также известная как защита против (!!)) в КМИ определяется следующей практикой:

    Пусть определяет вероятность того, что в вышеописанном эксперименте. После этого определяется преимущество как . В ССА2 (3)

    Инкапсуляция с проверкой состояния ключа и устойчивость к утечке информации. Для того, чтобы определить устойчивость к утечке информации, за инкапсуляцию с проверкой состояния ключа принимается механизм , в котором декапсуляция проводится с проверкой параметров и может быть формально разделена на на две последовательные стадии: Таким образом, соотношение зависимости данных ввода-вывода остается таким же, как и в стандартных КМИ.

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

    На () использования механизма декапсуляции, декапсулированный ключ рассчитывается по следующей схеме:

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

    Устойчивость к утечке определяется следующим образом. Пусть () является параметром утечки. Пусть в определении участвуют атаки, где противник может не только составить ряд () для декапсулированных значений (), но и может воспользоваться дополнительной информацией благодаря вычислениям и использованием этих двух значений. Таким образом, в эксперименте, противник может (дополнительно к данных выхода С) определить две эффективные и подсчитываемые функции утечки () с уровнем (), получая дополнительно к стандартным данным вывода () (), которые определяются как:

    с такими же обозначениями, как и в (1). Таким образом, функции () берут в качестве вводных данных те же данные, что и (). CCLA1 как уровень безопасности КМИ определяется в эксперимент, описанном ниже (обратите внимание, что теперь нам необходимо не только определить параметр безопасности (), но и уровень утечки ()):

    Пусть () определяет вероятность того, что () в вышеописанном эксперименте. После этого определяется преимущество () как ().

    Известно, что в CCA1 безопасный КМИ вместе с одноразовым симметричным шифрованием (?) позволяет использовать ССA1-безопасную систему PKE. Таким образом, это заявление также верно и для CCLA1 КМИ, так что для достижения наших целей достаточно всего лишь создаить CCLA1 КМИ. С другой стороны, необходимо отметить, что схема со сложением компонентов, описанных выше, в целом неверна для CCLA2 КМИ. То-есть, CCLA2 КМИ и CCA DEM вместе не составятся CCLA2 PKE систему.

    Шифр Эль-Гамаля

    Общая идея метода

    Основная идея ElGamal состоит в том, что не существует эффективных методов решения сравнения a x == b (mod p)

    Обозначения. Через Z(n) обозначим вычеты по модулю n, через Z*(n) — мультипликативную группу обратимых элементов в Z(n). Через a b (mod n) будем обозначать возведение a в степень b в кольце Z(n). Hапомню, что если p — простое число, то группа Z*(p) изоморфна Z(p-1).

    Пусть числа p и 2p+1 — простые, p>2,v и w — образующие мультипликативных групп Z*(p) и Z*(2p+1) соответственно.

    Лемма. Если v — образующая Z*(p), то v = (p + (p+1)v) (mod 2p ) — образующая мультипликативной группы Z*(2p). (Эта группа, очевидно, изоморфна Z*(p) ).

    Числа p, 2p+1, v, v, w фиксируются при выборе алгоритма.

    Пароли

    СЕКРЕТHЫЙ пароль — число x из Z*(p).

    ОТКРЫТЫЙ пароль (y) вычисляем в два шага.

      Сначала находим z=v x (mod 2p), z принадлежит группе Z*(2p).

  • Hаконец вычисляем сам открытый пароль y = w z (mod 2p+1), y принадлежит группе Z*(2p+1).
  • Теорема. При любом выборе секретного пароля (x) открытый пароль (y) будет являться образующей мультипликативной группы Z*(2p+1). Другими словами, сравнение y a = b (mod 2p+1) разрешимо относительно a при любом b.

    Доказательство. Число w^z будет образующей группы Z*(2p+1) iff числа z и 2p взаимно просты. Hо z = v x (mod 2p), где v0 — образующая группы Z*(2p).

    Электронная подпись

    Пусть s — число (информация), к которому надо найти электронную подпись, s принадлежит группе Z(2p). Для этого выбираем случайное число r из группы Z*(2p), изоморфной Z*(p), и в качестве подписи выдаем пару чисел (a,b), где

    a = a(r,s) = z -1 *r*s = v (-x) *r*s (mod 2p); b = b(r,s) = w r (mod 2p+1).

    Таким образом, для составления подписи требуется знать секретный пароль (x), точнее говоря z=v x .

    Для проверки подлинности подписи можно воспользоваться равенством

    y a = b s (mod 2p+1).

    y a = (w z )^(z -1 *r*s) = w^(z*z -1 *r*s) = w rs = (w r )^s = b s (mod 2p+1)

    Следовательно, для проверки подлинности подписи достаточно знать только открытый пароль (y).

    При вычислении подписи число s(файл) находится с помощью однонаправленной хэш-функции (аналог MD4, но другое).

    (c,d) — зашифрованное сообщение, e — промежуточное выражение из Z*(2p+1).

    Hахождение открытого ключа по секретному. x =>y

    Электронная подпись x, s, r =>a, b (r — случайное)

    Проверка подписи y, s, a, b =>y/n

    Шифрование y, s, r =>c, d

    1. e = y r (mod 2p+1)
    2. c = w r (mod 2p+1)
    3. d = s*e (mod 2p+1)

    Схема формирования ЭЦП Эль Гамаля

    Лабораторная работа

    Исследование электронной цифровой подписи (ЭЦП)

    Цель работы: исследование структуры алгоритма и методики практической реализации (ЭЦП) RSA и Эль-Гамаля.

    1. Основные положения

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

    Одновременно при этом возникает проблема, как аутентификации автора электронного документа, так и самого документа, т.е. установление подлинности автора и отсутствия изменений в полученном электронном сообщении.

    В алгоритмах ЭЦП как и в асимметричных системах шифрования используются однонаправленные функции. ЭЦП используется для аутентификации текстов, передаваемых по телекоммуникационным каналам.

    ЭЦП используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Функционально она аналогична обычной рукописной подписи и обладает основными её свойствами:

    — удостоверяет, что подписанный текст исходит от лица, поставившего подпись;

    — не даёт этому самому лицу возможности отказаться от обязательств, связанных с подписанным текстом;

    — гарантирует целостность подписанного текста.

    ЭЦП представляет собой относительно небольшой объём дополнительной цифровой информации, передаваемой вместе с подписанным текстом.

    Концепция формирования ЭЦП основана на обратимости асимметричных шифров, а также на взаимосвязанности содержимого сообщения, самой подписи и пары ключей. Изменение хотя бы одного из этих элементов сделает невозможным подтверждение подлинности подписи, которая реализуется при помощи асимметричных алгоритмов шифрования и хэш-функций.

    Система ЭЦП включает две процедуры:

    — формирование цифровой подписи;

    — проверку цифровой подписи.

    В процедуре формирования подписи используется секретный ключ отправителя сообщения, в процедуре проверки подписи — открытый ключ отправителя.

    Алгоритм электронной цифровой подписи (ЭЦП) RSA

    Безопасность системы RSA определяется вычислительной трудностью разложения на множители больших целых чисел. Недостатком алгоритма цифровой подписи RSA является уязвимость её к мультипликативной атаке. Другими словами, алгоритм ЭЦП RSA позволяет хакеру без знания секретного ключа сформировать подписи под теми документами, в которых результат хэширования можно вычислить как произведение результата хэширования уже подписанных документов.

    Обобщённая схема формирования и проверки электронной цифровой подписи приведена на рис. 1.

    Рис. 1. Схема электронной цифровой подписи RSA

    1) Определение открытого «е» и секретного «d» ключей (действия отправителя)

    — Выбор двух взаимно простых больших чисел р и q

    — Определение их произведения n = р*q

    — Определение функции Эйлера: φ(п) = (p-1)(q-1)

    — Выбор секретного ключа d с учетом условий: 1

    — Определение значения открытого ключа e:е d (mod п) и открытый текст сообщения M

    3) Аутентификация сообщения — проверка подлинности подписи

    — Расшифровка цифровой подписи S с помощью открытого ключа e и вычисление её хэш-значения m’=S e (mod п)

    — Вычисление хэш-значения принятого открытого текста M

    — Сравнение хэш-значений т и т’ если т = т’то цифровая подпись S – достоверна.

    Процедуру формирования ЭЦП сообщения М рассмотрим на следующем простом примере:

    Хешируемое сообщение M представим как последовательность целых чисел 312. В соответствии с приведённым выше алгоритмом формирования ЭЦП RSA выбираем два взаимно простых числа р = 3, q = 11, вычисляем значение п=p*q = 3*11 = 33, выбираем значение секретного ключа d =7 и вычисляем значение открытого ключа е = 3. Вектор инициализации Н выбираем равным 6 (выбирается случайным образом). Хэш-код сообщения M=312 формируется следующим образом:

    Н1 = (M1 + H) 2 (mod п) = (3 + 6) 2 (mod 33) = 81 (mod 33) = 15;

    Н3 = (М3 + H2) 2 (mod п) = (2 + 25) 2 (mod 33) = 729 (mod 33) = 3; т = 3

    Для получения ЭЦП шифруем хэш-значение m с помощью секретного ключа d и отправляем получателю цифровую подпись S = m d (mod n) и открытый текст сообщения M: S = 3 7 (mod 33) =2187 (mod 33) = 9

    Проверка подлинности ЭЦП

    Расшифровка S (т.е. вычисление её хэш-значения т’) производится с помощью открытого ключа е.

    m’= S e (mod п) = 9 3 (mod 33) =729 (mod 33) = 3

    Если сравнение хэш-значений т’ и т показывает их равенство, т.е. т = m’ то подпись достоверна.

    Схема формирования ЭЦП Эль Гамаля

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

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

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

    1) Определение открытого «у» и секретного «x» ключей (действия отправителя)

    — Выбор двух взаимно простых больших чисел р и q,q

    — Выбор значения секретного ключа х,х x (mod р)

    2) Формирование ЭЦП

    — Вычисление хэш-значения сообщения M: т =h(M)

    — Выбор случайного числа k,0 k (mod р)

    — Определение значения bиз выражения:

    — Цифровая подпись S = (а, b) и открытый текст сообщения M отправляются получателю.

    3)Аутентификация сообщения — проверка подлинности подписи (действия получателя)

    — Вычисление хэш-значения принятого открытого текста сообщения M

    — Подпись считается достоверной, если а a a b (mod р) = q m’ (mod р)

    4) В качестве процедуры формирования ЭЦП рассмотрим следующий пример (для удобства расчётов в данном примере использованы числа малой разрядности):

    — Выбираем простое число р и два случайных числа qи х(q и х x (mod р) = 2 8 ( mod 11) = 3;

    — Определяем хэш-значение исходного сообщения М, (312) т = h (M), в данном примере принимаем т = 3(методика определения хэш значения сообщения M описана в алгоритме ЭЦП RSA ).

    — Выбираем случайное целое число k, взаимно простое с р-1. Принимаем k=9, НОД(9, 10) = 1.

    — Для формирования ЭЦП вычисляем элементы подписи а и b

    а = q k (mod р) = 2 9 (mod 11) =6.

    Элемент b определяем с помощью расширенного алгоритма Евклида из следующего соотношения:

    m = (ха + kb) (mod (р-1)); 3= (8*6 + 9*b) (mod 10)) -9*b = -45(mod 10)

    В данном примере цифровой подписью является пара чисел а = 6, b = 5.

    Цифровая подпись S = (а,b) и открытый текст сообщения M отправляются получателю. Для контроля целостности сообщения и достоверности ЭЦП получатель вычисляет хэш-значение m’ принятого открытого текста сообщения M. При этом отправитель и получатель использует одну и ту же хэш-функцию h( ).

    Получив подписанное сообщение и открытый ключ у = 3, получатель для проверки подлинности подписи проверяет выполнение условия

    у a a b (mod р) = q m’ (mod р)

    3 6 *6 5 (mod 11) = 2 3 (mod 11)

    5668704(mod 11) = 8 (mod 11) 8(mod 11) = 8(mod 11),

    так как условие выполняется, то принятое получателем сообщение признаётся подлинным.

    Таким образом, процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщения.

    Следует иметь ввиду, что каждая подпись по схеме Эль Гамаля требует нового значения k. Случайное значение k должно храниться в секрете.

    2. Выполнение работы

    Задачи лабораторной работы:

    1) Разработать приложения формирования ЭЦП RSA и Эль-Гамаля.

    2) Привести сравнительную характеристику формирования ЭЦП RSA и Эль-Гамаля. Описать их преимущества и недостатки.

    3. Контрольные вопросы

    1. Изложите принципиальную схему организации обмена документами, заверенными цифровой подписью.

    2. Перечислите основные требования, предъявляемые к хэш-функции, пригодной для использования при вычислении цифровой подписи документа.

    3. Назовите и охарактеризуйте методы, реализующие ЭЦП.

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

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

    6. Сравните наиболее распространенные стандарты ЭЦП.

    | следующая лекция ==>
    Под дебиторской задолженностью понимаются. | Квалифицирующие признаки убийства, харкт-ие потерпевшего и объект.ст. (п 1-7, 15 ч.2)

    Дата добавления: 2020-11-12 ; просмотров: 2296 | Нарушение авторских прав

    Илон Маск рекомендует:  Record - Ключевое слово Delphi
    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL