Расшифровать сообщение эль гамаля

Обновлено: 30.06.2024

Идея криптосистемы Эль-Гамаля
Предположим, Алиса хочет общаться с Бобом.

Ниже приводится реализация криптосистемы ElGamal в Python.

from math import pow

a = random.randint( 2 , 10 )

return gcd(b, a % b)

key = random.randint( pow ( 10 , 20 ), q)

while gcd(q, key) ! = 1 :

key = random.randint( pow ( 10 , 20 ), q)

def encrypt(msg, q, h, g):

for i in range ( 0 , len (msg)):

print ( "g^k used : " , p)

print ( "g^ak used : " , s)

for i in range ( 0 , len (en_msg)):

en_msg[i] = s * ord (en_msg[i])

return en_msg, p

def decrypt(en_msg, p, key, q):

h = power(p, key, q)

for i in range ( 0 , len (en_msg)):

dr_msg.append( chr ( int (en_msg[i] / h)))

print ( "Original Message :" , msg)

q = random.randint( pow ( 10 , 20 ), pow ( 10 , 50 ))

g = random.randint( 2 , q)

h = power(g, key, q)

print ( "g used : " , g)

print ( "g^a used : " , h)

en_msg, p = encrypt(msg, q, h, g)

dr_msg = decrypt(en_msg, p, key, q)

print ( "Decrypted Message :" , dmsg);

if __name__ = = '__main__' :

Шифровка. Метод Эль-Гамаля
Здравствуйте! Решил написать шифровку текста по методу Эль-Гамаля. Написал программу(пока только.

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

Шифрование по алгоритму RSA
Криптосистема шифрования данных RSA Не получается дешифрование. Что не так? Пара чисел (e,n) .

Вопрос снят. Разобрался. Дело было в процедуре decrypt, а точнее в процессе распознавания строки для присвоения значений переменным a и b, как я и думал.

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

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

Протокол Диффи—Хеллмана

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

Протокол обмена состоит из следующих действий.

Алиса выбирает случайное
Боб выбирает случайное
Боб вычисляет сессионный ключ
Алиса вычисляет

Алиса выбирает случайное
Меллори выбирает случайное
Меллори вычисляет сессионный ключ для канала с Алисой

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

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

Стороны договорились о группе точек эллиптической кривой , её циклической подгруппе мощности и генераторе группы (или хотя бы достаточно большой подгруппы группы ).
Алиса выбирает случайное
Боб выбирает случайное
Боб вычисляет точку
Алиса вычисляет точку

Протокол Эль-Гамаля

Протокол Эль-Гамаля ([ElGamal, 1984], [ElGamal, 1985]) за счёт предварительного распространения открытого ключа одной из сторон обеспечивает аутентификацию ключа для этой стороны. Можно гарантировать, что только владелец соответствующего закрытого ключа сможет вычислить сеансовый ключ. Однако подтверждение факта получение ключа (выполнение целей G1 и G8) не является частью протокола.

Протокол MTI/A(0)

В 1986 году Ц. Мацумото (Tsutomu Matsumoto), И. Такашима (Youichi Takashima) и Х. Имаи (Hideki Imai) предложили несколько алгоритмов, позже названных семейством протоколов MTI ([Matsumoto, Tsutomu, Imai 1986]). За счёт предварительного распространения открытых ключей обоих сторон они обеспечивали неявную аутентификацию ключа (цель G7). То есть сессионный ключ гарантированно мог получить только владельцы соответствующих открытых ключей. Мы рассмотрим одного из представителей данного семейства — протокол MTI/A(0).

Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .

Алиса сгенерировала случайное число
Боб сгенерировал случайное число
Боб вычислил сеансовый ключ
Алиса вычислила сеансовый ключ

Протокол Station-to-Station

Протокол STS (Station-to-Station, [Diffie, Oorschot, Wiener 1992]) предназначен для систем мобильной связи. Он использует идеи протокола Диффи—Хеллмана и криптосистемы RSA. Особенностью протокола является использование механизма электронной подписи для взаимной аутентификации сторон.

Каждая из сторон и обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи и открытым ключом для шифрования и проверки подписи .

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

Как показала атака Лоу 1996 года ([Lowe 1996]), протокол не может гарантировать аутентификацию субъектов (цель G1), ключей (G7) и подтверждение владения сессионным ключом (G8). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.

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

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

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

Процесс шифрования и дешифрования изображен на следующей иллюстрации —

Наиболее важные свойства схемы шифрования с открытым ключом —

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

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

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

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

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

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

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

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

Существует три типа схем шифрования с открытым ключом. Мы обсудим их в следующих разделах —

Криптосистема RSA

Эта криптосистема является одной из исходных систем. Это остается наиболее используемой криптосистемой даже сегодня. Система была изобретена тремя учеными Роном Ривестом, Ади Шамиром и Леном Адлеманом, и, следовательно, она называется криптосистемой RSA.

Мы увидим два аспекта криптосистемы RSA: во-первых, создание пары ключей и, во-вторых, алгоритмы шифрования-дешифрования.

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

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

Генерация модуля RSA (n)

Выберите два больших простых числа, p и q.

Рассчитайте n = p * q. Для надежного неразрушимого шифрования пусть n будет большим числом, обычно не менее 512 бит.

Найти производное число (е)

Число e должно быть больше 1 и меньше (p — 1) (q — 1).

Не должно быть общего множителя для e и (p — 1) (q — 1), за исключением 1. Другими словами, два числа e и (p — 1) (q — 1) взаимно просты.

Форма открытого ключа

Пара чисел (n, e) образует открытый ключ RSA и становится открытой.

Интересно, что хотя n является частью открытого ключа, сложность факторизации большого простого числа гарантирует, что злоумышленник не сможет найти за конечное время два простых числа (p & q), использованных для получения n. Это сила ОГА.

Генерация закрытого ключа

Закрытый ключ d рассчитывается из p, q и e. Для данных n и e существует уникальное число d.

Число d является обратной величиной e по модулю (p — 1) (q — 1). Это означает, что d является числом, меньшим (p — 1) (q — 1), так что при умножении на e оно равно 1 по модулю (p — 1) (q — 1).

Это соотношение записано математически следующим образом:

Генерация модуля RSA (n)

Выберите два больших простых числа, p и q.

Найти производное число (е)

Число e должно быть больше 1 и меньше (p — 1) (q — 1).

Форма открытого ключа

Пара чисел (n, e) образует открытый ключ RSA и становится открытой.

Генерация закрытого ключа

Закрытый ключ d рассчитывается из p, q и e. Для данных n и e существует уникальное число d.

Это соотношение записано математически следующим образом:

Расширенный Евклидов Алгоритм принимает p, q и e в качестве входных данных и дает d в качестве выходных данных.

пример

Пример генерации пары ключей RSA приведен ниже. (Для простоты понимания простые числа p & q, взятые здесь, являются небольшими значениями. На практике эти значения очень высоки).

Пусть два простых числа p = 7 и q = 13. Таким образом, модуль n = pq = 7 x 13 = 91.

Выберите e = 5, что является допустимым выбором, поскольку не существует числа с общим множителем 5 и (p — 1) (q — 1) = 6 × 12 = 72, кроме 1.

Введите p = 7, q = 13 и e = 5 в расширенный евклидов алгоритм. Выход будет d = 29.

Проверьте правильность рассчитанного значения d, рассчитав:

Пусть два простых числа p = 7 и q = 13. Таким образом, модуль n = pq = 7 x 13 = 91.

Введите p = 7, q = 13 и e = 5 в расширенный евклидов алгоритм. Выход будет d = 29.

Следовательно, открытый ключ (91, 5) и закрытый ключ (91, 29).

Шифрование и дешифрование

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

Интересно, что RSA не работает напрямую со строками битов, как в случае шифрования с симметричным ключом. Он работает по номерам по модулю n. Следовательно, необходимо представлять открытый текст в виде последовательности чисел, меньшей n.

RSA шифрование

Затем отправитель представляет открытый текст в виде последовательности чисел, меньшей n.

Для шифрования первого открытого текста P, который является числом по модулю n. Процесс шифрования является простым математическим шагом, так как —

Затем отправитель представляет открытый текст в виде последовательности чисел, меньшей n.

Другими словами, зашифрованный текст C равен открытому тексту P, умноженному на него e раз, а затем уменьшенному по модулю n. Это означает, что C также число меньше n.

Возвращаясь к нашему примеру генерации ключей с открытым текстом P = 10, мы получаем зашифрованный текст C —

Расшифровка RSA

Процесс дешифрования для RSA также очень прост. Предположим, что получатель пары открытого ключа (n, e) получил зашифрованный текст C.

Получатель поднимает C до уровня своего личного ключа d. Результат по модулю n будет открытым текстом P.

Возвращаясь снова к нашему числовому примеру, зашифрованный текст C = 82 расшифровывается до номера 10 с использованием закрытого ключа 29 —

Анализ RSA

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

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

Генерация ключа . Сложность определения личного ключа из открытого ключа RSA эквивалентна факторизации модуля n. Таким образом, злоумышленник не может использовать знание открытого ключа RSA для определения закрытого ключа RSA, если он не может указать n. Это также односторонняя функция, переход от значений p & q к модулю n прост, но обратный процесс невозможен.

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

Сила шифрования RSA резко снижается против атак, если числа p и q не являются большими простыми числами и / или выбранный открытый ключ e является небольшим числом.

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

Наряду с RSA предлагаются и другие криптосистемы с открытым ключом. Многие из них основаны на разных версиях проблемы дискретного логарифма.

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

Давайте рассмотрим простую версию ElGamal, которая работает с числами по модулю p. В случае вариантов эллиптической кривой она основана на совершенно разных системах счисления.

Генерация пары ключей Эль-Гамаля

Каждый пользователь криптосистемы ElGamal генерирует пару ключей следующим образом:

Выбор большого простого числа p. Обычно выбирается простое число длиной от 1024 до 2048 бит.

Выбор элемента генератора g.

Это число должно быть от 1 до p — 1, но не может быть любым числом.

Это генератор мультипликативной группы целых чисел по модулю p. Это означает, что для любого целого числа m, взаимно простого с p, существует такое целое число k, что g k = a mod n.

Например, 3 является генератором группы 5 (Z ₅ = ).

Выбор большого простого числа p. Обычно выбирается простое число длиной от 1024 до 2048 бит.

Выбор элемента генератора g.

Это число должно быть от 1 до p — 1, но не может быть любым числом.

Например, 3 является генератором группы 5 (Z ₅ = ).

Выбор закрытого ключа. Закрытый ключ x — это любое число больше 1 и меньше p − 1.

Вычислительная часть открытого ключа. Значение y вычисляется из параметров p, g и закрытого ключа x следующим образом:

Выбор закрытого ключа. Закрытый ключ x — это любое число больше 1 и меньше p − 1.

Получение открытого ключа. Открытый ключ Эль-Гамаля состоит из трех параметров (p, g, y).

Например, предположим, что p = 17 и g = 6 (можно подтвердить, что 6 является генератором группы Z ₁₇ ). Закрытый ключ x может быть любым числом больше 1 и меньше 71, поэтому мы выбираем x = 5. Затем значение y вычисляется следующим образом:

Получение открытого ключа. Открытый ключ Эль-Гамаля состоит из трех параметров (p, g, y).

Таким образом, закрытый ключ равен 62, а открытый ключ — (17, 6, 7).

Шифрование и дешифрование

Генерирование пары ключей Эль-Гамаля сравнительно проще, чем эквивалентный процесс для RSA. Но шифрование и дешифрование немного сложнее, чем RSA.

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

Отправитель представляет собой открытый текст в виде последовательности чисел по модулю p.

Для шифрования первого открытого текста P, который представлен в виде числа по модулю p. Процесс шифрования для получения зашифрованного текста C выглядит следующим образом:

Произвольно сгенерировать число k;
Вычислить два значения С1 и С2, где —

Отправитель представляет собой открытый текст в виде последовательности чисел по модулю p.

Отправьте зашифрованный текст C, состоящий из двух отдельных значений (C1, C2), отправленных вместе.

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

Произведите случайное число, скажем, к = 10
Вычислить два значения С1 и С2, где —

Отправьте зашифрованный текст C, состоящий из двух отдельных значений (C1, C2), отправленных вместе.

Отправьте зашифрованный текст C = (C1, C2) = (15, 9).

Эль-Гамальская расшифровка

Чтобы расшифровать зашифрованный текст (C1, C2) с помощью закрытого ключа x, предпринимаются следующие два шага:

Вычислить модульную обратную величину (C1) x по модулю p, которая равна (C1) -x , обычно называемому коэффициентом дешифрования.

Получите открытый текст, используя следующую формулу —

В нашем примере для расшифровки зашифрованного текста C = (C1, C2) = (15, 9) с использованием закрытого ключа x = 5 коэффициент дешифрования равен

Извлечь открытый текст P = (9 × 9) мод 17 = 13.

Эль-Гамаль Анализ

В системе ElGamal каждый пользователь имеет закрытый ключ x. и имеет три компонента открытого ключа — простой модуль p, генератор g и открытый Y = g x mod p . Сила Эль-Гамаля основана на сложности проблемы дискретного логарифма.

Размер безопасного ключа обычно> 1024 бит. Сегодня используется даже ключ длиной 2048 бит. Что касается скорости обработки, Elgamal довольно медленный, он используется в основном для протоколов аутентификации ключей. Из-за более высокой эффективности обработки варианты ElGamal с эллиптической кривой становятся все более популярными.

Криптография с эллиптической кривой (ECC)

Криптография с эллиптической кривой (ECC) — это термин, используемый для описания набора криптографических инструментов и протоколов, безопасность которых основана на специальных версиях проблемы дискретного логарифма. Он не использует числа по модулю p.

ECC основан на наборах чисел, которые связаны с математическими объектами, называемыми эллиптическими кривыми. Существуют правила сложения и вычисления кратных этих чисел, так же как и для чисел по модулю p.

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

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

Более короткие ключи дают два преимущества:

Простота управления ключами
Эффективные вычисления

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

Читайте также: