Выходом генератора является i, если х,- < (p - i)/2, и 0 в противном случае.

Если p достаточно велико, чтобы вычисление дискретных логарифмов mod p стало физически невозможным, то этот генератор безопасен. Дополнительные теоретические результаты можно найти в [i627, 986, 985, i237,

896, 799].

Этот генератор RSA [35, 36] является модификацией [200]. Начальные параметры - модуль N, произведение двух больших простых чисел p и q, и целое число e, относительно простое с (p-i)(q-i), а также стартовое случайное число x0, меньшее N.

x,-+i = xe; mod N

Выход генератора представляет собой младший значащий бит x,. Безопасность этого генератора опирается на сложность вскрытия RSA. Если N достаточно велико, то генератор безопасен. Дополнительная теория приведена в [i569, i570, i57i, 30, 354].

Blum, Blum, and Shub

Простейший и наиболее эффективный генератор, использующий сложностно-теоретический подход, в честь своих авторов называется Blum, Blum, and Shub. Мы сократим его название до BBS, хотя иногда его называют генератором с квадратичным остатком [i93].

Теория генератора BBS использует квадратичные остатки по модулю n (см. раздел ii.3). Вот как он работает.

Сначала найдем два простых числа, p и q, которые конгруэнтны 3 modulo 4. Произведение этих чисел, n, является целым числом Блюма (Blum). Выберем другое случайное целое число x, взаимно простое с n. Вычислим

x0 = x2 mod n

Это стартовое число генератора.

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

Самым интригующим свойством этого генератора является то, что для получения ,-го бита не нужно вычислять предыдущие ,-i биты. Если вам известны p и q, вы можете вычислить ,-ый бит непосредственно.

bt - это младший значащий бит xb где x* = x0(2 )mod((/>-i)(q

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

Безопасность этой схемы основана на сложности разложения n на множители. Можно опубликовать n, так что кто угодно может генерировать биты с помощью генератора . Однако пока криптоаналитик не сможет разложить n на множители, он никогда не сможет предсказать выход генератора - ни даже утверждать что-нибудь вроде: "Следующий бит с вероятностью 5i процент будет единицей".

Более того, генератор BBS непредсказуем в левом направлении и непредсказуем в правом направлении. Это означает, что получив последовательность, выданную генератором, криптоаналитик не сможет предсказать ни следующий, ни предыдущий бит последовательности . Это вызвано не безопасностью, основанной на каком-то никому не понятном сложном генераторе битов, а математикой разложения n на множители.

Этот алгоритм медленен, но есть способы его ускорить . Оказывается, что в качестве псевдослучайных битов можно использовать несколько каждого x*. В соответствии с [i569, i570, i57i, 35, 36] если n - длина xb можно использовать log2n младших значащих битов x*. Генератор BBS сравнительно медленный и не подходит для потоковых шифров. Однако для высоконадежных приложений, таких как генерация ключей, этот генератор лучше многих других.

17.10 Другие подходы к проектированию потоковых шифров

При информационно-теоретическом подходе к потоковым шифрам предполагается, что криптоаналитик о б-ладает неограничеными временем и вычислительной мощностью . Единственным практически реализованным потоковым шифром, защищенным от такого противника, является одноразовый блокнот (см. раздел i.5). Так как писать биты в блокноте не очень удобно, его иногда называют одноразовой лентой. На двух магнитных лентах, на одной для шифрования, а на другой для дешифрирования, должен быть записан идентичный поток ключей. Для шифрования просто выполняется XOR открытого текста с битами ленты. Для дешифрирования

выполняется XOR шифротекста с битами другой, идентичной ленты. Один и тот же поток ключей нельзя и с-пользовать дважды. Так как биты потока ключей действительно случайны, предсказать поток ключей нево з-можно. Если сжигать ленты после использования, то безопасность будет абсолютной (при условии, что у кого-то другого нет копии ленты).

Другой информационно-теоретический потоковый шифр, разработанных Клаусом Шнорром ( Claus Schnorr) предполагает, что криптоаналитик имеет доступ только к ограниченному числу битов шифротекста [1395]. Результаты являются слишком теоретическими results и не имеют практического значения. Подробности можно найти [1361, 1643,1193].

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

Шифр "Рип ванВинклъ"

Джеймс Массей (James Massey) и Ингемар Ингемарсон (Ingemar Ingemarsson) предложили шифр "Рип ван Винкль" [1011], названный так, потому что получатель, чтобы начать дешифрирование, должен получить 2n битов шифротекста. Алгоритм, показанный на 7-й, прост в реализации, гарантировано безопасен и совершенно непрактичен. Просто выполните XOR открытого текста с потоком ключей и задержите поток ключей на время от 0 до 20 лет - точная задержка является частью ключа. По словам Массея: "Можно легко доказать, что вражескому криптоаналитику для вскрытия шифра понадобятся тысячи лет, если кто-то согласится подождать с чт е-нием открытого текста миллионы лет." Развитие этой идеи можно найти в [1577, 755].

Поток случайных битов

Поток битов открытого текста

Открытый текст

0-20 лет

(Длина засекречена и зависит от ключа)

Рис. 17-10. Шифр "Рип ван Винкль".

Рандомизированный потоковый шифр Диффи

Эта схема впервые была предложена Уитфилдом Диффи [1362]. Используется 2й случайных последовательностей. Ключ представляет собой случайную й-битовую строку. Для шифрования сообщения Алиса использует k-ую случайную строку как одноразовый блокнот. Затем она отправляет шифротекст и 2й случайных строк по 2n+1 различным каналам связи.

Боб знает k-, поэтому он может легко выбрать, какой из одноразовых блокнотов использовать для дешифр и-рования сообщения. Еве остается только перебирать случайные последовательности, пока она не найдет пр а-вильный одноразовый блокнот. Для вскрытия потребуется проверить некоторое число битов, по порядку равное 0(2n). Рюппел указал, что, если вы отправляете n случайных строк вместо2й, и если ключ используется для задания линейной комбинации этих случайных строк, безопасность остается на прежнем уровне .

Рандомизированный потоковый шифр Маурера

Уели Маурер (Ueli Maurer) описал схему, основанную на выполнении XOR открытого текста с несколькими большими открытыми последовательностями случайных битов [1034, 1029, 1030]. Ключ является набором стартовых позиций в каждой последовательности . Можно доказать, что такой шифр почти безопасен, с вероя т-ность взлома определяется объемом памяти, имеющейся в распоряжении взломщика, независимо от доступной ему вычислительной мощности. Маурер утверждает, что эта схема становится практичной при 100 различных последовательностях длиной 1020 случайных битов каждая. Одним из способов получить рак много битов явля-

ется оцифровка поверхности Луны.

17.11 Шифры с каскадом нескольких потоков

Если производительность не важна, то нет причин выбирать несколько потоковых шифров и объединять их в каскад. Для получения шифротекста просто выполните XOR выхода каждого генератора с открытым текстом . Результат Уели Маурера (см. раздел i5.7) показывает, что если генераторы используют независимые ключи, то безопасность каскада по крайней мере не меньше безопасности самого сильного алгоритма каскада, а скорее всего и намного больше .

Потоковые шифры объединяются теми же способами, что и блоковые (см. главу i5). Потоковые шифры можно объединить в каскад (см. раздел i5.7) с другими потоковыми шифрами или с блочными шифрами .

Ловким трюком является использование одгого алгоритма, потокового или блочного, для частого обновл е-ния ключа быстрого потокового алгоритма (которым может быть и блочный алгоритм в режиме OFB). Быстрый алгоритм может быть слабым, так как криптоаналитик никогда не получит достаточно открытого текста, з а-шифрованного одним ключом.

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

17.12 Выбор потокового шифра

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

Я предпочитаю потоковые шифры, спроектированные подобно блочным шифрам : нелинейные преобразования, большие S-блоки, и т.д. Больше всего мне нравится RC4, а затем SEAL. Мне бы очень хотелось увидеть результаты криптоанализа предложенных мной генераторов, объединяющих LFSR и FCSR. Эта область кажется весьма привлекательной для изучения возможности использования в реальных разработках . Или для получения потокового шифра можно использовать блочный шифр в режиме OFB или CFB.

В 14-й для сравнения приведены временные соотношения для некоторых алгоритмов . Табл. 17-3.

Скорости шифрования нескольких потоковых шифров на i486SX/33 МГц

АлгоритмСкорость шифрования (Мбайт/с)

PIKE62 RC4i64

SEAL38i

17.13 Генерация нескольких потоков из одного генератора псевдослучайной последовательности

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

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