Что такое код elgamal


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

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

Основная идея 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?


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

    Я смотрел бесконечно на примерах, но я могу найти буквально ноль в Google. Ohloh менее полезен, так как я просто возвращаю бесконечные страницы исходных файлов cryptopp ElGamal, которые я, похоже, не могу понять (я относительно новичок в использовании Crypto++ и до 3 дней назад hadn ‘ даже не слышал об Эль Гамале).

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

    Тем не менее, это действительно не очень помогает мне, поскольку я не знаю, как подключить мои уже вычисленные значения. Я не уверен, что я борюсь с моим пониманием того, как Elgamal работает (полностью возможно), или если я просто идиот, когда дело доходит до использования того, что у меня есть с CryptoPP. Может ли кто-нибудь помочь указать мне в правильном направлении?

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

    Мы не можем вам помочь, потому что мы ничего не знаем о том, что должно быть сделано.

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

    Не могли бы вы узнать, что такое ключи? является эфемерным ключом ключа Диффи-Хеллмана и статическим ключом под ключ ElGamal?

    Если мое понимание правильное, это все, что мне нужно для выполнения шифрования, но я изо всех сил пытаюсь понять, как использовать Crypto++.

    Для примера шифрования я собираюсь немного обмануть и использовать пример шифрования RSA и передать его в ElGamal. Это примерно так же сложно, как копирование и вставка, поскольку шифрование RSA и шифрование ElGamal соответствуют интерфейсам PK_Encryptor и PK_Decryptor . Подробнее см. В PK_Encryptor и PK_Decryptor . (И имейте в виду, вам может понадобиться пример подписи ElGamal или Nyberg-Rueppel (NR)).

    Crypto++ имеет криптосистему, построенную на ElGamal. Криптосистема будет шифровать большой блок обычного текста под симметричным ключом, а затем зашифровать симметричный ключ под ключом ElGamal. Я не уверен, какой стандарт это следует, хотя (вероятно, IEEE P1363). См. SymmetricEncrypt и SymmetricDecrypt в файле elgamal.h.

    Размер ключа искусственно мал, поэтому программа работает быстро. ElGamal является проблемой дискретного журнала, поэтому его размер ключа должен быть на 2048 бит или выше на практике. 2048 бит одобрены ECRYPT (Азия), ISO/IEC (Worldwide), NESSIE (Европа) и NIST (США).

    Если вам нужно сохранить/перенести/загрузить созданные вами ключи, см. Раздел » Ключи и форматы» в Crypto++ wiki. Короткий ответ — вызвать decryptor.Save() и decryptor.Load() ; и избегайте кодирования .

    Если вы хотите, вы можете использовать стандартную string а не SecByteBlock . string будет проще, если вы хотите печатать материал на терминале через cout и друзей.

    Наконец, теперь есть страница в Crypto++ Wiki, посвященная теме с исходным кодом для программы ниже. См. Crypto++ Шифрование ElGamal.

    Вы также можете создать Decryptor из PrivateKey следующим образом:

    И Encryptor из PublicKey :

    Вы можете сохранять и загружать ключи на диск и с него следующим образом:

    Ключи закодированы в ASN.1, поэтому вы можете сбросить их с помощью чего-то вроде Peter Gutmann dumpasn1 :

    ElGamal encryption example?

    I apologise in advance for the n00bishness of asking this question, but I’ve been stuck for ages and I’m struggling to figure out what to do next. Essentially, I am trying to perform ElGamal encryption on some data. I have been given the public part of an ephemeral key pair and a second static key, as well as some data. If my understanding is correct, this is all I need to perform the encryption, but I’m struggling to figure out how using Crypto++.

    I’ve looked endlessly for examples, but I can find literally zero on Google. Ohloh is less than helpful as I just get back endless pages of the cryptopp ElGamal source files, which I can’t seem to be able to figure out (I’m relatively new to using Crypto++ and until about 3 days ago hadn’t even heard of ElGamal).

    The closest I’ve been able to find as an example comes from the CryptoPP package itself, which is as follows:

    However, this doesn’t really seem to help me much as I’m unaware of how to plug in my already computed values. I am not sure if I’m struggling with my understanding of how Elgamal works (entirely possible) or if I’m just being an idiot when it comes to using what I’ve got with CryptoPP. Can anyone help point me in the right direction?

    1 Answer 1

    I have been given the public part of an ephemeral key pair and a second static key, as well as some data.

    We can’t really help you here because we know nothing about what is supposed to be done.

    The ephemeral key pair is probably for simulating key exchange, and the static key is long term for signing the ephemeral exchange. Other than that, its anybody’s guess as to what’s going on.

    Would you happen to know what the keys are? is the ephemeral key a Diffie-Hellman key and the static key an ElGamal signing key?

    If my understanding is correct, this is all I need to perform the encryption, but I’m struggling to figure out how using Crypto++.

    For the encryption example, I’m going to cheat a bit and use an RSA encryption example and port it to ElGamal. This is about as difficult as copy and paste because both RSA encryption and ElGamal encryption adhere to the the PK_Encryptor and PK_Decryptor interfaces. See the PK_Encryptor and PK_Decryptor classes for details. (And keep in mind, you might need an ElGamal or Nyberg-Rueppel (NR) signing example).

    Crypto++ has a cryptosystem built on ElGamal. The cryptosystem will encrypt a large block of plain text under a symmetric key, and then encrypt the symmetric key under the ElGamal key. I’m not sure what standard it follows, though (likely IEEE’s P1363). See SymmetricEncrypt and SymmetricDecrypt in elgamal.h.

    The key size is artificially small so the program runs quickly. ElGamal is a discrete log problem, so its key size should be 2048-bits or higher in practice. 2048-bits is blessed by ECRYPT (Asia), ISO/IEC (Worldwide), NESSIE (Europe), and NIST (US).

    If you need to save/persist/load the keys you generate, then see Keys and Formats on the Crypto++ wiki. The short answer is to call decryptor.Save() and decryptor.Load() ; and stay away from the encodings.

    Илон Маск рекомендует:  Добавление приложения


    If you want, you can use a standard string rather than a SecByteBlock . The string will be easier if you are interested in printing stuff to the terminal via cout and friends.

    Finally, there’s now a page on the Crypto++ Wiki covering the topic with the source code for the program below. See Crypto++’s ElGamal Encryption.

    You can also create the Decryptor from a PrivateKey like so:

    And an Encryptor from a PublicKey :

    You can save and load keys to and from disk as follows:

    The keys are ASN.1 encoded, so you can dump them with something like Peter Gutmann’s dumpasn1 :

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

    Секция: 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 Encryption Algorithm

    ElGamal encryption is an public-key cryptosystem. It uses asymmetric key encryption for communicating between two parties and encrypting the message.
    This cryptosystem is based on the difficulty of finding discrete logarithm in a cyclic group that is even if we know g a and g k , it is extremely difficult to compute g ak .

    Илон Маск рекомендует:  Атрибут itemscope в HTML


    Idea of ElGamal cryptosystem
    Suppose Alice wants to communicate to Bob.

    1. Bob generates public and private key :
      • Bob chooses a very large number q and a cyclic group Fq.
      • From the cyclic group Fq, he choose any element g and
        an element a such that gcd(a, q) = 1.
      • Then he computes h = g a .
      • Bob publishes F, h = g a , q and g as his public key and retains a as private key.
    2. Alice encrypts data using Bob’s public key :
      • Alice selects an element k from cyclic group F
        such that gcd(k, q) = 1.
      • Then she computes p = g k and s = h k = g ak .
      • She multiples s with M.
      • Then she sends (p, M*s) = (g k , M*s).
    3. Bob decrypts the message :
      • Bob calculates s ′ = p a = g ak .
      • He divides M*s by s ′ to obtain M as s = s ′ .

    Following is the implementation of ElGamal cryptosystem in Python

    Что такое код elgamal

    Overview: elgamal is a python module that lets you encrypt and decrypt text using the ElGamal Cryptosystem.

    Intended Use: This program was created as an exercise in cryptography in one of my classes at the University of Kentucky. I later turned it into a module. I do not recommend you use it to protect any sensitive information.

    Using elgamal: Install elgamal by downloading elgamal.py and placing it in your module search path.

    If you don’t know your module search path, fire up a python console and run

    To generate a public/private key pair do

    By default generate_keys() generates a key of 256 bits with probability 0.9999999997671694 (1-(2^-32)) that your key is prime. You can alter the bitness of your keys and the certainty that your key is prime by passing arguments n and t like this.

    where n is the number of bits you want your key to have and t means the probability that the key is prime is 1-(2^-t).

    To encrypt a message do

    To decrypt the cipher text do

    Compatibility: Python 3.4. Does not work in python 2.7!

    Пример шифрования ElGamal?

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

    Я смотрел бесконечно на примерах, но я могу найти буквально ноль в Google. Ohloh менее полезен, так как я просто возвращаю бесконечные страницы исходных файлов cryptopp ElGamal, которые я, похоже, не могу понять (я относительно новичок в использовании Crypto++ и до 3 дней назад hadn ‘ даже не слышал об Эль Гамале).

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

    Тем не менее, это действительно не очень помогает мне, поскольку я не знаю, как подключить мои уже вычисленные значения. Я не уверен, что я борюсь с моим пониманием того, как Elgamal работает (полностью возможно), или если я просто идиот, когда дело доходит до использования того, что у меня есть с CryptoPP. Может ли кто-нибудь помочь указать мне в правильном направлении?

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

    Мы не можем вам помочь, потому что мы ничего не знаем о том, что должно быть сделано.

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

    Не могли бы вы узнать, что такое ключи? является эфемерным ключом ключа Диффи-Хеллмана и статическим ключом под ключ ElGamal?

    Если мое понимание правильное, это все, что мне нужно для выполнения шифрования, но я изо всех сил пытаюсь понять, как использовать Crypto++.

    Для примера шифрования я собираюсь немного обмануть и использовать пример шифрования RSA и передать его в ElGamal. Это примерно так же сложно, как копирование и вставка, поскольку шифрование RSA и шифрование ElGamal соответствуют интерфейсам PK_Encryptor и PK_Decryptor . Подробнее см. В PK_Encryptor и PK_Decryptor . (И имейте в виду, вам может понадобиться пример подписи ElGamal или Nyberg-Rueppel (NR)).

    Crypto++ имеет криптосистему, построенную на ElGamal. Криптосистема будет шифровать большой блок обычного текста под симметричным ключом, а затем зашифровать симметричный ключ под ключом ElGamal. Я не уверен, какой стандарт это следует, хотя (вероятно, IEEE P1363). См. SymmetricEncrypt и SymmetricDecrypt в файле elgamal.h.

    Размер ключа искусственно мал, поэтому программа работает быстро. ElGamal является проблемой дискретного журнала, поэтому его размер ключа должен быть на 2048 бит или выше на практике. 2048 бит одобрены ECRYPT (Азия), ISO/IEC (Worldwide), NESSIE (Европа) и NIST (США).

    Если вам нужно сохранить/перенести/загрузить созданные вами ключи, см. Раздел » Ключи и форматы» в Crypto++ wiki. Короткий ответ — вызвать decryptor.Save() и decryptor.Load() ; и избегайте кодирования .

    Если вы хотите, вы можете использовать стандартную string а не SecByteBlock . string будет проще, если вы хотите печатать материал на терминале через cout и друзей.

    Наконец, теперь есть страница в Crypto++ Wiki, посвященная теме с исходным кодом для программы ниже. См. Crypto++ Шифрование ElGamal.

    Вы также можете создать Decryptor из PrivateKey следующим образом:

    И Encryptor из PublicKey :


    Вы можете сохранять и загружать ключи на диск и с него следующим образом:

    Ключи закодированы в ASN.1, поэтому вы можете сбросить их с помощью чего-то вроде Peter Gutmann dumpasn1 :

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

    Секция: 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. Шифрование сообщения


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

    Илон Маск рекомендует:  Svg worldmap example

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

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

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

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

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

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

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

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

    Также абонент ─ первообразный корень по модулю : . Далее выбирается случайное натуральное число , меньшее и не равное 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ды

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

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

    Алгоритмы шифрования с открытым ключом и ЭЦП были опубликованы Т. Эль-Гамалем (Taher Elgamal) в 1984 г. Криптографическая система Эль-Гамаля использует ту же математическую основу, что и рассмотренная ранее схема распределения ключей Диффи — Хеллмана. Шифрование фактически производится путем умножения сообщения на общий секретный ключ системы Диффи — Хеллмана.

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

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

    Пусть имеются абоненты А и В, которые хотят обмениваться секретными сообщениями, не имея защищенных каналов связи. Система Эль-Гамаля легко обобщается на случай нескольких абонентов. Для всей группы абонентов выбирается большое простое число р и число g, такое, что 1 13 mod 23 = 21.

    Абонент А выбирает случайное число /г, например к = 7, и вычисляет:


    А пересылает абоненту В пару (17, 12).

    Абонент В вычисляет

    Абонент В смог расшифровать переданное сообщение.

    Шифрование ElGamal

    Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения Mсначала выбирается случайное число k, взаимно простое с p- 1. Затем вычисляются

    Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого текста. Для дешифрирования (a,b) вычисляется

    Так как a x º g kx (mod p) и b/a x º y k M/a x º g xk M/ g kx = M (mod p), то все работает (см. Табл. 19-6). По сути это то же самое, что и обмен ключами Диффи-Хеллмана (см. раздел 22.1)за исключением того, что y- это часть ключа, а при шифровании сообщение умножается на y k .

    Табл. 19-6.
    Шифрование ElGamal

    Открытый ключ:

    x mod p

    p простое число (может быть общим для группы пользователей)
    g

    Закрытый ключ:

    Шифрование:

    k выбирается случайным образом, взаимно простое с p-1
    a (шифротекст) =g k mod p
    b (шифротекст)= y k Mmod p

    Дешифрирование:

    M (открытый текст) = b/a x mod p

    Скорость

    Некоторые примеры скорости работы программных реализаций EIGamal приведены в Табл. 19-7 [918].

    Табл. 19-7.
    Скорости EIGamal для различных длин модулей при 160-битовом показателе степени (на SPARC II)

    512 битов 768 битов 1024 битов
    Шифрование 0.33 с 0.80 ñ 1.09 ñ
    Дешифрирование 0.24 ñ 0.58 ñ 0.77 ñ
    Подпись 0.25 ñ 0.47 ñ 0.63 ñ
    Проверка l.37 ñ 5.12 ñ 9.30 c

    Патенты

    ElGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что PKP считает, что этот алгоритм попадает под действие патента Диффи-Хеллмана [718]. Однако срок действия патента Диффи-Хеллмана заканчивается 29 апреля 1997 года, что делает ElGamal первым криптографическим плгоритмом с открытыми ключами, пригодным для шифрования и цифровых подписей и несвязанным в Соединенных Штатах патентами. Я не могу дождаться этого момента.

    McEliece

    В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с открытыми ключами на основе теории алгебраического кодирования [1041]. Этот алгоритм использует существование определенного класса исправляющих ошибки кодов, называемых кодами Гоппа (Goppa).Он предлагал создать код Гоппа и замаскировать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной. Хорошее описание этого алгоритма можно найти в [1233], см. также [1562]. Ниже приведен только краткий обзор.

    Пусть dH(x,y) обозначает расстояние Хэмминга между xи y. Числа n, k и tслужат параметрами системы.

    Закрытый ключ состоит из трех частей: G’- это матрица генерации года Гоппа, исправляющего tошибок. P-это матрица перестановок размером n*n. S- это nonsingular матрица размером k*k.

    Открытым ключом служит матрица G размером k*n: G= SG’P.

    Открытый текст сообщений представляет собой строку kбитов в виде k-элементного вектора над полем GF(2).

    Для шифрования сообщения случайным образом выбирается n-элементный вектор z над полем GF(2), для которого расстояние Хэмминга меньше или равно t.

    Для дешифрирования сообщения сначала вычисляется c’= cP -1 . Затем с помощью декодирующего алгоритма для кодов Гоппа находится m’, для которого dH(m’G,c) меньше или равно t.Наконец вычисляется m = m’S -1 .

    В своей оригинальной работе МакЭлис предложил значения n= 1024, t= 50 и k= 524. Это минимальные значения, требуемые для безопасности.

    Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и вне появлялось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографическом сообществе. Схема на два-три порядка быстрее, чем RSA, но у нее есть ряд недостатков. Открытый ключ огромен: 2 19 битов. Сильно увеличивается объем данных — шифротекст в два раза длиннее открытого текста.

    Ряд попыток криптоанализа этой системы можно найти в [8, 943, 1559, 306]. Ни одна из них не достигла успеха для общего случая, хотя сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного волнует.

    В 1991 два русских криптографа заявили, что взломали систему МакЭлиса с некоторыми параметрами [882]. В их статье это утверждение не было обосновано, и большинство криптографов не приняли во внимание этот результат. Еще одно выполненное русскими вскрытие, которое нельзя непосредственно использовать против системы МакЭлиса, описано в [1447, 1448]. Расширения McEliece можно найти в [424, 1227, 976].

    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL