Фізичні процеси та математичні процедури генерації ключів

Территория рекламы

Вступ

Невід’ємною складовою безпеки криптографічного захисту є безпека фізичних та математичних методів що покладені в основу систем генерації (виготовлення) ключової інформації.

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

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

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

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

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

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

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

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

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

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

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

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

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

Далі, нехай послідовність випадкових величин {xt} приймає лише дискретні значення, тобто для будь якого t випадкова величина xt{1,2, … ,n}.

Згідно з найбільш поширеним визначенням, дискретна рівномірно розподілена випадкова послідовність (РРВП) {xt, t1} це послідовність незалежних за сукупністю випадкових величин, що приймають будь яке значення i{1,2, … ,n} з ймовірністю P{xt=i}=1/n, де n потужність алфавіту послідовності.

Для двійкової РРВП (тобто n=2) маємо P{xt=0}=P{xt=1}=0.5

Досить легко перевірити, що РРВП має наступні властивості:

РРВП1.Її математичне очікування M(xt)=(n-1)/2, а дисперсія D(xt)=(n2-1)/12. Для двійкової РРВП: M(xt)=1/2 та D(xt)=1/3;

РРВП2.Для будь якого k та набору індексів t1,…,tk: має місце P(xt1,…,xtk)=1/n-k, тобто будь який k-мірний вектор з компонентами xt має рівномірний розподіл;

РРВП3.Будь яка підпослідовність з послідовності {xt, t1} (вибірка) також є РРВП;

РРВП4.Додавання за модулем n (modn) РРВП до будь якої незалежної від неї послідовності також є РРВП. Наприклад, в разі застосування шифру Вернама з РРВП у якості ключу ми маємо саме таку ситуацію, тому зашифроване повідомлення буде також РРВП;

РРВП5.РРВП є непередбачуваною, тобто для будь якого натурального l кількість інформації по Шеннону, яка міститься в раніше отриманому векторі Xl=(x1,…,xl) про наступний елемент xl+1, дорівнює нулю: I(xl+1/Xl)=0.

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

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

Аналогічні за суттю вимоги до двійкової періодичної послідовності створеної за допомогою ГПВД яку доцільно використовувати для формування ключових даних сформулював американський математик Соломон Голомб в своїх постулатах (ПГ1-ПГ3):

А саме, нехай Х={х1,....,хN} – двійкова послідовність, яка має деякий період Т: хi=хi+T для будь якого натурального i. Позначимо через:

n1 та n0 кількість одиниць і нулів цьому періоді відповідно: n1+n0=T,

n1(s) та n0(s) – кількість s- грам (s≥1), що складені з одиниць і нулів відповідно;

Х(d)={хjхj+d}, d{1,2,…,Т-1}, j=0,1,2,…. двійкова послідовність, що отримана у підсумку порозрядного додавання вихідної послідовності та її копії зі зсувом, що дорівнює натуральному числу d;

n1(d) та n0(d) – кількість одиниць і нулів у послідовності Х(d) відповідно;

CX(d)=(n1(d)-n0(d))/Т – характеристика, яка отримала назву функції автокореляції послідовності X;

В умовах введених позначень постулати Голомба мають наступний вид:

ПГ1. Кількість "1" в періоді не може відрізнятися від кількості "0" більше ніж на одиницю, тобто |n1n0|≤1.

ПГ2. Кількість серій з "1" и "0" довжини s≤[log2Т] повинні співпадати. При цьому серій довжини один повинно бути половина від загальної кількості, довжини два одна чверть, довжини три одна восьма тощо:

n1·2-s=n1(s)=n0(s)=n0·2-s, s=1,2,…,[log2Т]

ПГ3. Функція автокореляції повинна принімати лише два значення у той час коли параметр d змінює своє значення в інтервалі 0≤dТ1.

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

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

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

2. Загальні відомості щодо теорії випадкових процесів. Фізичні випадкові процеси для генераторів випадкових даних

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

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

Підсумовуючі результати цих наукових праць можливо з’ясувати, що в якості джерел випадкових процесів доцільно використовувати шумові сигнали, що породжені физическими процессами, такими как Броуновское движение (тепловой шум), дробовой эффект и радиоактивный распад.

В 1918 году Шоттки среди шумов, наблюдаемых в усилителях, выделил два источника шума, основанных на фундаментальных явлениях природы: тепловой и дробовой шум.

Тепловой шум определяется тепловым движением частиц вещества в проводнике, приводящим к флуктуациям плотности электронов. Тепловой шум порождается броуновским движением носителей электричества. Шумовой сигнал имеет нормальное распределение амплитуд, определяемое суммой очень большого числа элементарных источников напряжения. В формулировке Найквиста (1928 г.) идеальный резистор содержит генератор ЭДС, среднеквадратичное значение напряжения которого определяется как:

V2 = 4RkTB,

где R – сопротивление резистора, Ом; k – постоянная Больцмана равная 1.38 x 10-23 Дж / град. Кельвина; T – температура, град. Кельвина; B – полоса частот шумового сигнала, Гц.

Дробовой шум определяется флуктуациями тока, обусловленными дискретностью электрических зарядов. Дробовой шум порождается при преодолении потенциального барьера носителями электричества в вакууме или полупроводнике. Такой шум генерируют вакуумные диоды, резисторы при высоких температурах, обратно смещенные диоды с переходом Зенера (стабилитроны), газоразрядные приборы. Для стабилитронов и газоразрядных приборов характерно усиление выбросов тока дробового шума за счет эффекта лавинного пробоя. В соответствии с теорией Шоттки (1918 г.) средний квадрат флуктуаций тока диода определяется как:

I2 = 2eiB,

где e – заряд электрона, равный 1.6 x 10-19 Кл; i – величина постоянного тока, протекающего через прибор, А; B – полоса частот шумового сигнала, Гц.

Для частот, превышающих определенные значения, мощность теплового и дробового шума постоянна, вплоть до очень высоких частот. В практических случаях верхняя частота шума ограничена только свойствами приёмника (усилителя). Для теплового шума мощность изменяется в очень небольших, прогнозируемых пределах, в то время как мощность дробового шума зависит от многих факторов.

Распад радиоактивных элементов как источник шума далее не будет рассматриваются, ввиду эксплуатационных ограничений.

Должно быть обеспечено возможно близкое приближение распределения плотности вероятности значений шумового сигнала к нормальному. Это требование определяется предсказуемостью результатов последующих преобразований шумового сигнала в случайную последовательность чисел.

Должна быть обеспечена независимость отсчетов шумового сигнала при заданной частоте дискретизации или возможно близкое приближение спектральной плотности мощности к равномерной в диапазоне половины частоты дискретизации.

Физические генераторы получили широкое распространение после создания микропроцессоров, имеющие невысокую стоимость при условии достаточной производительности. На рис. 1 представлен физический генератор случайных данных ORB, реализованный компанией APA Consulting на микроконтроллере семейства PIC12C67X (8-ми контактный корпус SOIC размером 5.38.1мм).

Рис. 1. Генератор случайных чисел ORB

В основу работы данного генератора положен принцип измерения напряжения на конденсаторе, который заряжается и разряжается в соответствии с некоторым потоком бит.

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

В силу названных причин при построении программных и программно-аппаратных средств криптографической защиты информации широкое распространение получили генераторы ПСП

3. Генераторы псевдослучайных последовательностей

На практике одной из важнейших является следующая задача. Исходя из выше перечисленных и других свойств РРСП, необходимо определить, является ли конкретная последовательность реализацией РРСП. В дальнейшем, для краткости изложения, реализацию РРСП будем называть просто случайной последовательностью.

Конструктивний підхід к определению случайной последовательности предложили Блюм, Голдвассер, Микалли и Яо. Их определение считает последовательность случайной, если не существует полиномиального (вероятностного) алгоритма, который сможет отличить ее от чисто случайной. Такая последовательность называется полиномиально неразличимой от случайной или псевдослучайной.

Этот подход позволяет использовать для формирования псевдослучайных последовательностей (ПСП) детерминированные алгоритмы, реализуемые конечными автоматами. Хотя с математической точки зрения такие последовательности не случайны, так как они полностью определяются начальным заполнением, тем не менее, их практическое использование не дает никаких преимуществ криптоаналитику благодаря “неразличимости” со случайными. Поскольку этот подход представляется более конструктивным, остановимся на нем детальнее.

Случайные последовательности в смысле последнего определения также называют “случайными для всех практических применений”. Генераторы таких последовательностей, называют криптографически надежными (cryptographically strong) или криптографически безопасными (cryptographically secure). Псевдослучайность в данном случае есть не только свойство последовательности (или генератора), но и свойство наблюдателя, а точнее его вычислительных возможностей.

Для ПСП доказаны два важных утверждения:

Последовательность является псевдослучайной тогда и только тогда, когда она непредсказуема, т.е. выдерживает тестирование очередным битом. Это означает, что если даже известна часть последовательности любой длины, то при неизвестных начальном заполнении генератора и параметрах алгоритма генерации для получения очередного бита нельзя предложить алгоритм, существенно лучший простого угадывания или подбрасывания монеты.

Криптографически сильные генераторы существуют в том и только в том случае, если существуют легко вычислимые функции, но вычислительно сложно обратимые (односторонние функции - one-way functions). В этом случае каждому генератору ПСП можно поставить во взаимнооднозначное соответствие некоторую одностороннюю функцию, которая зависит от определенных параметров.

Наиболее простым датчиком псевдослучайных чисел является линейный конгруэнтный генератор (ЛКГ), который описывается рекуррентным уравнением вида Xn=(aXn-1+b) mod N, где X0 – случайное начальное значение, а – множитель, b – приращение, N – модуль.

Период выходной последовательности такого генератора не превышает N, максимальное значение достигается при правильном выборе параметров a,b, N, а именно, когда

числа N и b взаимнопросты: НОД(N,b)=1);

a-1 кратно любому простому p, делящему N;

a-1 кратно 4, если N кратно 4.

В [6] приведен список констант для ЛКГ, обеспечивающих максимальный период последовательности и, что не менее важно, соответствующие последовательности проходят статистические тесты.

Для реализации ЛКГ на персональных компьютерах с учетом их разрядной сетки нередко используется модуль N=231-12.14109. При этом наиболее качественные статистические свойства ПСП достигаются для константы a=397204094.

По сравнению с другими видами генераторов ПСП данный вид обеспечивает высокую производительность за счет малого числа операций для создания одного псевдослучайного бита.

Недостатком ЛКГ в плане их использования для создания поточных шифров является предсказуемость выходных последовательностей. Эффективные атаки на ЛКГ были предложены Joan Boyar, ей принадлежат методы атак на квадратичные Xn=(aXn-12+bXn-1+c)modN и кубические Xn=(aXn-13+bXn-12+cXn-1+d)modN генераторы.

Другие исследователи обобщили результаты работ Boyar на случай общего полиномиального конгруэнтного генератора. Stern и Boyar показали, как взломать ЛКГ, даже если известна не вся последовательность.

Wishmann и Hill, а позже Pierre L’Ecuger изучили комбинации ЛКГ. Результаты не являются более стойкими криптографически, но имеют большие периоды и лучше ведут себя на некоторых критериях случайности.

Регистры сдвига с линейной обратной связью (Linear Feedback Shift Registers - LFSR) включают собственно регистр сдвига и схему вычисления функции обратной связи (tap sequence) – см. рис. 12:

Поток

бит

n

∙∙∙

2

1

Рис. 2. Регистр сдвига с линейной обратной связью (LFSR)

На схеме содержимое регистра последовательность бит – сдвигается с приходом тактового импульса (clock pulse) на один разряд вправо. Бит самого младшего разряда считается выходом LFSR в данном такте работы. Значение самого старшего разряда при этом является результатом сложения по mod2 (функция XOR) разрядов обратной связи.

Теоретически, n-битный LFSR может сгенерировать псевдослучайную последовательность с периодом 2n-1 бит, такие LFSR называются регистрами максимального периода. Для этого регистр сдвига должен побывать во всех 2n-1 внутренних состояниях (2n-1, т.к. нулевое заполнение регистр сдвига, вызовет бесконечную последовательность нулей).

Напомним, что полином называется неприводимым, если он не может быть выражен как произведение других полиномов меньшей степени отличных от 1 и самого себя.

Примитивный полином степени n – это неприводимый полином, который делит , но не делит xd+1 для любого d: (2n-1d)

Теорема (без доказательства): Для того, чтобы LFSR имел максимальный период, необходимо и достаточно, чтобы полином, образованный из элементов обратной связи (tap sequence) плюс единица был примитивным полиномом по модулю 2. (на самом деле, примитивный полином – это генератор в данном поле).

Список практически применимых примитивных полиномов приведен в [3].

Например, примитивным полиномом является x32x7x5x3x2x1. Запись (32,7,5,3,2,1,0) означает, что, взяв 32-битный регистр сдвига и генерируя бит обратной связи путем сложения по mod2 7-го, 5-го, 3-го, 2-го и 1-го бита, мы получим LFSR максимальной длины (с 232-1 состояниями).

Заметим, если р(х) – примитивный полином, то xnp(1/x) – также примитивный.

Например, если полином (a,b,0) примитивный, то (a,a-b,0) – примитивный. Если полином (a,b,c,d,0) примитивный, то и (a,a-d,a-c,a-b,0) – примитивный и т.д.

Примитивные трехчлены особенно удобны, т.к. складываются только 2 бита регистра сдвига, но при этом они и более уязвимы к атакам.

LFSR – удобны для технической реализации, но имеют неприятные свойства. Последовательные биты линейно зависимы, что делает их бесполезными для шифрования. Даже если схема обратной связи неизвестна, то достаточно 2n выходных бит, чтобы определить ее.

Большие случайные числа, сгенерированные из последовательных битов LFSR, сильно коррелированы и иногда даже не совсем случайны. Тем не менее, LFSR достаточно часто используются в качестве элементов более сложных алгоритмов формирования шифрующей ключевой последовательности.

Существует еще ряд генераторов ПСП (в т.ч. генераторы чисел Фибоначчи), которые по ряду причин не нашли широкого применения в криптографических системах. Наиболее эффективные решения были получены на основе составных генераторов.

Идея построения составного генератора базируется на том факте, что комбинация двух и более простых генераторов ПСП, в случае правильного выбора объединяющей функции (в т.ч. mod 2, mod 232-1 и др.), дает генератор с улучшенными свойствами случайности, и, как следствие, с повышенной криптографической стойкостью.

В случае создания криптографически стойкого генератора ПСП просто решается вопрос создания потоковых шифров. Выход таких ПСП неотличим (точнее, должен быть неотличим) от РРСП. Два генератора всегда могут быть синхронно запущены из одного вектора начального состояния, который намного короче передаваемого сообщения, что выгодно отличает эту схему от шифра Вернама.

Известно 4 подхода к конструированию соответствующих генераторов:

1) системно-теоретический подход;

2) сложностно-теоретический подход;

3) информационно-теоретический подход;

4) рандомизированный подход.

Эти подходы различаются в своих предположениях о возможностях криптоаналитика, определении криптографического успеха и понятия надежности.

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

На основе такого подхода Рюппелем сформулирован следующий набор критериев для потоковых шифров:

Большой период выходной последовательности, отсутствие повторений;

Высокая линейная сложность, как характеристика нашего генератора через регистр LFSR минимальной длины, который может сгенерировать такой же выход;

Неотличимость от РРСП по статистическим критериям;

Перемешивание: любой бит ключевого потока должен быть сложным преобразованием всех или большинства бит начального состояния (ключа);

Рассеивание: избыточность во всех подструктурах алгоритма работы генератора должна рассеиваться;

Критерии нелинейности преобразований: в соответствии с некоторой метрикой расстояние до линейных функций должно быть достаточно большим, критерий лавинообразности распространения изменений в случае изменения одного бита и др.

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

Основная проблема подобных криптосистем заключается в том, что для них трудно доказать какие-либо факты об их криптостойкости, так как для всех этих критериев не была доказана их необходимость или достаточность. Потоковый шифр может удовлетворять всем этим принципам и все-таки оказаться нестойким, т.к. стойкость по отношению к заданному набору криптоаналитических атак ничего не гарантирует.

Примером удачного построения составного генератора с точки зрения повышения линейной сложности является каскад Голмана (рис. 3).

Каскад Голмана включает несколько регистров LFSR, причем тактирование каждого следующего LSFR управляется предыдущим так, что изменение состояния LFSR-(k+1) в момент времени t происходит, если в предыдущем такте t-1 выход LFSR-k равняется 1, и LFSR-(k+1) не меняет свое состояние в противном случае.

Если все LFSR – длины l, то линейная сложность системы с n регистрами равна l(2l-1)n-1.

LFSR-1

X(t)

LFSR-2

LFSR-3

Такт

Рис. 3. Каскад Голмана

Типовым решением для построения составного генератора может быть схема чередующегося старт-стопного генератора (Alternating Stop-and-Go Generator).

В этом генераторе (рис. 4) используется три регистра LFSR различной длины. LFSR-2 меняет состояние, если выход LFSR-1 равен 1; LFSR-3 меняет состояние в противном случае. Результат генератора есть сложение по mod 2 выходов регистров LFSR-2, LFSR-3.

LFSR-1

X(t)

LFSR-2

LFSR-3

Такт

Рис. 4. Чередующийся старт-стопный генератор

У этого генератора большой период и большая линейная сложность.

Применяя сложностно-теоретический подход, криптограф пытается доказать стойкость генератора используя теорию сложности. Основу решений при этом подходе составляют генераторы, базирующиеся на понятии однонаправленной функции.

Однонаправленную функцию f(x): D→R легко вычислить для всех x D, но очень трудно инвертировать для почти всех значений из R. Иначе, если V – вычислительная сложность получения f(x), а V* – вычислительная сложность нахождения f-1(x), то имеет место неравенство V*V. Нетрудно видеть, что кандидатом на однонаправленную функцию может быть степенная функция в некотором конечном поле f(x)=ax, где a,xGF(q) – поле Галуа из q элементов.

Нетрудно видеть, что умножение, за счет свойства ассоциативности, можно выполнить за меньшее, чем число x-1 шагов. Например, a9=a((a2)2)2, что позволяет вычислить искомую степень вместо восьми за четыре шага (вначале a2=a a, затем a4=a2 a2, a8=a4 a4 и, наконец, a9=a8 a).

Обратная операция – нахождение показателя степени по значению степенной функции (логарифмирование) в конечном поле пока не может быть решена лучше, чем с помощью оптимизированных методов перебора возможных вариантов. В случае большого размера поля (порядка 21024) эта задача при современном развитии компьютерной техники вычислительно неразрешима.

Примером соответствующего генератора может алгоритм RSA. Пусть параметр N=pq, где p,q – простые числа, начальное значение генератора x0N, e: НОД(e,(p-1)(q-1))=1.

xi+1=xeimod N

Результат генератора – наименьший значимый бит xi+1. Стойкость этого генератора эквивалентна стойкости RSA. Если N достаточно большое, то генератор обеспечивает практическую стойкость.

Другой пример генератора, построенного на сложностном подходе, предложен Blum, Blum и Shub (BBS). На данный момент это один из простых и эффективных алгоритмов. Математическая теория этого генератора – квадратичные вычеты по модулю n.

Выберем два больших простых числа p и q, дающих при делении на 4 остаток 3. Произведение npq назовем числом Блюма. Выберем х: НОД(n,x)=1. Найдем начальное значение генератора: x0=x2 mod n.

Теперь i-ым псевдослучайным числом является наименьший значимый бит xi, где xi=x2i-2 mod n.

Заметим, что для получения i-го бита, не требуется вычисления (i-1) состояния. Если мы знаем p,q, то мы можем его вычислить сразу: bi есть наименьшее значение бит:

Это свойство позволяет использовать BBS-генератор для работы с файлами произвольного доступа (random-access).

Число n можно распространять свободно, для того чтобы каждый абонент сети смог самостоятельно сгенерировать необходимые биты. При этом если криптоаналитик не сможет разложить на простые множители число n, он не сможет предсказать следующий бит, даже в вероятностном смысле, например, «с вероятностью 51% следующий бит равен 1».

Отметим; что генераторы, построенные на однонаправленных функциях, очень медленные, для их практической реализации необходимы специальные процессоры.

Следующие два подхода информационно-теоретический и рандомизированный не нашли широкого практического применения.

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

В случае рандомизированного подхода задача заключается в том, чтобы увеличить число бит, с которыми необходимо работать криптоаналитику (не увеличивая при этом ключ). Этого можно достичь путем использования больших случайных общедоступных строк. Ключ будет обозначать, какие части этих строк необходимо использовать для зашифрования и расшифрования. Тогда криптоаналитику придется использовать метод тотального перебора вариантов (грубой силы) на случайных строках.

Стойкость этого метода может быть выражена в терминах среднего числа бит, которые придется изучить криптоаналитику, прежде чем шансы определить ключ станут выше простого угадывания.

Ueli Maurer описал такую схему. Вероятность вскрытия такой криптосистемы зависит от объема памяти, доступного криптоаналитику (но не зависит от его вычислительных ресурсов).

Чтобы эта схема приобрела практический вид, требуется около 100 битовых последовательностей по 1020 бит каждая. Оцифровка поверхности Луны – один из способов получения такого количества бит.

В заключение отметим, что для построения генератора ПСП необходимо получить несколько случайных бит. Наиболее простой способ использовать наименьший значимый бит таймера компьютера.

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

Самый лучший способ получить случайное число – это обратиться к естественной случайности реального мира – шумы в результате переходных процессов в полупроводниковых диодах, тепловые шумы высокомных резисторов, радиоактивный распад и т.д. В принципе, элемент случайности есть и в компьютерах:

- время дня;

- загруженность процессора;

- время прибытия сетевых пакетов и т.п.

Проблема не в том, чтобы найти источники случайности, но в том, чтобы сохранить случайность при измерениях.

Например, это можно делать так: найдем событие, случающееся регулярно, но случайно (шум превышает некоторый порог). Измерим время между первым событием и вторым, затем между вторым и третьим. Если t1,2t2,3, то полагаем выход генератора равным 1; если t1,2<t2,3, то выход равен 0. Далее процесс продолжим.

Американский национальный институт стандартов (ANSI) разработал метод генерации 64-битных ключей при помощи DES-алгоритма (ANSI X9.17). Его основное назначение состоит в получении большого количества ключей для многократных сеансов связи. Вместо DES-алгоритма можно использовать любой другой стойкий алгоритм шифрования.

Пусть функция Е K (Р) осуществляет шифрование Р по DES-алгоритму на заранее заготовленном ключе К, который используется только для генерации секретных ключей. Пусть далее V 0 является начальным 64-битным значением, которое держится в тайне от противника, а Т iпредставляет собой отметку даты-времени, когда был сгенерирован i-й ключ. Тогда очередной случайный ключ R i вычисляется с помощью преобразования:

R i = Е К (Е К (Т i )  V i )

Чтобы получить очередное значение V i , надо вычислить

V i = Е К (Е К (Т i )  R i )

Существенной проблемой систем генерации случайных данных является наличие отклонений и корреляций в сгенерированной последовательности. Сами процессы могут быть случайными, но проблемы могут возникнуть в процессе измерений. Как с этим бороться?

1) Сложением по mod 2 двух независимых последовательностей: если случайный бит смещен к 0 на величину ε, то вероятность появления 0 может быть записана как P(0)=0.5+ε.

Сложение по mod 2: двух одинаково распределенных независимых бит даст: P(0)=(0.5+ε)2+(0.5-ε)2=0.5+2ε2, сложением четырех бит получим: P(0) =0.5+8 ε4 и т.д. Процесс сходится к равновероятному распределению 0 и 1.

2) Пусть распределение единиц и нулей в последовательности есть величины p и q соответственно. Воспользуемся методом кодирования: рассмотрим два бита:

- если это одинаковые биты, то отбросим их и рассмотрим следующую пару;

- если биты различны, то в качестве выходного значения возьмем первый бит.

Данный метод позволяет решить проблему смещения, сохранив свойства случайности источника (с некоторой потерей в объеме данных).

Потенциальная проблема обоих методов в том, что при наличии корреляции между соседними битами данные методы увеличивают смещение. Один из способов избежать этого – использовать различные источники случайных чисел.

Факт наличия смещения у генератора случайных чисел, вообще говоря, не означает его непригодность. Например, пусть для генерации 112-битного ключа для алгоритма «тройной» DES (Triple DES) используется генератор со смещением к нулю: P{xt=0}=0.55, Р{xt=1}=0.45 (энтропия Н=0.99277 на один бит ключа по сравнению с 1 для идеального генератора).

В этом случае нарушитель может оптимизировать процедуру тотального перебора ключей за счет поиска ключа начиная с наиболее вероятного значения (00…0) и заканчивая наименее вероятным (11…1). Вследствие наличия смещения, можно ожидать нахождения ключа в среднем за 2109 попыток. Если бы смещения не было, то потребовалось бы 2111 попыток. Выигрыш есть, но несущественный.

4. Статистическое тестирование ПСП и генераторов

С учетом изложенного, будем считать последовательность символов некоторого алфавита псевдослучайной в узком смысле, если никакой алгоритм из некоторого набора полиномиальных алгоритмов не может ее отличить от случайной.

Алгоритмы этого набора будем называть тестами (критериями) на случайность, а процесс проверки последовательности – тестированием. Если тест не смог отличить последовательность от случайной, то будем говорить, что последовательность проходит или выдерживает, данный тест. В противном случае, будем говорить, что тест отклоняет последовательность.

Итак, вопрос о проверке случайности последовательности сводится к вопросу построения соответствующего набора тестов. Для этого вначале необходимо определить принцип их работы, а именно: каким образом тест должен принимать одни последовательности и отклонять другие?

Одним из ответов на этот вопрос является проверка наличия у заданной последовательности некоторого свойства, характерного для любых случайных последовательностей.

Например, пусть элементы последовательности выбираются независимо и равновероятно из множества Z2. В этом случае последовательность из n единиц, плохо подходит на роль случайной для практических применений, хотя вероятность ее появления равна 2-n, как и любой другой реализации из множества .

Однако она не будет типовой с точки зрения появления в РРСП (достаточно большой длины) существенного дисбаланса между числом единиц и нулей. В тоже время, предпочтительно считать типовой последовательность, у которой количество единиц и нулей отличаются несущественно.

В дальнейшем тесты, построенные на свойствах встречаемости элементов последовательности, будем называть частотными, так как они проверяют распределение частот встречаемости и выявляют его отклонение от равновероятного распределения (в т.ч.: критерии χ2, максимального правдоподобия и максимальной частоты).

Возвращаясь к работе теста, заметим, что его результатом всегда будет принятие или отклонение гипотезы Н0, которая предполагает, что конкретная последовательность является последовательностью независимых, равномерно распределенных случайных величин. Ее альтернативой будем считать сложную гипотезу Н1, которая включает все возможные неравномерные распределения элементов последовательности, так и все возможные виды зависимостей между ними.

Получив результаты тестирования некоторой последовательности, мы делаем вывод о ее происхождении с достаточно большой (но меньше 1) вероятностью, которая зависит от параметров теста. С каждым тестом связаны два параметра:

α – вероятность ошибки 1-го рода - вероятность отклонить истинно случайную последовательность, т.е. принять гипотезу Н1, в то время как верна гипотеза Н0. Величина α также называется уровнем значимости теста;

β – вероятность ошибки 2-го рода - вероятность принять неслучайную последовательность за случайную, т.е. принять гипотезу Н0 при условии, что верна гипотеза Н1.

Уровень значимости задается до начала работы теста, при этом он определяет относительную часть чисто случайных последовательностей, которые не обладают свойствами, наличие которых проверяет тест. Обычно α выбирается из практических соображений. Если вероятность поверяемой гипотеза достаточно высока, то уровень значимости выбирается маленьким (10-2-10-3).

Параметр β зависит от α и длины последовательности n так, при фиксированном α с ростом n величина β уменьшается. Поскольку гипотеза Н1 сложная, то из множества тестов нельзя выбрать единый тест, который соответствует равномерно наиболее мощному критерию, т.е. такой, который при заданном уровне значимости α минимизирует значение β.

В ходе работы теста, исходя из тестируемой последовательности, вычисляется некоторая величина U, называемая статистикой. Будем говорить, что тест принимает последовательность, если U≤Uα, где – называется пороговым значением статистики. Тест называется двусторонним, если при его проверке используется неравенство |U|≤Uα.

Величина находится из соотношения (U)=1-, где функция распределения вероятностей, α – уровень значимости теста. Поскольку функция – возрастающая, то вместо сравнения U и можно сравнивать (U) и (U). Значение PU=1-(U) называется P-величиной.

Итак, последовательность считается случайной, если PU≥α.

Величины α и PU являются вероятностями того, что случайная последовательность будет иметь значение статистики больше чем и U соответственно.

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

(1)

Где vi – частота встречаемости символа iZm в последовательности знаков шифрованного текста, N=0+…+m-1 – длина тестируемой последовательности, (p0,…,pm-1) – вектор вероятностей, соответствующий гипотезе Н0. Доказано, что статистика (1) при N имеет распределение Пирсона с m-1 степенями свободы.

В случае РРСП имеем (p0,…,pm-1)=(1/m,…,1/m), пусть величина квантиль распределения 2 с m-1 степенью свободы, соответствующий уровню значимости , т.е.:

Если для выборки выполняется неравенство:

(2)

то принимается гипотеза Н0 о случайном характере последовательности, в противном случае – гипотеза Н0 отвергается.

Отметим, что согласие экспериментальных данных с гипотезой о наличии у последовательности определенного свойства не свидетельствует о противоречии этих же данных с другой гипотезой. На основе наблюдения реализации последовательности с помощь статистических критериев нельзя доказать справедливость той или иной гипотезы, а можно лишь утверждать, что результаты наблюдений не противоречат данной гипотезе.

Рассмотрим основные требования к набору тестов. Ясно, что набор должен содержать некоторое минимально необходимое множество тестов, которое определяется будущим применением тестируемых последовательностей и может быть различным в каждом конкретном случае.

Например, набор тестов, рекомендованный Национальным институтом стандартов США NIST для тестирования двоичных последовательностей [5], включает 16 тестов (в т.ч. тесты: частотный монобитный; частотный блочный; тесты серий и длинных серий единиц; ранга случайной {0,1}-матрицы и др.).

Большинство тестов из набора NIST предназначены для тестирования двоичных последовательностей длиной от 103 –106, однако некоторые из них могут использоваться для тестирования последовательностей длиной от 102 элементов (монобитный и блочный частотные тесты, тест серий, тест серий максимальной длины, тест частот v-грамм с перекрытием и др.). Можно создать аналоги тестов этого набора для тестирования последовательностей элементов из произвольного алфавита.

Количество тестов в некотором их наборе определяется исходя из так называемой общей ошибки 1-го рода, т.е. той части случайных последовательностей, которые не пройдут хотя бы один из тестов.

Общая ошибка 1-го рода A(n,) находится для заданных ошибок 1-го рода каждого из тестов при условии их независимости. Если для всех тестов задана одно значение , то вероятность того, что случайная последовательность не пройдет, по крайней мере, один тест из набора равна:

Для заданной величины А количество тестов определяется из уравнения:

Заметим, что с ростом n величина А стремится к 1:

а потому количество тестов не должно быть чрезмерно большим.

Пример. Если в каждом из 16 тестов из набора, рекомендованного NIST, ошибка 1-го рода равна 0.01, то A(n,)=0.15, т.е. около 15% чисто случайных последовательностей не пройдет хотя бы один из тестов набора.

Как уже было отмечено, тестированию подлежат:

криптографические свойства конкретных последовательностей;

свойства генератора, используемого для создания случайных последовательностей.

Для статистики наиболее существенной особенностью любой последовательности является ее длина. На практике отдельно рассматриваются вопросы тестирования последовательностей “большой” и “малой” длины. Основной причиной дифференцированного подхода к этим двум случаям является тот факт, что свойства случайной последовательности становятся тем более выразительными, чем больше ее длина.

Считается, что минимальная длина последовательности для частотных тестов должна быть в 5-10 раз больше объема алфавиту. В таком случае при условии равномерного распределения символов последовательности вероятность того, что каждый символ встретится, по меньшей мере, 1 раз близка к единице.

Действительно, в этих условиях вероятность того, что какой-то символ не встретился ни разу, чрезвычайно мала:

Другие тесты могут предъявлять еще более жесткие требования к длине последовательности.

Поскольку, любая подпоследовательность РРСП также является РРСП, наряду с тестированием всей реализации необходимо тестировать ее разные подпоследовательности. Эти подпоследовательности должны выбираться с помощью некоторых правил, причем так, чтобы символ, который выбирается, не зависел бы от своего значения. В частности, нельзя выбирать подпоследовательность, которая состоит только из нулей.

Правила выбора подпоследовательностей могут быть следующими:

каждый j-ый элемент исходной последовательности;

каждый элемент, перед которым встречается некоторая фиксированная комбинация символов;

элементы, номера мест которых определяются некоторой последовательностью, независимой от данной и т.д.

Тестирование генераторов случайных последовательностей (чисел) состоит из двух этапов:

тестирование достаточного количества (103) последовательностей с помощью подобранного набора тестов;

обработка полученных результатов.

Для генератора случайных последовательностей должны выполняться следующие соображения:

если последовательность испытывается тестом, для которого задан уровень значимости α, то с вероятностью α последовательность не пройдет этот тест. Например, при α=0.01 в среднем 1 из 100 последовательностей не пройдет тест;

на выходные последовательности генератора должны иметь равномерное распределение соответствующих им значений PU.

Методика NIST обработки результатов тестирования генераторов предполагает следующие действия:

Вычисление пропорции последовательностей, которые прошли тест: Пусть было протестировано k последовательностей, из них k прошли тест. Тогда пропорция равняется k/k. Если уровень значимости теста равен α, то должно выполняться неравенство:

(1)

Проверка равномерности распределения P-величин:

Подсчитываются числа: Fi – количество P-величин, принадлежащих интервалу [0.1(i-1),0.1i), где i=1,…,10, после чего вычисляется статистика:

Находится значение PT=igams(4.5,0.52), где igams – неполная гамма-функция; вычисляемая по формуле:

, где

Если выполняется неравенство

PT≥0.0001,

(2)

то P-величины считаются равномерно распределенными.

Генераторы, для которых выполняется (1), (2), по терминологии NIST [5] называются одобренными (approved).

Генератор со свойствами (1) и (2) в зависимости от набора тестов может быть достаточно хорош для формирования гаммы однократного использования и других криптографических приложений.

Заключна частина

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

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

← Предыдущая
Страница 1
Следующая →

Скачать

ПАК_Лекция_Т3(Л3).docx

ПАК_Лекция_Т3(Л3).docx
Размер: 158.7 Кб

Бесплатно Скачать

Пожаловаться на материал

Характеристики випадкових та псевдовипадкових послідовностей. Методи формування ключової інформації. Фізичні випадкові процеси у генераторах випадкових даних. Методи вирівнювання характеристик ГВД. Принципи побудови генераторів псевдовипадкових чисел. Статистичне тестування псевдовипадкових послідовностей і генераторів.

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Дифференциалды психология

Жануарлар мен адамға ортақ жүйке жүйесінің қасиеттері. Гиппократ пен Павловтың типологияларының ортақтығы және айырмашылығы.

Энергоэффективность в строительстве

Сокращение расходов ТЭР при проектировании. Энергосберегающие мероприятия при разработке генеральных планов

Курсовая работа по экономическому анализу

В связи с переходом от директивно управляемой экономики к рыночной возникла необходимость в управлении предприятием как субъектом рыночных отношений.

Теория государства и права. Часть 2

Природные ресурсы и условия, понятия, классификация

С точки зрения потребностей общества все тела и силы природы могут быть условно подразделены на две группы: непосредственно участвующие в материальном производстве и сфере нематериальных услуг (природные ресурсы) и все остальные (обычно относимые к природным условиям).

Сохранить?

Пропустить...

Введите код

Ok