Методи симетризації та селекції поліпшення якості ПВП

Date: 2015-10-07; view: 349.

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

Це, наприклад, вибір підпослідовностей, додавання за модулем 2 частини бітів блоку, видалення підпослідовностей бітів з блоків, тощо.

Наприклад, в українському стандарті на цифровий підпис ДСТУ 4145-2002, для побудови рандомізаторів застосовується генератор випадкових двійкових послідовностей побудований за схемою ANSI X9.17 з використанням алгоритму ГОСТ 28147-89.

При цьому черговий біт такої послідовності є правим крайнім розрядом відповідного блоку довжини 64, що за ANSI X9.17 міститься у ПВП цілком.

Для порушення зв'язку ПВП з первісним алгоритмом, або для поліпшення первісної ПВП, можна застосувати т. зв. алгоритми симетризації та селекції.

Метод симетризації полягає у наступному.

Нехай - первісна двійкова псевдовипадкова послідовність з незалежними елементами, в якій порушено умову рівноймовірності:

; , де , .

За допомогою наступних (або еквівалентних) перетвореннь первісна послідовність перетворюються до виду: , якщо ; , якщо ; - у інших випадках.

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

З послідовності відкинемо значення . В результаті, отримуємо двійкову послідовність . Підрахуємо розподіл ймовірностей елементів послідовності .

Оскільки , то після відкидання значень отримуємо двійкову послідовність з рівноймовірним розподілом.

Зауважимо, що цей результат використовує умову щодо попарної незалежності елементів первісної послідовності.

Крім того, чим більше відхиляється від 0,5, тим більше скорочується довжина .

Але у випадку, коли первісна послідовність є результатом шифроперетворення, обидва ці недоліки практично відсутні.

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

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

Елементи послідовності називаються селекторами.

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

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

Приклад 1. Стискуючий генератор SG (Shrinking Generator), що генерує двійкову ПВП.

У цьому генераторі послідовності і породжуються двійковими регістрами зсуву з лінійним зворотним зв'язком і відповідно.

Теорема 8.1Нехай мінімальні поліноми регістрів і примітивні, , , а періоди послідовностей і - взаємно прості числа.

Тоді період і лінійна складність послідовності, що генерується, задовільняють умовам: , .

Приклад 2. Послідовність генерується так званим старт-стоп генератором. У цьому генераторі задіяні три РЗЛЗЗ і . Регістр рухається рівномірно і керує рухом регістрів , : якщо після просування його вихід дорівнює 1, то просувається , інакше, просувається .

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

Приклад 3. Нерівноймовірна послідовність селекторів.

Послідовність отримується з рекурентного співідношення виду , , з початковим станом . Елементи - двійкові числа розміром 32 біти. Операція означає, що спочатку числа додаються звичайним образом. Далі результат розглядається як 33-х розрядне число, яке розбивається на старший розряд і молодші 32 розряди, які становлять значення . Значення є черговим бітом послідовності селекторів .

Приклад 4. У якості і вибираємо послідовності з прикладів 2 і 3, або послідовності, що відповідно отримані з генератора ANSI X9.17 і генератора Блюма-Мікалі.