ИССЛЕДОВАНИЕ И ОПТИМИЗАЦИЯ АЛГОРИТМА ЭЛЬ-ГАМАЛЯ

Введение. 4
1. Анализ предметной области. 6
1. Схема шифрования Эль-Гамаля. 6
2. Схема шифрования IEC. 6
3. Бинарное возведение в степень по модулю. 7
4. Китайская теорема об остатках 8
5. Редукция Монтгомери 9
6. Редукция Барретта 10
7. Look-up table 11
8. FFT 12
2. Разработка модификации. 15
1. Внедрение оригинальных модификаций. 1 5
2. Внедрение дополнительных модификаций. 1 5
3. Разработка оптимизированной шифросистемы. 15
3. Реализация оптимизаций. 16
1. Общие параметры. 16
2. КТО. 16
3. Монтгомери. 18
4. Барретт. 20
5. Look-up Table. 22
6. Монтгомери + КТО. 24
7. Барретт + КТО. 26
8. Модифицированный Монтгомери.
9. Модифицированный Монтгомери+КТО. 30
10. FFT. 32
11. IEC Шифрование. 34
12. IEC Расшифровывание 36
13. Окончательный вывод 3 7
4. Заключение 38
5. Список литературы 39
6. Листинг 40

Купить

Криптография - наука, занимающаяся разработкой криптосистем, то есть исследованием математических методов преобразования информации с целью защиты систем от несанкционированного доступа.
Целью данной работы является оптимизация реализации алгоритма шифрования Эль-Гамаля. Нашей главной задачей является уменьшение времени шифрования и расшифровывания. Для этого мы будем оптимизировать работу отдельных элементов алгоритма шифрования. Также мы должны измерить выигрыши по времени.
В век современных технологий время является очень ценным ресурсом. Поэтому важным показателем работы реализации является его скорость вычислений. Процесс оптимизации идет в двух направлениях:
1. Уменьшение асимптотики алгоритма. Крайне трудная задача, так как не всегда возможна. Но гарантирует выигрыш по времени при больших значениях параметров.
2. Уменьшение коэффициента в асимптотике. Есть несколько способов достижения: распараллеливание, приведение к битовой арифметике, разбиение на подзадачи,.... Основная сложность в том, что иногда сложно подсчитать получаемое изменение константы.
Алгоритм шифрования с открытым ключом Эль-Гамаля был предложен Тахером Эль-Гамалем в 1985 году. Вся схема была разработана на основе протокола Диффи-Хеллмана. Криптостойкость данного алгоритма основывается на трудности вычисления дискретного логарифма в конечном поле. Отсутствие патента на алгоритм делает его более дешевой альтернативой алгоритму RSA.
Самыми сложными операциями в шифровании являются операции взятия по модулю и операции умножения. Поэтому наша работа будет направлена на оптимизацию именно этих операций.
В ходе работы мы посмотрим на эффективность известных оптимизаций. Выберем наиболее эффективные и на основе нее реализуем оптимизированную криптосистему.

Купить