An application as course project for IOZLD for Technical University of Sofia
В криптографията ElGamal е алгоритъм за криптиране с асиметричен ключ за криптография с публичен ключ, който се основава на обмена на ключове на Diffie-Hellman. Описан е за първи път от Тахер Елгамал през 1985 г. Шифроването с ElGamal се използва в безплатния софтуер GNU Privacy Guard, последните версии на PGP и други криптосистеми. Алгоритъмът за цифров подпис (DSA) е вариант на схемата за подпис на ElGamal, която не трябва да се бърка с криптирането чрез ElGamal. Шифроването чрез ElGamal може да бъде дефинирано върху всяка циклична група G, като мултипликативна група от цели числа по модул n. Сигурността му зависи от трудността на определен проблем в G, свързан с изчисляването на дискретни логаритми.
Описание на алгоритъма:
Шифроването чрез ElGamal се състои от три компонента:
• генератор на ключове
• алгоритъм за шифроване
• алгоритъм за дешифроване
Генератор на ключове:
Нека от първата страна, Алис генерира двойка ключове, както следва:
• генерира се описание на цикличната група G от ред q, с генератор g; нека e представлява елемента на идентичност на G
• избира се произволно цяло число x от интервала {1, …, q – 1}
• изчислява се h:=g^x
• публичният ключ съдържа следните стойности – (G, q, g, h)
Алис споделя генерирания публичен ключ и запазва x като свой частен ключ, който трябва да се пази в тайна.
В програмната реализация е създаден клас ElGamal, който съдържа функцията GenerateKeys(string generatorFileName).
Алгоритъм за шифроване:
Нека от втората страна, Боб криптира съобщението M до Алис, използвайки нейния публичен ключ (G, q, g, h) както следва:
• съпоставя съобщението M към елемент m от G, използвайки обратна функция
• избира се произволно цяло число y от интервала {1, …, q – 1}
• изчислява се частния споделен ключ s:=h^y
• изчислява се c1:=g^y
• изчислява се c2:=m * s
• изпраща се шифрования текст (c1, c2) към Алис
В програмната реализация е създаден клас ElGamal, който съдържа функцията Encrypt(string publicKeyFileName, string messageFileName)
Алгоритъм за дешифроване:
Алис от своя страна дешифрова критограмата (c1, c2), използвайки своя частен ключ x, както следва:
• изчислява s:=c1^x; c1=g^y, c1^x=g^xy = h^y и това е същия частен споделен ключ използван от Боб
• изчислява се s^-1, обратното на s в групата G; може да бъде изчислено по няколко начина; ако G е подгрупа на мултипликативна група от цели числа по модул n, където n е просто число, модулната мултипликативна обратна може да бъде изчислена с помощта на разширения Евклидов алгоритъм; друга алтернатива е да се изчисли като c1^q-x
• изчислява се m:=c2 * s^-1; тази калкулация образува оригиналното съобщение m, защото c2 = m * s, следователно c2 * s^-1 = (m * s) * s^-1 = m * e = m.
• съпоставя се всеки елемент m към оригиналното съобщение M
В програмната реализация е създаден клас ElGamal, който съдържа функцията Decrypt(string privateKeyFileName, string encryptedMessageFileName)
Функция за подписване:
В програмната реализация е създаден клас ElGamal, който съдържа функцията Sign(string privateKeyFileName, string messageFileName)
Функция за потвърждение на подписването:
В програмната реализация е създаден клас ElGamal, който съдържа функцията VerifySignature(string publicKeyFileName, string messageFileName, string signatureFileName)
Частна функция за изчисление на реципрочна стойност:
В програмната реализация е създаден клас ElGamal, който съдържа частната (private) функция MultiplicativeInverse(BigInteger a, BigInteger m)
Употреба на програмата:
• Програмата се стартира като и се подава един от следните аргументи:
• k (генериране на ключове)
• e (шифроване)
• d (дешифроване)
• s (подписване)
• v (потвърждение на подписа)
• plain-text.txt файлът трябва да съдържа число, което ще се шифрова, като не се поддържа ASCII
• generator.txt файлът трябва да съдържа на първия ред просто число, а на втория генератор число
• message-for-signing.txt файлът съдържа числото, което ще бъде подписано