Програма, що генерує електронний цифровий підпис ESIGN

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

РЕФЕРАТ

Пояснювальна записка до курсової роботи: 34c., 1 рис., 5 розд., 1 дод., 6 джерел.

Об'єкт дослідження - електронний цифровий підпис ESIGN.

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

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

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

Розроблена програма, яка генерує електронний цифровий підпис ESIGN.

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

ЕЦП, ПроСТЕ ЧИСЛО, ГЕШ ФУНКЦІЯ, ОСТАЧА ВІД ДІЛЕННЯ ПО МОДУЛЮ, ТЕСТ ЛЕМАНА.

ЗМІСТ

Вступ

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

2. Теоретичні відомості про електронний цифровий підпис ESIGN

2.1 Загальні відомості про електронний цифровий підпис

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

2.2.1 Алгоритм генерації ESIGN

2.2.2 Перевірка правильності ESIGN

2.2.3 Параметр безпеки k електронного цифрового підпису ESIGN

3. Теоретичні відомості з методів і алгоритмів використаних для генерації підпису

3.1 Геш функція

3.2 Просте число

3.3 Тест простоти

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

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

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

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

Висновки

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

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

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

ВСТУП

Криптографія (від грецького 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. ПОСТАНОВКА ЗАВДАННЯ І СФЕРА ЗАСТОСУВАННЯ ЕЛЕКТРОННОГО ЦИФРОВОГО ПІДПИСУ

Завдання: дослідити сучасні методи генерації електронного цифрового підпису та їх використання. Розробити власну програму, яка буде генерувати й перевіряти на правильність електронний цифровий підпис ESIGN й продемонструвати його роботу на невеликих числах.

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

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

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

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

2.1 Загальні відомості про електронний цифровий підпис

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

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

Послуги ЕЦП надаються Центрами Сертифікації Ключів:

Українські акредитовані центри сертифікації ключів

"Український сертифікаційний центр"

ЗАТ "Інфраструктура Відкритих Ключів"

АЦСК ДП «УСС»

ТОВ "СІГНУА"

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

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

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

2.2.1 Алгоритм генерації ESIGN

ESIGN - це схема цифрового підпису, розробленого NTT Japan. Стверджувалось, що він не менш безпечний ніж RSA чи DSA, й набагато швидший при тих же розмірах ключа й підпису. Закритим ключем служить пара великих цілих чисел p й q. Відкритим ключем є n, для якого

n=p*p*q (2.1)

H - це геш-функція, що приміняється до повідомлення m, при чому H(m) знаходиться в межах від 0 до n-1. Використовується також параметр безпеки k.

1) Аліса бере довільне число х, яке менше pq.

2) Аліса вираховує:

w, найменше ціле, яке більше або рівне

(H(m)-x^kmod n)/pq (2.2)

s=x+((w/kx^k-1mod p)pq (2.3)

3) Аліса відсилає s Бобу.

2.2.2 Перевірка правильності ESIGN

Для перевірки підпису.

1) Боб вираховує s^k mod n.

2) Він вичисляє а, найменше ціле, яке більше або рівне подвоєному числу бітів n, розділеному на 3.

3) Якщо H(m) менше або рівне s^kmod n, і якщо s^kmod n меньше H(m)+2^a, то підпис вважається правильним[1].

2.2.2 Параметр безпеки k електронного цифрового підпису ESIGN

Коли цей алгоритм був вперше запропонований, k було вибрано рівним 2. Така схема була швидко зламана Ерні Брікеллом й Джоном ДеЛаурентісом, які розширили своє розкриття і на випадок k=3. Модифікована версія цього алгоритму була зламана Шаміром. Спроби розкрити ESIGN пізнішої модифікації з більшим параметром безпеки були безрезультатні.

На сьогоднішній день автори рекомендують використовувати наступні значення k: 8, 16, 32, 64, 128, 256, 512 й 1024. Вони також рекомендують, щоб p й q були не менше 192 бітів кожне, генеруючи n не менше, ніж 576 бітів завдовжки. Автори вважають, що з такими значеннями параметрів, безпека ESIGN набагато вища, ніж у RSA або Rabin. Й виконаний ними аналіз показує, що швидкість ESIGN набагато вища, ніж у RSA, ElGamal й DSA[1].

3. ТЕОРИТИЧНІ ВІДОМОСТІ З МЕТОДІВ І АЛГОРИТМІВ ВИКОРИСТАНИХ ДЛЯ ГЕНЕРАЦІЇ ПІДПИСУ

3.1 Геш функція

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

Криптографічна геш-функція повинна забезпечувати:

стійкість до колізій (два різні набори даних повинні мати різні результати перетворення);

необоротність (неможливість обчислити вхідні дані за результатом перетворення).

Геш-функції також використовуються в деяких структурах даних -- геш таблицях і декартових деревах. Вимоги до хеш-функції в цьому разі інші:

добра перемішуваність даних;

швидкий алгоритм обчислення.

Список алгоритмів:HAVAL, MD2, MD4, MD5, N-Hash, RIPEMD-160, SHA, Snefru, Tiger, Whirlpool[2].

3.2 Просте число

Просте число -- це натуральне число, яке має рівно два натуральних дільника (лише 1 і саме число). Решту чисел, окрім одиниці, називають складеними. Таким чином, всі натуральні числа понад одиницю розбивають на прості і складні. Теорія чисел вивчає властивості простих чисел. В теорії кілець простим числам відповідають неприводимі елементи.

Послідовність простих чисел починається так:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, … (Послідовність A000040 з Енциклопедії цілочисельних послідовностей)

Розклад натуральних чисел на добуток простих

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

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

Тест простоти

Решето Ератосфена, решето Сундарама та решето Аткіна дають прості способи складання початкового списку простих чисел до певного значення.

Однак, на практиці, замість отримання списку простих чисел найчастіше потрібно перевірити, чи є дане число простим. Алгоритми, які вирішують це завдання, називають тестами простоти. Існує безліч поліноміальних тестів простоти, але більшість з них є стохастичні (наприклад, тест Міллера - Рабина) і використовуються для потреб криптографії. Тільки в 2002 році було доведено, що завдання перевірки на простоту в загальному вигляді можна розв'язати за поліноміальний час, але запропонований детермінований алгоритм має досить велику складність, що ускладнює його застосування на практиці.

Для деяких класів чисел існують спеціалізовані ефективні тести простоти. Наприклад, для перевірки на простоту чисел Мерсена використовують тест Люка - Лемера, а для перевірки на простоту чисел Ферма -- тест Пепіно.

Скільки існує простих чисел?

Простих чисел нескінченно багато. Найдавніший відомий доказ цього факту було дано Евклідом в «Началах» (книга IX, твердження 20). Його доказ може бути коротко відтворено так:

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

Математики пропонували інші докази. Одне з них (наведене Ейлером) показує, що сума всіх чисел, зворотніх до простих, розходиться.

Відома теорема про розподіл простих чисел стверджує, що кількість простих чисел менших за n, яке позначають як р(n), росте як n / ln(n).

Найбільше відоме просте число

Здавна ведуться записи, в яких відзначають найбільші відомі на той час прості числа. Один з рекордів поставив свого часу Ейлер, знайшовши просте число 231 ? 1 = 2147483647.

Найбільшим відомим простим числом станом на червень 2009 року є 243112609 ? 1. Воно складається з 12 978 189 десяткових цифр і є простим числом Мерсена (M43112609). Його знайшли 23 серпня 2008 року на математичному факультеті університету UCLA в рамках проекту по розподіленому пошуку простих чисел Мерсена GIMPS. Попереднє за величиною відоме просте, також є простим числом Мерсенна M37156667, було знайдено 6 вересня 2007 року учасником проекту GIMPS Гансом-Міхаелем Елвеніхом (нім. Hans-Michael Elvenich).

Числа Мерсена вигідно відрізняються від решти наявністю ефективного тесту простоти: тесту Люка -- Лемера. Завдяки йому прості числа Мерсена давно утримують рекорд як найбільші відомі прості.

За знаходження простих чисел з понад 100 000 000 та 1 000 000 000 десяткових цифр EFF призначила грошові призи в 150 000 та 250 000 доларів США відповідно.

Деякі властивості

Якщо p -- просте, і p ділить ab, то p ділить a або b. Цю властивість довів Евкліда, і відома вона як лема Евкліда. Її використовують при доведенні основної теореми арифметики.

Кільце остач є полем тоді і тільки тоді, коли n -- просте.

Характеристика кожного поля -- нуль або просте число.

Якщо p -- просте, a -- натуральне, то ap ? a ділиться на p (мала теорема Ферма).

Якщо G -- скінченна група з pn елементів, то G містить елемент порядку p.

Якщо G -- скінченна група, і pn -- максимальний ступінь p, який ділить | G |, то G має підгрупу порядку pn, яку називають підгрупою Силова, більше того, кількість підгруп Силова дорівнює pk + 1 для деякого цілого k (теореми Силова).

Натуральне p > 1 є простим тоді і тільки тоді, коли (p ? 1)! + 1 ділиться на p (теорема Вільсона).

Якщо n > 1 -- натуральне, то існує просте p, Таке, що n < p < 2n (постулат Бертрана).

Будь-яка арифметична прогресія виду a,a + q,a + 2q,a + 3q,..., Де a,q > 1 -- цілі взаємно-прості числа, містить нескінченно багато простих чисел (Теорема Діріхле про прості числах в арифметичній прогресії).

Будь-яке просте число більше 3, можна представити у вигляді 6k + 1, або у вигляді 6k ? 1, де k -- деяке натуральне число.

Якщо p > 3 -- просте, то p2 ? 1 кратне 24.

Множина додатніх значень многочлена

(k + 2)(1 ? [wz + h + j ? q]² ? [(gk + 2g + k + 1)(h + j) + h ? z]² ? [2n + p + q + z ? e]² ? [16(k + 1)³(k + 2)(n + 1)² + 1 ? f2]² ? [e³(e + 2)(a + 1)² + 1 ? o2]² ? [(a² ? 1)^y2 + 1 ? x2]2 ? [16r²y⁴(a2 ? 1) + 1 ? u²]² ? [((a + u²(u² ? a))² ? 1)(n + 4dy)² + 1 ? (x + cu)²]² ? [n + l + v ? y]² ? [(a2 ? 1)l² + 1 ? m²]² ? [ai + k + 1 ? l ? i]² ? [p + l(a ? n ? 1) + b(2an + 2a ? n² ? 2n ? 2) ? m]² ? [q + y(a ? p ? 1) + s(2ap + 2a ? p² ? 2p ? 2) ? x]² ? [z + pl(a ? p) + t(2ap ? p² ? 1) ? pm]²)

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

Відкриті питання

Досі існує багато відкритих запитань відносно простих чисел, найвідоміші з яких були перераховані Едмундом Ландау на П'ятому Міжнародному математичному конгресі

Проблема Гольдбаха (перша проблема Ландау): довести або спростувати, що кожне парне число, більше двох, може бути представлено у вигляді суми двох простих чисел, а кожне непарне число, більше 5, може бути представлено у вигляді суми трьох простих чисел.

Друга проблема Ландау : чи нескінченна множина «простих близнюків» -- простих чисел, різниця між якими дорівнює 2?

Гіпотеза Лежандра (третя проблема Ландау) чи вірно, що між n2 і (n + 1)2 завжди знайдеться просте число?

Четверта проблема Ландау:чи нескінченна множина простих чисел виду n2+1?

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

Застосування

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

Варіації і узагальнення

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

В теорії вузлів існує поняття простого вузла, який, у певному сенсі, не може бути розбитий на більш прості вузли[2].

3.3 Тест простоти

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

Найпростіший тест простоти полягає в такому: коли задане число n, перевірити чи якесь ціле m від 2 до n-1 ділить n. Якщо n ділиться на певне m, то n складене, в іншому разі воно просте. Замість перевірки всіх m до n-1, досить лише перевірити m до : якщо n складене, то його можна розкласти на два множники, принаймні один з яких не перевищує. Можна також покращити ефективність, пропускаючи всі парні m, за винятком 2, бо коли якесь парне число ділить n, то 2 також ділить. Можна далі вдосконалити зауважуючи, що всі прості числа, за винятком 2 та 3, мають вигляд 6k ± 1. Дійсно, всі цілі можна подати як (6k + i) для деякого k та для i = -1, 0, 1, 2, 3, або 4; 2 ділить (6k + 0), (6k + 2), (6k + 4); а 3 ділить (6k + 3). Спочатку перевіряємо чи n ділиться на 2 або 3, тоді пробігаємо всі числа вигляду 6k ± 1. Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд ck + i lkz i<c де i належить до чисел, взаємно простих з c. Фактично, коли кількість значень, які ck + i може набувати в певному діапазоні, зменшується, а, отже, час тестування n зменшується. Для цього методу, слід ділити на всі прості менші ніж c. Спостереження, аналогічні до попереднього, можна застосувати рекурсивно, отримуючи решето Ератосфена. Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням n на простоту з використанням серйозного методу, спочатку перевіряємо чи n не ділиться на якесь просте із цього списку.

Ймовірнісні тести

Найбільш популярними тестами простоти є ймовірнісні тести. Ці тести використовують, крім тестованого числа n, деякі інші числа a, які випадково вибираються з певного набору; звичні рандомізовані тести простоти ніколи не оголошують прості числа складеними, але можливе для складених чисел оголошення їх простими. Імовірність помилки можна зменшити, повторюючи тест з ріними незалежно вибраними a; для двох найчастіше вживаних тестів, для будь-якого складеного n принаймні половина aвизначає складеність n, тому k повторень зменшують імовірність помилки до щонайбільше 2?k. Останню величину можна зробити як завгодно малою, збільшуючи k.

Базова структура рандомізованих тестів простоти є такою:

Випадково вибрати число a.

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

Виконувати крок 1, поки не буде досягнуто потрібної певності.

Після низки повторень, якщо не отримано, що n є складене число, то його можна оголосити імовірнісним простим.

Найпростішим ймовірнісним тестом простоти є тест простоти Ферма. Це лише евристичний тест; деякі складені числа (числа Кармайкла) будуть оголошені "ймовірнісними простими" незалежно від того, яке свідчення вибране. Проте, він деколи використовується з метою швидкої перевірки числа, наприклад, на фазі утворення ключа криптографічного алгоритму з відкритим ключем RSA.

Тест простоти Міллера-Рабіна та Тест простоти Соловея-Штрассена є вдосконаленими варіантами, які визначають всі складені числа (це означає: для кожного складеного числа n, принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел a є свідченнями складеності n). На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести простоти.

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

Швидкі детерміновані тести

Першим детермінованим тестом простоти значно швидшим, ніж наївні методи, був циклотомічний тест; для часу його виконання отримано оцінку O((log n)clog(log(log(n)))), де n тестоване на простоту число, а c константа, незалежна від n. Це повільніше, ніж поліноміальний час.

Для тесту простоти на основі еліптичних кривих можна отримати оцінку O((log n)⁶), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з з найчастіше вживаних на практиці детермінованих тестів.

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

Якщо вважається вірною узагальнена гіпотеза Рімана, то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log n)⁴). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.

У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, AKS тест простоти, який як доведено виконується за O((log n)¹²). Крім того, якщо вірна гіпотеза Харді-Літлвуда, яку вважають справедливою, то він виконується за O((log n)⁶). Отже, маємо перший детермінований тест простоти з доведеним поліноміальним часом виконання. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.

Складність

У теорії складності обчислень, формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до coNP: її доповнення COMPOSITES належить до NP, бо можна показати складеність недетерміновано вгадуючи дільник.

У 1975 Вауган Пратт показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до NP.

Подальше відкриття алгоритмів Соловея-Штрассена та Міллера-Рабіна показало належність PRIMES до coRP. У 1992 алгоритм Адлемана-Хуанга звузив складність до ZPP = RP, що є заміщенням результату Пратта.

Циклотомічний тест Адлемана, Померанце та Рамлі 1983р. показав належність PRIMES до QP (квазі-поліноміальний час), для якого невідоме порівняння із згаданими раніше класами.

Існування AKS тесту простоти, який остаточно розв'язав цю давню проблему, означає, що PRIMES належить до P.

Теоретико-числові методи

Існують певні теоретико-числові методи для тестування чи є число простим, зокрема тест Лукаса-Лемера та тест Профа. Як правило, для цих тестів потрібний розклад n + 1, n ? 1, або аналогічних чисел, а це означає, що вони не підходять для тестування простоти чисел загального вигляду, проте часто є досить потужним засобом, коли тестуємо число n спеціального вигляду.

Тест Лукаса-Лемера спирається на факт, що мультиплікативний порядок числа a за модулем n дорівнює n ? 1 для простого n, якщо a примітивний корінь за модулем n. Коли можемо показати, що a примітивний корінь для n, то можемо довести простоту n[2].

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

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

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

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

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

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

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

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

1) Функція считування масиву даних з файлу:

bool LoadFile(char * filename,unsigned char * M,int & n)

Дана функція виконує зчитування масиву даних (символів) з файлу. Її ми використовуємо для того, щоб зчитати повідомлення, яке будемо зашифровувати. Масив повинен бути записаний в текстовий файл з розширенням “.txt”.

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

2) Функція збереження даних в файл:

void SaveEncFile(char * filename, unsigned int S)

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

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

3) Тест Лемана:

int LemanTest(unsigned int P,int k)

Дана функція перевіряє просте число чи ні. Тест Лемана перевіряє одне з особливостей простого числа:

для любого а<р, де р - число, яке ми перевіряємо; повинна виконуватися умова:

а^(р-1)/2= +1(mod p) (4.1)

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

(1/2)^k, (4.2)

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

4)Функція піднесення в степінь по модулю:

void EncrDecr (unsigned int Src, unsigned int Key,unsigned int N,unsigned int &Dst)

Дана функція призначена для піднесення чисел в високу степінь і знаходження значення отриманого результату за заданим модулем. Проведення таких розрахунків на папері зайняло б дуже багато часу. В функції ми використовуємо допоміжну змінну y типу unsigned __int64 для запису результату проміжних розрахунків. Змінна типу unsigned __int64 тому, що результат множення двох 32-х бітних чисел буде 64-х бітним числом В функції ми беремо двоїчний код числа, що показує в яку степінь ми підносимо і в циклі перевіряємо кожен його біт. Якщо в і-й біт числа записаний 0 то ми виконуємо:

y = (y*y)%N, (4.3)

де N - модуль по якому нам потрібно отримати результат;

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

Роботу функції можна записати як:

Dst=Src^Keymod n (4.4)

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

5)Функція генерації криптопараметрів:

void Poiskpqn(unsigned int K, unsigned int &p, unsigned int &q, unsigned int &n)

Дана функція випадковим образом генерую два закритих ключі p й q, які є простими числами. Для перевірки їх простоти використовуємо тест Лемана. Потім на їх основі знаходить n.

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

6)Функція знаходження w:

void Poiskw(unsigned char *M, unsigned int &H, unsigned int &x, unsigned int k, unsigned int n, unsigned int p, unsigned int q, unsigned int &w)

Функція знаходить w, що використовується для подальших розрахунків.

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

7)Функція знаходженя електронного цифрового підпису:

void Poisks(unsigned int x, unsigned int w, unsigned int k, unsigned int p, unsigned int q, unsigned int &S)

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

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

8) Функція перевірки електронного цифрового підпису

void Proverka(unsigned int S, unsigned int k, unsigned int n, unsigned int H)

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

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

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

Кожна функція програми бере одні дані і генерує інші, або перевіряє їх на виконання деяких умов.

1) bool LoadFile(char * filename,unsigned char * M,int & n)

Вхідні дані:

сhar * filename - ім'я файлу, з якого считується інформація (записується повністю адреса, де знаходиться файл на комп'ютері, або саме ім'я, якщо файл знаходиться в папці з програмою);

іnt & n - довжина масиву, що буде зчитуватися з файлу.

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

unsigned char * M - змінна, в яку буде передаватися масив.

2) void SaveEncFile(char * filename, unsigned int S)

Вхідні дані:

unsigned int S - змінна, значення якої буде записуватися в файл.

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

char * filename - ім'я файлу, в який зберігається інформація (записується повність адреса де знаходиться файл на комп'ютері, або саме ім'я, якщо файл находиться в папці з програмою.

3) int LemanTest(unsigned int P,int k)

Вхідні дані:

unsigned int P - число яке ми перевіряємо на простоту;

int k - параметр k.

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

функція повертає 0 або 1. Якщо число Р просте вертає 0, якщо ні - 1.

4) void EncrDecr (unsigned int Src, unsigned int Key,unsigned int N,unsigned int &Dst)

Вхідні дані:

unsigned int Src - число яке ми підносимо до степіня;

unsigned int Key - степінь в яку ми підносимо число;

unsigned int N - модуль по якому ми беремо результат.

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

unsigned int &Dst - змінна в яку ми записуємо результат обчислень.

5) void Poiskpqn(unsigned int K, unsigned int &p, unsigned int &q, unsigned int &n)

Вхідні дані:

unsigned int K - число k для тесту Лемана.

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

unsigned int &p - закритий ключ p;

unsigned int &q - закритий ключ q;

unsigned int &n - відкритий ключ n.

6) void Poiskw(unsigned char *M, unsigned int &H, unsigned int &x, unsigned int К, unsigned int n, unsigned int p, unsigned int q, unsigned int &w)

Вхідні дані:

unsigned char *M - повідомлення з якого мо генеруємо електронний цифровий підпис;

unsigned int k - число k для тесту Лемана;

unsigned int p - закритий ключ p;

unsigned int q - закритий ключ q;

unsigned int n - відкритий ключ n.

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

unsigned int &x - допоміжна змінна;

unsigned int &H - геш функція від повідомлення;

unsigned int &w - число, яке потрібне для подальших розрахунків.

7) void Poisks(unsigned int x, unsigned int w, unsigned int k, unsigned int p, unsigned int q, unsigned int &S)

Вхідні дані:

unsigned int x - допоміжна змінна;

unsigned int w - число, яке потрібне для подальших розрахунків;

unsigned int k - число k для тесту Лемана;

unsigned int p - закритий ключ p;

unsigned int q - закритий ключ q.

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

unsigned int &S - згенерований електронний цифровий підпис.

8) void Proverka(unsigned int S, unsigned int k, unsigned int n, unsigned int H)

Вхідні дані:

unsigned int S - згенерований електронний цифровий підпис;

unsigned int k - число k для тесту Лемана;

unsigned int n - відкритий ключ n;

unsigned int &H - геш функція від повідомлення.



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

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

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

Програма бере повідомлення з текстового файлу “1.txt”. Завантажує дані в масив з якого буде генерувати електронний цифровий підпис ESIGN.

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

Результати розрахунки записуються в 4 різних файли:

"n.txt" - відкритий ключ;

"p.txt" та "q.txt" - закриті ключі;

"podpis.txt" - згенерований електронний цифровий підпис.

ВИСНОВКИ

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

ПЕРЕЛІК ПОСИЛАНЬ

1. Брюс Шнаєр Прикладна криптографія. - М.:"Тріумф", 2002. - 867 с..

2. Інтернет ресурс uk.wikipedia.org.

3. ГОСТ 19.701-90. ЕСПД. Схеми алгоритмів, програм, даних і систем. Умовні позначення і правила виконання.- М.: 1991.

ДОДАТОК А.

Текст програми

#include "stdafx.h"

#include <iostream>

#include <time.h>

#include <math.h>

#include <fstream>

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#include "D:\CRC32_v-8\CRC32.h"

using namespace std;

void EncrDecr (unsigned int Src, unsigned int Key,unsigned int N,unsigned int &Dst)

{

unsigned __int64 y;

unsigned int i;

for (i=0x80000000;(Key&i)==0;i=i>>1);

i=i>>1;

y=(unsigned __int64)Src;

for (;i!=0;i=i>>1)

{

y=(y*y)%N;

if((Key&i)!=0)

y=(y*Src)%N;

}

Dst=(unsigned int)y;

} int LemanTest(unsigned int P,int k)

unsigned int a,s,t,m;

m=P-1;

s=(P-1)/2;

bool b=false;

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

{a=rand()%(P-3)+3;

EncrDecr(a,s,P,t);

if(t==m)

b=true;

else if (t!=1)

return 1;

}

if(b) return 0;

return 1;

}

bool LoadFile(char * filename,unsigned char * M,int & n)

{

long begin,end;

ifstream myfile(filename);

if( !myfile) return false;

begin = myfile.tellg();

myfile.seekg (0, ios::end);

end = myfile.tellg();

myfile.close();

long size = end-begin;

FILE * input;

M = new unsigned char[size];

n = size;

input = fopen(filename,"r");

fread(M,1,size,input);

fclose(input);

void SaveEncFile(char * filename, unsigned int S)

{

FILE * output;

output = fopen(filename,"wb");

fwrite(&S,32,1,output);

fclose(output);

cout << "File saved to " << filename << endl;

}

void Poiskpqn(unsigned int K, unsigned int &p, unsigned int &q, unsigned int &n)

{

do{p=rand()%254;}

while (LemanTest(p,K)==1);

do{q=rand()%(254*254);}

while (LemanTest(q,K)==1);

n=p*p*q;

cout<<"Close parametr p="<<p<<endl;

cout<<"Close parametr q="<<q<<endl;

cout<<"Open parametr n="<<n<<endl;

}

void Poiskw(unsigned char *M, unsigned int &H, unsigned int &x, unsigned int k, unsigned int n, unsigned int p, unsigned int q, unsigned int &w)

{

unsigned int F;

unsigned int R;

H=(CRC32Count(M,sizeof(M))%(n));

cout<<"H="<<H<<endl;

x=(rand())%(p*q);

EncrDecr(x,k,n,F);

if(H>F)

R=H-F;

else

R=n-F+H;

if(R%(p*q)==0)

w=R/(p*q);

else

w=R/(p*q)+1;

}

void Poisks(unsigned int x, unsigned int w, unsigned int K, unsigned int p, unsigned int q, unsigned int &S)

{

unsigned int L;

unsigned int r;

unsigned int ki;

ki=K-1;

EncrDecr(x,ki,p,L);

if((w%K)==0)

r=w/K;

else

r=w/K+1;

cout<<r<<endl;

S=x+((r*L)%p)*p*q;

cout<<"S="<<S<<endl;

}

void Proverka(unsigned int S, unsigned int k, unsigned int n, unsigned int H)

{

unsigned int Z;

unsigned int a;

unsigned int b;

int z=32;

for(int i=31;1>=0;i--)

if(n&(1<<i)==0)

z--;

else

break;

if((z%3)==0)

a=2*z/3;

else

a=2*z/3+1;

EncrDecr(S,k,n,Z);

EncrDecr(2,a,n,b);

if(((H<Z)||(H==Z))&&(Z<(H+b)))

cout<<"Podpis rabotaet"<<endl;

else

cout<<"Podpis ne rabotaet"<<endl;

}

void main()

{

unsigned int H;

unsigned int w;

unsigned int p;

unsigned int q;

unsigned int x;

unsigned int n;

unsigned int S;

unsigned int Q;

int k=128;

int K=256;

srand(time(NULL));

cout<<"1-polnaya generacia"<<endl;

cout<<"2-generaciya tolko parametrow"<<endl;

cout<<"3-proverca podpisy"<<endl;

cout<<"vyberite deystvie"<<endl;

cin>>Q;

int size = 0;

unsigned char * M = new unsigned char[1];

LoadFile("1.txt",M,size);

if(Q==1)

{

Poiskpqn(K,p,q,n);

Poiskw(M,H,x,k,n,p,q,w);

Poisks(x,w,k,p,q,S);

Proverka(S,k,n,H);

SaveEncFile("C:\\n.txt",n);

SaveEncFile("C:\\p.txt",p);

SaveEncFile("C:\\q.txt",q);

SaveEncFile("C:\\podpis.txt",S);

}

else if(Q==2)

{

Poiskpqn(K,p,q,n);

SaveEncFile("C:\\n.txt",n);

SaveEncFile("C:\\p.txt",p);

SaveEncFile("C:\\q.txt",q);

}

else if(Q==3)

{

unsigned char * V = new unsigned char[1];

LoadFile("C:\\podpis.txt",V,size);

unsigned int G = (unsigned int)V;

cout<<"vvedite n"<<endl;

cin>>n;

cout<<"vvedite hesh"<<endl;

cin>>H;

Proverka(G,k,n,H);

}

else

{

cout<<"Nado pravelno vvodit, perezapustite programu"<<endl;

}

cin.get();

cin.get();

}

ДОДАТОК Б. ІНСТРУКЦІЯ КОРИСТУВАЧА

Мінімальні системні вимоги:

- OS MS-DOS або Windows

- 19.8 МБ на жорсткому диску

- 0.432 МБ оперативної пам'яті

Диск, що додається, містить наступні файли:

- Chfym.cpp (текст програми)

- Код програми.doc (текст програми у документі Microsoft Word)

- Пояснювальна записка.doc (записка пояснення)

- Readme.txt (інструкція користувача)