В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел od return r Как вы, наверное, уже догадались, E ( K, C ) — это функция шифрования блочного шифра, на вход которой подаются ключ K и блок открытого текста C . Вначале функция GenerateBlocks проверяет, не равно ли значение C нулю (это бы означало, что на вход данного генератора еще никогда не пода- валось начальное число). Перед началом цикла переменной r присваивается пустая строка, после чего к ней поочередно присоединяется каждый следу- ющий подсчитанный блок. Строка, сформированная таким образом, и будет выходным значением функции. 10.4.4 Генерация случайных данных Функция PseudoRandomData генерирует случайные данные по запросу пользователя генератора. Она позволяет получить псевдослучайную строку длиной до 2 20 байт и гарантирует, что после выполнения запроса любая ин- формация о сгенерированных данных будет уничтожена. функция PseudoRandomData вход: G Состояние генератора; изменяется этой функцией. n Количество байт случайных данных, которое необходимо сгенерировать. выход: r Псевдослучайная строка длиной n байт. Ограничим длину выходной строки, чтобы уменьшить статистиче- ское отклонение от истинно случайных данных. Убедимся также, что заданная длина строки не является отрицательной. assert 0 ≤ n ≤ 2 20 Сгенерируем выходные данные. r ← первые − n − байт ( GenerateBlocks ( G , d n/ 16 e )) Изменим значение ключа, чтобы избежать возможной дискредита- ции этих данных в будущем. K ← G enerateBlocks ( G , 2) return r Как видите, результат функции PseudoRandomData генерируется пу- тем вызова функции G enerateBlocks . Единственное различие между ними состоит в “усечении” результата функции PseudoRandomData до нужного количества байт. (Оператор d . . . e — это оператор округления сверху.) По- сле этого мы генерируем еще два блока данных, чтобы сформировать новый ключ. Когда старый ключ K будет уничтожен, никто не сможет повторно 10.5. Аккумулятор 189 вычислить значение r . Если функция PseudoRandomData не сохранит ко- пию значения r и очистит область памяти, в которой хранилось это значение, то по завершении работы функции у генератора просто не останется путей для утечки какой-либо информации об r . Именно поэтому даже последующий взлом генератора, если таковой когда-нибудь произойдет, никак не повлияет на секретность предыдущих выходных данных. Он будет угрожать лишь без- опасности будущих выходных данных — проблема, решением которой должен заниматься аккумулятор. Как уже отмечалось, объем данных, которые может возвратить функция PseudoRandomData , ограничен. Мы не будем описывать оболочку, которая сможет возвращать случайные строки большего размера путем многократно- го вызова функции PseudoRandomData . Обратите внимание: увеличивать максимальный размер выходных данных, получаемых за один вызов функ- ции, не следует, поскольку это увеличит статистическое отклонение от ис- тинно случайной последовательности. Выполнение повторяющихся вызовов функции PseudoRandomData не приведет к снижению эффективности. До- полнительные расходы состоят лишь в том, что на каждый мегабайт сгене- рированных случайных данных система генерирует еще 32 байта случайных данных (для формирования нового ключа) и выполняет пересчет подклю- чей блочного шифра. Для всех предложенных нами блочных шифров такие расходы являются незначительными. 10.4.5 Скорость работы генератора Генератор Fortuna, описанный в предыдущих разделах, является крип- тографически сильным генератором псевдослучайных чисел в том смысле, что он преобразует начальное число в псевдослучайную строку произволь- ной длины. Скорость работы генератора Fortuna практически равна скоро- сти работы используемого блочного шифра. В системах с PC-совместимыми процессорами генерация одного байта псевдослучайных данных для больших запросов занимает менее 20 циклов работы процессора. Таким образом, наш генератор может легко применяться в качестве замены большинства библио- течных функций генерации псевдослучайных чисел. 10.5 Аккумулятор Аккумулятор собирает истинно случайные данные из различных источни- ков энтропии и применяет их для обновления начального числа генератора. |