Генераторы случайных последовательностей и потоковые шифры

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Датчики истинно случайных чисел
Генераторы псевдослучайных последовательностей
Генераторы псевдослучайных последовательностей с добавлением истинной случайности
Потоковые алгоритмы шифрования

У Г А Т У
Датчики случайных чисел
Уфимский государственный авиационный технический университет
В лекции рассмотрена задача генерации двоичных случайных данных
? как сгенерировать небинарные случайные данные («число от 0 до 99»)
Вариант 1. Сгенерировать 7 случайных бит (число от 0 до 127) и вычислить значение по модулю 99. Плохой вариант: вероятность выпадения 10 вдвое больше, чем вероятность выпадения 90
Вариант 2 (предпочтительный). генерировать 7 случайных бит, пока не выпадет число в промежутке от 0 до 99.

У Г А Т У
Датчики истинно случайных чисел
Уфимский государственный авиационный технический университет
Повторить сгенерированную последовательность невозможно
Наиболее распространенное применение – генерация ключей
Недостаток – зачастую невозможно сгенерировать быстро много случайных чисел
Существуют тесты на случайность последовательности:
Наиболее известные наборы – NIST и DIEHARD
Если последовательность можно сжать без потери данных – она неслучайна
Примеры источников случайных данных:
Специализированные электронные элементы - шумовые диоды
Временные интервалы между нажатиями на клавиатуры (могут быть неслучайными из-за правил обработки нажатий)
Пиксели зашумленного изображения, напр. фото лунной поверхности
Результаты измерения некоторых физических величин
Иррациональные математические константы (?,?,√2 и т.д.)
Из получаемых чисел берутся биты на несколько позиций младше младших значащих

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Датчики истинно случайных чисел
Генераторы псевдослучайных последовательностей
Конгруэнтные генераторы
Сдвиговые регистры с обратной связью
Генератор Блюм-Блюм-Шуба
Генераторы псевдослучайных последовательностей с добавлением истинной случайности
Потоковые алгоритмы шифрования

У Г А Т У
Генераторы ПСП
Уфимский государственный авиационный технический университет
Вся последовательность (гамма) определяется некоторым начальным блоком
Каждый следующий блок вычисляется на основе предыдущего
Гамма имеет конечную длину – период; после достижения периода гамма зацикливается
Криптографический ГПСП – по сути «хеш-функция наоборот»
Аргумент - двоичный код фиксированной длины (секретный ключ); значение - двоичный код произвольной длины
По любому фрагменту ПСП нельзя определить ни аргумент, ни остальные части ПСП
Криптостойкость, вычислительная сложность

У Г А Т У
Линейные конгруэнтные генераторы
Уфимский государственный авиационный технический университет

У Г А Т У
Сдвиговые регистры с обратной связью
Уфимский государственный авиационный технический университет
Dn-1
Dn-2
D0
…
…
F
Ключ или синхропосылка
Псевдослучайная последовательность

У Г А Т У
Сдвиговые регистры с обратной связью
Уфимский государственный авиационный технический университет

У Г А Т У
Сдвиговые регистры с обратной связью
Уфимский государственный авиационный технический университет

У Г А Т У
Генератор Блюм-Блюм-Шуба
Уфимский государственный авиационный технический университет

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Датчики истинно случайных чисел
Генераторы псевдослучайных последовательностей
Генераторы псевдослучайных последовательностей с добавлением истинной случайности
FORTUNA
Потоковые алгоритмы шифрования

У Г А Т У
ГПСП с добавлением энтропии
Уфимский государственный авиационный технический университет
Применяется, если нужно быстро сгенерировать много непредсказуемых случайных данных
Пример: чтобы создать пару ключей алгоритма RSA, нужно сгенерировать порядка мегабайта случайных данных
Данные с датчика истинно случайных чисел используются для перезапуска ГПСП
Если злоумышленник получит временный доступ к внутреннему состоянию ГПСП, он сможет восстановить только часть ПСП
ПСП непредсказуема и потому не может применяться для гаммирования
*Когда речь идет о таких генераторах, понятие «энтропия» обозначает истинно случайные данные.
В других областях информатики у этого понятия более сложное определение.

У Г А Т У
FORTUNA
Уфимский государственный авиационный технический университет
Нильс Фергюссон и Брюс Шнайер, 2003
Три программных модуля:
Генератор ПСП
Аккумулятор энтропии
Установщик начального значения
В ходе работы системы периодически сохраняет истинно случайные данные в файл
При загрузке системы данные из этого файла становятся начальным числом генератора

У Г А Т У
FORTUNA
Уфимский государственный авиационный технический университет
Генератор ПСП
Может использоваться любой блочный шифр со 128-битным блоком и 256-битным ключом
Параметры, задающие внутреннее состояние генератора:
К – ключ, 256 бит
с – счетчик блоков, 128 бит
с* - нонс, генерируемый на основе счетчика, 128 бит
Инициализация генератора при первом запуске
К=0; с=0;
Обновление ключа при получении энтропии
\\ S – энтропия (истинно случайные данные)
K = SHA2-256( SHA2-256(K||S) );
c = c + 1;
Вычисление нонса
с* = NONCE(c); \\ порядок байт в с меняется на противоположный

У Г А Т У
FORTUNA
Уфимский государственный авиационный технический университет
Генератор ПСП
Генерация n блоков псевдослучайных данных
r = NULL;
K0 = NULL;
для i от 1 до n+2
c* = NONCE(c);
BLOCK = Ш(c*,K);
c = c + 1;
если i < n+1
то r= r||BLOCK
иначе K0=K0||BLOCK
конец
K = K0

У Г А Т У
FORTUNA
Уфимский государственный авиационный технический университет
Аккумулятор энтропии
Энтропия поступает из разных источников числом до 256
Каждый источник записывает энтропию в один из 32-х пулов (P[0]…P[31])
(Источник – программа, отслеживающая случайный процесс, а пул - область памяти, куда записываются случайные данные)
Запись энтропии от одного события производится только в один пул
Каждое новое событие источник записывает в новый по порядку пул
Генератор обновляется, когда объем энтропии, накопленной пулом P[0] достигнет 128 бит, но не раньше чем через 100 миллисекунд после прошлого обновления
Запись полученной энтропии в пул
Поскольку используются не сами случайные данные, а хэш-функция от них, в памяти пула достаточно хранить хэш-функцию от заполненных блоков и последний недозаполненный блок

У Г А Т У
FORTUNA
Уфимский государственный авиационный технический университет
Аккумулятор энтропии
Инициализация пулов
для i от 0 до 31 P[i]=NULL;
j=0; \\ количество произведенных записей энтропии в генератор
Обновление генератора истинно случайными данными
// t – время, прошедшее с прошлого обновления, мс
ОБРАБОТКА СОБЫТИЯ ( LENGTH(P0)>127 И t>10 ) S = NULL; j = j + 1;
для i от 0 до 31
если j mod 2^i != 0 то BREAK;
S = S || SHA2-256 (SHA2-256(P[i]));
P[i] = NULL
конец

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Датчики истинно случайных чисел
Генераторы псевдослучайных последовательностей
Генераторы псевдослучайных последовательностей с добавлением истинной случайности
Потоковые алгоритмы шифрования
А5
RC4
Salsa20

У Г А Т У
А5
Уфимский государственный авиационный технический университет
Используется в GSM для шифрования трафика между телефоном и базовой станцией
A5/0 – шифрование не применяется
А5/1, А5/2 – поточные алгоритмы с длиной ключа 64 бита
С современной точки зрения эти алгоритмы не криптостойки, однако представляют интерес как наиболее защищенные схемы на LFSR; теоретически по аналогии с этими схемами можно создать LFSR-шифры, криптостойкие в современном понимании
A5/3 – применяется блочный алгоритм KASUMI

У Г А Т У
А5/1
Уфимский государственный авиационный технический университет
3 LFSR, выход алгоритма равен XOR их выходов
19 бит, отводная последовательность {5,2,1,0}, 10-й тактовый бит
22 бита, отводная последовательность {1,0}, 11-й тактовый бит
23 бита, отводная последовательность {15,2,1,0}, 12-й тактовый бит
Сигнал синхронизации
f = MA(t1,t2,t3) – мажоритарная функция тактовых битов соответствующих регистров
если ti = f, то i-й регистр сдвигается
на каждом такте сдвигаются либо 2, либо 3 регистра

У Г А Т У
А5/1
Уфимский государственный авиационный технический университет
Режим работы
Данные шифруются по кадрам
В начале обработки кадра все регистры обнулены
этап 1. 64 такта - помимо отводной последовательности выход каждого регистра складывается с ключом
этап 2. 22 такта - помимо отводной последовательности выход каждого регистра складывается с номером кадра
этап 3. 100 холостых тактов
этап 4. 114 тактов - передача 114 бит от Алисы Бобу
этап 5. 114 тактов – передача 114 бит от Боба Алисе

У Г А Т У
А5/2
Уфимский государственный авиационный технический университет
Отличия от А5/1
По другому определяются синхроимпульсы
Дополнительный LFSR – 17 бит, отводная последовательность {5,0}
t1,t2,t3 – это 10-й, 3-й и 7-й биты данного LFSR
Выход алгоритма определяется как XOR
Трех основных регистров
Мажоритарной функции от 12-го, 14-го и 15-го битов первого регистра
Мажоритарной функции от 9-го, 13-го и 16-го битов второго регистра
Мажоритарной функции от 13-го, 16-го и 18-го битов второго регистра
На первом холостом такте в 3-й, 7-й и 10-й биты дополнительного регистра записываются единицы

У Г А Т У
RC4
Уфимский государственный авиационный технический университет
Разработан в 1987
До 1994 был секретен, затем опубликован анонимно
Длина ключа от 1 до 255 байт
Самый простой по структуре из получивших широкое применение современных симметричных шифров
Первые 3072 элемента гаммы рекомендуется генерировать вхолостую
В алгоритме не задан параметр IV
Каждый ключ можно использовать только 1 раз
Либо IV конкатенируется с ключом перед инициализацией таблицы

У Г А Т У
RC4
Уфимский государственный авиационный технический университет
Принцип работы алгоритма:
Используется динамическая таблица элементов гаммы, записываемая в байтовый массив S[0],…,S[255]; в ней содержатся все возможные значения, которые может принимать 1 байт
На этапе инициализации производится перестановка элементов таблицы, зависящая от ключа
При генерации гаммы, каждый новый элемент берется из таблицы, после чего производится перестановка таблицы

У Г А Т У
RC4
Уфимский государственный авиационный технический университет
Инициализация
\\ К0[0]…K0[k-1] – секретный ключ длиной k байт, К[0]…K[255] – байтовый массив
n = 0; j=0;
ДЛЯ i = 0:255
S[i] = i;
K[i] = K0[n]; n = (n + 1) mod k; \\ в К записывается ключ, при необходимости повторяясь
КОНЕЦ
ДЛЯ i = 0:255
j = (j + S[i] + K[i]) mod 256;
S = S[i]; S[i] = S[j]; S[j] = S; \\ S[i] и S[j] меняются местами
КОНЕЦ

У Г А Т У
RC4
Уфимский государственный авиационный технический университет
Генерация одного байта гаммы
\\ i и j – переменные, в которые перед началом генерации записываются нули
i = (i + 1) mod 256;
j = (j + S[i]) mod 256;
S = S[i]; S[i] = S[j]; S[j] = S; \\ S[i] и S[j] меняются местами
t = (S[i] + S[j]) mod 256;
Г[m] = S[t]; \\ m – порядковый номер элемента гаммы

У Г А Т У
Salsa20
Уфимский государственный авиационный технический университет

У Г А Т У
Salsa20
Уфимский государственный авиационный технический университет