Характеристики випадкових та псевдовипадкових послідовностей

ЛЕКЦІЯ

з навчальної дисципліни

____ Прикладні аспекти криптології ____

(назва навчальної дисципліни)

Тема: ___№3 «Фізичні процеси та математичні процедури генерації ключів» ___________

(номер і назва теми)

Заняття _______________________ №3, лекція ____________________________________

(номер і назва заняття)

Навчальний час – _2_ годин (и).

Для студентів інституту (факультету) __________________________

___________________________________________________________

Навчальна та виховна мета: 1. Вивчити питання моделювання під час аналізу криптосистем

2. Навчити майбутніх спеціалістів (магістрів) системно підходити до оцінки стійкості криптосистем.

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

Обговорено та схвалено на засіданні кафедри “___” _________ 20___ року Протокол №____

Київ – 2014

Зміст

Вступ.

1. Характеристики випадкових та псевдовипадкових послідовностей.

2. Методи формування ключової інформації.

3. Фізичні випадкові процеси у генераторах випадкових даних. Методи вирівнювання характеристик ГВД.

4. Принципи побудови генераторів псевдовипадкових чисел.

5. Статистичне тестування псевдовипадкових послідовностей і генераторів.

Заключна частина.

Л I Т Е Р А Т У Р А

1. Гулак Г.М., Мухачев В.А., Хорошко В.О., Яремчук Ю.Є. Основи криптографічного захисту інформації: підручник, Вінниця, ВНТУ, 2012, с.48-71.

2. Харин Ю.С., Берник В.И., Матвеев Г.В., Математические основы криптологии, Минск, БГУ, 1999, С.319.

3. Фомичев В.М., Дискретная математика и криптология. – М: ДИАЛОГ-МИФИ, 2003. С.138-152,318–337.

4. Гулак Г., Ковальчук Л. Різні підходи до визначення випадкових послідовностей// Науково-технічний збірник «Правове, нормативне та метрологічне забезпечення системи захист інформації в Україні». – Київ. – 2001. – №3 – С. 127 133.

5. Иванов М.А., Криптографические методы защиты в компьютерных системах и сетях. – М.: КУДИЦ-ОБРАЗ, 2001. С.39– 83.

6. NIST Special Publications 800-22, A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications, 2000.

7. Кнут Д. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы. – М.: МИР, 1977. – 235 С.

Завдання на самостійну роботу

1. Знайти у Положенні про порядок постачання ключів до засобів КЗІ (Наказ Адміністрації Держспецзв’язку від 20.07.2007 №114) умови постачання ключів до засобів КЗІ та законспектувати їх.

2. Самостійно розрахувати ймовірності зустрічаємості бітів у двійковій послідовності яка є результатом порозрядного додавання двох інших двійкових послідовностей, одна з яких має ймовірності зустрічаємості одиниці та нуля P та Q відповідно, інша ‑ p та q відповідно.

Вступ

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

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

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

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

Характеристики випадкових та псевдовипадкових послідовностей

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

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

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

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

Таким чином, необхідно відповісти на три тісно пов’язаних між собою питання:

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

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

- як встановити, що деяка фіксована послідовність задовольняє вимогам випадковості та рівномірності в сенсі вимог ключових даних?

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

Далі, нехай послідовність випадкових величин { x_t }приймає лише дискретні значення, тобто для будь якого t випадкова величина x_t Î{1,2, …, n }.

Згідно з найбільш поширеним визначенням, дискретна рівномірно розподілена випадкова послідовність (РРВП) { x_t, t>1 } ‑ це послідовність незалежних за сукупністю випадкових величин, що приймають будь яке значення i Î{1,2, …, n } з ймовірністю P { x_t=i } = 1/ n, де n ‑ потужність алфавіту послідовності.

Для двійкової РРВП (тобто n= 2) маємо P { x_t= 0} =P { x_t= 1} = 0.5

Досить легко перевірити, що РРВП має наступні властивості:

РРВП1. Її математичне очікування M (x_t) = (n- 1) / 2, а дисперсія D (x_t) = (n²- 1) / 12. Для двійкової РРВП: M (x_t) = 1/2 та D (x_t) = 1 / 3;

РРВП2. Для будь якого k та набору індексів t₁,…,t_k: має місце P(x_t1,…,x_tk)= 1/ n^-k, тобто будь який k -мірний вектор з компонентами x_t має рівномірний розподіл;

РРВП3. Будь яка підпослідовність з послідовності { x_t, t> 1} (вибірка) також є РРВП;

РРВП4. Додавання за модулем n (mod n)РРВП до будь якої незалежної від неї послідовності також є РРВП. Наприклад, в разі застосування шифру Вернама з РРВП у якості ключу ми маємо саме таку ситуацію, тому зашифроване повідомлення буде також РРВП;

РРВП5. РРВП є непередбачуваною, тобто для будь якого натурального l кількість інформації по Шеннону, яка міститься в раніше отриманому векторі X_l= (x₁,…,x_l) про наступний елемент x_l+1, дорівнює нулю: I (x_l+1/X_l) = 0.

Пристрій, що реалізує РРВП, називається генераторомРРВП.

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

Аналогічні за суттю вимоги до двійкової періодичної послідовності створеної за допомогою ГПВД яку доцільно використовувати для формування ключових даних сформулював американський математик Соломон Голомб в своїх постулатах (ПГ1-ПГ3):

А саме, нехай Х= { х₁,....,х_N } – двійкова послідовність, яка має деякий період Т: х_i=х_i+T для будь якого натурального i. Позначимо через:

n₁ та n₀ ‑ кількість одиниць і нулів цьому періоді відповідно: n₁+n₀ = T,

n₁^(s) та n₀^(s) – кількість s - грам (s≥1),що складені з одиниць і нулів відповідно;

Х (d) = { х_j Å х_j+d }, dÎ { 1,2,…,Т-1 }, j=0,1,2,…. ‑ двійкова послідовність, що отримана у підсумку порозрядного додавання вихідної послідовності та її копії зі зсувом, що дорівнює натуральному числу d;

n₁ (d) та n₀ (d) – кількість одиниць і нулів у послідовності Х (d) відповідно;

C_X (d) = (n₁ (d) -n₀ (d)) /Т – характеристика, яка отримала назву функції автокореляції послідовності X;

В умовах введених позначень постулати Голомба мають наступний вид:

ПГ1. Кількість "1" в періоді не може відрізнятися від кількості "0" більше ніж на одиницю, тобто | n _1‑ n ₀|≤1.

ПГ2. Кількість серій з "1" и "0" довжини s≤[ log₂Т ] повинні співпадати. При цьому серій довжини один повинно бути половина від загальної кількості, довжини два ‑ одна чверть, довжини три ‑ одна восьма тощо:

n₁·2^-s=n₁^(s)=n₀^(s)=n₀·2^-s, s=1,2,…, [ log₂Т ]

ПГ3. Функція автокореляції повинна принімати лише два значення у той час коли параметр d змінює своє значення в інтервалі 0≤ d ≤ Т‑ 1.

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

Послідовність, яка задовольняє постулатам Голомба, називається псевдошумовою послідовністю (ПШП) або псевдовипадковою послідовністю (ПВП).

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