Розробка електронного цифрового підпису

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

РЕФЕРАТ

Пояснювальна записка до курсової роботи містить: 28 сторінку; 2 рисунка; 13 посилань.

Мета курсової роботи - реалізувати схеми електронного цифрового підпису по Ель Гамалю і DSS/DSA. Оцінити криптостойкость даних алгоритмів

Об'єкт дослідження - метод розробки електронного цифрового підпису

Предмет дослідження - способи розробки електронного цифрового підпису

Електронний цифровий підпис, хешування, Ель Гамаль, Dds/Dsa, криптографія, криптостійкість

ТЕХНІЧНЕ ЗАВДАННЯ

Варіант завдання курсової роботи

Вихідні дані, відповідні 2 варіанту:

1) Використовуючи матеріали стандартів FIPS 180-2 і FIPS 186-2 розробити код, який би реалізовував схеми електронного цифрового підпису по Ель Гамалю і DSS/DSA (FIPS 186-1 і FIPS 186-2).

2) Використовуючи тестові вектора перевірити схеми електронного цифрового підпису на коректність.

3) Провести порівняльний аналіз використовуваних алгоритмів. Оцінити продуктивність програмної реалізації та криптографічний стійкість даних систем при їх реалізації. Зробити висновки.

ЗМІСТ

Вступ

1. Загальні відомості

1.1 Криптологія

1.2 Системи електронного цифрового підпису (ЕЦП)

1.3 Хеш функція

2. Електронний цифровий підпис за Ель Гамаль і DSS / DSA

2.1 Цифровий підпис на основі алгоритму Ель Гамаля (EGSA)

2.2 Стандарт ЕЦП DSS/DSА

3. Розробка програмного коду

3.1 Програмний код для алгоритму ЕЦП по Ель Гамалю

3.2 Програмний код для алгоритму ЕЦП ЕЦП DSS/DSА

Висновки

Перелік використаних джерел

ВСТУП

Метою аутентифікації електронних документів є їх захист від можливих видів зловмисних дій, які можуть завдати істотної шкоди банківським і комерційним структурам, державним підприємствам і організаціям, а також приватним особам, що застосовують у своїй діяльності комп'ютерні інформаційні технології.

При обробці документів в електронній формі абсолютно непридатні традиційні способи встановлення автентичності по рукописного підпису та відбитку печатки на паперовому документі. Принципово новим рішенням є електронний цифровий підпис (ЕЦП).

Електронний цифровий підпис використовується для аутентифікації текстів, переданих по телекомунікаційних каналах. Функціонально вона аналогічний звичайному рукописному підпису і володіє її основними перевагами: засвідчує, що підписаний текст виходить від особи, яка поставила підпис; не дає самому цій особі можливості відмовитися від зобов'язань, пов'язаних з підписаним текстом; гарантує цілісність підписаного тексту.

При цьому електронний документ з електронним цифровим підписом має юридичне значення при здійсненні відносин, зазначених у сертифікаті ключа підпису.

Схема формування електронного цифрового підпису під електронним документом його творцем (відправником) передбачає обчислення хеш-функції цього документа і шифрування цього значення за допомогою секретного ключа відправника.

У роботі будуть вирішуватися питання реалізації схем електронного цифрового підпису на основі алгоритмів Ель Гамаля і DSS/DSA. Так само оцінка криптостійкості цих алгоритмів, переваг та недоліків.

1. ЗАГАЛЬНІ ВІДОМОСТІ

1.1 Криптологія

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

Спочатку криптографія вивчала методи шифрування інформації - оборотного перетворення відкритого (вихідного) тексту на основі секретного алгоритму або ключа в шифрований текст (шифротекст). Традиційна криптографія утворює розділ симетричних криптосистем, в яких шифрування і дешифрування проводиться з використанням одного і того ж секретного ключа. Крім цього розділу сучасна криптографія включає в себе асиметричні криптосистеми, системи електронного цифрового підпису (ЕЦП), хеш-функції, управління ключами, отримання прихованої інформації, квантову криптографію.

1.2 Системи електронного цифрового підпису (ЕЦП)

Електронний цифровий підпис (ЕЦП) - вид електронного підпису, отриманого за результатом криптографічного перетворення набору електронних даних, який додається до цього набору або логічно з ним зв'язується і дає змогу підтвердити його цілісність та ідентифікувати особу, його підписує.

Цифровий підпис дозволяє вирішити наступні три завдання:

ѕ здійснити аутентифікацію джерела даних,

ѕ встановити цілісність повідомлення або електронного документа,

ѕ забезпечити неможливість відмови від факту підпису конкретного повідомлення.

Схема електронного підпису зазвичай включає в себе:

ѕ алгоритм генерації ключових пар користувача;

ѕ функцію обчислення підпису;

ѕ функцію перевірки підпису.

Надійність схеми цифрового підпису визначається складністю наступних трьох завдань:

ѕ Підробки підпису, тобто знаходження значення підписи під заданим документом особою, що є власником секретного ключа;

ѕ Створення підписаного повідомлення, тобто знаходження хоча б одного повідомлення з правильним значенням підпису;

ѕ Підміни повідомлення, тобто підбору двох різних повідомлень з однаковими значеннями підпису.

Функція обчислення підпису на основі документа і секретного ключа користувача обчислює власне підпис. Залежно від алгоритму функція обчислення підпису може бути детермінованою або ймовірнісної. Детерміновані функції завжди обчислюють однакову підпис за однаковими вхідними даними. Імовірнісні функції вносять у підпис елемент випадковості, що підсилює криптостойкость алгоритмів ЕЦП. Однак, для імовірнісних схем необхідний надійний джерело випадковості (або апаратний генератор шуму, або криптографічно надійний генератор псевдовипадкових чисел), що ускладнює реалізацію.

Функція перевірки підпису перевіряє, чи відповідає дана підпис даного документу та відкритому ключу користувача. Відкритий ключ користувача доступний всім, так що будь-хто може перевірити підпис під даним документом.

Оскільки документи, які підписували - змінної (і досить великий) довжини, в схемах ЕЦП найчастіше підпис ставиться не на сам документ, а на його результат обчислення хеш. Для обчислення хешу використовуються криптографічні хеш-функції, що гарантує виявлення змін документа при перевірці підпису. Хеш-функції не є частиною алгоритму ЕЦП, тому в схемі може бути використана будь надійна хеш-функція.

Алгоритми ЕЦП діляться на два великі класи: звичайні цифрові підписи і цифрові підписи з відновленням документа. Звичайні цифрові підписи необхідно пристиковувати до підписувати документи. До цього класу належать, наприклад, алгоритми, засновані на еліптичних кривих (ECDSA, ГОСТ Р 34.10-2001, ДСТУ 4145-2002). Цифрові підписи з відновленням документа містять в собі підписується документ: у процесі перевірки підпису автоматично обчислюється і тіло документа. До цього класу належить один з найпопулярніших алгоритмів - RSA.

Електронний цифровий підпис функціонує на основі криптоалгоритмів з асиметричними (відкритими) ключами та інфраструктури відкритих ключів. Проблема традиційних алгоритмів шифрування з симетричними ключами полягає в тому, що шифрування і дешифрування відбувається за допомогою одного і того ж ключа. У зв'язку з цим виникає питання про обмін ключами. Для того щоб зробити захищений обмін інформацією, користувачам необхідно обмінятися ключами, при чому використовувати для цього обміну альтернативні засоби передачі інформації, оскільки при обміні нешифрований інформацією по електронній пошті висока ймовірність дискредитації ключа. Ідеальним, з точки зору безпеки, варіантом представляється особистий обмін ключовими носіями, проте він є найбільш ресурсоємним.

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

Для реалізації подібної взаємодії використовуються спеціальні структури, які засвідчують центри. Їх основна функція - поширення публічних і секретних ключів користувачів, а також верифікація сертифікатів. Засвідчують центри можуть об'єднуватися в ланцюжки. Вищий (кореневої) засвідчує центр може видати сертифікат і права на видачу ключів нижчестоящому центру. Той, у свою чергу, може видати права ще іншому нижчестоящому центру і так далі, причому, сертифікат, виданий одним з центрів, може бути верифікований кожним із серверів в ланцюжку. Таким чином існує можливість встановити центр розповсюдження секретних ключів в безпосередній близькості від користувача, що вирішує проблему дискредитації ключа при передачі по мережах зв'язку.

У випадку з ЕЦП процес обміну повідомленням виглядає наступним чином (якщо це алгоритм, то значить в ньому є певна послідовність дій. Отже форматування краще робити у вигляді нумерації кроків):

ѕ відправник отримує у засвідчувального центру секретний ключ;

ѕ використовуючи цей ключ, формує електронний цифровий підпис і відправляє лист;

ѕ одержувач за допомогою публічного (загальнодоступного) ключа і цифрового сертифіката, отриманого у засвідчувального центру, встановлює авторство документа і відсутність спотворень.

1.3 Хеш-функція

Функція хешування - це відображення h з безлічі всіх послідовностей символів з алфавіту А в , де m - деяке фіксоване натуральне число. Таким чином, кожна послідовність (довільної довжини) над А відображається в послідовність довжини m над А-хеш або цифровий відбиток. У типових додатках А = {0,1}, а m приймає значення між 64 і 256.

Хеш-функція призначена для стиснення підписуваного документа до декількох десятків або сотень біт. Хеш-функція h(·) приймає в якості аргументу повідомлення (документ) М довільної довжини і повертає хеш-значення фіксованої довжини. Зазвичай хешірованного інформація є стислим двійковим поданням основного повідомлення довільної довжини. Слід зазначити, що значення хеш-функції h(М) складним чином залежить від документа М і не дозволяє відновити сам документ М.

Обчислення хеш-функцій засноване на принципі односпрямованих функцій. Цей клас функцій відносно легко обчислюється, але інвертується з великими труднощами. Тобто, знаючи х, просто розрахувати f(х), але за відомим f(х) нелегко обчислити х. Тут, «нелегко» означає, що для обчислення можуть знадобитися мільйони років, навіть якщо цю проблему будуть вирішувати всі комп'ютери світу. Сенс односпрямованих хеш - функцій і полягає в забезпеченні для М унікального ідентифікатора. Якщо користувач А підписав М за допомогою алгоритму цифрового підпису на базі Н(М), а користувач В може створити інше повідомлення, відмінне від М - М', для якого Н(М) = Н(М'), то В зможе стверджувати, що А підписав М'. (Рис. 1.1).

Рисунок 1.1 - Односпрямована ітеративна функція

Однонаправлені хеш - функції будуються на ідеї функції стиснення, яка видає вихідне значення довжини n при заданих вхідних даних більшої довжини більшої довжини m. Входами функції стиснення є блок сполучення і вихід попереднього результату стиснення, тобто, хеш - значення блоку M_i одно:

(1.1)

де: - хеш - функція

- повідомлення

- значення хеш-функції на попередньому етапі

Це значення разом з наступним блоком повідомлення стає наступним входом функції стиснення. Цифровим відбитком всіх даних є значення останнього блоку.

програмний криптографічний електронний підпис

2. ЕЛЕКТРОННИЙ ЦИФРОВИЙ ПІДПИС ЗА ЕЛЬ ГАМАЛЕМ І DSS/DSA

2.1 Цифровий підпис на основі алгоритму Ель Гамаля (EGSA)

Хешування відбувається за схемою, зображеної на рис. 2.1

Рисунок 2.1 - Схема функції хешування

Назва ЕGSА походить від слів ЕІ GаmаІ Signaturе Аlgorithm (алгоритм цифрового підпису Ель Гамаля). Ідея ЕGSА заснована на тому, що для обґрунтування практичної неможливості фальсифікації цифрового підпису може бути використана більш складна обчислювальна задача, ніж розкладання на множники великого цілого числа, - завдання дискретного логарифмування. Крім того, Ель Гамалю вдалося уникнути явної слабкості алгоритму цифрового підпису RSА, пов'язаної з можливістю підробки цифрового підпису під деякими повідомленнями без визначення секретного ключа.

Розглянемо докладніше алгоритм цифрового підпису Ель Гамаля. Для того щоб генерувати пару ключів «відкритий ключ - секретний ключ», спочатку вибирають деяке велике просте ціле число Р і велике ціле число G, причому G < Р. Відправник і одержувач підписаного документа використовують при обчисленнях однакові великі цілі числа Р (~ 10308 або ~ 21024) і G (~ 10154 або ~ 2512), які не є секретними.

Відправник вибирає випадкове ціле число X, 1 <Х <(Р-1), і обчислює:

 (2.1)

де:

- відкритий ключ

- велике ціле число

- секретне число

- велике просте число

У ході підписування повідомлення М обчислюється його цифровий відбиток:

(2.2)

де:

- функція хешування

Вибирається випадкове ціле К, 1 <К <(Р - 1), взаємно просте з Р-1, і обчислюється

(2.3)

де:

- велике ціле число

- випадкове ціле число

- велике просте число

Після цього, за допомогою розширеного алгоритму Евкліда вирішується відносно s рівняння

(2.4)

де: - секретний ключ

- випадкове ціле число

- велике просте число

і - електронний цифровий підпис

Підпис утворює пари чисел (r, s). Після вироблення підпису значення К знищується. Одержувач підписаного повідомлення обчислює цифровий відбиток повідомлення:

(2.5)

де: - функція хешування

і перевіряє виконання рівності:

(2.6)

де: - відкритий ключ

r і s - електронний цифровий підпис

- велике просте число

- велике ціле число

- цифровий опечаток

Коректність цього рівняння очевидна:

(2.7)

де: - відкритий ключ

r і s - електронний цифровий підпис

- велике просте число

- велике ціле число

- цифровий опечаток

- секретний ключ

- випадкове число

2.2 Стандарт ЕЦП DSS/DSА

У 1991 р NIST (National Institute of Standards and Technology) запропонував для обговорення проект стандарту ЕЦП DSS (Digital Signature Standard), використовуючий алгоритм DSA (Digital Signature Algorithm). Стійкість даного алгоритму заснована на складності вирішення завдання дискретного логарифмування в мультіплікатівной групі простого поля F (p). Цифровий підпис служить для встановлення змін даних і для встановлення автентичності підписалася сторони. Одержувач підписаних даних може використовувати цифровий підпис для доказу третій стороні факту, що підпис дійсно зроблена відправником.

Відправник і одержувач електронного документа використовують при обчисленні великі цілі числа: G і Р - прості числа, L біт кожне (512 <L <1024); q - просте число довжиною 160 біт (дільник числа (Р-1)). Числа G, Р, q є відкритими і можуть бути спільними для всіх користувачів мережі.

Відправник вибирає випадкове ціле число X, 1 <Х <q. Число Х є секретним ключем відправника для формування електронного цифрового підпису. Потім відправник обчислює значення:

(2.8)

де: і - прості числа

Число Y є відкритим ключем для перевірки підпису відправника. Число Y передається всім одержувачам документів.

Цей алгоритм також передбачає використання односторонньої функції хешування h(). У стандарті DSS визначено алгоритм безпечного хешування SНА (Secure Hash Algorithm).

Для того щоб підписати документ М, відправник хешірует його в ціле хеш-значення m:

(2.8)

де: - функція хешування

Потім генерує випадкове ціле число К, 1 < К < q, і обчислює число r:

(2.9)

де: і і - прості числа

- випадкове ціле число

Потім відправник обчислює за допомогою секретного ключа Х ціле число s:

(2.10)

де:

і - електронний цифровий підпис

- цифровий відбиток

- секретний ключ

- випадкове ціле число

- просте число

Пара чисел і утворює цифровий підпис під документом :

(2.11)

Таким чином, підписане повідомлення являє собою трійку чисел [М, r, s]. Одержувач підписаного повідомлення [М, r, s] перевіряє виконання умов:

0 <r <q, 0 <s <q (2.12)

І відкидає підпис, якщо хоча б одна з цих умов не виконано. Потім одержувач обчислює значення:

(2.13)

де: - параметр електронного цифрового підпису

- просте число

Хеш-значення:

(2.14)

де: - функція хешування

І числа:

(2.15)

де: - цифровий відбиток

- верифікація електронного цифрового підпису

- параметр електронного цифрового підпису

- просте число

Далі одержувач за допомогою відкритого ключа Y обчислює значення:

(2.16)

Де: і і - прості числа

- відкритий ключ

- верифікація електронного цифрового підпису

- верифікація електронного цифрового підпису

Перевіряє виконання умови:

(2.17)

Де: - підтвердження дійсності електронного цифрового підпису

Якщо умова виконується, тоді підпис під документом визнається одержувачем справжньою.

Можна строго математично довести, що остання рівність буде виконуватися тоді, і тільки тоді, коли підпис під документом отримана за допомогою саме того секретного ключа , з якого був отриманий відкритий ключ . Таким чином, можна надійно упевнитися, що відправник повідомлення володіє саме даними секретним ключем (не розплющуючи при цьому значення ключа ) і що відправник підписав саме даний документ .

3. РОЗРОБКА ПРОГРАМНОГО КОДУ

3.1 Програмний код для алгоритму ЕЦП по Ель Гамалю

#include "stdafx.h"

#include "ElGamal.h"

#include <ctime>

#include <iostream>

inline void genPrime(int bitLen, big p, csprng *rng) // генерация простых

заданной длины

{

int len = bitLen / 8 / sizeof(mr_small) + ((bitLen % (8 * sizeof(mr_small))) ?

1 : 0); // длина в 4х байтовых словах

big t = mirvar(0);

t->len = len + 1;

t->w[len] = 1; // 1 в bitLen+1 позиции

strong_bigrand(rng, t, p); // p -- случайное

p->w[0] |= 1; // нечетное

if (!isprime(p)) // если не простое

nxprime(p, p); // берем следующее за ним простое

mirkill(t);

}

inline void sha_string(char* msg, int len, char* tmp) // хеширование в

строку

{

sha sha; // sha1 хеш

shs_init(&sha); // инициализация

for (int i = 0; i < len; i++)

shs_process(&sha, msg[i]); // хешируем сообщение

shs_hash(&sha, tmp); // записываем результат в выходной буфер

}

inline void sha_string(char* msg, int len, big t) // хеширование в big число

{

char tmp[20];

sha_string(msg, len, tmp); // хешируем в строку

bytes_to_big(20, tmp, t); // преобразуем строку в число

}

ElGamal::ElGamal(char *seed, int len)

{

strong_init(&rng, len, seed, time(NULL)); // инициализация генератора

ПСЧ

}

ElGamal::~ElGamal()

{

mirkill(p);

mirkill(g);

}

void ElGamal::sign(void *msg, int len, big x, big r, big s)

{

big K = mirvar(0), k = mirvar(0), p = mirvar(0), t = mirvar(0);

big m = mirvar(0);

sha_string((char*)msg, len, m);

copy(this->p, p);

p->w[0]--; //p=P-1

do

{

do

{

strong_bigrand(&rng, this->p, K);

K->w[0] |= 3; //K>1, нечетное, рундовый ключ

} while (xgcd(K, p, k, k, k) != 1); // k=1/K

powmod(g, K, this->p, r); // подсказка

insign(-1, r); // меняем знак r

mad(x, r, m, p, t, s); // замудренная функция, делает кучу вычислений

внутри себя, лучше почиатть в документации

insign(1, r); // востанавливаем знак

multiply(s, k, s); // домножаем s на k^-1

divide(s, p, p); // берем по модулю

if (exsign(s) == -1) // если S<0

add(s, p, s); // добавляем P-1

} while (s->len == 0); // пока S=0

mirkill(K);

mirkill(k);

mirkill(p);

mirkill(t);

mirkill(m);

}

bool ElGamal::check(void *msg, int len, big y, big r, big s)

{

big t1 = mirvar(0), t2 = mirvar(0);

big m = mirvar(0);

sha_string((char*)msg, len, m);

powmod(g, m, p, t1); // тут собсно все по формулам

powmod2(y, r, r, s, p, t2);

bool res = compare(t1, t2) == 0;

mirkill(t1);

mirkill(t2);

mirkill(m);

return res;

}

void ElGamal::genKeys(big x, big y)

{

strong_bigrand(&rng, p, x);

x->w[0] |= 3; // ключ должен быть больше 2?

powmod(g, x, p, y);

}

void ElGamal::genOpenParams(char *seed, int len)

{

gprime(1 << 15); // инициализация miracl'овской таблицы простых,

используется в тестах простоты

big q1 = mirvar(0), q2 = mirvar(0);

big t = mirvar(0);

big r1 = mirvar(0), r2 = mirvar(0), r3 = mirvar(0);

p = mirvar(0);

g = mirvar(0);

// конструируем p

genPrime(1024 / 2, q1, &rng); // крупный простой множитель

while (true)

{

std::swap(q1, q2);

genPrime(1024 / 2, q1, &rng); // тоже

multiply(q1, q2, p); // p=q1*q2

sftbit(p, 1, p);

incr(p, 1, p); // p=2*q1*q2+1

if (isprime(p)) // если получилось простое -- выходим из цикла

break;

}

multiply(q1, q2, r1); // конструируем степени для выбора генератора, я

точно уже не помню что и как

sftbit(q1, 1, r2); // но суть в том, что если g в этих степенях не равна 1

sftbit(q2, 1, r3); // такое g можно исполдьзовать

int g;

for (g = 4; g < 1 << 30; g++) // цикл по g

{

powltr(g, r1, p, t);

if (t->len == 1 && t->w[0] == 1)

continue; // выпала 1

powltr(g, r2, p, t);

if (t->len == 1 && t->w[0] == 1)

continue;

powltr(g, r3, p, t);

if (t->len == 1 && t->w[0] == 1)

continue;

break; // 1 не выпала, это генератор мультипликативной группы

}

convert(g, this->g); // преобразуем int в big

mirkill(q1); mirkill(q2); mirkill(t);

mirkill(r1); mirkill(r2); mirkill(r3);

}

3.2 Програмний код для алгоритму ЕЦП ЕЦП DSS/DSА

#include "stdafx.h"

extern "C"

{

#include "miracl.h"

}

#include <ctime>

#include <cstring>

#include <iostream>

class DSA

{

public:

big p, q, g; // открытые параметры алгоритма

csprng rng; // криптографический стойкий генератор ПСЧ

void sign(void *msg, int len, big x, big r, big s); // подпись

bool check(void *msg, int len, big y, big r, big s); // проверка

void genKeys(big x, big y); // генерация ключевой пары

void genOpenParams(char *seed, int len); // генерация открытых

параметров

DSA(char *seed, int len);

~DSA();

};

// здесь во всю используется бблиотека miracl, big -- число большой

разрядности

inline void sha_string(char* msg, int len, char* tmp) // хеширование в

строку

{

sha sha; // sha1 хеш

shs_init(&sha); // инициализация

for (int i = 0; i < len; i++)

shs_process(&sha, msg[i]); // хешируем сообщение

shs_hash(&sha, tmp); // записываем результат в выходной буфер

}

inline void sha_string(char* msg, int len, big t) // хеширование в big число

{

char tmp[20];

sha_string(msg, len, tmp); // хешируем в строку

bytes_to_big(20, tmp, t); // преобразуем строку в число

}

inline void inc(char *seed, int len) // увеличиваем seed на 1, используется

при генерации открытых параметров

{

seed[len - 1]++; // инкрементируем младший байт

for (int i = len - 2; i >= 0; i--) // идем начиная с предпоследнего

{

if (seed[i + 1] == 0) // если байт 0 -- считаем что произошло

переполнение

seed[i]++; // и увеличиваем старший байт на один

else

break; // при первом отсутствии переполнения выходим из цикла

}

}

DSA::DSA(char *seed, int len)

{

strong_init(&rng, len, seed, time(NULL)); // инициализация генератора

ПСЧ

}

DSA::~DSA()

{

mirkill(p); // освобождаем память

mirkill(q);

mirkill(g);

}

void DSA::sign(void *msg, int len, big x, big r, big s)

{

big k = mirvar(0); // раундовый ключ

big t = mirvar(0); // временная переменная

strong_bigrand(&rng, q, k); // заполняем k случайным числом меньшим q

powmod(g, k, p, r); // вычисляем r по модулю p

divide(r, q, q); // теперь берем по модулю q

sha_string((char*)msg, len, t); // хешируем сообщение

multiply(x, r, s); // расчет s

add(s, t, s);

divide(s, q, q);

xgcd(k, q, k, k, k); // поиск обратного элемента

multiply(s, k, s);

divide(s, q, q);

mirkill(k); // подчищаем

mirkill(t);

}

bool DSA::check(void *msg, int len, big y, big r, big s)

{

big w = mirvar(0), u1 = mirvar(0), u2 = mirvar(0), v = mirvar(0);

copy(s, w);

xgcd(w, q, w, w, w); // w=1/s

sha_string((char*)msg, len, u1); // хешируем

multiply(u1, w, u1); // домножаем

multiply(r, w, u2);

powmod2(g, u1, y, u2, p, v); // двойное возведение в степень,

v=g^u1*y^u2 mod p

divide(v, q, q); // приводим по модулю q

bool res = !compare(v, r); // compare вернет 0 при совпадении

переменных

mirkill(w); mirkill(u1); mirkill(u2); mirkill(v);

return res;

}

void DSA::genKeys(big x, big y)

{

strong_bigrand(&rng, q, x); // случайных закрытый ключ

powmod(g, x, p, y); // открытый

}

void DSA::genOpenParams(char *seed, int len) // стр 11 fips 186-1

{

p = mirvar(0);

q = mirvar(0);

g = mirvar(0);

do

{

// step 2

char u[20];

sha_string(seed, len, u); //певый операнд в u

inc(seed, len); // seed = seed + 1

char t[20];

sha_string(seed, len, t); // второй операнд

for (int i = 0; i < 20; i++) // xor

u[i] ^= t[i];

//step 3

u[0] |= 1;

u[len - 1] |= 1 << 7;

bytes_to_big(20, u, q); // переводим массив байт в число

} while (!isprime(q)); // step 4

big X = mirvar(0);

big t = mirvar(1);

sftbit(t, 1023, t); // t=2^(L-1)

do

{

inc(seed, len); // вместе с первым inc в следующем цикле образует

offset=2

char V[1024 / 8];

char *ptr = V; // указатель на Vk

for (int k = 0; k < 1024 / 160; k++) // step 7

{

inc(seed, len); // seed += 1

sha_string(seed, len, ptr); // Vk=SHA1(seed+offset+k)

ptr += 20; // по сути K++, переход к следующей части буфера

}

bytes_to_big(sizeof(V), V, X); // step 8

add(X, t, X); // в t 2^(L-1)

//step 9

sftbit(q, 1, q); // q=2q, побитовый сдвиг

copy(X, t); // t=X

divide(t, q, q); // t=X mod 2q, в документации это c

sftbit(q, -1, q); // q=2q/2=q

decr(t, 1, t); // c-1

subtract(X, t, p); // p=X-(c-1)

convert(1, t); // востанавливаем 2^(L-1) в t

sftbit(t, 1023, t);

if (compare(p, t) == -1) // step 10

goto loopend;

if (isprime(p))

break; // если p простое -- выходим из цикла

loopend:

inc(seed, len); // по сути offset+=1

} while (true);

copy(p, X); // X=p

decr(X, 1, X); // X=p-1

copy(q, t); // t=q

xgcd(t, p, t, t, t); //t=1/q

multiply(X, t, X); // X=(p-1)/q

divide(X, p, p); // X=(p-1)/q mod p, в документации на 7 стр, степень при

h

do

{

bigrand(q, t);// по сути t=h

powmod(t, X, p, g); // генерация g=h^((p-1)/q) mod p

} while (size(g) == 1); // пока g=1

mirkill(X);

mirkill(t);

}

template<typename Signature>

void test(char *msg, char *alg) // тест подписи

{

char seed[20] = { 1, 2, 3, 4, 5, 6, 7 }; // зерно

Signature sign(seed, sizeof(seed));

sign.genOpenParams(seed, sizeof(seed)); // генерация открытых

параметров

big x = mirvar(0), y = mirvar(0); // ключи

sign.genKeys(x, y); // их генерация

std::cout << "Testing " << alg << ": " << std::endl;

big r = mirvar(0), s = mirvar(0); // подпись

sign.sign(msg, strlen(msg), x, r, s); // подписываем

std::cout << "Sing: ";

char num[1000];

cotstr(r, num); // функция, конвертирующая big в строку, часть miracl

std::cout << num << std::endl;

cotstr(s, num);

std::cout << num << std::endl;

if (sign.check(msg, strlen(msg), y, r, s)) // проверяем подпись

std::cout << "Sign match" << std::endl;

else

std::cout << "Sign mismatch" << std::endl;

msg[0] ^= 1; // меняем сообщение

std::cout << "Changing msg... msg: " << msg << ": ";

if (sign.check(msg, strlen(msg), y, r, s)) // проверяем отклонение подписи

std::cout << "Sign match" << std::endl;

else

std::cout << "Sign mismatch" << std::endl;

msg[0] ^= 1; // востанавлдиваем сообщение

incr(r, 1, r); // и портим подпись

std::cout << "Restoring msg and changing r: ";

if (sign.check(msg, strlen(msg), y, r, s)) // проверяем отклонение подписи

std::cout << "Sign match" << std::endl;

else

std::cout << "Sign mismatch" << std::endl;

}

int _tmain(int argc, _TCHAR* argv[])

{

mirsys(64 * 3, 0)->IOBASE = 16; // инициализируем miracl, ввод-вывод в

16й системе

char msg[1024]; // сообщение

std::cout << "Enter msg:> ";

std::cin.getline(msg, sizeof(msg));

test<DSA>(msg, "DSA"); // тестируем DSA

system("pause");

return 0;

}

ВИСНОВКИ

Схема цифрового підпису Ель Гамаля має ряд переваг у порівнянні зі схемою цифрового підпису RSА:

ѕ при заданому рівні стійкості алгоритму цифрового підпису цілі числа, що беруть участь в обчисленнях, мають запис на 25% коротше, що зменшує складність обчислень майже в два рази і дозволяє помітно скоротити обсяг використовуваної пам'яті.

ѕ при виборі модуля Р достатньо перевірити, що це число є простим і що у числа (Р-1) є великий простий множник (тобто всього два досить просто перевіряються умови).

ѕ процедура формування підпису за схемою Ель Гамаля не дозволяє обчислювати цифрові підписи під новими повідомленнями без знання секретного ключа (як в RSА).

Однак алгоритм цифрового підпису Ель Гамаля має і деякі недоліки в порівнянні зі схемою підпису RSА. Зокрема, довжина цифрового підпису виходить в 1,5 рази більше, що, в свою чергу, збільшує час її обчислення.У порівнянні з алгоритмом цифрового підпису Ель-Гамаля алгоритм DSА має такі основні переваги:

ѕ при будь-якому допустимому рівні стійкості, тобто при будь-якій парі чисел G і Р (від 512 до 1024 біт), числа q, X, r, s мають довжину по 160 біт, скорочуючи довжину підпису до 320 біт.

ѕ більшість операцій з числами К, r, s, Х при обчисленні підписи проводиться за модулем числа q довжиною 160 біт, що скорочує час обчислення підпису.

ѕ при перевірці підпису більшість операцій з числами , , V, W також проводиться за модулем числа q довжиною 160 біт, що скорочує обсяг пам'яті і час обчислення.

Недоліком алгоритму DSА є те, що при підписуванні і при перевірці підпису доводиться виконувати складні операції ділення по модулю q, що не дозволяє отримувати максимальну швидкодію.

Слід зазначити, що реальне виконання алгоритму DSА може бути прискорене за допомогою виконання попередніх обчислень. Значення r не залежить від повідомлення М і його хеш-значення m. Можна заздалегідь створити рядок випадкових значень К і потім для кожного з цих значень обчислити значення r. Можна також заздалегідь обчислити зворотні значення К-1для кожного із значень К. Потім, при надходженні повідомлення М, можна обчислити значення s для даних значень r і К-1. Ці попередні обчислення значно прискорюють роботу алгоритму DSА.

Вищеописане порівняння свідчить про те, що алгоритм цифрового підпису Ель Гамаля більш стійкий для пари відправник-одержувач, ніж алгоритм RSA. У той же час даний алгоритм є менш стійким в порівнянні зі стандартом DSS / DSA. Головна перевага останнього полягає в тому, що певні попередні обчислення можуть прискорити його роботу, тобто поліпшити працездатність алгоритму. Якщо взяти той факт, що реалізації обох алгоритмів в програмному коді не особливо відрізняються, виходить, що стандарт DSS / DSA більш вигідний, криптостійкий і швидкий.

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Баричев С.Г Основи сучасної криптографії // Гончаров В.В., Сєров Р.Е. - Москва, Гаряча лінія - Телеком, 2001

2. Бєляєв А.В. Методи і засоби захисту інформації (курс лекцій)

3. Володін А. «Хто запевнить ЕЦП» - журнал «Банківські системи» - листопад 2000

4. Іртегов Д. Захист інтелектуальної власності в інтернеті, СПб, БХВ- Петербург, 2007р.

5. Петров А.А. Комп'ютерна безпека. Криптографічні методи захисту. ДМК, Москва, 2000 р.

6. Солоніцин Ю.А. Інтернет. Енциклопедія, СПб, Пітер, 2006 р.

7. Столлінгс В. Криптографія та захист мереж: теорія і практика. М: Вільямс. 2001. Пер. з англ.

8. Терехов А.А. Програмування РАН // А. Тіскін, №5 (вересень-жовтень), 1994, стор. 17--22

9. Фигурнов В.Є. Інтернет для користувача. Короткий курс. - М.: ИНФРА-М, 1999 р.

10. Криптографічні системи

11. Лекції з криптографіі

12. Прості числа від 1 до 100 000

13. Алгоритм Евкліда

Размещено на Allbest.ru