Оцінка стійкості електронного цифрового підпису згідно ISO/IEC 15946-4-8 та розробка програми для знаходження ймовірності виникнення колізії

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

РЕФЕРАТ

Пояснювальна записка до курсової роботи: 36c., 2 рис., 7 табл., 4 розд., 2 дод., 8 джерел.

Об'єкт дослідження - ЕЦП згідно ISO/IEC 15946-4-8.

Мета роботи -проаналізувати ЕЦП з відновленням повідомлення та розробка програми для розрахунку ймовірності колізії.

Методи дослідження - підбір і вивчення літератури, написання і відладка програми на комп'ютері.

Вивчення літератури, що описує ЕЦП з відновленням повідомлення. Дослідження ЕЦП Нюрберга-Рюпеля в групі точок еліптичної кривої. Аналіз стійкості ЕЦП згідно ISO/IEC 15946-4-8. Реалізація програми, яка буде розраховувати ймовірність колізії.

Проаналізовано ЕЦП згідно ISO/IEC 15946-4-8.

Розроблена програма, яка розраховує ймовірність виникнення колізії.

Програма написана на мові С++ в середовищі Visual C++.

ЕЦП, ЕЛІПТИЧНА КРИВА, ГЕШ ФУНКЦІЯ, КОРОТКЕ ПОВІДОМЛЕННЯ, КОЛЛІЗІЯ, КРИПТОСТІЙКІСТЬ.



ЗМІСТ

Вступ

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

1. Постановка завдання і сфера застосування електронного цифрового підпису

2. Електронний цифровий підпис із відновленням повідомлення

2.1 Загальна модель ЕЦП з відновленням повідомлень

2.1.1 Процес обчислення параметрів

2.1.2 Процес обчислення підпису

2.1.3Процес перевіряння підпису

2.1.4 Особливості ЕЦП з відновленням повідомлення

2.1.5 Перелік функцій і процедур

2.1.6 Генерування (обчислення) асиметричної ключової пари ЦП

2.1.7 Генерування (обчислення) ключа сеансу та попереднього ЦП

2.1.8 Обчислення першої і другої частин підпису

2.1.9 Відновлення попереднього підпису та вхідних даних

2.2 Обчислення цифрового підпису

2.2.1 Формування ключа сеансу та попереднього підпису

2.2.2 Розщеплення повідомлення

2.2.3 Формування вхідних даних та обчислення ЦП

2.2.4 Порядок обчислення цифрового підпису

2.3 Перевіряння цифрового підпису

2.3.1 Функції перетворення та генерації маски

3. Цифровий підпис Ніберга-Рюпеля в групі точок еліптичних кривих

3.1 Ключі цифрового підпису ECNR

3.2 Обчислення цифрового підпису

4. Аналіз ЕЦП з відновленням повідомлення

4.1 Стійкість ЕЦП з відновленням повідомлення до колізій

4.2 Стійкість до колізій відновлюваної частини повідомлення

4.3 Аналіз складності реалізації ЕЦП з відновленням повідомлення

4.4 Число гешувань MGF

5. Програмна реалізація

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

5.2 Опис логічної структури

5.3 Вхідні й вихідні дані

Висновки

33 Перелік посилань

Додаток А. Текст програми

Додаток Б. Інструкція користувача

ПЕРЕЛІК СКОРОЧЕНЬ

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

ECNR - Цифровий підпис Нюберга-Рюпеля в групі точок еліптичних кривих



ВСТУП

Криптографія (від грецького kryptуs -- прихований і grбphein -- писати) -- наука про математичні методи забезпечення конфіденційності (неможливості прочитання інформації стороннім) і автентичності (цілісності і справжності авторства) інформації. Розвинулась з практичної потреби передавати важливі відомості найнадійнішим чином. Для математичного аналізу криптографія використовує інструментарій абстрактної алгебри.

Для сучасної криптографії характерне використання відкритих алгоритмів шифрування, що припускають використання обчислювальних засобів. Відомо більш десятка перевірених алгоритмів шифрування, які, при використанні ключа достатньої довжини і коректної реалізації алгоритму, роблять шифрований текст недоступним для криптоаналізу. Широко використовуються такі алгоритми шифрування як Twofish, IDEA, RC4 та ін.

У багатьох країнах прийняті національні стандарти шифрування. У 2001 році в США прийнятий стандарт симетричного шифрування AES на основі алгоритму Rijndael з довжиною ключа 128, 192 і 256 біт. Алгоритм AES прийшов на зміну колишньому алгоритмові DES, який тепер рекомендовано використовувати тільки в режимі Triple-DES (3DES)

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

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

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

Історія криптографії

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

Найперші форми тайнопису вимагали не більше ніж аналог олівця та паперу, оскільки в ті часи більшість людей не могли читати. Поширення писемності, або писемності серед ворогів, викликало потребу саме в криптографії. Основними типами класичних шифрів є перестановочні шифри, які змінюють порядок літер в повідомленні, та підстановочні шифри, які систематично замінюють літери або групи літер іншими літерами або групами літер. Прості варіанти обох типів пропонували слабкий захист від досвідчених супротивників. Одним із ранніх підстановочних шифрів був шифр Цезаря, в якому кожна літера в повідомленні замінювалась літерою через декілька позицій із абетки. Цей шифр отримав ім'я Юлія Цезаря, який його використовував, зі зсувом в 3 позиції, для спілкування з генералами під час військових кампаній, подібно до коду EXCESS-3 в булевій алгебрі.

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

Шифротексти, отримані від класичних шифрів (та деяких сучасних), завжди видають деяку статистичну інформацію про текст повідомлення, що може бути використано для зламу. Після відкриття частотного аналізу (можливо, арабським вченим аль-Кінді) в 9-тому столітті, майже всі такі шифри стали більш-менш легко зламними досвідченим фахівцем. Класичні шифри зберігли популярність, в основному, у вигляді головоломок (див. криптограмма). Майже всі шифри залишались беззахисними перед криптоаналізом з використанням частотного аналізу до винаходу поліалфавітного шифру, швидше за все, Альберта Леоном-Баттіста приблизно в 1467 році (хоча, існують свідчення того, що знання про такі шифри існували серед арабських вчених). Винахід Альберті полягав в тому, щоб використовувати різні шифри (наприклад, алфавіти підстановки) для різних частин повідомлення. Йому також належить винахід того, що може вважатись першим шифрувальним приладом: колесо, що частково реалізовувало його винахід (див. Шифрувальний диск Альберті). В поліалфавітному шифрі Віженера (англ. Vigenиre cipher), алгоритм шифрування використовує ключове слово, яке керує підстановкою літер в залежності від того, яка літера ключового слова використовується. В середині 1800-тих, Чарльз Беббідж показав, що поліалфавітні шифри цього типу залишились частово беззахисними перед частотним аналізом.

Енігма, автомат, варіанти якого використовувались німецькими військовими починаючи з другої половини 1920-тих і до кінця Другої світової війни. Цей автомат реалізовував складний електро-механічний поліафавітний шифр для захисту таємних повідомлень. Злам шифру Енігми в Бюро Шифрів (Biuro Szyfrуw), та, слід за цим, дешифрування повідомлень в Блетчі Парк (англ. Bletchley Park), було важливим чинником перемоги Союзників у війні.

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

Було створено різні механічні прилади та інструменти для допомоги в шифруванні. Одним з найперших є скітала в стародавній Греції, палиця, що, як вважається, використовувалась Спартанцями в якості перестановочного шифру. В середньовіччя, було винайдено інші засоби, такі як дірочний шифр, що також використовувася для часткової стеганографії. Разом із винаходом поліалфавітних шифрів, було розроблено досконаліші засоби, такі як власний винахід Альберті шифрувальний диск, табула ректа Йогана Тритеміуса, та мультициліндр Томаса Джефферсона (повторно винайдений Базерієсом приблизно в 1900 році). Декілька механічних шифрувально/дешифрувальних приладів було створено на початку 20-го століття і багато запатентовано, серед них роторні машини -- найвідомішою серед них є Енігма, автомат, що використовувася Німеччиною з кінця 20-тих і до кінця Другої світової війни. Шифри, реалізовані прикладами покращених варіантів цих схем призвели до істотного підвищення криптоаналітичної складності після Другої світової війни.. Поява цифрових комп'ютерів та електроніки після Другої світової війни зробило можливим появу складніших шифрів. Більше того, комп'ютери дозволяли шифрувати будь-які дані, які можна представити в комп'ютері у двійковому виді, на відміну від класичних шифрів, які розроблялись для шифрування письмових текстів. Це зробило непридатними для застосування лінгвістичні підходи в криптоаналізі. Багато комп'ютерних шифрів можна характеризувати за їхньою роботою з послідовностями бінарних бітів (інколи в блоках або групах), на відміну від класичних та механічних схем, які, зазвичай, працюють безпосередньо з літерами. Однак, комп'ютери також знайшли застосування у криптоаналізі, що, в певній мірі, компенсувало підвищення складності шифрів. Тим не менше, гарні сучасні шифри залшались попереду криптоаналізу; як правило, використання якісних шифрів дуже ефективне (тобто, швидке і вимагає небагато ресурсів), в той час як злам цих шифрів потребує набагато більших зусиль ніж раніше, що робить криптоаналіз настільки неефективним та непрактичним, що злам стає практично неможливим.

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

Широкі академічні дослідження криптографії з'явились порівняно нещодавно -- починаючи з середини 1970-тих, разом із появою відкритої специфікації стандарту DES (Data Encryption Standard) Національного Бюро Стандартів США, публікацій Діффі-Хелмана та оприлюдненням алгоритму RSA. Відтоді, криптографія перетворилась на загальнопоширений інструмент для передачі даних, в комп'ютерних мережах, та захисті інформації взагалі. Сучасний рівень безпеки багатьох криптографічних методів базується на складності деяких обчислювальних проблем, таких як розклад цілих чисел, або проблеми з дискретними логарифмами. В багатьох випадках, існують докази безпечності криптографічних методів лише за умови неможливості ефективного розв'язання певної обчислювальної проблеми. За одним суттєвим винятком -- схема одноразових блокнотів.

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

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

Симетричні алгоритми шифрування

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

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

Сучасні дослідження симетричних алгоритмів шифрування зосереджено, в основному, навколо блочних та потокових алгоритмів шифрування та їх застосуванні. Блочний шифр подібний до поліалфавітного шифру Алберті: блочні шифри отирмують фрагмент відкритого тексту та ключ, і видають на виході шифротекст такого самого розміру. Оскільки повідомлення зазвичай довші за один блок, потрібен деякий метод склеювання послідовних блоків. Було розроблено декілька методів, що відрізняються в різних аспектах. Вони є режимами дії блочних шифрів та мають обережно обиратись під час застосування блочного шифру в криптосистемі.

Шифри Data Encryption Standard (DES) та Advanced Encryption Standard (AES) є стандартами блочних шифрів затверджених урядом США (однак, стандартизацію DES було скасовано після прийняття стандарту AES). Не зважаючи на те, що стандарт DES було визнано застарілим, він (та особливо його все ще дійсний варіант triple-DES) залишається досить популярним; він використовується в багатьох випадках, від шифрування в банкоматах до забезпечення приватності електронного листування та безпечному доступі до віддалених терміналів. Було також розроблено багато інших шифрів різної якості. Багато з них було зламано.

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

Криптографічні хешувальні функції (англ. cryptographic hash functions, або англ. message digest functions) не обов'язково використовують ключі, але часто використовуються і є важливим класом криптографічних алгоритмів. Ці функції отримують дані (часто, ціле повідомлення), та обчислюють коротке, фіксованого розміру число (геш). Гарні гешувальні функції створені таким чином, що дуже важко знайти колізії (два відкритих тексти, що мають однакове значення хешу).

Коди аутентифікації повідомлень (англ. Message authentication code, MAC) подібні до криптографічних гешувальних функцій, за виключенням того, що вони використовують секретний ключ для аутентифікації значення гешу при отриманні повідомлення. Ці функції пропонують захист проти атак на прості гешувальні функції.

Асиметричні алгоритми шифрування

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

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



1. ПОСТАНОВКА ЗАВДАННЯ І СФЕРА ЗАСТОСУВАННЯ ЕЛЕКТРОННОГО ЦИФРОВОГО ПІДПИСУ

Завдання: проаналізувати стійкість ЕЦП згідно ISO/IEC 15946-4-8 та створити програму для знаходження ймовірності виникнення колізії.

Безпека передачі даних по каналам зв'язку є актуальною. Сучасні комп'ютерні мережі не виняток. Нажаль, в мережевих операційних системах (Windows NT/XP, Novell й т.д.) іноземного виробництва, як наслідок, з-за експортних міркувань рівень алгоритмів шифрування сильно знижений.

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



2. ЕЛЕКТРОННИЙ ЦИФРОВИЙ ПІДПИС ІЗ ВІДНОВЛЕННЯМ ПОВІДОМЛЕННЯ

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

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

Теоретичні обґрунтування й практичні дослідження ЕЦП з відновленням повідомлення були виконані, у порівнянні з ЕЦП з додатком, пізніше. Значною мірою вони з'явилися, коли виникла необхідність в ЕЦП для коротких повідомлень. Цей напрям був успішно розвинутий у роботах. Як наслідок у 2003 році був прийнятий міжнародний стандарт ІS0/ІЕС15946-4. У нього було включено 5 незалежних алгоритмів ЕЦП з відновленням повідомлення, криптографічні перетворення в якому базуються на еліптичних кривих. У подальшому цей стандарт було вдосконалено, і він був прийнятий у 2006 році як ІS0/ІЕС 9796-3 на заміну існуючому. Додатково в нього був включений алгоритм ЕЦП, що ґрунтується на перетворенні в полі Галуа.

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

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

Таким чином, схеми ЕЦП із відновленням повідомлення доцільно використовувати в інформаційних системах і протоколах з чітко визначеними повідомленнями. Це є принциповою особливістю з точки зору їх застосування. Також, зважаючи на те, що ЕЦП з відновленням повідомлення є специфічним, наведемо основні символи та позначення, що використовуються в цьому розділі (таблиця 2.1)[1].

Таблиця 2.1 - Основні символи та позначення ЕЦП з відновленням

d, d'	Вхідні дані та відновлені вхідні дані відповідно
h, h', h»	Геш-токен (значення), відновлений (обрізаний) геш-токен, повторно обчислений (обрізаний) геш-токен відповідно
K	Ключ сеансу
Lh	Довжина (обрізаного) геш-токену (у бітах)
Lf	Розмір поля F(в октетах)
Lrec>Lclr, Ln	Довжина (у бітах) Mrec , Мclr та n відповідно
Lp	Довжина р (в октетах)
L1, L2	Довжина (у бітах) короткої і довгої надлишковості, відповідно
M, Mclr, Mrec	Повідомлення M, `ешування`ювана частина Mclr і відновлювана частина Mrec відповідно
M, M'rec	Відновлене повідомлення, відновлена частина повідомлення відповідно
M	Ціле натуральне число
n, а	Порядок базової точки та `ешування елемент простого поля Галуа відповідно
F(q)	Скінченне поле з q елементами, де q є простим ступенем
E(F(q))	Група з u точками на еліптичній кривій - порядок еліптичної кривої
?	Попередній підпис
r, r'	Перша частина підпису r, що обчислений підписувачем, і перша частина підпису r', що має перевірник, відповідно
s, s'	Друга частина підпису s, що обчислений підписувачем, і друга частина s', що має перевірник, відповідно
XA	Особистий ключ підпису об'єкта А
YA	Відкритий ключ перевірки об'єкта А
P, Q	Точки, які приймають значення в залежності від обраної схеми генерації ключів. Так, Р = G і Q = YA для схеми генерації ключів І, та Р = YA і Q = G для схеми генерації ключів II
р	Функція перетворення точки на еліптичній кривій на ціле число
X	Добуток в декартовій системі координат
XOR	Побітова сума виключного АБО (сума за модулем 2)
SYM	Використовуваний симетричний шифр, ключ якого формується за допомогою функції формування ключів KDF
KDF	Функція формування симетричних ключів, у якій на вхід подається точка еліптичної кривої, а на виході видається значення, що може бути використане як симетричний ключ симетричного шифру SYM

2.1 Загальна модель ЕЦП з відновленням повідомлень

У стандарті ISO/IEC9796-3:2006 визначено 6 різних схем (методів) і на їх основі 6 механізмів цифрових підписів з відновленням повідомлення. Механізми цифрового підпису подані в стандарті, мають назву «механізм підпису з відновленням». Вони забезпечують повне або часткове відновлення повідомлення. У подальшому ЕЦП з відновленням повідомлення будемо розглядати через специфікацію процесів обчислення (генерації) параметрів, обчислення (генерації) підпису та перевіряння підпису[1].

2.1.1 Процес обчислення параметрів

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

Обов'язково мають бути визначені такі параметри:

· ідентифікатор схеми цифрового підпису, що використовується;

· функція `ешування (Hash);

· процедури генерації параметрів користувача.

Кожен об'єкт має свої власні відкриті й особисті параметри. До параметрів користувача об'єкта A належать:

· особистий ключ підпису ХA;

· відкритий ключ перевірки YA;

· інша інформація (необов'язково), що є специфічною для об'єкта яка використовується в процесі генерації підпису і/або в процесі перевіряння.

Застосовувані параметри та ключі повинні бути дійсними - у сенсі їх цілісності та справжності (автентичності).

Впевненість у дійсності доменних параметрів може бути забезпечена в один із таких способів:

1) за умови вибору дійсних доменних параметрів з довірчого опублікованого джерела, наприклад такого, як стандарт відповідного ЕЦП;

2) коли обчислення дійсних доменних параметрів виконується третьою довірчою стороною, такою як центр сертифікації;

3) коли перевірка дійсності кандидатів до доменних параметрів здійснюється третьою довірчою стороною, такою як центри сертифікації;

4) за умови обчислення доменних параметрів підписувачем з використанням довірчої системи;

5) коли перевірка дійсності кандидатів до доменних параметрів виконується підписувачем або перевірником.

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

1) при генерації (обчисленні) пари відкритого ключа перевірки особистого ключа підпису з використанням довірчої третьої сторони;

2) коли перевірка дійсності відкритого ключа перевірки здійснюється третьою довірчою стороною, такою, як центр сертифікації;

3) коли перевірка дійсності відкритого ключа перевірки здійснюється підписувачем або перевірником[1].

2.1.2 Процес обчислення підпису

Для обчислення ЕЦП мають бути введені:

· дійсні доменні параметри;

· параметри користувача `ешування`ю A, зокрема особистий ключ підпису XA;

· повідомлення M, що має бути підписане.

Незалежновідсхеми,процесобчисленняпідписускладаєтьсязтакихокремихетапів(процедур):

1. розщеплення повідомлення на складові;

2. обчислення надлишковості, або обчислення геш-значення повідомлення (за вибором користувача);

3. обчислення в групі точок еліптичної кривої;

4. обчислення за модулем порядку групи базової точки G;

5. форматування підписаного повідомлення.

Вихідними даними процесу генерації підписує пара цілих чисел (r,s), що є цифровим підписом повідомлення М відповідного об'єкта, наприклад[1].



2.1.3 Процес перевіряння підпису

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

· дійсні доменні параметри;

· відкритий ключ перевірки ЕЦП YA користувача A;

· не відновлюване повідомлення M'clr (якщо воно є).

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

1) перевіряння розміру підпису;

2) відновлення попереднього підпису та вхідних даних;

3) відновлення повідомлення;

4) перевірка надлишковості, або обчислення геш-значення повідомлення (з правом вибору);

5) обчислення за модулем порядку групи базової точки G;

6) обчислення в групі точок еліптичної кривої;

7) перевірка підпису.

Якщо всі процедури пройшли успішно, перевірник приймає підпис, в іншому випадку підпис відхиляється[1].

2.1.4 Особливості ЕЦП з відновленням повідомлення

Для реалізації кожного з механізмів цифрового підпису, визначених у стандарті, повинні бути обрані такі доменні параметри конкретної схеми цифрового підпису:

· скінчене поле Галуа F(q) ;

· еліптична крива Е над полем F(q), яка має унікальну циклічну підгрупу простого порядку п;

· точка G на еліптичній кривій Е простого порядку n.

· Користувачі повинні обрати одну з таких надлишковостей:

· природна надлишковість;

· додана надлишковість;

· обидва типи надлишковості.

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

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

Повна надлишковість, яка складається з природної надлишковості і доданої надлишковості, має бути більше деякого мінімального значення, що визначено застосуванням у відповідному додатку.

Якщо використовується додана надлишковість, то типи надлишковості мають бути віднесені до таких фіксованих значень:

· коротка надлишковість;

· довга надлишковість.

Коротка надлишковість має використовуватись у випадках, коли з підпису можна відновити все повідомлення.

Довга надлишковість має використовуватись у випадках, коли з підпису можна відновити лише частину повідомлення.

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

Типовими значеннями l1, є 64 або 80. Типові значення len_2 змінюються у діапазоні від 136 до 168. Також допускається встановлювати l1 = l2[1].



2.1.5 Перелік функцій і процедур

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

Підпис виконується через виконання таких процедур (етапів):

1) генерування (обчислення) доменних параметрів;

2) генерування (обчислення) асиметричної ключової пари ЦП;

3) формування ключа сеансу та попереднього підпису;

4) обчислення першої частини підпису;

5) обчислення другої частини підпису;

6) відновлення попереднього підпису;

7) відновлення вхідних даних[1].

2.1.6 Генерування (обчислення) асиметричної ключової пари ЦП

Для обчислення асиметричної ключової пари ЦП може застосовуватись один із двох наступних методів.

Метод генерації ключа І

Для заданого дійсного набору доменних параметрів еліптичної кривої асиметрична пара, тобто особистий ключ підпису XA та відповідний йому відкритий ключ YA , повинні генеруватись таким чином.

1. Обрати (згенерувати) з множини [2, n - 2] випадкове або псевдовипадкове ціле число XA, тобто особистий ключ. Ключ XA має бути захищеним від несанкціонованого розкриття і бути непередбачуваним.

2. Обчислити відкритий ключ як точку еліптичної кривої YA = XA G .

3. Асиметричною ключовою парою є пара (YA, XA) .

Надалі для уніфікації позначення та однакового представлення в цьому розділі приймемо позначення Р := G і Q := YA .

Метод генерації ключа II

Для другого методу та заданого дійсного набору доменних параметрів еліптичної кривої асиметрична ключова пара, тобто особистий ключ підпису YA та відповідний йому відкритий ключ Ya , повинні генеруватися таким чином.

1. Обрати (згенерувати) з множини [2, n - 2] випадкове або псевдовипадкове ціле число е та обчислити ціле число XA в інтервалі [2, n - 2] - таке, що XA е = 1 mod n .

2. Обидва цілі числа XA і е мають бути захищеними від несанкціонованого розкриття та бути непередбачуваними.

3. Обчислити точку еліптичної кривої YA = XA G .

4. Ключовою парою є (YA, XA) , де, як і раніше, YA - відкритий ключ перевірки, а XA - особистий ключ ЦП.

Перед використанням відкритого ключа перевірки перевірник повинен мати гарантію його дійсності та володіння[1].

2.1.7 Генерування (обчислення) ключа сеансу та попереднього ЦП

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

Ключем сеансу є ціле число k - таке, що 1 < k < n - 1. Реалізація схеми підпису має забезпечувати виконання таких двох вимог:

1. використані ключі сеансу к не повинні ніколи розкриватися, й одразу після використання кожен ключ повинен бути знищеним;

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

Попередній підпис у всіх ЦП з відновленням повідомлення обчислюється як функція ключа сеансу. При цьому необхідно мати на увазі, що розкриття ключа сеансу k (після його використання) може призвести до компрометації особистого ключа підпису XA. Але оскільки кожен із ключів сеансу, що вже використаний, більше не використовується ні підписувачем, ні перевірником, то він може (повинен) бути знищеним відразу після обчислення підпису[1].

2.1.8 Обчислення першої і другої частин підпису

Перша частина підпису r у всіх алгоритмах ЦП обчислюється як функція попереднього підпису ? і вхідних даних D, які є цілим числом, що залежить від повідомлення, причому 0 ? D < n. Вона є цілим числом r - таким, що 0 < r < n, де n - є порядок базової точки.

Друга частина підпису s у всіх алгоритмах обчислюється із застосуванням особистого ключа підпису XA , першої частини підпису r і ключа сеансу k. Вона є цілим числом s - таким, що 0 ? s < n, де n є порядок базової точки[1].

2.1.9 Відновлення попереднього підпису та вхідних даних

Відновлення попереднього підпису ? здійснюється з використанням відкритого ключа `ешування`ю, наприклад YA, та самого підпису (r, s) .

Відновлення вхідних даних d виконується з використанням заданої першої частини г підпису та відновленого попереднього підпису ?'[1].

2.2 Обчислення цифрового підпису

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

1. Формування ключа сеансу та обчислення попереднього підпису (перед- підпису);

2. Розщеплювання повідомленням на відновлювану частину М та `ешування`ювана частину повідомлення Мrec ;

3. Формування вхідних даних d;

4. Обчислення цифрового підпису (r, s);

5. Форматування підписаного повідомлення.

На рис. 2.1 наведено алгоритм обчислення підпису[1].

Рисунок 2.1 - Алгоритм обчислення підпису.

2.2.1 Формування ключа сеансу та попереднього підпису

Попередній підпис Р є проміжним елементом даних, що виробляється до початку процесу обчислення підпису в будь-якому захищеному від його компрометації механізмі цифрового підпису. При формуванні `ешування`юва спершу у відповідності з вимогами, що викладені вище, формується особистий ключ сеансу k. Термін «особистий» застосовується у тому сенсі, що відносно нього повинна бути забезпечена конфіденційність. Тому значення ключа сеансу k має бути доступним тільки процесу генерації цифрового підпису. Попередній підпис Р є відкритим елементом даних, а по суті відкритим ключем сеансу, тоді як значення ключа сеансу k має бути доступне тільки процесу обчислення підпису й бути конфіденційним. Необхідно також відзначити, що особисті ключі сеансу к можуть формуватися, а відповідні попередні підписи Р можуть обчислюватися автономно та зберігатися безпечним способом для використання при виконанні наступних цифрових підписів[1].

2.2.2 Розщеплення повідомлення

Повідомлення М розщеплюється на відновлювану частину Мrес та `ешування`ювана частину повідомлення Мclr, при цьому відповідно lrес і lclr визначені як довжини відновлюваної частини Мrес і невідновлюваної частини Мclr. При цьому додана надлишковість повідомлення М може бути розщеплена таким чином.

· Якщо довжина lM (у бітах) повідомлення M задовольняє умові

lM ? ln - l1 - 1 (2.1)

то з підпису можна відновити все повідомлення М. У цьому випадку правильними є рівняння: Мrес = М та lrес = lм. Окрім того, lclr = 0 та lh = l1.

· Якщо довжина lм (у бітах) повідомлення М задовольняє умові

lM ? ln - l1 - 1. (2.2)

то lrес визначається як ціле число, таке що Lrec ? ln - l2 - 1. Крайні ліві біти М складають відновлювану частину повідомлення Мrес. А крайні праві lм - lrес біти складають `ешування`ювана частину Мclr повідомлення М, і правильними є рівняння lrec = lM - lrec та lh = l2 [1].

2.2.3 Формування вхідних даних та обчислення ЦП

Вхідними даними функції формування даних є:

§ lrес, lclr та попередній підпис П;

§ `ешування`ювана частина повідомлення Мclr (необов'язково) і геш-токен повідомлення, що відновлюється;

§ Мrec з доданою надлишковістю, або повідомлення, що відновлюється, Мrec з природною надлишковістю.

Геш-токен є або самим геш-значенням, або геш-значенням, до якого праворуч приєднано ідентифікатор геш-функції, якщо геш-значення обчислюється способом `ешування повідомлення. Вибір щодо включення до геш-токену ідентифікатора геш-функції має обумовлюватися доменними параметрами. Виходом функції введення даних є значення D, яке після перетворення на ціле число знаходиться в діапазоні 0 < D < n[1].

2.2.4 Порядок обчислення цифрового підпису

Цифрові підписи, що формуються, мають дві частини -- r та s . Перша частина r обчислюється як функція вхідних даних D і попереднього підпису П. Друга частина s обчислюється як функція від першої частини підпису r, ключа сеансу k та особистого ключа підпису XA[1].

2.3 Перевіряння цифрового підпису

Наведемо алгоритм (процес) перевіряння підпису. Він складається з таких кроків:

1. відкриття повідомлення з цифровим підписом;

2. перевіряння розміру компонент r та s цифрового підпису;

3. відновлення попереднього підпису та або вхідних даних; Ц відновлення вхідних даних або повідомлення;

4. повторне обчислення геш-токену (необов'язкове);

5. зіставлення підпису та прийняття рішення.

Зіставлення підпису складається із:

1) порівняння відновлених і повторно обчислених (обрізаних) геш-токенів;

2) перевіряння надлишковості[1].

2.3.1 Функції перетворення та генерації маски

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

ВS2ІР - примітив перетворення бітових рядків на цілі числа.

ВS2OSР - примітив перетворення бітових рядків на октетові (байтові) рядки.

ЕС2OSР - примітив перетворення точки еліптичної кривої на октетові рядки.

FE2IP - примітив перетворення елементів кінцевого поля на цілі

числа.

FЕ2OSР - примітив перетворення елементів кінцевого поля на октетові рядки.

І2ВSР - примітив перетворення цілих чисел на бітові рядки.

І2OSР - примітив перетворення цілих чисел на октетові рядки.

МGF1, MGF2 - функції генерації маски.

0S2ВSР - примітив перетворення октетових рядків на бітові рядки.

OS2ЕСР - примітив перетворення октетових рядків на точку еліптичної кривої.

OS2FЕР - примітив перетворення октетових рядків на елементи кінцевого поля.

OS2ІР - примітив перетворення октетових рядків на цілі числа[1].



3. ЦИФРОВИЙ ПІДПИС НІБЕРГА-РЮПЕЛЯ В ГРУПІ ТОЧОК ЕЛІПТИЧНИХ КРИВИХ (ELLIPTIC CURVE NYRBERG-RUEPPEL (ECNR) MESSAGE RECOVERY SIGNATURE)

3.1 Ключі цифрового підпису ECNR

Асиметрична ключова пара цифрового підпису ECNR повинна формуватись таким чином:

1) спочатку генерується або вибирається особистий (довгостроковий) ключ цифрового підпису хА об'єкта А причому хА - випадкове ціле число з інтервалу [2,n-2];

2) обчислюється відкритий ключ перевірки цифрового підпису YA об'єкта згідно 2.1.6 (спосіб І або спосіб II) [1].

3.2 Обчислення цифрового підпису

Вхідними даними до процесу обчислення підпису є такі

- дійсні доменні параметри -- a, b, n,G, и,Р ( f(x)),h;

- особистий ключ цифрового підпису хА;

- вхідні дані d як елемент простого поля Галya F(n).

Дані d формуються з повідомленням. Виходом процесу обчислення підпису є пара чисел (r,s) є F(n)ЧF(n), що є цифровим підписом А для даних.

Підпис даних d об'єкт А виконує в такій послідовності.

1. Генерація ключа сеансу й попереднього підпису:

а) обрати (генерувати) випадкове ціле k з інтервалу [2, n-2];

б) обчислити точку еліптичної кривої (х1,у1) = kP, де Р - базова точка порядку n.

2. Обчислення за модулем n порядку групи G:

а) визначити попередній підпис Р=р(kP)(mod n) = x1(mod n);

б) обчислити першу складову ЦП r=d+I(mod n);

в) обчислити другу складову ЦП s=k-xar(mod n);

г) знищити особистий ключ сеансу k.

Якщо s=0 або r=0, то процес обчислення підпису має бути повторене з новим випадковим значенням k.

3 Форматування підписаного повідомлення:

Пара (r,s) є F(n)ЧF(n) є підписом А для даних d.

Перевіряння цифрового підпису

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

Вхідними даними до процесу перевіряння підпису є такі:

- доменні параметри еліптичної кривої - a, b, n,G, и,Р ( f(x)),h;

- відкритий ключ перевіряння цифрового підпису Ya об'єкта А;

- підпис для даних d, представлений двома цілими числами r` і s`;

- не відновлюване повідомлення М`crl (за наявності).

Для перевірки підпису об'єкта А для d об'єкт В повинен виконати такі кроки.

1. Зробити перевірку розміру підпису, тобто перевірити, що 0<r`<n та 0<s`<n; якщо це не так, то відхилити підпис.

2. Встановлення попереднього (старого) підпису та вхідних даних ( у групі точок еліптичної кривої):

1) Обчислити точку на ЕС R1`=s`P+r`Q, де Р - базова точка ЕС, а Q - відкритий ключ.

2) Обчислити попередній підпис I=р(R`1)(mod n)=x1(mod n).

1. Відновлення вхідних даних або повідомлення.

2. Обчислення d`=r`-I`(mod n).

3. Зіставлення підпису.

Зіставлення надлишковості має здійснюватись за обчисленої надлишковості та відомої перевірнику. Якщо d`=d, то вважається, що повідомлення цілісне й справжнє, інакше робиться відхилення прийнятого повідомлення (підпису).

Необхідно визначити, що в процесі обчислення та перевіряння підпису необхідно застосовувати відповідні функції перетворення та маски. Тоді обчислення перед підпису необхідно виконати із забезпеченням таких перетворень:

k=rand([1,n-1]), (3.1)

R=kP, (3.2)

Р=FC2OSPE(R,compressed). (3.3)

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

д=OS2lP(d) д є [0,n-1], (3.4)

р=OS2lP(Р) mod n, (3.5)

r=(д+р) mod n, (3.6)

s=(k-xAr) mod n. (3.7)

r=OSP(r,L(n). (3.8)

Перевіряння цифрового підпису має бути виконано з дотриманням таких вимог:

r=OS2lP®, (3.9)

R`=s`P+r`Q, (3.10)

Р=EC2OSP(R`,compressed), (3.11)

д`=(r`-р`) mod n, (3.12)

d`=l2OSP(д`,Ldat). (3.13)



4.АНАЛІЗ ЕЦП З ВІДНОВЛЕННЯМ ПОВІДОМЛЕННЯ

4.1 Стійкість ЕЦП з відновленням повідомлення до колізій

У таблиці 4.1 наведені загальні показники ЕЦП з відновленням повідомлень

цифровий підпис повідомлення колізія

Таблиця 4.1. Показники ЕЦП

L(d)	L(H*(Mrec))	L(H*(Mclr))	(r,s)
L(n)-1	d:L(d)-L(Mrec)	{0,1}8L(n)x[1,n-1]

Модель компоненти захисту від підробки

Для захисту від підробки використовується код виробу, що складається з коду групи товарів і серійного номеру виробу.

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

Код виробу вкладається в частину відновлюваного підпису.

Опціонально може бути включена додаткова відкрита інформація (можливо, як частина параметрів домену виробника), що буде розглядатися як відкрита частина повідомлення[1].

4.2 Стійкість до колізій відновлюваної частини повідомлення

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

Імовірність колізії для підписів з відновленням повідомлення серед w продуктів, з точки зору всього підпису, можна оцінити

(4.1)

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

Максимальна довжина відновлюваної частини має величину L(n) -- 1. Для скінченного поля нині дозволяється використовувати довжину п є {2048,3072}. Для групи точок еліптичних кривих n є 160,163, .„431,... Оскільки рішення щодо справжності підпису приймається після перевірки надлишковості, стійкість усієї схеми залежить від її розміру. Тому максимальна кількість корисної інформації, що може бути відновлена з підпису, зменшується на необхідний розмір надлишковості.

Для ЕЦП імовірність колізії Р кодів, вироблених з ключем у п бітів у партії з со виробів, згідно парадоксу про день народження, зі збільшенням розміру корисного повідомлення SL(Mrec) може бути визначена як:

(4.2)

Формула (4.2) також дозволяє обчислити ймовірність колізії у відкритій частині тексту.

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

(4.3)

(4.4)



Тепер підрахуємо дійсну кількість товару, яку можна маркувати із зазначеною схемою. Для того введемо додаткову умову

(4.5)

Із уточненнями рівняння буде мати вигляд:

(4.9)

Можна побачити, що довжина Мrec = 37 забезпечить найбільш повне використання простору значень нашої моделі, коли ймовірність колізії Р = 2-53, та n = 163. Якщо взяти 7 бітів як код групи товарів (приблизно 100 груп, із надлишковістю), то загальна кількість товарів, що може бути випущена у межах групи, дорівнюватиме 230= 1073741824.

Стійкість до колізій невідновлюваної частини повідомлення

ЕЦП із відновленням повідомлення гарантує цілісність і неспростовність не тільки відновлюваної частини повідомлення, але й усього повідомлення взагалі. Cтверджується, що для підпису ECNR імовірність до колізії відкритої частини повідомлення така ж сама, як і для закритої (4.2).

4.3 Аналіз складності реалізації ЕЦП з відновленням повідомлення

У таблиці 4.2 наведено значення числа операцій, що необхідно виконати для алгоритмів обчислення ЕЦП.



Таблиця 4.2. Число операцій, що виконуються при обчисленні підпису

	ECNR
Складання за модулем п	2
Множення за модулем п	1
Інверсія за модулем п	0
Скалярне множення в групі точок ЕК, або підведення до ступеня в скінченному полі	1
Сума за модулем 2	0
Гешування	1
МGF/КDF	0
БСШ	0

У таблиці 4.3 наведено значення числа операцій, що необхідно виконати для алгоритмів при перевірці ЕЦП.

Таблиця 4.3. Число операцій, що виконуються при перевірці підпису

	ECNR
Складання за модулем п	1
Множення за модулем п	0
Інверсія за модулем п	0
Складання на еліптичній кривій або множення у скінченному полі	1
Скалярне множення в групі точок ЕК, або підведення до ступеня в скінченному полі	2
Сума за модулем 2	0
Гешування	1
МGF/КDF	0
БСШ	0

У таблиці 4.4 наведено значення числа операцій, що необхідно виконати для алгоритмів додавання та подвоєння в різних базисах.

Таблиця 4.4. Складність додавання та подвоєння в різних базисах

Координати	Додавання точок	Подвоєння точок
Афінні	t(A+A)=I+2M+S	t(2A)=I+2M+S
Проективні	t(P+P)=l2M+2S	t(2P)=7M+5S
Якобіанові	t(y+y)=l2M+4S	t(2I)=4M+6S
Чудновського	t(yc +yc)=l1M+3S	t(Ic)=5M+6S
Модифіковані якобіанові	t(ym +ym)=13M+6S	t(Im)=4M+4S

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

4.4 Число гешувань MGF

Стандарт ISО/ІЕС 9796-3 визначає алгоритми формування гамми MGF1 та MGF2, як:

MGF1(x,l)=[Hash(x||I20SP(0,4))||

||Hash(x||I20SP(1,4))||…||Hash(x||I20SP(k-1,4))]8l; (4.11)

MGF2((x,l)=[Hash(x||I20SP(1,4))||

||Hash(x||I20SP(2,4))||…||Hash(x||I20SP(k,4))]8l, (4.12)

де k=l/LHash

Таким чином, для кожного виконання функцій МGF потрібне обчислення k функцій гешування.

У таблиці 4.5 наведено експериментально отримані значення швидкості підпису ECNR.

Таблиця 4.5. Швидкість підпису ECNR

	Підпис (100/с)	Перевірка (100/с)
ECNR	10,61	21,54

У таблиці 4.6 наведені дані щодо обсягу пам'яті, що необхідна для реалізації ECNR.



Таблиця 4.6. Обсяг пам'яті, що необхідний для реалізації ECNR

	Підпис/100	Перевірка/100
ECNR	1274718104	2610783160



5. ПРОГРАМНА РЕАЛІЗАЦІЯ

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

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

Для функціювання програми спеціальне програмне забезпечення не потрібне. Програма написана на мові програмування С++.

Основним завданням програми є знаходження ймовірності виникнення колізії при заданих розмірові поля, довжені повідомлення (в бітах) та кількості виробів.

5.2 Опис логічної структури

Програма можна використовувати для знаходження ймовірності колізії. При запуску програми нас просять ввести основні параметри (розмір поля, довжину повідомлення (в бітах) та кількість виробів

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

1) Функція розрахунку ймовірності виникнення колізії:

long double Kolizii (int w, int n, int M)

Функція виконує математичні розрахунки, що наведені в формулі (4.2).

Повний код функції наведений в дод. А.

2) Основна функція

Void main()

Видається запит на введення основних параметрів, що потрібні для розрахунків та виведення результатів.



5.3 Вхідні й вихідні дані

1) long double Kolizii (int w, int n, int M)

Вхідні дані:

int w - кількість виробів;

int n - розмір поля;

int M - довжина повідомлення.

Вихідні дані:

long double P - ймовірність винекнення колізії.

Після відпрацювання всіх алгоритмів програма виводе наступне вікно (рис.5.1).

Рисунок 5.1 - Результат роботи програми



ВИСНОВКИ

В даній роботі були досліджені електронні цифрові підписи з відновленням повідомлення які описуються стандартом ISO/IEC 15946-4 та ІSО/ІЕС 9796-3 (був прийнятий в 2006р. на заміну попереднього). Проаналізована їхні властивості, швидкодія, складність реалізації, стійкість до колізій та ін.. Особлива увага була приділена ЕЦП Ніберга-Рюпеля в групі точок еліптичної кривої. Досліджений алгоритм підпису ECNR та його перевірки.

Електронні цифрові підписи з відновленням повідомлення знайшли своє використання в поштових марках розміром від 20 до 50 байт та для підписування дуже коротких повідомлень або повідомлень із надлишком у 20 байт.