12. Цифровий підпис Ель-Гамаля.

Лінійна двійкова рекурентна послідовність. У криптосхемах потокових шифрів широко застосовуються криптовузли, засновані т.з. регістрах зрушення із зворотним зв'язком. Найбільш простим вузлом є т.з. двійковий регістр зрушення з лінійними зворотними зв'язками (РЗЛЗЗ|), що генерує рекурентну послідовність вигляду . Безпосередньо для генерації гамми РЗЛЗЗ| не підходять. На практиці застосовуються комбінації залежних РЗЛЗЗ|, що взаємно впливають на формування своїх послідовних заповнень. Ця послідовність є періодичною. Максимальний період рівний числу . За рахунок вибору параметрів рекуренти| можна добитися максимального значення періоду для будь-якого n.

Генератор псевдовипадкових чисел ANSI X9.17. Генератори псевдовипадкових чисел призначені для отримання числових послідовностей, у яких розподіли вибірок елементів поводяться як аналогічні вибірки з сукупності з рівноімовірним і незалежним розподілом вірогідності. У криптографії застосовуються т.з. криптографічний стійкі датчики псевдовипадкових чисел (КСД|). Так називаються генератори ПВЧ|, що використовують секретні параметри. Для таких генераторів потрібна властивість непередбачуваності: відрізок вихідної послідовності щодо великої довжини не може бути продовжений як вперед (управо) так і назад (наліво) без знання ключа. Одним з прикладів КСД| є генератор, рекомендований стандартом ANSI X9.17, використовуваний, зокрема, при здійсненні платіжних операцій.Генератор ПВЧ| ANSI X9.17, що використовує алгоритм DES.

DES

T(i)

V(i+1)

DES c ключом К



DES

V(i)

DES



R(i)

На виході генератора формуються два блоки розмірів в 64 біта: псевдовипадковий блок R(i), що є елементом формованої псевдовипадкової послідовності і псевдовипадковий блок V(i+1), використовуваний для роботи в наступному циклі.

Вхідними даними генератора, постійними протягом сеансу генерації, є К – ключ шифрування і блок V(0) - секретне початкове значення. Крім того, в кожному циклі роботи генератора використовується блок T(i), пов'язаний із значенням дати-часу початку циклу i .Очевидно, дану схему можливо пристосувати для використання будь-якого блокового шифру.У Українському стандарті на цифровий підпис ДСТУ| 4145-2002 генератор випадкових двійкових послідовностей побудований по схемі ПВЧ| ANSI X9.17 з використанням криптоалгоритму ГОСТ 28147-89. Черговий біт b(i) такої послідовності є правим крайнім розрядом відповідного блоку R(i).

13. Лінійна двійкова рекурентна послідовність у якості гами. Генератор псевдовипадкових чисел ansi x9.17.

При використанні асиметричних криптосистем виникає необхідність побудови надвеликих псевдовипадкових простих чисел.

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

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

Існує два типу критеріїв простоти: детерміновані і імовірнісні. Детерміновані тести дозволяють довести, що тестоване число – просте.

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

Детерміновані тести корисніші, коли необхідно побудувати велике просте число, а не перевірити простоту, скажімо, деякої єдиного числа.

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

Прикладом імовірнісного тесту є тест на основі малої теореми Ферма. Ця теорема стверджує, що якщо - просте, то для всіх , взаємно простих з , виконується умова (нерівність Ферма): . Таким чином, якщо умова теореми Ферма не виконана хоч би для одного числа в інтервалі , то - складове.

Тест на основі малої теореми Ферма полягає в наступному.

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

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

Можна показати, що якщо існує (взагалі кажучи, невідоме) основа , по якій не є псевдопростим, то при повторенні тесту Ферма вірогідність -кратного виконання нерівності рівна . В цьому випадку вірогідність помилки тесту прямує до нуля із збільшенням .

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

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