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

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

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

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

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

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

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

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

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

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

Далі, нехай послідовність випадкових величин {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 (modn)РРВП до будь якої незалежної від неї послідовності також є РРВП. Наприклад, в разі застосування шифру Вернама з РРВП у якості ключу ми маємо саме таку ситуацію, тому зашифроване повідомлення буде також РРВП;

РРВП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.

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

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

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