33656

Метод Эль-Гамаля

Доклад

Информатика, кибернетика и программирование

1 WP1 = 1 mod P Затем генерируется секретный ключ Ха из диапазона 1 X P1. Затем вычисляется открытый ключ Y как степень: Y = WX mod P. Затем выбрав число K мы вычисляем число R по формуле : R = YK mod P. Для ее формирования используется операция побитового сложения по модулю 2: C1 = WK mod P 5.

Русский

2013-09-06

103 KB

23 чел.

21.метод Эль-Гамаля

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

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

В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма, т.е если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.

Основу системы составляют параметры Р и W - числа, первое из которых - очень большое простое целое число (несколько сотен десятичных разрядов), а второе - целое. Т.к. программная реализация алгоритмов, которые позволяли бы работать с большими числами, очень трудна, то в лабораторной работе я использую числа до 1018 чего вполне достаточно для применения ее в учебных целях.

Число W находится из условий:

0 < W < P-1         (5.1)

WP-1 = 1 mod P  

Затем генерируется секретный ключ Ха из диапазона 1 Xa P-1.

Затем вычисляется открытый ключ Ya как степень:

Ya = WXa mod P.        (5.2)

Для того чтобы зашифровать сообщение М выбирается дополнительное число К удовлетворяющее условию 1 K P-1. Сообщение М – это ничто иное, как 1 символ текста, или, точнее говоря, ASCII-код символа (от 0 до 255).

Затем, выбрав число K, мы вычисляем число R по формуле :

R = YaK mod P.        (5.3)

Криптограмма, или закодированное сообщение,  формируется из двух элементов. Для ее формирования используется операция побитового сложения по модулю 2:

C1 = WK mod P,        (5.4)

C2 = M  R.

Для восстановления по криптограмме С исходного сообщения сначала используя С1 находят R, для этого возводят С1 в степень Ха по модулю Р:

R = C1Xa mod P = WKXa mod P = (WXa)K mod P = YaK mod P. (5.5)

Если известно R то дешифрование исходного текста не представляет какой-либо трудности. Дешифрование производится по формуле:

M = C2  R.        (5.6)

Таким образом в лабораторной работе происходит циклическое считывание из исходного файла по 1 символу, который затем интерпретируется как ASCII-код и помещается в переменную М. Затем происходит сохранение результата сложения по M xor R в выходном файле, что и представляет собой криптограмму С2. В начало же выходного файла (самым первым его байтом) записывается полученное значение элемента криптограммы С1, поэтому размер закодированного файла больше исходного на 1 байт. При декодировании из закодированного файла сначала считывается первый байт С1, который будет необходим для вычисления R, а затем также циклически происходит побайтовое считывание закодированного файла.


 

А также другие работы, которые могут Вас заинтересовать

71346. Периферийные устройства ЭВМ 1.1 MB
  Учебное пособие «Администрирование локальных вычислительных сетей» по дисциплине ЭВМ и телекоммуникации» предназначено для студентов Псковского государственного политехнического института специальности 220100 «Вычислительные машины, комплексы, системы и сети очно-заочной форм обучения.
71348. Глобализация - отличительная черта современного мирового сообщества 600 KB
  К глобальным проблемам человечества следует отнести, прежде всего, такие, как предотвращение третьей мировой войны, охрана окружающей среды и борьба с техногенными катастрофами, энергетическая, сырьевая, продовольственная, а также освоение космоса и Мирового океана...
71349. Восстановление деталей обработкой под ремонтный размер 678.5 KB
  Ремонтные размеры делятся на регламентированные – размеры и допуски устанавливает изготовитель, детали с регламентными размерами выпускает промышленность (поршни, поршневые кольца и т.д.); ремонтные предприятия обрабатывают под эти размеры сопряженные детали...
71350. Понятие о военной и экстремальной медицине 421 KB
  Военная медицина стала оформляться в самостоятельную область знаний с появлением постоянных армий. В России это конец XVIIначало XVIII веков когда возникла необходимость иметь в составе регулярной армии военно-медицинскую службу ВМС предназначенную для медицинского обеспечения войск.
71351. КУРС ЛЕКЦЫЙ “БІБЛІЯТЭКАЗНАЎСТВА. ГІСТОРЫЯ” 1.24 MB
  “Бібліятэказнаўства: Гісторыя” раскрывае сусветную гісторыю бібліятэчнай справы, вывучае патрэбнасці грамадства ў бібліятэцы, яе ролю ў вытворчым і культурным жыцці. Вывучэнне сусветнай гісторыі бібліятэчнай справы як састаўной часткі сусветнай культуры неабходна для разумення...
71352. Возникновение государства у восточных славян (VIII-IX века) 931 KB
  В течение веков город оставался крупным торговым политическим и военным центром на северо-западе России. Опричнина ухудшила экономическое и политическое положение России установила в ней режим страха и насилия укрепила личную власть Ивана Грозного.
71353. ПРЕДМЕТ И МЕТОДЫ ИСТОРИИ ЗЕМЕЛЬНО-ИМУЩЕСТВЕННЫХ ОТНОШЕНИЙ И ЗЕМЛЕУСТРОЙСТВА 588.5 KB
  Развитие любого общества немыслимо без использования земли. Земля выступает в качестве средства производства во всех отраслях и сферах деятельности людей. Роль земли в отдельных отраслях производства неодинакова.