ЛИСП-реализации алгоритма кодирования информации Эль Гамаля

Содержание

Введение

1 Постановка задачи

2 Математические и алгоритмические основы решения задачи

2.1 Взаимно простые числа

2.2 Алгоритм Эль Гамаля

3 Функциональные модели и блок-схемы решения задачи

4 Программная реализация решения задачи

5 Пример выполнения программы

Заключение

Список использованных источников и литературы



Введение

Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом волновала человеческий ум с давних времен. История криптографии - ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные. Священные книги Древнего Египта, Древней Индии тому примеры.

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

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

Почему проблема использования криптографических методов в информационных системах (ИС) стала в настоящий момент особо актуальна?

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

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

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

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

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

Схема шифрования Эль Гамаля может быть использована как для формирования цифровых подписей, так и шифрования данных.

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

При использовании алгоритма шифрования Эль Гамаля длина шифротекста вдвое больше длины исходного открытого текста М.

В реальных схемах шифрования необходимо использовать в качестве модуля n большое простое число, имеющее в двоичном представлении длину 512… 1024 бит.

Следует отметить, что формирование каждой подписи по данному методу требует нового значения k, причём это значение должно выбираться случайным образом. Если нарушитель раскроет значение k, повторно используемое отправителем, то может раскрыть и секретный ключ x отправителя.

Целью данной курсовой работы является ЛИСП-реализации алгоритма кодирования информации Эль Гамаля.



1. Постановка задачи

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

Система шифрования Эль Гамаля является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость.

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

Основу системы составляют параметры p и g - числа, первое из которых - простое, а второе - целое.

Александр генерирует секретный ключ x и вычисляет открытый ключ y:

.

Если Борис хочет послать Александру сообщение m, то он выбирает случайное число k, меньшее p и вычисляет

,

.

Борис получает зашифрованное сообщение как (a, b) и отправляем Александру.

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



.

Шифрование:

Входные данные: M - сообщение, состоящее из целых чисел.

Выходные данные: T - Зашифрованное сообщение, состоящее из пары чисел.

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

Входные данные: T - Результат шифрования, представленный в виде пары чисел. Выходные данные: M - изначальное сообщение.

Пример 1.

Процедуру шифрования данных рассмотрим на следующем примере ( для удобства расчётов в данном примере использованы числа малой разрядности):

1. Выбираем два взаимно простых числа p = 11 и q = 2.

2. Выбираем значение секретного ключа x, (x < p), x = 8.

3. Вычисляем значение открытого ключа y из выражения x

.

4.Выбираем значение открытого сообщения M = 5.

5. Выбираем случайное число k = 9; НОД (9, 10) = 1.

6. Определяем значение a из выражения.

.

7. Определяем значение b из выражения:

.



Таким образом, получаем зашифрованное сообщение как

(a, b) =(6, 9)

и отправляем получателю.

8. Получатель расшифровает данный шифротекст, используя секретный ключ x и решая следующее сравнение:

.

Вычисленное значение сообщения M = 5 представляет собой заданное исходное сообщение.

Пример 2.

1. Выбираем два взаимно простых числа p = 1801 и q = 1296.

2. Выбираем значение секретного ключа x, (x < p), x = 828.

3. Вычисляем значение открытого ключа y из выражения x

.

4.Выбираем значение открытого сообщения M = 21.

5. Выбираем случайное число k = 1567; НОД (1567, 1800) = 1.

6. Определяем значение a из выражения.

.

7. Определяем значение b из выражения:

.



Таким образом, получаем зашифрованное сообщение как

(a, b) =(1335, 339)

и отправляем получателю.

8. Получатель расшифровает данный шифротекст, используя секретный ключ x и решая следующее сравнение:

.

Вычисленное значение сообщения M = 21 представляет собой заданное исходное сообщение.



2. Математические и алгоритмические основы решения задачи

2.1 Взаимно простые числа

Два целых числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.

Если среди чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми (для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают).

Свойства:

Если числа a₁,…, a_n -- попарно взаимно простые числа, то

НОК(a₁,…, a_n) = |a₁·…·a_n|.

Числа a и b взаимно просты тогда и только тогда, когда

НОД(a, b) = 1,

или, иными словами, существуют целые x и y такие, что ax + by = 1.

Если координатную сетку считать «лесом», в котором из точек с целыми координатами растут «деревья» нулевой толщины, то из начала координат видны только деревья, координаты которых взаимно просты.

Примеры:

8, 15 -- не простые, но взаимно простые.

6, 8, 9 -- взаимно простые числа, но не попарно взаимно просты.

8, 15, 49 -- попарно взаимно простые.

2.2 Алгоритм Эль Гамаля

Алгоритм Эль Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется:

y = g^x mod p.

Общедоступными ключами являются y, g и p, а секретным ключом является х. Для подписи сообщения M выбирается случайное число k, которое является простым по отношению к p-1. После этого вычисляется a = g^k mod p. Далее из уравнения

M = (xa + kb) mod (p-1)

находим b. Электронной подписью для сообщения M будет служить пара a и b. Случайное число k следует хранить в секрете. Для верификации подписи необходимо проверить равенство:

y^aa^b mod p = g^M mod p.

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

M = b/a^x mod p.



3. Функциональные модели и блок-схемы решения задачи

Функциональные модели и блок-схемы решения задачи представлены на рисунках 1, 2, 3.

Условные обозначения:

P - случайное простое число;

Q - взаимно простое число с P;

X - секретный ключ;

Y - открытый ключ;

K - случайное число;

A - открытый ключ, составляющая часть зашифрованного сообщения;

B - открытый ключ, составляющая часть зашифрованного сообщения;

NUM - случайное число;

PH - взаимно простое число с NUM.

Рисунок 1 - Функциональная модель решения задачи для функции GET_SIMPLE_NUM



Рисунок 2 - Блок-схема решения задачи для функции MUTUALLY_DISTINCT

Рисунок 3 - Блок-схема решения задачи для функции DECODING



4. Программная реализация решения задачи

;ФУНКЦИЯ ГЕНЕРИРУЕТ СЛУЧАЙНОЕ ПРОСТОЕ ЧИСЛО ИЗ СПИСКА LIST_SIMPLE_NUM

(DEFUN GET_SIMPLE_NUM ()

(DECLARE (SPECIAL LIST_SIMPLE_NUM))

;СПИСОК ПРОСТЫХ ЧИСЕЛ

(SETQ LIST_SIMPLE_NUM

'(1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223

1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373

1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511

1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657

1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811

1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987

1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129

2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287

2293 2297 2309 2311 2333 2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423

2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617

2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741

2749 2753 2767 2777 2789 2791 2797 2801 2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903

2909 2917 2927 2939 2953 2957 2963 2969 2971 2999 3001 3011 3019 3023 3037 3041 3049 3061 3067 3079

3083 3089 3109 3119 3121 3137 3163 3167 3169 3181 3187 3191 3203 3209 3217 3221 3229 3251 3253 3257

3259 3271 3299 3301 3307 3313 3319 3323 3329 3331 3343 3347 3359 3361 3371 3373 3389 3391 3407 3413

3433 3449 3457 3461 3463 3467 3469 3491 3499 3511 3517 3527 3529 3533 3539 3541 3547 3557 3559 3571))

(NTH (RANDOM (- (LENGTH LIST_SIMPLE_NUM) 1)) LIST_SIMPLE_NUM))

;ПОИСК ВЗАИМНО ПРОСТОГО ЧИСЛА

(DEFUN MUTUALLY_DISTINCT(NUM PH)

(DO()

((< NUM PH) NUM)

(SETQ NUM (TRUNCATE NUM 2)))

(DO()

((EQL (GCD NUM PH) 1) NUM)

(IF (EQL (REM NUM 2) 0) (SETQ NUM (+ NUM 1 )))

(SETQ NUM (+ NUM 2))))

;ДЕКОДИРОВАНИЕ ЧИСЛА

(DEFUN DECODING (XABP)

;ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ

(DECLARE (SPECIAL X))

(DECLARE (SPECIAL A))

(DECLARE (SPECIAL B))

(DECLARE (SPECIAL P))

(SETQ X (CAR XABP))

(SETQ A (CADR XABP))

(SETQ B (CADDR XABP))

(SETQ P (CADDDR XABP))

(SETQ A (EXPT A X))

(DO ((I 1))

((= (MOD (- (* I A) B) P) 0) I)

(SETQ I (+ I 1))))

(DEFUN ELGAMAL (TEXT)

;ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ

(DECLARE (SPECIAL P))

(DECLARE (SPECIAL Q))

(DECLARE (SPECIAL X))

(DECLARE (SPECIAL Y))

(DECLARE (SPECIAL K))

(DECLARE (SPECIAL B))

(DECLARE (SPECIAL A))

(DECLARE (SPECIAL KEY))

(SETQ P (GET_SIMPLE_NUM))

(SETQ Q (GET_SIMPLE_NUM))

(SETQ Q (MUTUALLY_DISTINCT Q P))

(SETQ X (RANDOM P))

(SETQ Y (MOD (EXPT Q X) P))

(SETQ K 100000)

(SETQ K (MUTUALLY_DISTINCT K (- P 1)))

(SETQ A (MOD (EXPT Q K) P))

(SETQ B (MOD (* TEXT (EXPT Y K)) P))

(SETQ KEY (LIST X A B P)))

(DEFUN SET_PUBLIC_KEY (XABP)

;ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ

(DECLARE (SPECIAL PUBLIC_KEY))

(SETQ PUBLIC_KEY (CDR XABP)))

;СЧИТЫВАЕМ СООБЩЕНИЕ

(SETQ TEXT 0)

(SETQ INPUT (OPEN " D:\\NUMBERS.TXT" :DIRECTION :INPUT))

(SETQ TEXT (READ INPUT))

(CLOSE INPUT)

;ШИФРОВАНИЕ

(SETQ KEY (MAPCAR 'ELGAMAL TEXT))

;УСТАНОВКА ОТКРЫТОГО КЛЮЧА

(SETQ PUBLIC_KEY (MAPCAR 'SET_PUBLIC_KEY KEY))

(SETQ OUTPUT (OPEN "D:\\CODING.TXT" :DIRECTION :OUTPUT))

(PRINT 'PUBLC_KEY OUTPUT)

(PRINT PUBLIC_KEY OUTPUT)

(TERPRI OUTPUT)

(CLOSE OUTPUT)

;ДЕШИФРОВКА

(SETQ DECODING_TEXT (MAPCAR 'DECODING KEY))

(SETQ OUTPUT (OPEN "D:\\DECODING.TXT" :DIRECTION :OUTPUT))

(PRINT DECODING_TEXT OUTPUT)

(TERPRI OUTPUT)

(CLOSE OUTPUT)

5. Пример выполнения программы

Пример 1.

Рисунок 4. Текст для шифрования



Рисунок 5. Шифрование с помощью алгоритма Эль Гамаля

Рисунок 6. Расшифрование с помощью алгоритма Эль Гамаля, используется секретный ключ

Пример 2.

Рисунок 7. Текст для шифрования

Рисунок 8. Шифрование с помощью алгоритма Эль Гамаля

Рисунок 9. Расшифрование с помощью алгоритма Эль Гамаля, используется секретный ключ



Пример 3.

Рисунок 10. Текст для шифрования

Рисунок 11. Шифрование с помощью алгоритма Эль Гамаля

Рисунок 12. Расшифрование с помощью алгоритма Эль Гамаля, используется секретный ключ



Заключение

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

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



Список использованных источников

1. Брассар, Ж. Современная криптология. [Текст] / Ж. Брассар - М.: Полимед, 1999. С. 84.

2. Кландер, Л. Hacker Prof: полное руководство по безопасности компьютера. [Электронный ресурс] / Л. Кландер - М.: Попурри, 2002. С. 642.

3. Кнут, Д.Э. Искусство программирования. Получисленные алгоритмы [Текст] / Д.Э. Кнут. - М.: Вильямс, 2004. Т.2. - 832 с.

4. Ковалевский, В. Криптографические методы [Текст]. / В. Ковалевский, В. Максимов - М.: КомпьютерПресс, 1993. С. 65.

5. Молдовян, Н.А. Введение в криптосистемы с открытым ключом: Проблематика криптографии; элементы теории чисел; двухключевые криптосистемы и др. [Электронный ресурс] / Н.А. Молодовян, А.А.Молдовян. - М.: БВХ-Петербург, 2005. С.288.

6. Петров, А.А. Компьютерная безопасность. Компьютерные методы защиты. [Текст] / Петров А.А.. - М.: ДМК, 2000. С.448.

7. Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. - Краснодар: КубГТУ, 2002.- 160с.

8. Шифр ЭльГамаля [Электронный ресурс] - Режим доступа: http://program.rin.ru/razdel/html/936.html.