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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Курсова робота

з дисципліни «Основи програмування»

ТЕМА: «Датчики псевдовипадкових чисел та їх застосування в криптографічних системах»

Вступ

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

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

Сучасна криптографія містить у собі чотири значні розділи:

Симетричні криптосистеми. У симетричних криптосистемах і для шифрування, і для дешифрування використовується той самий ключ. (Шифрування — перетворювальний процес: вихідний текст, який називається також відкритим текстом, замінюється шифрованим текстом, дешифрування — обернений шифруванню процес. На основі ключа шифрований текст перетвориться у вихідний) Криптосистеми з відкритим ключем. У системах із відкритим ключем використовуються два ключі - відкритий і закритий, що математично пов’язані один з одним. Інформація шифрується за допомогою відкритого ключа, який доступний усім бажаючим, а розшифровується за допомогою закритого ключа, відомого тільки одержувачу повідомлення. (Ключ — інформація, необхідна для безперешкодного шифрування і дешифрування текстів.)

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

Керування ключами. Це процес системи опрацювання інформації, утриманням яких є упорядкування і розподіл ключів між користувачами.

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

В даній курсовій роботі розроблений алгоритм генерації гамми шифра за допомогою лінійного конгруентного датчика псевдовипадкових чисел, розроблена комп’ютерна програма на об'єктно-орієнтованій мові програмування Microsoft Visual C++ 6.0 ®, яка реалізує цей алгоритм. Також наведений приклад використання такого генератора в криптосистемі.

Visual C++ - це компілятор C++, але це також і середовище, компоненти якого, взаємодіючи один з одним, спрощують процес розробки застосувань. Середовище Visual C++ пропонує великі можливості для програмування Windows-програм. Найхарактернішою його компонентою є бібліотека основних класів Microsoft (Microsoft Foundation Classes — MFС). Великий набір класів С++ інкапсулює основну частину API (Application Standard Interface) Win32 і пропонує могутню основу для написання типових застосувань. До складу Visual C++ входить Microsoft Developer Studio Integrated Development Environment — інтегроване середовище для розробки програм (IDE). Visual Studio 97 — є ядром системи розробки Visual C++. Вона пропонує багато різних можливостей, надає доступ до багатьох компонент системи розроблювача Visual C++, а також взаємодіє з такими засобами розробки Microsoft, як Visual J++ або Microsoft Network Library.

Теоретичні відомості

Вимоги до криптосистем

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

зашифроване повідомлення повинно піддаватися читанню тільки при наявності ключа;

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

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

знання алгоритму шифрування не повинно впливати на надійність захисту;

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

структурні елементи алгоритму шифрування повинні бути незмінними; додаткові біти, що вводяться в повідомлення в процесі шифрування, повинний бути цілком і надійно сховані в шифрованому тексті;

довжина шифрованого тексту повинна бути рівній довжині вихідного тексту;

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

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

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

Симетричні криптосистеми

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

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

перестановка — символи тексту, що шифрується переставляются по деякому правилу в межах заданого блока переданого тексту;

аналітичні перетворення — текст, що шифрується перетвориться по деякому аналітичному правилу, наприклад гаммування — полягає в накладенні на вихідний текст деякої псевдовипадкової послідовності, що генерується на основі ключа ;

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

1.3 Системи з відкритим ключем Як би не були складні і надійні криптографічні системи — їх слабке місце при практичній реалізації - проблема розподілу ключів. Для того, щоб був можливий обмін конфіденційною інформацією між двома суб'єктами ІС (інформаційних систем), ключ повинен бути згенерований одним з них, а потім якимось чином знову ж у конфіденційному порядку переданий іншому. Тобто у загальному випадку для передачі ключа знову ж потрібне використання якоїсь криптосистеми. Для вирішення цієї проблеми на основі результатів, отриманих класичною і сучасною алгеброю, були запропоновані системи з відкритим ключем. Суть їх складається в тому, що кожним адресатом ІС генеруються два ключі, пов’язані між собою по визначеному правилу. Один ключ оголошується відкритим, а інший закритим. Відкритий ключ публікується і доступний будь-кому, хто бажає послати повідомлення адресату. Секретний ключ зберігається в таємниці. Вихідний текст шифрується відкритим ключем адресата і передається йому. Зашифрованій текст в принципі не може бути розшифрований тим же відкритим ключем. Дешифрування повідомлення можливо тільки з використанням закритого ключа, який відомий тільки самому адресату. Криптографічні системи з відкритим ключем використовують так називані необоротні або односторонні функції, що мають таку властивість: при заданому значенні x досить просто обчислити значення f (x), проте якщо y=f (x), те немає простого шляху для обчислення значення x. Множина класів необоротних функцій і породжує вся розмаїтість систем із відкритим ключем. Проте не всяка необоротна функція підходить для використання в реальних ІС. В самому визначенні необоротності є присутнім непевність. Під необоротністю розуміється не теоретична необоротність, а практична неможливість обчислити обернене значення використовуючи сучасні обчислювальні засоби за допустимий інтервал часу. Тому щоб гарантувати надійний захист інформації, до систем із відкритим ключем (СВК) ставляться два важливі і очевидні вимоги:

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

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

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

Розкладання великих чисел на прості множники.

Обчислення логарифма в кінцевому полі.

Обчислення коренів алгебраїчних рівнянь.

Тут же слід зазначити, що алгоритми криптосистеми з відкритим ключем (СВК) можна використовувати в таких призначеннях.

Як самостійні засоби захисту передаваних і збережуваних даних.

Як засоби для розподілу ключів.

Алгоритми СВК більш трудомісткі, ніж традиційні криптосистеми. Тому часто на практику раціонально за допомогою СВК розподіляти ключі, обсяг яких як інформації незначний. А потім за допомогою звичайних алгоритмів здійснювати обмін великими інформаційними потоками. Один з найбільше поширених — система з відкритим ключем — RSA. Криптосистема RSA, розроблена в 1977 році й одержала назву на честь її творців: Рона Рівеста, Аді Шаміра і Леонарда Эйдельмана. Вони скористалися тим фактом, що знаходження великих простих чисел в обчислювальному відношенні здійснюється легко, але розкладання на множники добутку двох таких чисел практично неможливо здійснити. Доведено (теорема Рабіна), що розкриття шифру RSA еквівалентно такому розкладанню. Тому для будь-якої довжини ключа можна дати нижню оцінку числа операцій для розкриття шифру, а з урахуванням продуктивності сучасних комп’ютерів оцінити і необхідний на цей час. Можливість гарантовано оцінити захищеність алгоритму RSA стала однією з причин популярності цієї СВК на фоні десятків інших схем. Тому алгоритм RSA використовується в банківських комп’ютерних мережах, особливо для роботи з віддаленими клієнтами (обслуговування кредитних карток).

1.4 Генерація ключів

Ще раз зверну увагу на те, що не варто використовувати невипадкові ключі з метою легкості їх запам’ятовування. В серйозних інформаційних системах використовуються спеціальні апаратні і програмні методи генерації випадкових ключів. Як правило використовують датчики ПВЧ (псевдовипадкових чисел). Проте ступінь випадковості їх генерації повинна бути достатньо високою. Ідеальним генераторами є пристрої на основі «натуральних» випадкових процесів. Наприклад випадковим математичним об'єктом є десяткові знаки ірраціональних чисел, що обчислюються за допомогою стандартних математичних методів.

1.5 Метод гаммування

Гаммування є також широко застосовуваним криптографічним перетворенням.

Принцип шифрування гаммуванням полягає в генерації гами шифру за допомогою датчика псевдовипадкових чисел і накладенні отриманої гами на відкриті дані зворотним чином (наприклад, використовуючи додавання по модулю 2).

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

Отриманий зашифрований текст є достатньо важким для розкриття в тому випадку, якщо гама шифру не містить повторюваних бітових послідовностей. По суті справи гама шифру повинна змінюватися випадковим чином для кожного шифрованого слова. Фактично ж, якщо період гамми перевищує довжину всього зашифрованого тексту і невідома ніяка частина вихідного тексту, то шифр можна розкрити тільки прямим перебором («лобова атака», «brute-force attack»). Криптостійкість у цьому випадку визначається розміром ключа.

Метод гаммування стає безсильним, якщо сторонній особі стає відомий фрагмент вихідного тексту і відповідна йому шифрограмма. Простим вирахуванням по модулю утворюється відрізок псевдовипадкового періоду і по ньому відновляється вся послідовність. Стороння особа може зробити це на основі догадок про зміст вихідного тексту. Так, якщо більшість повідомлень починається зі слів «ЦІЛКОМ ТАЄМНО», то криптоаналіз всього тексту значно полегшується. Це необхідно враховувати при створенні реальних систем інформаційної безпеки.

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

1.6 Датчики ПВЧ (псевдовипадкових чисел)

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

Датчики М — послідовностей

М — послідовності популярні, завдяки відносній легкості їх реалізації.

М — послідовності являють собою лінійні рекурентні послідовності максимального періоду, формовані k-розрядними генераторами на основі регістрів зсуву. На кожному такті біт зміщує k попередніх і до нього додається їх сума по модулю 2. Витискуваний біт додається до гамми.

Строго це можна представити у вигляді таких відношень:

r1:=r0 r2:=r1 … rk-1:=rk-2

r0:=a0 r1 a1 r2 … ak-2 rk-1

Гi:= rk;

Тут r0 r1 … rk-1 — k однобітних регістрів, a0 a1 … ak-1 — коефіцієнти неприводимого двійкового поліному ступеня k-1. Гi — i-е значення вихідної гамми.

Період Мпослідовностей виходячи з її властивостей дорівнює 2k-1.

Іншою важливою властивістю Мпослідовності є обсяг ансамблю, тобто кількість різноманітних Мпослідовностей для заданого k. Ця характеристика приведена в таблиці:

Очевидно, що такі обсяги ансамблів послідовності неприйнятні.

Тому на практиці часто використовують послідовності Голда, що утворюються підсумовуванням декількох Мпослідовностей. Обсяг ансамблів цих послідовностей на декілька порядків перевершують обсяги ансамблів породжуючих М-послідовностей. Так при k=10 ансамбль збільшується від 1023 (Мпослідовності) до 388 000.

Також перспективними рекомендуються нелінійні датчики ПВЧ (наприклад зсувові регістри з елементом И в ланцюзі зворотного зв’язку), проте їхні властивості ще недостатньо вивчені.

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

криптографічний шифрування гаммування псевдовипадковий

Алгоритм RC4

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

Алгоритм RC4 — це потоковий шифр з перемінною довжиною ключа, розроблений в 1987 році Рональдом Райвістом для компанії RSA Data Security. Як і його попередник блоковий шифр RC2, RC4 — шифр з перемінною довжиною ключа, придатний для магістрального шифрування. Він дуже компактний в термінах розміру коду, і особливо зручний для процесорів з побайтно-орієнтованою обробкою. RC4 може шифрувати дані зі швидкістю близько 1 МБайт/сек на 33 МГц машині і (аналогічно RC2), має особливий статус.

Опис криптосхеми. Криптогенератор функціонує незалежно від відкритого тексту. Генератор має підстановочну таблицю (S-бокс 8×8): S1, S2, …, S255. Входами генератора є замінені по підстановці числа від 0 до 255, і ця підстановка є функцією від ключа змінної довжини. Генератор має два лічильника i і j, які ініціалізуються нульовими значеннями.

Для генерації випадкового байта гамми виконуються наступні операції:

i = (i+1) mod 256

j = (j+Si) mod 256

swap Si and Sj

t = (Si+Sj) mod 256

K = St

Байт К складується операцією XOR з відкритим текстом для виготовлення шифротексту, або складується операцією XOR з шифротекстом для отримання байта відкритого тексту. Шифрування проходить достатньо швидко — приблизно в 10 раз швидше DES-алгоримту.

Ініціалізація S-боксу проста. На першому кроці він заповнюється лінійно: S0=0, S1=1,. .. ., S255=255. Після цього ще один 256-байтний масив повністю заповнюється ключем, для чого ключ повторюється відповідну кількість разів у залежності від довжини: К0, К1, …, К255. Індекс j виставляється в нуль. Після цього:

for i=0 to 255

j = (j+Si+Ki) mod 256

swap Si and Sj

Схема показує, що RC4 може приймати приблизно 21 700 (256!*2562) можливих станів, а це дуже багато. S-бокс повільно змінюється в процесі роботи: параметр i забезпечує зміну кожного елемента, а j відповідає за те, щоб ці елементи змінювались випадково.

В даний час алгоритм RC4 реалізований в десятках комерційних криптопродуктах, включаючи Lotus Notes, Apple Computer’s AOCE, Oracle Secure SQL, а також є частиною специфікації стандарту сотового зв’язку CDPD.

Конгруентні датчики

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

Одним із хороших конгруентних генераторів є лінійний конгруентний датчик ПВЧ. Лінійний конгруентний датчик ПВЧ — це генератор псевдовипадкових чисел T (i), які описуються співвідношенням

T (i+1) = (A*T (i)+C) mod m,

де, А і С — константи, Т (0) — вихідна величина, обрана у якості породжуючого числа. Очевидно, що ці три розміри і утворять ключ.

Такий датчик ПВЧ генерує псевдовипадкові числа з визначеним періодом повторення, що залежить від обраних значень, А і С. Значення m звичайно встановлюється рівним 2n, де n — довжина машинного слова в бітах. Датчик має максимальний період М до того, як що генерується послідовність почне повторюватися. Через, відзначеної раніше, необхідно вибирати числа, А и С такі, щоб період М був максимальним. Як показано Д. Кнутом, лінійний конгруентний датчик ПСЧ має максимальну довжину М тоді і тільки тоді, коли С — непарне, і А mod 4 = 1. В таблиці наведений список констант для лінійних конгруентних датчиків. Всі вони породжують генератори максимального періоду, і що найважливіше проходять спектральні тести на випадковість для розмірностей 2, 3, 4, 5 і 6.

Для шифрування даних за допомогою датчика ПВЧ може бути обраний ключ будь-якого розміру. Наприклад, нехай ключ складається з набору чисел x (j) розмірністю b, де j=1, 2, …, n. Тоді утворювану гаму шифру G можна представити як об'єднання множин, що не перетинаються, H (j).

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

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

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

Інформаційне забезпечення

2.1 Програмна реалізація алгоритму Комп’ютерна програма генерації псевдовипадкових послідовностей за допомогою лінійного конгруентного генератора псевдовипадкових чисел розроблена на об'єктно-орієнтованій мові програмування С++ в інтегрованому середовищі розробки Microsoft Visual C++®. В програмі реалізовані два генератора псевдовипадкових чисел: лінійний конгруентний генератор та комбінований конгруентний генератор як різновид простого генератора з більш потужним періодом.

Інтерфейс програми «LCG» (Linear Congruential Generator)

Результат роботи програми.

Наприклад необхідно зашифрувати файл методом гаммування з паролем «АВС». Тоді необхідно згенерувати шифруючу послідовність на основі даного пароля. ASCII-коди символів «АВС» — відповідно «65», «66» і «67». В результаті генерації гамми за допомогою лінійного конгруентного генератора наступну псевдовипадкову послідовність (для зручності візьмемо наступні параметри генератора а=17, с=9, m=32): «261 128»

Накладемо цю гамму на послідовність байт файлу, що шифрується за допомогою самого широковживаного методу — складення по модулю 2 (xor):

байти відкритого файлу — 79, 56 31,

" 261 128″ xor «795 631» = «855 103»

Вихідний код програми наведений в додатку 1.

2.2 Криптоаналіз лінійних конгруентних генераторів ПВЧ Оскільки конгруентний генератор — це метод генерації послідовності S0, S1,.. ., Sn, де Sі обчислюється на основі рекурентного відношення

то проведені криптоаналітичні досліди відкрили серйозні недоліки конгруентних генераторів з погляду їх використання в якості стійких генераторів псевдовипадкових чисел. Проте існує список спеціальних констант для лінійних конгруентних генераторів ПВЧ (таблиця констант наведена в додатку 2). Всі вони породжують гамми максимального періоду, і що більш важливо, проходять спектральні тести на випадковість для розмірностей 2, 3, 4, 5 і 6. Їх підбір зроблений на основі принципу максимального добутку, який не викликає переповнення довжини слова. Головні переваги лінійних конгруентних генераторів в тому, що вони швидко працюють і вимагають мало операцій на біт послідовності.

3. Практичне застосування В якості прикладу застосування лінійного конгруентного генератора псевдовипадкових чисел в криптографічних програмах приводжу програму шифрування файлів власної розробки «AT-Crypt». В програмі «AT-Crypt» реалізований алгоритм блочного шифрування за допомогою методу гаммування. В якості генератора гамми шифра використовується лінійного конгруентний генератор псевдовипадкових чисел з періодом 2³². При відсутності відкритого тексту, тобто початкового файлу, програма забезпечує досить стійке шифрування.

Інтерфейс програми «AT-Crypt «

Додаток 1

Код програми «LCG» (Linear Congruential Generator) на мові програмування С++.

// LCG. h: main header file for the LCG application

#if !defined (AFX_LCG_H__ECD68524_47DB_11D6_85F6_2 1146AFD__INCLUDED_)

#define AFX_LCG_H__ECD68524_47DB_11D6_85F6_2 1146AFD__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

#ifndef __AFXWIN_H__

#error include 'stdafx.h' before including this file for PCH

#endif

#include «resource.h» // main symbols

// CLCGApp:

// See LCG. cpp for the implementation of this class

class CLCGApp: public CWinApp

{

public:

CLCGApp ();

// Overrides

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL (CLCGApp)

public:

virtual BOOL InitInstance ();

//}}AFX_VIRTUAL

// Implementation

//{{AFX_MSG (CLCGApp)

//}}AFX_MSG

DECLARE_MESSAGE_MAP ()

};

//{{AFX_INSERT_LOCATION}}

#endif // !defined (AFX_LCG_H__ECD68524_47DB_11D6_85F6_2 1146AFD__INCLUDED_)

// LCGDlg. h: header file

#if !defined (AFX_LCGDLG_H__ECD68526_47DB_11D6_85F6_2 1146AFD__INCLUDED_)

#define AFX_LCGDLG_H__ECD68526_47DB_11D6_85F6_2 1146AFD__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

// CLCGDlg dialog

class CLCGDlg: public CDialog

{

// Construction

public:

CLCGDlg (CWnd* pParent = NULL);

// Dialog Data

//{{AFX_DATA (CLCGDlg)

enum { IDD = IDD_LCG_DIALOG };

//}}AFX_DATA

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL (CLCGDlg)

protected:

virtual void DoDataExchange (CDataExchange* pDX);// DDX/DDV support

//}}AFX_VIRTUAL

// Implementation

protected:

HICON m_hIcon;

//{{AFX_MSG (CLCGDlg)

virtual BOOL OnInitDialog ();

afx_msg void OnSysCommand (UINT nID, LPARAM lParam);

afx_msg void OnPaint ();

afx_msg HCURSOR OnQueryDragIcon ();

virtual void OnOK ();

virtual void OnCancel ();

afx_msg void OnOk2();

afx_msg void OnAboutbox ();

//}}AFX_MSG

DECLARE_MESSAGE_MAP ()

};

//{{AFX_INSERT_LOCATION}}

#endif // !defined (AFX_LCGDLG_H__ECD68526_47DB_11D6_85F6_2 1146AFD__INCLUDED_)

// LCG. cpp: Defines the class behaviors for the application.

#include «stdafx.h»

#include «LCG.h»

#include «LCGDlg.h»

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

// CLCGApp

BEGIN_MESSAGE_MAP (CLCGApp, CWinApp)

//{{AFX_MSG_MAP (CLCGApp)

//}}AFX_MSG

ON_COMMAND (ID_HELP, CWinApp: OnHelp)

END_MESSAGE_MAP ()

// CLCGApp construction

CLCGApp:CLCGApp ()

{

}

// The one and only CLCGApp object

CLCGApp theApp;

// CLCGApp initialization

BOOL CLCGApp: InitInstance ()

{

AfxEnableControlContainer ();

// Standard initialization

#ifdef _AFXDLL

Enable3dControls ();

#else

Enable3dControlsStatic ();statically

#endif

CLCGDlg dlg;

m_pMainWnd = &dlg;

int nResponse = dlg. DoModal ();

if (nResponse == IDOK)

{

}

else if (nResponse == IDCANCEL)

{

}

return FALSE;

}

// LCGDlg. cpp: implementation file

#include «stdafx.h»

#include «LCG.h»

#include «LCGDlg.h»

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

#define MODMULT (a, b, c, m, s) q = s/a; s = b*(s-a*q) — c*q; if (s<0) s+=m ;

long combinedLCG (void);

void initLCG (long InitS1, long InitS2);

int gen (int G);

static long s1, s2, q;

int Gamma, Value ;

long Gamma1, Value1, Value2;

long combinedLCG (void)

{

long z;

MODMULT (53 668, 40 014, 12 211, 214 748 3563L, s1);

MODMULT (52 774, 40 692, 3791, 214 748 3399L, s2);

z = s1 — s2 ;

if (z < 1) z += 2 147 483 562 ;

return z ;

};

void initLCG (long InitS1, long InitS2)

{

s1 = InitS1 ;

s2 = InitS2 ;

};

int gen (int G)

{

G=(9301*G+49 297) % 233 280;

return G;

}

class CAboutDlg: public CDialog

{

public:

CAboutDlg ();

//{{AFX_DATA (CAboutDlg)

enum { IDD = IDD_ABOUTBOX };

//}}AFX_DATA

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL (CAboutDlg)

protected:

virtual void DoDataExchange (CDataExchange* pDX); // DDX/DDV support

//}}AFX_VIRTUAL

// Implementation

protected:

//{{AFX_MSG (CAboutDlg)

virtual void OnOK ();

//}}AFX_MSG

DECLARE_MESSAGE_MAP ()

};

CAboutDlg:CAboutDlg (): CDialog (CAboutDlg:IDD)

{

MEMORYSTATUS *pmstat;

int TP, i;

i=2;

pmstat->dwLength=sizeof (MEMORYSTATUS);

GlobalMemoryStatus (pmstat);

TP=pmstat->dwMemoryLoad;

//SetDlgItemInt (IDC_EDIT8,i);

}

void CAboutDlg: DoDataExchange (CDataExchange* pDX)

{

CDialog:DoDataExchange (pDX);

}

BEGIN_MESSAGE_MAP (CAboutDlg, CDialog)

END_MESSAGE_MAP ()

CLCGDlg:CLCGDlg (CWnd* pParent /*=NULL*/)

: CDialog (CLCGDlg:IDD, pParent)

{

m_hIcon = AfxGetApp ()->LoadIcon (IDR_MAINFRAME);

}

void CLCGDlg: DoDataExchange (CDataExchange* pDX)

{

CDialog:DoDataExchange (pDX);

//{{AFX_DATA_MAP (CLCGDlg)

// NOTE: the ClassWizard will add DDX and DDV calls here

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP (CLCGDlg, CDialog)

//{{AFX_MSG_MAP (CLCGDlg)

ON_WM_SYSCOMMAND ()

ON_WM_PAINT ()

ON_WM_QUERYDRAGICON ()

ON_BN_CLICKED (IDOK2, OnOk2)

ON_BN_CLICKED (IDM_ABOUTBOX, OnAboutbox)

//}}AFX_MSG_MAP

END_MESSAGE_MAP ()

// CLCGDlg message handlers

BOOL CLCGDlg: OnInitDialog ()

{

CDialog:OnInitDialog ();

ASSERT ((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);

ASSERT (IDM_ABOUTBOX < 0xF000);

CMenu* pSysMenu = GetSystemMenu (FALSE);

if (pSysMenu ≠ NULL)

{

CString strAboutMenu;

strAboutMenu.LoadString (IDS_ABOUTBOX);

if (!strAboutMenu.IsEmpty ())

{

pSysMenu->AppendMenu (MF_SEPARATOR);

pSysMenu->AppendMenu (MF_STRING, IDM_ABOUTBOX, strAboutMenu);

}

}

SetIcon (m_hIcon, TRUE);

SetIcon (m_hIcon, FALSE);

return TRUE;

}

void CLCGDlg: OnSysCommand (UINT nID, LPARAM lParam)

{

if ((nID & 0xFFF0) == IDM_ABOUTBOX)

{

CAboutDlg dlgAbout;

dlgAbout.DoModal ();

}

else

{

CDialog:OnSysCommand (nID, lParam);

}

}

void CLCGDlg: OnPaint ()

{

if (IsIconic ())

{

CPaintDC dc (this); // device context for painting

SendMessage (WM_ICONERASEBKGND, (WPARAM) dc. GetSafeHdc (), 0);

int cxIcon = GetSystemMetrics (SM_CXICON);

int cyIcon = GetSystemMetrics (SM_CYICON);

CRect rect;

GetClientRect (&rect);

int x = (rect.Width () — cxIcon + 1) / 2;

int y = (rect.Height () — cyIcon + 1) / 2;

dc.DrawIcon (x, y, m_hIcon);

}

else

{

CDialog:OnPaint ();

}

}

HCURSOR CLCGDlg: OnQueryDragIcon ()

{

return (HCURSOR) m_hIcon;

}

void CAboutDlg: OnOK ()

{

CDialog:OnOK ();

}

void CLCGDlg: OnOK ()

{

Value=GetDlgItemInt (IDC_EDIT1,0,false);

Gamma=gen (Value);

SetDlgItemInt (IDC_EDIT2,Gamma);

}

void CLCGDlg: OnCancel ()

{

CDialog:OnCancel ();

}

void CLCGDlg: OnOk2()

{

Gamma1=0;

Value1=GetDlgItemInt (IDC_EDIT3,0,false);

initLCG (Value1,2);

Gamma1=combinedLCG ();

SetDlgItemInt (IDC_EDIT4,Gamma1);

}

void CLCGDlg: OnAboutbox ()

{

CAboutDlg dlgAbout;

dlgAbout.DoModal ();

}

Додаток 2.

Таблиця спеціальних констант для лінійних конгруентних генераторів ПВЧ.

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

Лінійні конгруентні генератори псевдовипадкових чисел широко застосовуються для криптографічних програм в якості генераторів гамми для ключів головним чином, завдяки своїй простоті реалізації, а також для інших програм, таких, як симуляція випадкового поводження. Такі послідовності ефективно генеруються і демонструють хороші статистичні властивості при випробуваннях більшістю емпіричних тестів. Головні переваги лінійних конгруентних генераторів в тому, що вони швидко працюють і вимагають мало операцій на біт послідовності. Шифрування за допомогою генератора ПВЧ є досить поширеним криптографічним методом. Багато в чому якість шифру, побудованого на основі генератора ПВЧ, визначається не тільки і не стільки характеристиками датчика, скільки алгоритмом одержання гамми.

Розроблена комп’ютерна програма «LCG», яка демонструє роботу лінійного конгруентного генератора ПВЧ по двом схемам.

Література

" Поточные шифры. Результаты зарубежной криптологии", Москва, 1997.

Крис Паппас, Уильям Мюррей, «Visual C++. Руководство разработчика», BHV, Киев, 2000.

Мюррэй Хилл, Бьярн Страустрап, «Язык C++», Нью Джерси, 1996,

B. Schneier, Applied Cryptography, 2-nd edition, John Wiley & Sons, New York, 1996.

W.H.Press, B.P.Flannery, S.A. Teukolsky and W.T. Vetterling, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, 1988.

E.H. Sibley, «Random Number Generators: Good Ones Are Hard to Find», Communications of the ACM, v.31, n.10, Oct 1988, pp. 1192−1201

B.A. Wichman and I.D. Hill, «An Efficient and Portable Pseudo-Random Number Generator», Applied Statistics, v. 31, 1982, pp. 188−190.

Веб-сайт: http://random.mat.sbg.ac.at/generators/,