Основи теорії захисту інформації: Конспекти лекцій № 1-32 (Введення в криптологію, основні поняття і визначення. Проблеми теорії і практики криптології), страница 22

Довжина серій	Необхідний інтервал
1 2 3 4 5 6	2267-2733 1079-1121 502-748 223-402 90-223 90-223

Тест довжин серій

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

Лекція №17

Випадкові послідовності

1.  Основні визначення випадкової послідовності.

2.  Методи і засоби перевірки на випадковість.

Стійкість у визначеній мері залежить від джерела ключів. Теорія Симонсона і теорія Шенона базується на тім, що:

                                     ключі породжуються джерелом випадково, (1)

                                     порівняно ймовірно, незалежно й однорідно

Усі теоретичні твердження й оцінки справедливі в (1). Якщо умова не виконується, то стійкість може знижуватися до неприпустимих меж.

                                                                    Рис.17.1

1.   Визначення Шенона

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

                                                               (2)

Можна показати, що extremum (2) досягається за умови, що:

                                              - порівняно ймовірні

                                                                                                               (3)

Якщо ключі породжуються порівняно ймовірно, то для КРА складність максимальна.

                                                                                           (4)

                                                                                                (4)

lо – відстань однозначності

                                                        

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

2.    Визначення Холмогорова

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

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

.     Визначення Блюма

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

                                                      

 - ПСП наближається до еталона.

                                                        Приклад:

                                                                 (6)

4 підхід

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

Метод тестування на основі

Критерій  дозволяє перевірити погодженість гіпотетичних ймовірностей.

                                                              

 які визначаються над вибіркою з n - незалежних чи спостережень подій.

При використанні критерію спочатку визначається статистика .

                                                                     (7)

де m- кількість інтервалів розбивки

Ухвалення рішення здійснюється на основі обчислення деякого граничного значення для рівня значимості a.

                                                              (8)

 l - кількість ступенів волі

 - граничне значення стандартного нормального розподілу

Гіпотеза відкидається, якщо:

                                                                                             (9)

Генератор псевдовипадкової послідовності на базі многомодульного перетворення

Генерується