Свойства и методы формирования криптопараметров и оценка стойкости. Криптографические хэш-функции. Методы и алгоритмы формирования рабочих ключей. Моделирование упрощенной модели электронной цифровой подписи файла с использованием метода Шнорра.
Аннотация к работе
ЭЦП это информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию. Обрабатывают информацию блоками определенной длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. 3) Сгенерированные для подписи ключи могут быть использованы только один раз, так как после подписывания раскрывается половина секретного ключа. Для того чтобы использование цифровой подписи имело смысл, необходимо выполнение двух условий: 1) Верификация подписи должна производиться открытым ключом, соответствующим именно тому закрытому ключу, который использовался при подписании. Я предлагаю для данной работы использовать алгоритм, в котором мы, выбрав изначальное q, мы будем домножать его на другое случайное число и прибавлять единицу и проверять на простоту получившееся число.void Power (unsigned int X, unsigned int Pow, unsigned int &Y, unsigned int Mod) // ф-ция побитового возведения в степень по модулю.
Введение
Цель моей курсовой работы познакомиться и понять принцип реализации электронно-цифровой подписи (в дальнейшем именуемой ЭЦП), научиться самостоятельно, реализовывать ЭЦП на языке программирования С .
Рассмотрим такое понятие как аутентификация. Аутентификация (англ. 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 Длина ключа
Длина симметричного ключа, бит Длина несимметричного ключа, бит
56 384
64 512
80 768
112 1792
128 2304
4) Процесс шифрования-расшифрования с использованием пары ключей проходит на два-три порядка медленнее, чем шифрование-расшифрование того же текста симметричным алгоритмом.
5) В чистом виде асимметричные криптосистемы требуют существенно больших вычислительных ресурсов, потому на практике используются в сочетании с другими алгоритмами.
1) Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой результат хеш-функции.
2) Для шифрования они используются в форме гибридных криптосистем, где большие объемы данных шифруются симметричным шифром на сеансовом ключе, а с помощью асимметричного шифра передается только сам сеансовый ключ.
Также метод, который я здесь рассматриваю, требует термина дискретное логарифмирование где: Дискретное логарифмирование (DLOG) - задача обращения функции в некоторой конечной мультипликативной группе .
Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.
Для заданных g и a решение x уравнения gx=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)=Ln[1/3, (64/9)1/3]
Полученное число будет одним из критериев криптостойкости.
В случае реализации подписи Шнорра важным параметром стойкости будет число t о котором будет упомянуто позже.
P-1 метод Полларда - алгоритм разложения натурального числа на простые множители. Предложен Джоном Поллардом в 1974 году. Алгоритм предназначен для нахождения простых делителей p, у которых p-1 хорошо раскладывается на множители, то есть имеет небольшой максимальный простой делитель. Если обозначить этот максимальный простой делитель , то алгоритм требует
O (B log B log2N) действий. Метод очень быстро находит простые факторы малой и средней величины (до 20-25 десятичных цифр).
1.1 Криптографические хэш-функции
Поскольку подписываемые документы - переменного (и как правило достаточно большого) объема, в схемах ЭП зачастую подпись ставится не на сам документ, а на его хеш. Для вычисления хэша используются криптографические хеш-функции, что гарантирует выявление изменений документа при проверке подписи. Хеш-функции не являются частью алгоритма ЭП, поэтому в схеме может быть использована любая надежная хеш-функция.
Использование хеш-функций дает следующие преимущества: 1. Вычислительная сложность. Обычно хеш цифрового документа делается во много раз меньшего объема, чем объем исходного документа, и алгоритмы вычисления хеша являются более быстрыми, чем алгоритмы ЭП. Поэтому формировать хэш документа и подписывать его получается намного быстрее, чем подписывать сам документ.
2. Совместимость. Большинство алгоритмов оперирует со строками бит данных, но некоторые используют другие представления. Хеш-функцию можно использовать для преобразования произвольного входного текста в подходящий формат.
3. Целостность. Без использования хеш-функции большой электронный документ в некоторых схемах нужно разделять на достаточно малые блоки для применения ЭП. При верификации невозможно определить, все ли блоки получены и в правильном ли они порядке.
Стоит заметить, что использование хеш-функции не обязательно при электронной подписи, а сама функция не является частью алгоритма ЭП, поэтому хеш-функция может использоваться любая или не использоваться вообще.
1.2 Методы и алгоритмы формирования рабочих ключей
Генератор псевдослучайных чисел (ГПСЧ, Pseudorandom number generator, PRNG) - алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).
И часто используются в криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчеркивает известный афоризм Роберта Р. Кавью: «генерация случайных чисел слишком важна, чтобы оставлять ее на волю случая».
Обычно используется создание некоторого набора из большого количества случайных чисел и опубликование его в некотором «словаре». Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с тем количеством, которое требуется приложениям сетевой безопасности. Хотя данные наборы действительно обеспечивают статистическую случайность, они не достаточно случайны, так как противник может получить копию словаря.
Генератор псевдослучайных чисел включен в состав многих современных процессоров (напр., семейства х86)
Криптографические приложения используют для генерации случайных чисел особенные алгоритмы. Эти алгоритмы заранее определены и, следовательно, генерируют последовательность чисел, которая теоретически не может быть статистически случайной. В то же время, если выбрать хороший алгоритм, полученная численная последовательность будет проходить большинство тестов на случайность. Такие числа называют псевдослучайными числами.
Возведение в степень по модулю возведение в степень по модулю целого числа, т.е.
М=Cd (mod N).
Прежде всего отметим, что не имеет смысла сначала находить R = , а потом определять его остаток от деления на N. Действительно, поступая таким образом при вычислении
1235 (mod 511) = 28153056843 (mod 511) = 359, мы получаем большой промежуточный результат - 28153056843. В реальной ситуации, когда возводятся в степень числа с 1024 двоичными знаками, промежуточный результат будет иметь 21024• 1024 знаков. Только для записи таких чисел потребуется около 1031 гигабайт на винчестере.
Чтобы промежуточные результаты не были столь огромны, необходимо вспомнить, что мы работаем по модулю N. Но даже при этом стоит быть внимательным. Наивный подход к решению нашей задачи привел бы к следующим вычислениям: х = 123, x2 = х·х (mod 511) = 310, x3= х·x2(mod 511) = 316, x4 = х·x3(mod 511) = 32, x5 = х·x4(mod 511) = 359.
На это уходит 4 умножения в кольце вычетов, что кажется приемлемым для нашего игрушечного примера. Но в общем случае, при возведении в 1024-разрядную степень потребуется около 21024 таких умножений. Если каждое произведение при этом осуществляется за 1 миллионную долю секунды, нам потребуется 10294 лет на осуществление операции расшифрования в алгоритме RSA.
Однако даже на нашем небольшом примерчике легко увидеть, как можно было бы сократить количество умножений: х = 123, x2= х·х (mod 511) =310, x4=x2*x2 (mod 511) =32, x5= x·x4(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?21024, q>=2130)
Пусть каждая доказывающая сторона A выбирает секрет a (закрытый ключ), такой, что 1<=a<=q-1 и вычисляет v=?-q(mod p), где v-открытый ключ.
Передаваемые сообщения: A B: x=?r(mod p)
A B: e (где 1<=e<=2t<q)
A B: y=(a*e r) (mod q)
Основные действия
A выбирает случайное r (1<r<q-1), вычисляет x=?r(mod p) и отсылает x стороне B (доказательство)
Сторона B отсылает случайное e из диапазона от 1 до q-1 (вызов)
A возвращает B y=(a*e r) (mod q)
B проверяет, действительно ли z=x, где z= ?r*ve(mod p) и, если это так, то идентификация считается успешной.
Пример: Выбирается простое р=48731 и простое q=443 ( )
Вычисляется ? из условия ?q=1 (mod p), в данном случае ?=11444
Тогда системными параметрами будут (48731,443,11444), a t=8
Сторона А выбирает закрытый ключ a=357 и вычисляет открытый ключ v=?-a(mod p)=7355
Сторона А случайным образом выбирает доказательство r=274 и отсылает x=?r(mod p)= 37123 стороне B
В отсылает A вызов e=129
A отсылает B y=(a*e r) (mod q)=255
B вычисляет z= ?r*ve(mod p) =37123 и идентифицирует 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*ve(mod p). Затем z и полученное сообщение M" пропускаются через хеш-функцию: e’=H (M’, x). Если e=e’, то подпись считается верной.
В данной курсовой работе была представлена реализация эцп по методу Шнорра.
2. Описание программы
2.1 Общие сведения шнорр криптографический подпись хеш
В данной курсовой работе реализована упрощенная модель электронной цифровой подписи файла с использованием метода Шнорра. В качестве хеш-значения в учебных целях используем несложную контрольную сумму CRC-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. ЕСПД. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.