Алгоритми генерації та оцінки стійкості паролів (Delphi)

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

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

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

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

1.1 Найменування та галузь використання

Вимоги до програмного забезпечення:

· робота в середовищі операційних систем Windows 2000/XP/Vista/7;

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

Мінімальні вимоги до апаратного забезпечення:

· IBM-сумісний комп'ютер, не нижче Pentium IІ, RAM-128Mb, SVGA-800*600*16bit;

· вільний простір на жорсткому диску не менш 2 Мб;

· монітор, клавіатура, маніпулятор типу «миша».

1.6 Джерела розробки

Джерелами розробки дипломної роботи є:

· технічне завдання на реалізацію проекту;

· довідкова література;

· наукова література;

· технічна література;

· програмна документація.

2. Огляд алгоритмів генерації псевдовипадкових послідовностей

програмний пароль тестування алгоритм

Протягом багатьох років ті, кому випадкові числа були необхідні для наукової праці, змушені були тягати кулі з урни, попередньо добре перемішавши їх, або кидати гральні кості, або розкладати карти. Таблиця, що містить більше 40 000 узятих навмання випадкових цифр зі звітів про перепис, була опублікована в 1927 році Л. X. К. Типпеттом.

З тих пор були побудовані механічні генератори випадкових чисел. Перша така машина була використана в 1939 році М.Ж. Кендаллом і Б. Бабінгтон-Смітом (В. Babington-Smith) для побудови таблиці, що містить 100 000 випадкових цифр. Комп'ютер Ferranti Mark I, уперше запущений в 1951 році, мав вбудовану програму, що використовувала резисторний генератор шуму та поставляла 20 випадкових бітів на суматор. Цей метод був запропонований А.М. Тьюрингом. В 1955 році. RAND Corporation опублікувала широко використовувані таблиці, у яких утримувався мільйон випадкових цифр, отриманих за допомогою інших спеціальних пристроїв. Відомий генератор випадкових чисел ERNIE застосовувався протягом багатьох років для визначення виграшних номерів британської лотереї.

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

Генератор ERNIE міг бути убудований у комп'ютер, як в Ferranti Mark I, але це виявилося незручно, оскільки неможливо точно відтворити обчислення навітьвідразу по закінченні роботи програми; більше того, такі генератори часто давали збої, що було вкрай важко виявити.

Технологічний прогрес дозволив повернутися до використання таблиць в 90-ті роки, тому що мільярди тестованих випадкових байтів можна було розмістити на компакт-дисках. Дж. Марсалья (George Marsaglia) допоміг пожвавити табличний метод в 1995 році, підготувавши демонстраційний диск із 650 Мбайт випадкових чисел, при генеруванні яких запис шуму діодного ланцюга сполучалася з певним чином скомпонованою музикою в стилі «реп». (Він назвав це «білим і чорним шумом».)

Недосконалість перших механічних методів спочатку розбудило інтерес до одержання випадкових чисел за допомогою звичайних арифметичних операцій, закладених у комп'ютер. Джон фон Нейман (John von Neumann) першим запропонував такий підхід близько 1940 року. Його ідея полягала у тому, щоб піднести до квадрата попереднє випадкове число й виділити середні цифри. Метод середин квадратів фон Неймана фактично є порівняно бідним джерелом випадкових чисел, однак він послужив відправною точкою наступних досліджень у цій області.

2.2 Загальні характеристики генераторів псевдовипадкових чисел

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

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

У більшості завдань прикладної математики, розв'язуваних стохастичними методами, винятково важливим є досить специфічна властивість «рівномірності розподілу» випадкових чисел, що генерують ГПВЧ. Специфічне тому, що воно радикально відрізняється від поняття, описуваного тим же терміном у математичній статистиці. Щоб не було подібної плутанини, термін «рівномірність розподілу» часто заміняють на «гарну розподіленість» і підкреслюють, що він ставиться саме до послідовності чисел («добре розподілена послідовність» або «well distributed sequence»). Як й у випадках з АГВЧ, коли хоча й неявно, але малося на увазі, що за апаратними засобами ГВЧ стоїть потужна й складна програмна підтримка, так й в обчислювальних застосуваннях ГПВЧ навіть над таким майже ідеальним генератором, як Mersenne Twister (Вихор Мерсенна), для одержання високих показників треба «надбудовувати» програмний прошарок, що формує з послідовності випадкових чисел добре розподілену послідовність.

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

Будь-який ГПВЧ із обмеженими ресурсами рано або пізно зациклюється - починає повторювати ту саму послідовність чисел. Довжина циклів ГПВЧ залежить від самого генератора й у середньому становить близько 2^n/2, де n - розмір внутрішнього стану в бітах, хоча лінійні конгруентні й LFSR-генератори мають максимальні цикли порядку 2ⁿ. Якщо ГПВЧ може сходитися до занадто коротких циклів, такий ГПВЧ стає передбачуваним й є непридатним.

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

· занадто короткий період;

· послідовні значення не є незалежними;

· деякі біти «менш випадкові», чим інші;

· нерівномірний одномірний розподіл;

· зворотність.

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

Різновидом ГПВЧ є ГПВБ - генератори псевдо-випадкових біт, а так само різних потокових шифрів. ГПВБ, як і потокові шифри, складаються із внутрішнього стану (звичайно розміром від 16 біт до декількох мегабайт), функції ініціалізації внутрішнього стану ключем або насінням (англ. seed), функції відновлення внутрішнього стану й функції виводу. ГПВБ підрозділяються на прості арифметичні, зламані криптографічні й криптостойкі. Їхнє загальне призначення - генерація послідовностей чисел, які неможливо відрізнити від випадкових обчислювальними методами.

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

У військових цілях й у польових умовах застосовуються тільки засекречені синхронні криптостойкі ГПВЧ (потокові шифри), блокові шифри не використаються. Прикладами відомих криптостойких ГПВЧ є RC4, ISAAC, SEAL, Snow, зовсім повільний теоретичний алгоритм Блюма, Блюма й Шуба, а так само лічильники із криптографічними кеш-функціями або криптостійкими блоковими шифрами замість функції виводу.

2.3 Випадкові числа й теорія імовірності

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

Приклади:

випробування - кидання монети, випадкова подія - випадання герба;

випробування - участь у грі «Російське лото», випадкове подія - виграш;

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

випробування - народження дитини, випадкова подія - стать дитини - чоловіча;

випробування - спостереження за погодою протягом дня, випадкова подія - протягом дня був дощ.

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

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

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

Стійкість відносної частоти була виявлена й багаторазово підтверджена експериментально натуралістами в 17-19 століттях. Найбільш вражаючим є результат К. Пирсона, що кидав монету 12000 разів, потім здійснив ще одну серію кидань - 24000 разів. У цих серіях він підраховував кількість випадань герба й одержав значення відносної частоти для нього 0,5016 й 0,5005, що відрізняються друг від друга на 0,0011.

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

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

Спочатку визначимо ймовірність регулярної випадкової події як число, біля якого коливається відносна частота в довгих серіях випробувань. Потім уведемо поняття рівноможливості, рівноймовірності двох подій. Зміст цього поняття ясний інтуїтивно, ціль введення - ми хочемо визначити математично поняття ймовірності зводячи його до більш простого не обумовленого поняття рівноможливості. Наявність рівноймовірності деяких подій що є результатами деякого випробування встановлюється з «загальних міркувань», не доводиться математично й не може бути доведено, не має потреби в доказі як первинне. Наприклад, при киданні гральної кістки випадання 1, 2, …, 6 очків уважають подіями рівноймовірності (або «майже» рівноймовірності) виходячи з передбачуваної фізичної однорідності матеріалу кості й геометричної правильності, тобто вважаючи кістку ідеальним кубом. Якщо в результаті випробування можливе настання рівноможливих подій, ніякі дві з яких не можуть наступити одночасно, то ймовірність кожного із цих подій визначається як , а самі події називаються елементарними подіями або елементарними результатами.

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

Це і є формула класичної ймовірності, яку ми будемо надалі використати в наших дослідженнях.

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

2.4. Алгоритми генерації псевдовипадкових чисел

Першим алгоритмічний метод одержання рівномірно розподілених псевдовипадкових чисел запропонував Джон фон Нейман (один з основоположників кібернетики). Метод одержав назву «метод середини квадрата».

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

Наприклад:

(2.1)

і т.д.

Як видно метод середини квадрата досить добре повинен «перемішувати» попереднє число. Однак він має недоліки:

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

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

Властивість «зациклюватися» стосується всіх послідовностей, побудованих по рекурентній формулі x_i+1=f(x_i). Повторюваний цикл називається періодом. Довжина періоду в різних послідовностей різна. Чим період більше, тим краще.

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

Деякі вчені експериментували з методом середин квадратів на початку 50-х років. Працюючи із чотиризначними числами замість восьмизначних, Дж.Е. Форсайт випробував 16 різних початкових значень і виявив, що 12 з них приводять до циклічних послідовностей, що закінчуються циклом 6100. 2100, 4100, 8100, 6100…., у той час як два з них приводять до послідовностей, що вироджується в нульові.

Більш інтенсивні дослідження, головним чином у двійковій системі числення, провів Н.К. Метрополис. Він показав, що якщо використати 20-розрядне число, то послідовність випадкових чисел, отримана методом середин квадратів, вироджується в 13 різних циклів, причому довжина найбільшого періоду дорівнює 142.

Лінійний конгруентний метод

У цей час найбільш популярними генераторами випадкових чисел є генератори, у яких використається схема, запропонована Д.Г. Лехмером в 1949 році - лінійний конгруентний метод.

Виберемо чотири «чарівних числа»:

- m, модуль; 0 < m;

- а, множник; 0 < a < m;

- с, приріст; 0 < з < m;

- X₀, початкове значення; 0 < X₀ < m.

Потім одержимо бажану послідовність випадкових чисел (Х_n), маючи на увазі

X_n+1 = (а* X_n+ с) mod m, n > 0. (2.2)

Ця послідовність називається лінійною конгруентною послідовністю. Одержання залишків по модулю m почасти нагадує зумовленість, коли кулька попадає в осередок колеса рулетки. Наприклад, для m = 10 й X₀ = а = с = 7 одержимо послідовність:

7,6,9,0,7,6,9,0,…. (2.3)

Як показує цей приклад, така послідовність не може бути «випадковою» при деяких наборах чисел m, а, с і Х₀. У прикладі ілюструється той факт, що конгруентна послідовність завжди утворить петлі, тобто обов'язково існує цикл, що повторюється нескінченне число раз. Ця властивість є загальною для всіх послідовностей виду Х_n+1 = f(Х_n), де f перетворить кінцеву множину саме в себе.

Цикли, що повторюються, називаються періодами; довжина періоду послідовності (2.3) дорівнює 4. Безумовно, послідовності, які ми будемо використати, мають відносно довгий період.

Заслуговує на увагу випадок, коли с = 0, тому що числа, що генеруються, будуть мати менший період, чим при с ? 0. Ми переконаємося надалі, що обмеження с = 0 зменшує довжину періоду послідовності, хоча при цьому усе ще можливо зробити період досить довгим. В оригінальному методі, запропонованому Д.Г. Лехмером, с вибиралося рівним нулю, хоча він і допускав випадок, коли с ? 0, як один з можливих. Той факт, що умова с ? 0 може приводити до появи більш довгих періодів, був установлений В.Е. Томсоном (W. Е. Thomson) і незалежно від нього А. Ротенбергом (А. Rotenberg). Багато авторів називають лінійну конгруентну послідовність при с = 0 мультиплікативним конгруентним методом, а при с ? 0 - змішаним конгруентним методом. Для спрощення формул уводимо константу: b = а-1.

Можна відразу відкинути випадок, коли а = 1, при якому послідовність Х_n може бути представлена у вигляді Х_n = (Х₀ + с) mod m і поводиться явно не як випадкова послідовність. Випадок, коли а = 0 навіть гірше. Отже, для практичних цілей припускаємо, що:

а>2, b>1. (2.4)

Зараз можна узагальнити формулу (2.2):

(2.5)

де (n + k) - й член виражається безпосередньо через n-й.

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

При практичній реалізації лінійного конгруентного методу вигідно вибирати m = 2^e, де e - число біт у машинному слові, оскільки це дозволяє позбутися відносно повільної операції приведення по модулю. Машинне слово - машиннозалежна й платформозалежна величина, вимірювана в бітах або байтах, рівна розрядності регістрів процесора й/або розрядності шини даних.

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

Таблиця 2.1. Параметри лінійних конгруентних генераторів

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

(2.6)

де V₀ - непарне.

Псевдовипадкові числа обчислюються в такий спосіб:

(2.7)

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

Підставою для вибору параметрів генератора послужило те, що в рамках цілочисельної 32-бітної машинної арифметики операції по модулі 2³¹, зокрема, множення довільного числа на 65539 = 2¹⁶ + 3, виконуються ефективно. У той же час, такий вибір володіє й принциповим недоліком. Розглянемо наступне вираження (будемо думати, що всі операції виконуються по модулю 2³¹).

(2.8),

звідки, розкривши квадратичний співмножник, одержуємо:

(2.9),

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

(2.10)

Метод Фібоначчі із запізненням

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

У зв'язку із цим лінійний конгруентний алгоритм поступово втратив свою популярність і його місце зайняло сімейство алгоритмів Фібоначчі, які можуть бути рекомендовані для використання в алгоритмах, критичних до якості випадкових чисел. В англомовній літературі датчики Фібоначчі такого типу називають звичайно «Subtract-with-borrow Generators» (SWBG).

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

Один із широко розповсюджених датчиків Фібоначчі заснований на наступній ітеративній формулі:

 (2.11),

де Xk - речовинні числа з діапазону (0,1), a, b - цілі позитивні числа, називані лагами. Для роботи датчику Фібоначчі потрібно знати max {a, b} попередніх генерованих випадкових чисел. При програмній реалізації для зберігання генерованих випадкових чисел використається кінцева циклічна черга на базі масиву. Для старту датчику Фібоначчі потрібно max {a, b} випадкових чисел, які можуть бути генеровані простим конгруентним датчиком.

Лаги a й b - «магічні» й їх не слід вибирати довільно. Рекомендуються вибирати наступні значення лагів: (a, b)=(55,24), (17,5) або (97,33). Якість одержуваних випадкових чисел залежить від значення константи a. Чим воно більше, тим вище розмірність простору, у якому зберігається рівномірність випадкових векторів, утворених з отриманих випадкових чисел. У той же час, зі збільшенням величини константи a збільшується об'єм використовуваної алгоритмом пам'яті.

Значення (a, b) = (17,5) можна рекомендувати для простих додатків, що не використовують вектори високої розмірності з випадковими компонентами. Значення (a, b) = (55,24) дозволяють одержувати числа, задовільні для більшості алгоритмів, вимогливих до якості випадкових чисел. Значення (a, b) = (97,33) дозволяють одержувати дуже якісні випадкові числа й використаються в алгоритмах, що працюють із випадковими векторами високої розмірності. Описаний датчик Фібоначчі випадкових чисел (з лагами 20 й 5) використається в широко відомій системі Matlab.

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

 (2.12),

де е - число бітів у мантисі дійсного числа.

Алгоритм Блюма - Блюма - Шуба

Цей генератор псевдовипадкових чисел був запропонований в 1986 році Ленор Блюм, Мануелем Блюмом і Майклом Шубом.

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

(2.13)

де M = p*q є добутком двох більших простих p й q. На кожному кроці алгоритму вихідні дані виходять із x_n шляхом узяття або біта парності, або одного або більше найменш значимого біту x_n.

Два простих числа, p й q, повинні бути обоє порівнянні з 3 по модулю 4 (це гарантує, що кожне квадратичне відхилення має один квадратний корінь, що також є квадратичним відхиленням) і найбільший загальний дільник НЗД повинен бути малий (це збільшує довжину циклу):

(2.14)

Цікавою особливістю цього алгоритму є те, що для одержання x_n необов'язково обчислювати всі n-1 попередніх чисел, якщо відомо початковий стан генератора x₀ і числа p й q, n-не значення може бути обчислене «прямо» використовуючи формулу:

(2.15)

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

Вихор Мерсенна

Із сучасних ГПВЧ широке поширення одержав вихор Мерсенна, запропонований в 1997 році Мацумото й Нишимурой. Їхня робота ґрунтується на властивостях простих чисел Мерсенна (звідси назва) і забезпечує швидку генерацію високоякісних псевдовипадкових чисел.

Перевагами цього методу є колосальний період (219937-1), рівномірний розподіл в 623 вимірах (лінійний конгруентний метод дає більш-менш рівномірний розподіл від сили в 5 вимірах), швидка генерація випадкових чисел (в 2-3 рази швидше, ніж стандартні ГПВЧ, що використають лінійний конгруентний метод). Однак існують складні алгоритми, що розпізнають послідовність, породжувану за допомогою вихрячи Мерсенна як невипадкову. Це робить вихор Мерсенна невідповідним для використання в криптографії.

Вихор Мерсенна є вітковим регістром зрушення з узагальненою віддачею (twisted generalised feedback shift register, TGFSR). «Вихор» - це перетворення, що забезпечує рівномірний розподіл псевдовипадкових чисел в 623 вимірах. Тому кореляція між послідовними значеннями у вихідній послідовності алгоритму «Вихор Мерсенна» дуже мала.

Існують ефективні реалізації алгоритму «Вихор Мерсенна», що перевершують по швидкості багато стандартні ГПВЧ (зокрема, в 2-3 рази швидше лінійних конгруентних генераторів). Вихор Мерсенна реалізований у бібліотеці gLib і стандартних бібліотеках для PHP, Python і Рубі.

Генеровані алгоритмом «Вихор Мерсенна» псевдовипадкові числа успішно проходять тести DIEHARD, що говорить про їх гарні статистичні властивості.

2.5 Статистичні критерії оцінки якості алгоритмів

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

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

Теоретична статистика надає деякі кількісні міри випадковості. Існує буквально нескінченне число критеріїв, які можна використати для перевірки того, чи буде послідовність випадковою. Обговоримо критерії, на наш погляд, найбільш корисні, найбільш повчальні й найбільш пристосовані до обчислень на комп'ютерах.

Якщо критерії 1, 2,…, Т_п підтверджують, що послідовність поводиться випадковим образом, це ще не означає, загалом кажучи, що перевірка за допомогою Т_п+1 - го критерію буде успішною. Однак кожна успішна перевірка дає усе більше й більше впевненості у випадковості послідовності. Звичайно до послідовності застосовується біля напівдюжини статистичних критеріїв, і якщо вона задовольняє цим критеріям, то послідовність уважається випадковою (це презумпція невинності до доказу провини).

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

Тести Diehard - це набір статистичних тестів, заснованих на емпіричних критеріях, які призначені для виміру якості набору випадкових чисел. Вони були розроблені Джорджем Марсалья (George Marsaglia) протягом декількох років і вперше опубліковані на CD-ROM, присвяченому випадковим числам. Разом вони розглядаються як один з найбільш строгих відомих наборів тестів.

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

Дні народження (Birthday Spacings) - вибираються випадкові точки на великому інтервалі. Відстані між крапками повинні бути асимптотическі розподілені по Пуассону. Назва цей тест одержала на основі парадокса днів народження.

Парадокс днів народження - твердження, що якщо дано групу з 23 або більше людин, то ймовірність того, що хоча б у двох з них дні народження (число й місяць) збіжаться, перевищує 50%. Для групи з 60 або більше людин імовірність збігу днів народження хоча б у двох її членів становить більше 99%, хоча 100% вона досягає, тільки коли в групі не менш 366 чоловік (з урахуванням високосних років - 367).

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

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

Пересічні перестановки (Overlapping Permutations) - аналізуються послідовності п'яти послідовних випадкових чисел. 120 можливих перестановок повинні виходити зі статистично еквівалентною ймовірністю.

Ранги матриць (Ranks of matrices) - вибираються деяка кількість біт з деякої кількості випадкових чисел для формування матриці над {0,1}, потім визначається ранг матриці. Підраховуються ранги.

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

Мавпячі тести (Monkey Tests) - послідовності деякої кількості біт інтерпретуються як слова. Уважаються пересічні слова в потоці. Кількість «слів», які не з'являються, повинні задовольняти відомому розподілу. Назва цей тест одержала на основі теореми про нескінченну кількість мавп.

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

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

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

Підрахунок одиничок (Count the 1's) - уважаються одиничні біти в кожному з наступний або обраних байт. Ці лічильники перетвориться в «літери», і вважаються випадки «слів» з п'яти літер.

Тест на паркування (Parking Lot Test) - випадково розміщаються одиничні окружності у квадраті 100х100. Якщо окружність перетинає вже існуючу, спробувати ще. Після 12000 спроб, кількість успішно «припаркованих» окружностей повинне бути нормально розподіленою.

Тест на мінімальну відстань (Minimum Distance Test) - 8000 крапок випадково розміщаються у квадраті 10000х10000, потім знаходиться мінімальна відстань між будь-якими парами. Квадрат цієї відстані повинен бути експоненціально розподілений з деякою медіаною.

Тест випадкових сфер (Random Spheres Test) - випадково вибираються 4000 точок у кубі з ребром 1000. У кожній точці міститься сфера, чий радіус є мінімальною відстанню до іншої крапки. Мінімальний об'єм сфери повинен бути експоненціально розподілений з деякою медіаною.

Тест стиску (The Squeeze Test) - 231 множиться на випадкові дійсні числа в діапазоні (0,1) доти, поки не вийде 1. Повторюється 100000 разів. Кількість дійсних чисел необхідних для досягнення 1 повинне бути розподілено певним чином.

Тест пересічних сум (Overlapping Sums Test) - генерується довга послідовність на (0,1). Додаються послідовності з 100 послідовних дійсних чисел. Суми повинні бути нормально розподілені з характерною медіаною й сигмою.

Тест послідовностей (Runs Test) - генерується довга послідовність на (0,1). Підраховуються висхідні й спадні послідовності. Числа повинні задовольняти деякому розподілу.

Тест гри в кістки (The Craps Test) - грається 200000 ігор у кістки, підраховуються перемоги й кількість кидків у кожній грі. Кожне число повинне задовольняти деякому розподілу.

3. Дослідження методів тестування та оцінки стійкості паролів

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