Другие предметы \ Алгоритмические основы криптографии

Методика статистичного тестування: Технічний звіт ІІТ – 001-2004, страница 7

Обчислюємо значення

. (50)

Значення для кожного x має бути більше від 0.01.

Рекомендована довжина послідовності: .

Примітка . На справді, стан x має приймати значення від до . Розробники керівництва НІСТ, вибрали іншу формулу, виграли у простоті, але програли (хоча зовсім не багато) у точності.

3.16. Перевірка випадкових відхилень-2 (Random Excursions Variant Test)

Даний тест є розширенням попереднього.

Нехай - двійкова послідовність довжини n. Перетворимо її у послідовність Х: (тобто 1®1, 0 ® -1). Cформуємо послідовність:

. (51)

Cформуємо послідовність:

(52)

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

Будемо вважати, що стан будь якого не нульового елементу х блоку може приймати одно із значень : (-9), (-8), (-7),...8, 9, тобто .

Нехай J – загальна кількість блоків та - кількість появ станів х у всіх J блоках.

Обчислюємо значення для кожного х

. (53)

Значення для кожного x має бути більше від 0.01.

Рекомендована довжина послідовності: .

Примітка . Як і у попередньому тесті розробники керівництва НІСТ спростили значення x. На справді, стан x має приймати значення від до .

4. Математичне обґрунтування тестів

4.1.Частотний тест

Основною ідеєю тесту є використання нульової гіпотези: у послідовності незалежних випадкових величин з розподілом Бернуллі (Х чи ε, де Х = 2ε – 1, так що S_n = X₁ + … + X_n = 2(ε₁ + … + ε_n) - n) імовірність появи 1 складає ½. Відповідно до класичної теореми Лапласа, для досить великого числа іспитів розподіл біноміальної суми, нормалізованої по , близько наближений до стандартного нормального розподілу. Даний тест використовує апроксимацію оцінки близькості частки 1 до ½. Результати всіх наступних тестів спираються на результати проходження цього основного тесту.

Даний тест отриманий з центральної граничної теореми для випадкового блукання, S_n = X₁ + … + X_n... Відповідно до центральної граничної теореми,

(54)

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

Відповідно до тесту, заснованому на статистиці , обчислюється розглянута величина |s(obs)| = |X₁ + … + X_n| /, після чого рахується відповідна Р-величина, рівна . Тут erfc є (додатковою) функцією помилки

Приклад.

Вхід: e = 110010010000111111011010101000100010000101101000110

0001000110100110001001100011001100010100010111000,

n = 100.

Тест:

s₁₀₀ = n₁ – n₀ = 42 – 58 = -16,

- тест пройдений.

4.2.Частотний тест в середині блоку

Метою тесту є виявлення відхилень частки «1» від ½ усередині під послідовностей, що не перекриваються, на які розбивається вхідна послідовність. Для оцінки відхилення використовується критерій .

Малі P - значення вказують на великі відхилення від рівної пропорції одиниць і нулів принаймні в одному з блоків. Рядок 0 і 1 (чи 1 і -1) розділений на множину непересічних блоків. Для кожного блоку обчислюється пропорція одиниць. Статистика хі-квадрат порівнює пропорції блоку з ідеалом ½. Статистика заснована на розподілі хі-квадрат зі ступенями свободи, рівними кількості блоків.

Параметрами цього тесту є М і N, так що n = МС, тобто, послідовність розбивається на N блоків, кожен довжиною М. Для кожного з цих блоків імовірність появи «1» оцінюється шляхом спостереження відповідних частот «1», , і = 1, ..., N. Сума