Электронно-цифровая подпись по методу Шнорра

Электронно-цифровая подпись по методу Шнорра

Цель моей курсовой работы познакомиться и понять принцип реализации электронно-цифровой подписи (в дальнейшем именуемой ЭЦП), научиться самостоятельно, реализовывать ЭЦП на языке программирования С++.

Рассмотрим такое понятие как аутентификация. Аутентификация (англ. Authentication) — процедура проверки подлинности, например: проверка подлинности пользователя путём сравнения введённого им пароля с паролем в базе данных пользователей; подтверждение подлинности электронного письма путём проверки цифровой подписи письма по ключу шифрования отправителя; проверка контрольной суммой файла на соответствие сумме, заявленной автором этого файла.

Итак, что же все-таки такое ЭЦП. ЭЦП это информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию.

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

ЭЦП бывает двух видов симметричные и асимметричные, рассмотрим вкратце каждый из этих видов:

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

Соответственно:

2) Ассиметричные цифровые подписи строятся на том, что для шифрования и расшифровывания используются разные ключи.

Рассмотрим «+» и «- «таких ЭЦП:

Симметричные ЭЦП:

Симметричные схемы ЭЦП относятся к криптосистемам с единственным ключом. Котрый используется и для подписания и для проверки. Практически устаревший алгоритм.

В настоящее время симметричные шифры — это:

1) Блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект — нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.

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

Симметричные схемы имеют следующие преимущества:

1) Стойкость симметричных схем ЭЦП вытекает из стойкости используемых блочных шифров, надежность которых также хорошо изучена.

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

Однако у симметричных ЭЦП есть и ряд недостатков:

1) Нужно подписывать отдельно каждый бит передаваемой информации, что приводит к значительному увеличению подписи.

2) Подпись может превосходить сообщение по размеру на два порядка.

3) Сгенерированные для подписи ключи могут быть использованы только один раз, так как после подписывания раскрывается половина секретного ключа.

Хотелось бы отметить что, симметричные ЭЦП устарели с появлением асимметричных, и в целом практически не используются.

Асимметричные ЭПЦ Асимметричные схемы ЭЦП относятся к криптосистемам с открытым ключом. В отличие от асимметричных алгоритмов шифрования, в которых зашифрование производится с помощью открытого ключа, а расшифрование — с помощью закрытого, в схемах цифровой подписи подписывание производится с применением закрытого ключа, а проверка — с применением открытого.

Общепризнанная схема цифровой подписи охватывает три процесса:

1) Генерация ключевой пары. При помощи алгоритма генерации ключа равновероятным образом из набора возможных закрытых ключей выбирается закрытый ключ, вычисляется соответствующий ему открытый ключ.

2) Формирование подписи. Для заданного электронного документа с помощью закрытого ключа вычисляется подпись.

2) Проверка (верификация) подписи. Для данных документа и подписи с помощью открытого ключа определяется действительность подписи.

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

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

2) Без обладания закрытым ключом должно быть вычислительно сложно, создать легитимную цифровую подпись.

Обеспечение этого во всех асимметричных алгоритмах цифровой подписи опирается на следующие вычислительные задачи:

1) Задачу дискретного логарифмирования (EGSA).

2) Задачу факторизации, то есть разложения числа на простые множители (RSA).

«+» и «-» ассиметричного шифрования:

Преимущества:

1) Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа по надёжному каналу.

2) В симметричной криптографии ключ держится в секрете для обеих сторон, а в асимметричной криптосистеме только один секретный.

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

4) В больших сетях число ключей в асимметричной криптосистеме значительно меньше, чем в симметричной.

Недостатки:

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

2) Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения.

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

Таблица 1.1 Длина ключа

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

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

1) Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой результат хеш-функции.

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

Также метод, который я здесь рассматриваю, требует термина дискретное логарифмирование где:

Дискретное логарифмирование (DLOG) — задача обращения функции в некоторой конечной мультипликативной группе .

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

Для заданных g и a решение x уравнения g^x=a называется дискретным логарифмом элемента a по основанию g. В случае, когда G является мультипликативной группой кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.

1. Способы использования и алгоритмы

Свойства и методы формирования криптопараметров и оценка стойкости.

Также для данной темы нам нужно оперировать сильными простыми числами рассмотрим что это такое:

В криптографии сильным называется простое число p, такое что:

p достаточно велико

p-1 имеет достаточно большие простые делители, то есть q1 в p=a1q1+1

q1−1 имеет достаточно большие простые делители, то есть q2 в q1=a2q1+1

p+1 имеет достаточно большие простые делители Иногда также добавляют дополнительные условия, например a1=1, a2=2 и т. п.

Такие числа часто используются в разных принципах криптографии.

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

Также мы должны ввести проверку GNFS:

Exp (((64/9)^1/3+o (1)) (log n)^1/3 (log log n)^2/3)=L_n[1/3, (64/9)^1/3]

Полученное число будет одним из критериев криптостойкости.

В случае реализации подписи Шнорра важным параметром стойкости будет число t о котором будет упомянуто позже.

P-1 метод Полларда — алгоритм разложения натурального числа на простые множители. Предложен Джоном Поллардом в 1974 году. Алгоритм предназначен для нахождения простых делителей p, у которых p-1 хорошо раскладывается на множители, то есть имеет небольшой максимальный простой делитель. Если обозначить этот максимальный простой делитель, то алгоритм требует

O (B log B log²N) действий. Метод очень быстро находит простые факторы малой и средней величины (до 20−25 десятичных цифр).

1.1 Криптографические хэш-функции

Поскольку подписываемые документы — переменного (и как правило достаточно большого) объёма, в схемах ЭП зачастую подпись ставится не на сам документ, а на его хеш. Для вычисления хэша используются криптографические хеш-функции, что гарантирует выявление изменений документа при проверке подписи. Хеш-функции не являются частью алгоритма ЭП, поэтому в схеме может быть использована любая надёжная хеш-функция.

Использование хеш-функций даёт следующие преимущества:

1. Вычислительная сложность. Обычно хеш цифрового документа делается во много раз меньшего объёма, чем объём исходного документа, и алгоритмы вычисления хеша являются более быстрыми, чем алгоритмы ЭП. Поэтому формировать хэш документа и подписывать его получается намного быстрее, чем подписывать сам документ.

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

3. Целостность. Без использования хеш-функции большой электронный документ в некоторых схемах нужно разделять на достаточно малые блоки для применения ЭП. При верификации невозможно определить, все ли блоки получены и в правильном ли они порядке.

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

1.2 Методы и алгоритмы формирования рабочих ключей

Генератор псевдослучайных чисел (ГПСЧ, Pseudorandom number generator, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

И часто используются в криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».

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

Генератор псевдослучайных чисел включён в состав многих современных процессоров (напр., семейства х86)

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

Возведение в степень по модулю возведение в степень по модулю целого числа, т. е.

М=C^d (mod N).

Прежде всего отметим, что не имеет смысла сначала находить R =, а потом определять его остаток от деления на N. Действительно, поступая таким образом при вычислении

123⁵ (mod 511) = 28 153 056 843 (mod 511) = 359,

мы получаем большой промежуточный результат — 28 153 056 843. В реальной ситуации, когда возводятся в степень числа с 1024 двоичными знаками, промежуточный результат будет иметь 2¹⁰²⁴* 1024 знаков. Только для записи таких чисел потребуется около 10³¹ гигабайт на винчестере.

Чтобы промежуточные результаты не были столь огромны, необходимо вспомнить, что мы работаем по модулю N. Но даже при этом стоит быть внимательным. Наивный подход к решению нашей задачи привел бы к следующим вычислениям:

х = 123,

x² = х· х (mod 511) = 310,

x³= х· x²(mod 511) = 316,

x⁴ = х· x³(mod 511) = 32,

x⁵ = х· x⁴(mod 511) = 359.

На это уходит 4 умножения в кольце вычетов, что кажется приемлемым для нашего игрушечного примера. Но в общем случае, при возведении в 1024-разрядную степень потребуется около 2¹⁰²⁴ таких умножений. Если каждое произведение при этом осуществляется за 1 миллионную долю секунды, нам потребуется 10²⁹⁴ лет на осуществление операции расшифрования в алгоритме RSA.

Однако даже на нашем небольшом примерчике легко увидеть, как можно было бы сократить количество умножений:

х = 123,

x²= х· х (mod 511) =310,

x⁴=x²*x² (mod 511) =32,

x⁵= x· x⁴(mod 511) =359.

Здесь нам потребовалось только три произведения, а не 4, как раньше. Обратите внимание на то, что двоичное представление числа 5 имеет вид: '101b', т. е.

— это трехзначное число,

— его вес Хемминга равен h = 2. (где вес Хемминга кол-во 1 в бинарном представлении числа) Поэтому мы произвели 1 = h — 1 умножение общего вида и 2 = t — 1 возведения в квадрат. Такой подсчет остается справедливым и в общем случае: возведение в степень по модулю целого числа может быть осуществлено с помощью h — 1 умножений и t — 1 возведения в квадрат, где t — количество знаков в двоичном представлении показателя, a h — его вес Хемминга. Усредненный вес Хемминга целого числа равен половине количества его двоичных знаков, т. е. t/2. Поэтому среднее число умножений и возведений в квадрат при вычислении экспоненты в кольце вычетов равно t + t/2 — 1. Это означает, что при возведении в 1024-битовую степень потребуется не более 2048 умножений, а среднее число операций и того меньше — 1535.

Метод, с помощью которого достигается такая экономия операций носит специальное название: метод двоичного потенцирования. Работает он, поочередно считывая знаки двоичного представления показателя, начиная с младшего разряда.

1.3 Формирование и проверка ЭЦП

Выбор параметров системы:

Выбирается простое p и простое q, такое, что q|p-1 (p?2¹⁰²⁴, q>=2¹³⁰)

Выбирается элемент в, такой, что в^q=1 (mod p)

Параметры (p, q, в) свободно публикуются Выбирается параметр t, t>40 q<2^t (t-уровень секретности) Выбор параметров доказывающей стороны Пусть каждая доказывающая сторона A выбирает секрет a (закрытый ключ), такой, что 1<=a<=q-1 и вычисляет v=в^-q(mod p), где v-открытый ключ.

Передаваемые сообщения:

AB: x=в^r(mod p)

AB: e (где 1<=e<=2^t

AB: y=(a*e+r) (mod q)

Основные действия

A выбирает случайное r (1^r(mod p) и отсылает x стороне B (доказательство) Сторона B отсылает случайное e из диапазона от 1 до q-1 (вызов)

A возвращает B y=(a*e+r) (mod q)

B проверяет, действительно ли z=x, где z= в^r*v^e(mod p) и, если это так, то идентификация считается успешной.

Пример:

Выбирается простое р=48 731 и простое q=443 ()

Вычисляется в из условия в^q=1 (mod p), в данном случае в=11 444

Тогда системными параметрами будут (48 731,443,11 444), a t=8

Сторона, А выбирает закрытый ключ a=357 и вычисляет открытый ключ v=в^-a(mod p)=7355

Сторона, А случайным образом выбирает доказательство r=274 и отсылает x=в^r(mod p)= 37 123 стороне B

В отсылает A вызов e=129

A отсылает B y=(a*e+r) (mod q)=255

B вычисляет z= в^r*v^e(mod p) =37 123 и идентифицирует A, так как z=x

Моделирование для цифровой подписи:

Пусть сторона A хочет отправить сообщение М стороне B; причем B должен убедиться в том, что сообщение пришло именно от A. Тогда:

A выбирает случайное r (), вычисляет x=в^r(mod p)

Пусть имеется однонаправленная хеш-функция H (M). Сторона, А объединяет M с x и хеширует результат e=(M, x)

Далее A вычисляет y=(a*e+r) (mod q). Значения e и y являются цифровой подписью и отсылаются B.

B вычисляет z= в^r*v^e(mod p). Затем z и полученное сообщение M' пропускаются через хеш-функцию: e'=H (M', x). Если e=e', то подпись считается верной.

В данной курсовой работе была представлена реализация эцп по методу Шнорра.

2. Описание программы

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

шнорр криптографический подпись хеш В данной курсовой работе реализована упрощенная модель электронной цифровой подписи файла с использованием метода Шнорра. В качестве хеш-значения в учебных целях используем несложную контрольную сумму СRC-32.

Программа, которая называется «Shnorr» реализована как консольное приложение на языке С++ и откомпилирована в среде MicrosoftVisualStudio 2010.

Она была реализована на операционной системе MS Windows 7 Home Edition. Программа функционирует на любой операционной системе типа Windows.

2.2 Функциональное назначение программы

Назначение программы состоит в вычислении ЭЦП для определенного файла. Подробное описание назначения ЭЦП приведено в подразделе 1.2. Также для вычисления ЭЦП нам нужна хеш функция описанная в разделе 1.3.

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

Для реализации нам понадобятся такие функции как: функция возведения в степень по модулю (Power), функция Рабина-Миллера для проверки числа на простоту (NoPrime), функция вычисления инверсного элемента (InversElem), функция нахождения НОД (NOD), функция сравнения которая нужна для оригинальной функции факторизации р-Поларда (Sravn), сама функция факторизации (Factor), функция для убеждения в том что число является сильным простым числом (GetQ), функция для генерации открытых параметров (GenOpenParam), функция генерации параметров подписываемой стороны (GetKeyA), Функция подписывания (Sign), Функция проверки підписи (ChekSign), общая функция (main).

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

Программа была написана на компютере с такими параметрами: процессор Intel Core i3, мощностью 2.2 GHz и 2.2 GHz, 4 Гб ОЗУ. Програма может быт отложена на любом современном компютере.

2.5 Запуск. Входные и выходные данные

Программа запускается с диска с помощью файла Shnorr.exe.

В меню, которое выводится на экран, четыре пункта. При вводе 1 выводится генерация случайных простых ключевых параметров. При вводе 2 генерирует параметры стороны А. При вводе 3 программа подписывает файл, название которого надо ввести. При вводе 4 программа выполняет проверку подписи файла, для которого эта подпись генерировалась при вводе 3. Для этого нужно опять ввести название того же файла и на экране отобразится результат проверки: Sign is WRONG! подпись не прошла проверку и Sign is OK! если подпись верная.

Перечень ссылок

1. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Триумф, 2002. — С. 296−300. — 816 с.

2. Горбенко І.Д., Гріненко Т. О. Захист інформації в інформаційно-телекомунікаційних системах: Навчальний посібник. Частина 1: Криптографічний захист інформації) — Харків. ХНУРЕ, 2004. — 376 с.

3. ДСТУ 3008−95 «ЗВІТИ У СФЕРІ НАУКИ І ТЕХНІКИ. Структура та правила оформлення».

4. ГОСТ 19.701 — 90. ЕСПД. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

Приложение А

// ЭЦП Шнорра

#include

#include

#include

#include «CRC32.h»

#pragma comment (lib, «CRC32.lib»)

#define MFILE «general.key» // файлы для параметров, ключей и подписи будут стандартными

#define AFILE «personal.key»

#define SFILE «sign.key»

using namespace std;

void Power (unsigned int X, unsigned int Pow, unsigned int &Y, unsigned int Mod) // ф-ция побитового возведения в степень по модулю.

{

int i;

unsigned __int64 time;

if (Pow==0) // если степнь 0, то результат == 1

{

Y=1;

return;

}

else if (Pow==1) // если степнь 1, то результат без изменений

{

Y=X % Mod;

return;

}

else

Y=X % Mod;

for (i=31;! (Pow&(1<=0; i-); // в таком цикле находим самый старгий еденичный бит

i —; // и берём следующий, т.к. по алгоритму с него надо начтинать

for (; i>=0; i-)

{

time=Y;

time*=time; // на каждой итерации возводим результат в квадрат

Y=time % Mod;

if (Pow&(1<

{

time=Y;

time*=X;

Y=time % Mod;

}

}

}

bool NoPrime (unsigned int Ch) // ф-ция Рабина-Миллера проверки числа на проостоту

{

unsigned int rez, a, pow₂ (0), coef (Ch-1);

if ((Ch==2) || (Ch==3) || (Ch==5) || (Ch==7) || (Ch==11))

return 0;

bool Flag;

do // с помощью этого цикле мы представляем число Ch-1 = 2^pow₂ * coef

{

coef/=2;

pow₂+=1;

} while (! (coef&1));

for (int i=0; i<100; i++) // для достаточной точности выбрак параметр к=100, тогда вероятность ошибки = (¼)^100

{ // тупо по алгоритму:

do

rand ())%(Ch-1); // выбираем случайное а

while (! a);

Power (a, coef, rez, Ch); // возводим в степень, полученную ранее

if ((rez == 1) || (rez == Ch-1)) // и если результат сравним с 1 или -1, то число вероятно простое, идём на след итерацию

continue;

Flag=1;

for (int j=0; j<(pow₂−1); j++) // иначе должно найтись хотя бы одно такое i Є (1, pow+2−1), что a^(2^i) == 1 по модулю Р.

{

Power (rez, 2, rez, Ch);

if (rez==1)

return 1;

if (rez==(Ch-1))

{

Flag=0;

break;

}

}

if (Flag) // если такое i ни разу не встретилось, то число составное

return 1;

}

return 0;

}

bool InversElem (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;

}

unsigned int NOD (unsigned int m, unsigned int n, int temp=1) // http://ru.wikipedia.org/wiki/Бинарный_алгоритм_вычисления_НОД

{

if (! m && m)

return n*temp;

else if (m &&! n)

return m*temp;

else if (m == n)

return m*temp;

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

return 1*temp;

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

return 1*temp;

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

{

temp*=2;

m/=2; n/=2;

NOD (m, n, temp);

}

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

{

m/=2;

NOD (m, n, temp);

}

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

{

n/=2;

NOD (m, n, temp);

}

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

{

if (n>m)

{

n-=m;

}

else

{

m-=n;

}

NOD (m, n, temp);

}

}

unsigned int Sravn (unsigned int x, unsigned int c, unsigned int Mod) //y=x²+c (mod Mod)

{ // это сравнение нужно для оригинального метода факторизации р-Полларда

unsigned int y;

unsigned __int64 temp;

temp = x*x;

temp%= Mod;

temp+=c;

temp%=Mod;

y=temp;

return y;

}

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

{ // ф-ция разложения на множители, но тольк она 2 множителя

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

do

rand ())%(Mod-1); // выбирая случайное с

while (! c);

do

x[0]=((rand ()<<16) while (! x[0]);

y[0]=x[0];

do

{

x[1]=Sravn (x[0], c, Mod); // на каждой итерации х_i=f (x_(i-1))

x[0]=x[1]; // f (x) — это и есть ф-ция Sravn ()

y[1]=Sravn (y[0], c, Mod); // а y_i=f (f (y_(i-1)))

y[1]=Sravn (y[1], c, Mod);

y[0]=y[1];

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

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

else

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

d=NOD (Mod, temp); // п оалгоритму надо назодить НОД разности х и у текущих

if (d==Mod) // это если Mod — простое

return 1;

} while (d==1);

P=d;

Q=Mod/P;

return 0;

}

void GetQ (unsigned int P, unsigned int &q)

{

unsigned int p1, p2; // зная Р, находим для него q, такое что q|Р-1

bool Err;

do

{

Err = Factor (P, p1, p2); // на каждой итерации факторизируем число

P = (p1>p2)? p1: p2; // и выбираем наибольшее из результатов

} while (! Err); // до тех пор пока не получим простое

q = P; // его и принимаем за q

}

void GenOpenParam (unsigned int &P, unsigned int &q, unsigned int &b)

{

unsigned int temp;

do

{

do

rand (); // снчала находим просто простое число

while (NoPrime (P));

P *= 2, P += 1; // потом по условию сильного протсого

} while (NoPrime (P));

GetQ (P, q);

for (b = P-1; b>=1; b-) // а бету находим методом перебора

{

Power (b, q, temp, P);

if (temp == 1)

break;

}

}

void GetKeysA (unsigned int P, unsigned int q, unsigned int b, unsigned int &a, unsigned int &v)

{ // генерация ключей для А-абонента

unsigned int temp;

do

a = (rand ()<<16) while (! a);

Power (b, a, temp, P);

InversElem (P, temp, v);

}

void Sign (unsigned int P, unsigned int q, unsigned int b, unsigned int a, FILE* File, unsigned int &e, unsigned int &y)

{ // ф-ция подписывания

unsigned int r, x;

unsigned __int64 temp;

unsigned char *S;

int FileLen;

do

rand ();

while (! r);

Power (b, r, x, P);

fseek (File, 0, SEEK_END); // ставим указатель в конец файла

FileLen = ftell (File); // находим его позицию в байтах (таким образом и длину самого файла)

fseek (File, 0, SEEK_SET); // и возвращаемся обратно в начало

S = new unsigned char [FileLen + 4]; // 4 доп байта для слеивания строки с x

fread (S+4, sizeof (unsigned char), FileLen, File);

S[0] = (x >> 3*8) & 0xff; // вот ттаким образом склеиваем строку со значением x

S[1] = (x >> 2*8) & 0xff;

S[2] = (x >> 1*8) & 0xff;

S[3] = (x >> 0*8) & 0xff;

e = CRC32Count (S, (FileLen+4)); // и находим хэш функцию от неё

temp = a*e;

temp%= q;

temp += r;

temp%= q;

y = temp;

delete [] S;

}

bool CheckSign (unsigned int P, unsigned int b, unsigned int v, unsigned int e, unsigned int y, FILE* File)

{ // почти то же, что и при подписывании

unsigned __int64 temp;

unsigned int Rez1, Rez2, z, FileLen, e1;

unsigned char *S;

Power (b, y, Rez1, P);

Power (v, e, Rez2, P);

temp = Rez1*Rez2;

temp%= P;

z = temp;

fseek (File, 0, SEEK_END);

FileLen = ftell (File);

fseek (File, 0, SEEK_SET);

S = new unsigned char [FileLen + 4];

S[0] = (z >> 3*8) & 0xff;

S[1] = (z >> 2*8) & 0xff;

S[2] = (z >> 1*8) & 0xff;

S[3] = (z >> 0*8) & 0xff;

fread (S+4, sizeof (unsigned char), FileLen, File);

e1 = CRC32Count (S, FileLen + 4);

if (e == e1)

return false;

else

return true;

}

int main ()

{

unsigned int Pr, P, q, b, a, v, e, y;

FILE *MFile, *AFile, *TFile, *SFile;

char temp[512];

do

{

cout<< «Entern1 to gen general parametrsn2 to gen keys for An3 to sign a filen4 to check signn0 to exitn»;

cin>>Pr;

cin.get ();

if (Pr == 1)

{

GenOpenParam (P, q, b);

MFile = fopen (MFILE, «wb»);

fwrite (&P, sizeof (unsigned int), 1, MFile);

fwrite (&q, sizeof (unsigned int), 1, MFile);

fwrite (&b, sizeof (unsigned int), 1, MFile);

fclose (MFile);

cout<< «General parametrs were gened! n»;

cin.get ();

}

if (Pr == 2)

{

MFile = fopen (MFILE, «rb»);

fread (&P, sizeof (unsigned int), 1, MFile);

fread (&q, sizeof (unsigned int), 1, MFile);

fread (&b, sizeof (unsigned int), 1, MFile);

fclose (MFile);

GetKeysA (P, q, b, a, v);

AFile = fopen (AFILE, «wb»);

fwrite (&a, sizeof (unsigned int), 1, AFile);

fwrite (&v, sizeof (unsigned int), 1, AFile);

fclose (AFile);

cout<< «Personal parametrs were gened! n»;

cin.get ();

}

if (Pr == 3)

{

cout<< «Enter the name of the file to sign: n»;

cin.getline (temp, 512);

TFile = fopen (temp, «rb»);

MFile = fopen (MFILE, «rb»);

AFile = fopen (AFILE, «rb»);

fread (&P, sizeof (unsigned int), 1, MFile);

fread (&q, sizeof (unsigned int), 1, MFile);

fread (&b, sizeof (unsigned int), 1, MFile);

fread (&a, sizeof (unsigned int), 1, AFile);

Sign (P, q, b, a, TFile, e, y);

fclose (TFile); fclose (AFile); fclose (MFile);

SFile = fopen (SFILE, «wb»);

fwrite (&e, sizeof (unsigned int), 1, SFile);

fwrite (&y, sizeof (unsigned int), 1, SFile);

fclose (SFile);

cout<< «The file was signed! n»;

cin.get ();

}

if (Pr == 4)

{

cout<< «Enter the name of the signed file: n»;

cin.getline (temp, 512);

TFile = fopen (temp, «rb»);

MFile = fopen (MFILE, «rb»);

AFile = fopen (AFILE, «rb»);

SFile = fopen (SFILE, «rb»);

fread (&P, sizeof (unsigned int), 1, MFile);

fread (&q, sizeof (unsigned int), 1, MFile);

fread (&b, sizeof (unsigned int), 1, MFile);

fseek (AFile, 4, SEEK_SET);

fread (&v, sizeof (unsigned int), 1, AFile);

fread (&e, sizeof (unsigned int), 1, SFile);

fread (&y, sizeof (unsigned int), 1, SFile);

if (CheckSign (P, b, v, e, y, TFile))

cout<< «The sign is WRONG! n»;

else

cout<< «The sign is correct! n»;

cin.get ();

fclose (TFile); fclose (MFile); fclose (AFile); fclose (SFile);

}

} while (Pr);

}