Материалы что дал Мухачев / Материалы что дал Мухачев-1 / Генератори_2014

Побудова криптографічно стійких генераторів ПВП на основі блокових шифрів

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

- наближення стат. властивостей ПВП до властивостей випадкових послідовностей,

- неможливість відновлення секретних параметрів алгоритму

- неможливість продовження відрізків ПВП у довільному напрямку, без знання початкового стану генератора.

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

Криптографічно стійкі генератори ПВП з використанням блокових шифрів можуть формуватися:

- на основі перешифрування детермінованої послідовності;

- на основі перешифрування послідовності з випадковим параметром;

- на основі поліпшення (модифікації) вихідної послідовності шифра;

- комбінуванням згаданих методів.

Наприклад, блоковий шифр перешифровує на ключі послідовність блоків виду , де - довільно вибраний (несекретний блок). ПВП складається з блоків , секретність основана на секретності ключа.

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

Генератор випадкових послідовностей ANSI X9.17 (США).

Генератор ANSI X9.17 у якості односпрямованої функції застосовує блоковий шифр 3DES.

Генератор залишається стійким, якщо 3DES замінити будь-яким стійким блоковим криптоалгоритмом.

3DES здійснює перешифрування , яке використовує алгоритм DES з двома ключами: для зашифрування , та розшифрування , .

Рис. Генератор ANSI X9.17

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

Крім того, на кожному циклі роботи генератора використовується блок , довжини 64 біти, пов’язаний із значенням часу початку цикла , що вимірюється з великою точністю. (фізична випадковість). Можливість фіксування моменту часу передбачена у процесорах ЕОМ.

ПВП на основі RSA

Параметрами генератора є параметри криптосистеми RSA, за винятком секретного ключа, тобто і . Генератор видає двійкову послідовність довжини , виходячи із випадкового секретного значення : .

Алгоритм генерації: , .

Генератор квадратичних лишків BBS

Позначення генератора пов’язано з прізвищами авторів (Blum, Blum, Shub). Параметри генератора: секретні великі нерівні прости числа , такі що, ; число ; - випадковий секретний лишок за модулем .

Алгоритм.

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

2. Обчислення елементу ПВП з номером : .

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

Генератор Блюма-Мікалі

Цей генератор оснований на складності дискретного логарифмування.

Нехай - велике просте число, таке, що дискретний логарифм у обчислювально неможливий, а елемент великого порядку.

Вибираємо випадково секретне початкове значення .

Алгоритм побудови ПВП наступний.

Обчислити . Якщо , то , інакше, .

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

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

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

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

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

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

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

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

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

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

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

Наприклад, в ДСТУ 4145-2002, для побудови рандомізаторів застосовується генератор випадкових двійкових послідовностей побудований за схемою ANSI X9.17 з використанням алгоритму ДСТУ ГОСТ 28147:2009. При цьому черговий біт такої послідовності є лише правим крайнім розрядом відповідного блоку довжини 64, що за ANSI X9.17 міститься у ПВП цілком.