Криптоалгоритмы, формирование открытых ключей

 

 

СОДЕРЖАНИЕ

 

 

ВВЕДЕНИЕ

1. ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ
1. Требования к свойствам криптопараметров
2. Бинарный алгоритм возведения в степень по модулю
3. Формирование рабочих ключей
4. Алгоритм формирования ЭЦП
5. Алгоритм проверки ЭЦП
6. Постановка задачи реализации
2. ОПИСАНИЕ ПРОГРАММЫ

2.1 Общие сведения

2.2 Функциональное назначение

2.3 Описание логической структуры

2.4 Используемые технические средства

2.5 Вызов и загрузка программы

6. Входные и выходные данные

ВЫВОДЫ

ПЕРЕЧЕНЬ ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А

 

ВВЕДЕНИЕ

 

 

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

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

Целостность – избежание несанкционированной модификации информации.

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

Аутентификация  – установление (то есть проверка и подтверждение) подлинности различных аспектов информационного взаимодействия: сеанса связи, сторон (идентификация), содержания (имитозащита) и источника (установление авторства) передаваемых сообщений, времени взаимодействия и т. д. Является важной составной частью проблемы обеспечения достоверности получаемой информации.

Криптосистемы разделяются на симметричные и с открытым ключом.

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

Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее.  

Другие криптосистемы  с открытым ключом основаны на трудности  вычисления дискретных логарифмов в конечном поле. Дискретное логарифмирование (DLOG) – это задача обращения функции g^x в некоторой конечной мультипликативной группе G. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.

Одной из таких криптосистем является схема Эль–Гамаля. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи.

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

 

1 ИСПОЛЬЗУЕМЫЕ МЕТОДЫ  И АЛГОРИТМЫ

 

 

1. Требования к свойствам  криптопараметров

 

Стойкость асимметричных  криптосистем базируется, в основном,  на алгоритмической трудности решить за приемлемое время какую-либо задачу. Если злоумышленнику удастся построить такой алгоритм, то дискредитирована будет вся система и все сообщения, зашифрованные с помощью этой системы. В этом состоит главная опасность асимметричных криптосистем в отличие от симметричных. Поэтому для повышения стойкости таких систем используемые криптопараметры должны быть больших размеров (512–4096 бит), чтобы злоумышленник не мог за приемлемое время получить ключи схемы или какие-либо другие параметры, позволяющие ему осуществить атаку.

Для оценки вычислительной сложности алгоритмов используется общий метод решета числового поля (GNFS англ. general number field sieve) и рассчитывается по формуле (1.1).

 

   (1.1)

 

Здесь n – это количество битов двоичного представления рассматриваемого числа (криптопараметра).

Очевидно, что чем больше число n, тем выше вычислительная сложность алгоритма и тем он надежнее. Далее приведена таблица, в которой показано количество mips-лет, которое требуется для разложения чисел различных размеров при использовании современных реализаций решета общего поля чисел.

Таблица 1.1 – Разложение на множители  с помощью решета общего поля чисел

Количество бит	Сколько mips-лет нужно для разложения
512	30000
768	2∙108
1024	2∙1011
1280	2∙1014
1536	2∙1016
2048	2∙1020

 

В криптосистеме Эль-Гамаля криптопараметрами являются простые числа, поэтому для ее реализации нужен генератор простых чисел.

Существует три класса методов  формирования простых чисел: аналитические, методы гипотез и вероятностные.

Аналитические методы позволят точно сказать, является ли число простым или же оно составное. Методы гипотез судят о простоте на основе гипотез, то есть они утверждают о простоте числа при справедливости каких-то недоказанных предположений. Вероятностные методы трактуют о виде числа с некоторой вероятностью. Обычно вероятность их ошибки очень мала, что достигается повторением одного и того же теста над рассматриваемым числом. Так как в своей работе я использую вероятностный тест, то далее буду подробнее рассматривать именно этот класс методов.

Пусть n ∈ N, n нечетно, n > 1. Вероятностный тест на простоту проводится следующим образом. Выбирается случайное a ∈ N, 1 £ a < n, и для него проверяется выполнение некоторых условий. Если какое-то из условий не выполнено, то число n - составное, поскольку для простых чисел эти условия являются необходимыми. Если же все условия выполнены, то из этого еще не следует простота n. Однако  можно будет считать, что «n - простое число с некоторой вероятностью». Кроме того, обычно доказывают оценку снизу для этой вероятности. Чем больше значений a мы протестируем, тем ближе эта вероятность к единице.

Тест простоты Ферма – это тест простоты натурального числа n, основанный на малой теореме Ферма. Если n – простое число, то оно удовлетворяет сравнению для любого a. Выполнение сравнения является необходимым, но не достаточным признаком простоты числа n. То есть если хотя бы для одного a не справедливо , то число n составное, в противном случае ничего сказать нельзя, хотя вероятность того, что число является простым, увеличивается. Однако существуют составные числа, для которых сравнение выполняется для всех a взаимно простых с n – это числа Кармайкла. Чисел Кармайкла – бесконечное множество, наименьшее число Кармайкла – 561. Тем не менее, тест Ферма довольно эффективен для обнаружения составных чисел.

Тест Соловея-Штрассена – вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные. Тест Соловея-Штрассена опирается на малую теорему Ферма и свойства символа Якоби: если – нечетное составное число, то количество целых чисел , взаимнопростых с и меньших , удовлетворяющих сравнению не превосходит по значению. Составные числа удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби по основанию . Вероятность ошибки теста Соловея-Штрассена равна . Как уже отмечалось выше для ее уменьшения следует тестировать число не одноразово. При тестированиях вероятность ошибки вычисляется как .

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

Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году. Тест основан на понятие свидетеля простоты и теореме Рабина: пусть – нечётное число большее 1. Число однозначно представляется в виде , где нечётно. Целое число , называется свидетелем простоты числа , если выполняется одно из условий: или , или существует целое число , , такое, что . Теорема Рабина утверждает, что составное нечётное число имеет не более различных свидетелей простоты, где – функция Эйлера.

Тест Лемана: если для какого–либо целого числа a < P не выполняется условие , то число P – составное. Если это условие выполняется, то число P – возможно простое, причем вероятность ошибки не превышает 50%.

И снова, вероятность  того, что случайное число a будет свидетелем составной природы числа P, не меньше 50%. Повторите эту проверку k раз. Если результат вычислений равен 1 или –1, но не всегда равен 1, то P является простым числом с вероятностью ошибки .

Алгоритм тестирования:

1. Выбрать случайно число a , меньшее P .
2. Вычислить
3. Если , то P не является простым.
4. Если, то вероятность того, что число P не является простым, не больше 50 %.
5. Повторить эту проверку k раз.
6. Если результат вычислений  равен 1 или -1, но не всегда  равен 1, то P является простым числом с вероятностью ошибки  .

Для защиты от специальных методов криптоанализа  используют сильные простые числа, которые усложняют задачу разложения числа на простые множители. Сильное простое число – это простое число с определёнными свойствами:

1. Наибольший общий делитель p – 1 и q – 1 должен быть небольшим.
2. И p – 1, и q – 1 должны иметь среди своих множителей большие простые числа, соответственно p' и q'.
3. И p' – 1, и q' – 1 должны иметь среди своих множителей большие простые числа.
4. И p + 1, и q + 1 должны иметь среди своих множителей большие простые числа.
5. И (p – 1)/2, и (q – 1)/2 должны быть простыми.

Такие числа можно представить в  виде

 

,      (1.2)

 

где R - тоже простое число. В ряде случаев к числу P ставится условие, что бы в каноническом разложении числа P-1 содержалось большое простое число, скажем q, тогда

 

(1.3)

 

В схеме Эль–Гамаля такими числами являются криптопараметры p и g.

Число p – это простое число, которое является одним из составляющих открытого ключа

 

(1.4)

 

Число g – это первообразный корень по модулю p, для которого есть некоторые условия.

Необходимые условия:

 

(1.5)

 

Необходимые и достаточные условия:

 

(1.6)

 

(1.7)

 

2. Бинарный алгоритм возведения в степень по модулю

 

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

Стандартным алгоритмом выполнения последовательности операций является бинарный алгоритм. В нем используется бинарное представление  множителя (показателя степени). Рассмотрим более подробно алгоритм модульного возведения  в степень.

Исходные данные: показатель степени n, основание a, модуль m. 
Результат: .

Если n = 1, то ; закончить работу алгоритма.

1. k = l_n – 2;  y = a (mod m), где l_n – длина числа n в битах.
2. Для i, принимающего значения от k до 0, выполнить шаги 4–5. 
3. y = y² (mod) m.
4. Если i–й бит n  равен 1, то y = y ∙ a (mod m).
5. Закончить работу алгоритма.

Этот алгоритм называется также SX–алгоритмом. Смысл такого названия состоит в следующем: считаем, что S (squaring) соответствует операции возведения в квадрат, а X – операции умножения на основание. К примеру, возведем основание a  в степень 23 по модулю  p. Запишем 23 в двоичной системе счисления как 10111. Далее, пропуская самый левый бит, который всегда равен 1, запишем под каждой цифрой 1 SX, а под каждой цифрой 0 – X (см. Табл. 1.2).

 

Таблица 1.2 – Формирование последовательности операций умножения и возведения в квадрат

1	0	1	1	1
	S	SX	SX	SX

 

Двигаясь слева направо, получим  определяющую строку SSXSXSX. Помня, что S – это возведение в квадрат, а X – умножение на основание, получаем следующую последовательность операций:

 

,

 

что соответствует  действительности.

Существуют более быстрые модификации данного алгоритма. Это так называемые М–арные алгоритмы, методы окна, представление множителя (показателя степени) в специальном виде с целью уменьшения единичных разрядов, в том числе троичное представление множителя (показателя степени). Однако во всех этих методах количество операций зависит от  веса Хемминга (количества единичных разрядов в двоичном представлении) показателя степени.

 

3. Формирование рабочих  ключей

 

Так, как система  Эль-Гамаля – это асимметричная криптосистема, то она имеет открытый и закрытый ключи. Открытый ключ – это набор чисел p, g и y; закрытый – число x. Числа p и g формируются согласно условиям, указанным в пункте 1.1 (см. формулы 1.4-1.7). Число y рассчитывается по формуле

 

.     (1.8)

 

Число x выбирается случайно в диапазоне .

Получив нужные для работы криптосистемы параметры  теперь можно перейти к алгоритму формирования ЭЦП.

 

4. Алгоритм формирования ЭЦП

 

ЭЦП осуществляется в два этапа. Сначала осуществляется генерация и распределение ключей, т.е. каждый пользователь, генерирует себе х_і ключ, сохраняет его себе в тайне, а открытый ключ вычисляется как:

.                                      (1.9)

Открытый  ключ Y_a пользователь распространяет всем корреспондентам системы, с которыми он имеет связь.

Эль – Гамаль предложил сформировать подпись как две компоненты ЭЦП: .

Эти компоненты формируются на основе решения  классического сравнения Эль  -Гамаля:

,                             (1.10)

где – первоначальный элемент в поле, – хеш-функция, – открытый ключ, причём

;                                            (4.11)

.                                       (4.12)

Подставим (1.9) и (1.12) в (1.10). В результате имеем, что:

откуда

.                             (1.15)

Выражение (4.15) является фундаментальным, поскольку позволяет вычислить вторую компоненту ЭЦП, а именно:

    (1.16)

или                                                        

.   (1.17)

 

6. Алгоритм проверки ЭЦП

 

Осуществляется всеми пользователями, которые обладают открытым ключом Y и общесистемных параметрами P, Q. Осуществляется на основе проверки сравнения(1.9). 
Устойчивость преобразования определяется сложностью решения сравнения (1.10) относительно .

 

7. Постановка задачи реализации

 

Программа будет состоять из трех частей:

1. Модуль генерации криптопараметров p и g размерностью 32 бита (см. п. 1.1):

Этот модуль должен генерировать простое число p, после чего проверять его на простоту с помощью теста Лемана (см. п. 1.1) и далее сформировать число g, являющееся первообразным корнем по модулю p. Оба числа сохраняются в бинарном файле.

2. Модуль генерации чисел x и y (так же размерностью 32 бита):

Этот модуль должен считывать из бинарного файла p и g и формировать числа y и x (см. п. 1.3). Число y рассчитывается по формуле (1.8), а x случайно выбирается в диапазоне . Оба числа сохраняются в отдельные бинарные файлы.

 

2. ОПИСАНИЕ  ПРОГРАММЫ ЭЦП Эль-Гамаля

 

 

2.1 Общие сведения

 

Для выполнения поставленной задачи программной реализации упрощенной одномодульной 32-битной версии ЭЦП была разработана специальная программа “ElGamal”.

Программа написана на языке программирования С++ в среде Microsoft Visual Studio 2010, запускается как консольное приложение и не требует дополнительно установленного программного обеспечения. Для ее работы достаточным является наличие любой операционной системы Windows8. Для компиляции кода вам потребуется программная среда Microsoft Visual Studio.

 

2.2 Функциональное назначение

 

Данная программа  предназначена для формирования ЭЦП текстовых файлов с помощью упрощенной версии системы Эль-Гамаля. Так же она содержит модуль генерации простых 32-битных чисел, который может использоваться отдельно. “ElGamal” – это учебно-демонстративный вариант криптосистемы Эль-Гамаля, поэтому она не может использоваться в целях защиты информации из-за малых размеров ключей (32 бита), что значительно занижает криптостойкость этой системы. Она может быть использована для обучения или для демонстрации работы системы Эль-Гамаля.

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

2.3 Описание  логической структуры

 

1. Реализована функция, выполняющая формирование пары рабочих ключей {X_i, Y_i}. При этом использована функция возведения в степень по модулю (бинарный метод).

2. Реализована функция, выполняющая формирование криптопараметров {P, q}. Сгенерированные ключи записываются в три двоичных файла:

{P, q} (открытая ключевые параметры);

Y_i (открытый ключ проверки ЭЦП); 

X_i (конфиденциальный ключ проверки ЭЦП).

 

3 Реализовано формирование хеш-значения H(M) от исходной информации М с помощью функции из библиотеки формирования контрольных сумм по алгоритмам CRC-32 .

4 Реализована функция, выполняющая формирование ЭЦП (пары чисел {R, S}) для некоторого сообщения М.

5 Реализована функция проверки ЭЦП:

проверка ЭЦП для заданного  исходного сообщения M (для поученного значения хеш-функции от сообщения H(M)) и заданных значений ЭЦП {R, S}) и вывод на экран результатов проверки ЭЦП.

Задание «поддельного» (измененного) сообщения M ^*. Повторная проверка ЭЦП для «поддельного» (измененного) сообщения M ^* (для измененного значения хеш-функции от сообщения H(M ^*) и корректных значений ЭЦП {R, S}). Вывод на экран результатов проверки ЭЦП.

Задание “поддельного” (измененного) значения второго компонента ЭЦП S ^*. Повторная проверка ЭЦП для заданного корректного исходного сообщения M (для начального значения хеш-функции от сообщения H(M)) и для “поддельных” (измененных) значений ЭЦП {R, S ^*}). Вывод на экран результатов проверки ЭЦП.

 

2.4 Используемые технические средства

 

Для работы программы  используется персональный компьютер  с операционной системой Windows. Обязательным условием работы программы является наличие установленной среды разработки Microsoft Visual Studio 2010 или более поздней версии. Программа тестировалась и прошла проверку на работоспособность на ПК с ОС Windows 7. Технические характеристики ПК: ОЗУ - 4096 Mb, процессор Intel Core i3 CPU 2310M 2.0 GHz.

 

2.5 Вызов и загрузка программы

 

Вызов программы  осуществляется через среду разработки Microsoft Visual Studio 2010.

2.6 Входные и выходные данные

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

 

 

ВЫВОДЫ

 

 

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

При разработке программы “ElGamal” я ознакомился с ГОСТами оформления программной продукции, получил навыки по написанию научных работ и разработке программного обеспечения на языке C++.

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

 

СПИОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

 

1. Горбенко І.Д., Гріненко Т.О. Захист інформації в інформаційно-телекомунікаційних системах: Навч. посібник, Ч. 1. Криптографічний захист інформації /  Горбенко І.Д., Гріненко Т.О.  – Харків: ХНУРЕ. – 2004. – 368 с.
2. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии / Василенко О. Н. — М.: МЦНМО, 2003.—328 с.
3. Вельшенбах М. Криптография на Си и С++ в действии. Учебное пособие / Вельшенбах М. – М.: Издательство Триумф. – 2004. – 464 с.
4. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы / Кнут Д. – М.: Мир. – Том 2. – 1976. – 788 с.
5. Петров А.А.  Компьютерная безопасность. Криптографические методы защиты / Петров А.А. – М.: ДМК. – 2000.
6. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Шнайер Б. – М.: Триумф. – 2002.
7. http://ru.wikipedia.org/

 

ПРИЛОЖЕНИЕ А

ЭЦП Эль-Гамаля

 

#include <iostream>

#pragma comment(lib,"CRC32.lib")

#include <conio.h>

#include <time.h>

#include <math.h>

#include <string.h>

#include "CRC32.h"

 

#define EXIT "exit"

using namespace std;

 

bool GetD (unsigned int Fn, unsigned int E, unsigned int &D)//ф-ция вычисляет обратный эл-т (D) для (E) методом цепных дробей

{

unsigned int r, s, a=Fn, b=E, ai[3]={0,1};

int M(-1);//кол-во итераций

do

{

r=a/b;

s=a%b;

ai[2]=r*ai[1]+ai[0];//находим текущее а

ai[0]=ai[1];//записываем предыдущее а в пре-предыдущее

ai[1]=ai[2];

a=b;//записываем числитель

b=s;//записываем знаменаткль

++M;//наращиваем итерации

} while (s); //до тех пор, пока есть остаток

if (a!=1)//если последний знаменатель НЕ 1 (т.е. НОД(Fn,D)!=1)

return 1; // Ошибка

if (M%2==0)

D=ai[0];

else

D=Fn-ai[0];

return 0;

}

 

void Xpower (unsigned int x, unsigned int k, unsigned int N, unsigned int &y) // Возводит x в степень k  по модулю N

{

if(k==0) //если степень 0 возвращаем 1

{

y = 1;

return;

}

if (k==1) //если степень 1 возвращаем х по модулю

{

y = x%N;

return;

}

y = x; //присваеваем у=х

int i;

for(i = 31; i >= 0; --i)//ищем первый ненулевой бит степени с конца

if((k & (1<<i)) != 0)

break;

unsigned __int64 j;

--i; //начинаем считать с бита на 1 младше чем самый старший ненулевой

for(;i >= 0; --i)//цикл пока не дошли до 0

{ 

j = y;

j*= j;//возвели у в квадрат

y = j%N;//взяли по модулю

if ((k & (1<<i)) != 0)//если текущих бит 1

{

j = y;

j*= x;

y = j%N;//то умножили еще на Х и взяли по модулю

}

}

return;

}

 

bool Miller_Rabin (unsigned int n)

{

    if (n == 1)

return 1;

if ((n == 2) || (n == 3))

return 0; // Простое

unsigned int k = 100, s=0, d, a, x, f = 1;

    d = n - 1;

    while (!(d%2))

    {

       d/= 2;

       s++; // на сколько 2 делится d

    }

    for (int t = 0; t < k; t++)

    {

       a = (( (rand()<<16) | (rand()) )%(n-3)) +2;

//   (rand())%(n-3); // !!!!!

       Xpower(a, d, n, x); // Возводим a в степень d по модулю n

       if (!(x==1 || x==n-1))

       {

           for (int r = 1; r < s; r++)

           {

              Xpower(x, 2, n, x);

              if (x==1)

                 return 1;  // n составное      

              if (x==n-1) f=0;      

           }      

           if (f)

           return 1; // n составное     

       } 

    }

    return 0; // Проверку прошло

}

 

void GenPrime (unsigned int &P)

{

bool b = 0;

do

{

P = ((( (rand()<<16) | (rand()) )%(65533)) +2)|1; // 65533 = (0xFFFF) - 2

b = Miller_Rabin(P);  

}

while (b);

return;

}

 

bool IsPrime (unsigned int P)

{

bool b = Miller_Rabin(P);  

return b;

}

 

unsigned int Xv2_C (unsigned int x, unsigned int c, unsigned int Mod) // y=x^2+c(mod Mod)

{

unsigned int y;

unsigned __int64 k;

Xpower(x, 2, Mod, y);

k = y;

k+= c;

k%= Mod;

y = k;

return y;

}

 

unsigned int NOD(unsigned int m, unsigned int n, int k = 1)

{

if(!m && n)

return n*k;

if (m && !n)

return m*k;

if (m == n)

return m*k;

if((m == 1) && n)

return 1*k;

if (m && (n == 1))

return 1*k;

if (!(m&1) && !(n&1))

{

k*= 2;

m/= 2;

n/= 2;

NOD(m, n, k);

}

else if (!(m&1) && (n&1))

{

m/= 2;

NOD(m, n, k);

}

else if((m&1) && !(n&1))

{

n/=2;

NOD(m, n, k);

}

 else if((m&1) && (n&1))

{

if (n > m)

{

n%= m;

}

else

{

m%= n;

}

NOD(m, n, k);

}

}

 

bool Fact_PQ (unsigned int K, unsigned int &P, unsigned int &Q)//если ошибка, возвращает 1, иначе 0

{

unsigned __int64 d, razn, x[2], y[2], c;

do

{

c = ((rand()<<16) | rand())%(K-1);

}

while (!c);

do

{

x[0] = ((rand()<<16) | rand())%(K-1);

}

while (!x[0]);

y[0] = x[0];

do

{

x[1] = Xv2_C(x[0], c, K);

x[0] = x[1];

y[1] = Xv2_C(y[0], c, K);

y[1] = Xv2_C(y[1], c, K);

y[0] = y[1];

if (x[1] > y[1])

razn = x[1] - y[1];

else

razn = y[1] - x[1];

d = NOD(K, razn);

if (d == K)

return 1;

} while (d == 1);

P = d;

Q = K/P;

return 0;

}

 

void MakePg (unsigned int &P, unsigned int &g) // Генерирует ключевые параметры P и его первообразный корень g

{

unsigned int Fn, P1, Q1, y1, y2;

bool temp;

do

{

do

{

GenPrime(P);

Fn = P - 1;

}

while(Fact_PQ(Fn, P1, Q1));

}

while (IsPrime(P1) || IsPrime(Q1));

do

{

do

{

g = 1 + ((rand()<<16) | rand())%(P-1);

}

while((g == 1) || ( g== 0));

Xpower(g, P1, P, y1);

Xpower(g, Q1, P, y2);

}

while((y1 == 1) || (y2 == 1));

return;

}

 

void FormXY(unsigned int P, unsigned int g, unsigned int &X, unsigned int &Y) // Генерирует ключи X и Y

{

X=0; Y=0;

  X = ((( (rand()<<16) | (rand()) )%(P-1)) +1)|1;