Простейший и наиболее эффективный генератор, использующий сложностно-теоретический подход, в честь своих авторов называется Blum, Blum, and Shub. Мы сократим его название до BBS, хотя иногда его называют генератором с квадратичным остатком [193].
Теория генератора BBS использует квадратичные остатки по модулю п (см. раздел 11.3). Вот как он работает.
Сначала найдем два простых числа, р и q, которые конгруэнтны 3 modulo 4. Произведение этих чисел, п, является целым числом Блюма (Blum). Выберем другое случайное целое число х, взаимно простое с п. Вычислим
x0 = x2 modH
Это стартовое число генератора.
Теперь можно начать вычислять биты. i'-ым псевдослучайным битом является младший значащий бит х„ где
x^xjmo&n
Самым интригующим свойством этого генератора является то, что для получения г'-го бита не нужно вычислять предыдущие i- биты. Если вам известны р и q, вы можете вычислить г'-ый бит непосредственно.
Ь, - это младший значащий бит х„ где х, = дЛг'^СМХ»-!))
Это свойство означает, что вы можете использовать этот криптографически сильный генератор псевдосл у-чайных чисел в качестве потоковой криптосистемы для файла с произвольным доступом .
Безопасность этой схемы основана на сложности разложения п на множители. Можно опубликовать и, так что кто угодно может генерировать биты с помощью генератора. Однако пока криптоаналитик не сможет разложить п на множители, он никогда не сможет предсказать выход генератора - ни даже утверждать что-нибудь вроде: "Следующий бит с вероятностью 51 процент будет единицей".
Более того, генератор BBS непредсказуем в левом направлениии непредсказуем в правом направлении. Это означает, что получив последовательность, выданную генератором, криптоаналитик не сможет предсказать ни следующий, ни предыдущий бит последовательности . Это вызвано не безопасностью, основанной на каком-то никому не понятном сложном генераторе битов, а математикой разложения п на множители.
Этот алгоритм медленен, но есть способы его ускорить. Оказывается, что в качестве псевдослучайных битов можно использовать несколько каждого х,. В соответствии с [1569, 1570, 1571, 35, 36] если п - длинах,, можно использовать log2H младших значащих битов х,. Генератор BBS сравнительно медленный и не подходит для потоковых шифров. Однако для высоконадежных приложений, таких как генерация ключей, этот генератор лучше многих других.
17.10 Другие подходы к проектированию потоковых шифров
При информационно-теоретическом подходе к потоковым шифрам предполагается, что криптоаналитик о б-ладает неограничеными временем и вычислительной мощностью. Единственным практически реализованным потоковым шифром, защищенным от такого противника, является одноразовый блокнот (см. раздел 1.5). Так как писать биты в блокноте не очень удобно, его иногда называют одноразовой лентой.На двух магнитных лентах, на одной для шифрования, а на другой для дешифрирования, должен быть записан идентичный поток ключей. Для шифрования просто выполняется XOR открытого текста с битами ленты. Для дешифрирования
выполняется XOR шифротекста с битами другой, идентичной ленты. Один и тот же поток ключей нельзя использовать дважды. Так как биты потока ключей действительно случайны, предсказать поток ключей нево з-можно. Если сжигать ленты после использования, то безопасность будет абсолютной (при условии, что у кого-то другого нет копии ленты).
Другой информационно-теоретический потоковый шифр, разработанных Клаусом Шнорром ( Claus Schnorr) предполагает, что криптоаналитик имеет доступ только к ограниченному числу битов шифротекста [1395]. Результаты являются слишком теоретическими results и не имеют практического значения. Подробности можно найти [1361, 1643,1193].
С помощью рандомизированного потокового шифра криптограф пытается сделать решение проблемы, сто я-щей перед криптоаналитиком, физически невозможным. Для этого, сохраняя небольшой размер секретного ключа, криптограф значительно увеличивает количество битов, с которыми придется иметь дело криптоанал и-тику. Это может быть сделано за счет использования при шифровании и дешифрировании большой опублик о-ванной случайной строки. Ключ же указывает, какие части строки будут использованы при шифровании и д е-шифрировании. Криптоаналитику, не знающему ключа, придется перебирать случайные комбинации частей строки. Безопасность такого шифра можно выразить с помощью среднего числа битов, которые должен пров е-рить криптоаналитик прежде, чем вероятностьопределить ключ значительно улучшится по сравнению с вероя т-ностью простого угадывания.
Шифр "Pun ван Винкль "
Джеймс Массей (James Massey) и Ингемар Ингемарсон (Ingemar Ingemarsson) предложили шифр Тип ван Винкль" [1011], названный так, потому что получатель, чтобы начать дешифрирование, должен получить 2П битов шифротекста. Алгоритм, показанный на 7-й, прост в реализации, гарантировано безопасен и совершенно непрактичен. Просто выполните XOR открытого текста с потоком ключей и задержите поток ключей на время от 0 до 20 лет - точная задержка является частью ключа. По словам Массея: "Можно легко доказать, что вражескому криптоаналитику для вскрытия шифра понадобятся тысячи лет, если кто-то согласится подождать с чт е-нием открытого текста миллионы лет." Развитие этой идеи можно найти в [1577, 755].
| Канал (мульти-плекси-рованный) | ||||||
| Поток случайных | —► | Задержка | ||||
| битов | 1 | |||||
| Поток битов | Задержка | —► | tr | L Открытый is текст | ||
| открытого текста | V * | >L | ||||
0-20 лет (Длина засекречена и зависит от ключа)