Проектування генератора істинно випадкових чисел для криптографічних додатків
І. Коряков
Введення
У багатьох криптографічних додатках потрібні великі об'єми і великі швидкості генерації якісної ключової інформації.
Створення високоякісних швидкісних генераторів випадкових чисел (ГВЧ) є непростим завданням, рішення якої має на увазі виконання ряду вимог на всіх етапах життя такого генератора, починаючи від формування Технічного завдання і закінчуючи його експлуатацією протягом усього терміну служби.
У даній роботі наведена спроба формулювання сукупності вимог до високопродуктивним генераторам випадкових чисел, що породжує істинно випадкові ключові дані для криптографічних додатків.
1. Наводиться приклад проектування ГВЧ.
Гіпотеза про генераторі випадкових чисел
Генератор випадкових чисел (далі мається на увазі генератор істинно випадкових чисел, ГІСЧ) - це об'єкт, що виробляє послідовність нулів і одиниць, який володіє наступними двома властивостями: випадковістю і непередбачуваністю.
Під випадковістю розуміється равновероятное поява нулів і одиниць на виході такого генератора в незалежності від його попередніх або наступних значень.
Непередбачуваність ГІСЧ означає неможливість визначити значення його виходу (або передбачити з вірогідністю, відмінної від 0.5) по відомим попереднім або наступним значенням.
У криптографічних додатках формуються найбільш жорсткі критерії близькості послідовностей до випадкових, так як стійкість криптографічних алгоритмів безпосередньо пов'язана з якістю генератора.
Актуальним є питання про визначення якості генератора випадкових чисел, ступеня його відповідності ідеалу.
У класичних роботах по генераторам випадкових чисел [1,2,3] розглядається перевірка так званої Нуль Гіпотези (H 0). В даному випадку вона полягатимуть в твердженні, що тестований генератор випадковий. Поєднаної з нуль гіпотезою є Альтернативна Гіпотеза (H a), яка стверджує, що генератор не випадкова.
Для перевірки цих гіпотез зазвичай оцінюють правдоподібність вибірки випадкових чисел, отриманих за допомогою конкретного генератора. Нуль гіпотеза відкидається, якщо випробовувана вибірка потрапляє в область малого правдоподібності. При цьому можливі чотири варіанти:
1) Гіпотеза вірна і вона приймається
2) Гіпотеза невірна і вона відкидається
) Гіпотеза вірна і вона відкидається (помилка першого роду)
) Гіпотеза невірна і вона приймається (помилка другого роду)
В даному випадку небезпечними є помилки другого роду, так як вони дозволяють невипадковому генератору успішно пройти тест на випадковість. Тому мінімізація такої помилки є однією з головних завдань, для якої відомі ефективні рішення [1,2,3].
. Методи граничного зменшення помилки другого роду
Автор звертає увагу на підхід, укорінений в області створення генераторів випадкових чисел: питання проектування генераторів і їх тестування розглядаються роздільно, без їх взаємної ув'язки. Тобто, хтось розробляє і потім пред'являє генератор СЧ, а, потім, хтось намагається визначити, чи дійсно цей генератор є випадковим, спостерігаючи тільки його вихідні послідовності.
Питання перевірки Нуль Гіпотези непростий, він навіть не зовсім чітко визначений з філософської точки зору. Зокрема, може бути пред'явлений ГВЧ з відмінними статистичними характеристиками вихідних послідовностей, а потім раптом виявиться детермінована складова цих послідовностей, не виявляються статистичними тестами. Знання цієї складової може, наприклад, призвести до зниження стійкості криптографічного алгоритму.
Нижче пропонується розгляд перевірки Нуль Гіпотези не тільки за оцінкою правдоподібності вибірок, але й по безлічі інших факторів, що впливають на ймовірність підтвердження Нуль Гіпотези і обумовлених глобально, впродовж терміну життя генератора, починаючи від формування принципів його побудови і кінчаючи визначення якості функціонування в процесі генерації випадкових чисел.
Декомпозиція Нуль Гіпотези полягає в заміні однієї гіпотези про істинність ГВЧ на декілька більш просто перевіряються гіпотез.
Наприклад, гіпотеза «даний генератор істинно випадковий» заміняється низкою гіпотез: «джерело випадковості має необхідні характеристики», «перетворення в бітову п...
