207355

Несмотря на это, вероятностное кодирование достигло такого состояния, при котором сейчас существует схема даже более эффективная, чем RSA. Для целей секретности (но не аутентификации) эта схема Блюма и Голдвассера, описываемая ниже, является наилучшей из того, что наука пока что смогла предложить. Она основана на вере в то, что возведение в квадрат по модулю целого числа Блюма является однонаправленной функцией с потайным ходом (последний пример в разделе 1.1) и на криптографически сильном псевдослучайном битовом генераторе, описанном в разделе 1.5.

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

Более формально, пусть p и q - два случайно выбранных различных простых числа, сравнимых с 3 по модулю 4, которые вместе образуют секретный ключ. Их произведение n = p*q является открытам ключом. Пространство сообщений открытого текста - это множество всех конечных двоичных строк произвольной длины (любое сообщение может, таким образом, кодироваться непосредственно без разбиения его на части и используется в одном из режимов шифрования DES, так же как в случае с RSA). Вероятностное пространство - это QRn, множество квадратичных остатков по модулю n. Пространством сообщений открытого текста является множество пар, образованных квадратичными остатками по модулю n и конечными двоичными строками.

Пусть m некоторое t - битовое сообщение. Пусть x[0] случайный квадратичный остаток по модулю n. Предположим, что BBS[n,t](x[0]) и x[t] определяются так же, как в разделе 1.5. Шифрование m, использующее исходное число x[0] и открытый ключ n, задается как пара , где "o" означает поразрядное "ислючающее или". Здесь BBS[n,t](x[0]) используется как одноразовый шифр открытого текста m. Значение x[t] включается в шифртекст для того, чтобы обеспечить эффективное дешифрование законному получателю, но оно не окажет никакой помощи нарушителю. Напомним, что знание множителей n является необходимым и достаточным для эффективного вычисления главных квадратных корней [196].

Примитивный алгоритм дешифрования заключается в вычислении псевдослучайной последовательности, начиная от x[t] в обратном порядке, используя рекурентное уравнение x[i] = корень квадратный из x[i+1] по mod(n).

Единственное значение BBS[n,t](x[0]), таким образом, восстанавливается и открытый текст легко получается из известного шифртекста.

Пусть l - число разрядов в модуле n. Эффективность только что описанного алгоритма шифрования очень похожа на эффективность криптосистемы RSA, так как ему требуется одна операция модульного возведения в квадрат, тогда как для RSA потребовалось бы одно модульное возведение в степень для каждого (l-1)блока открытого текста и поэтому каждое возведение в степень требует вычисления l квадратов и еще l дополнительных умножений (раздел 1.1).

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

отдельные биты случайной последовательности не только в прямом порядке, как описано в конце раздела 1.5, но и в обратном. Это обходится примерно во столько же, во сколько обходится одно возведение в степень ( или RSA-дешифрование одного блока), что позволяет законному получателю вычислить x[0] прямо из x[t], а затем проделать то же самое в прямом порядке, чтобы получить BBS[n,t](x[0]) так же эффективно, как это сделал отправитель.

Вот эффективный алгоритм для вычисления x[0] из x[t] и разложения n = p*q. В качестве предварительного шага с помощью обобщенного алгоритма Евклида лишь однажды вычисляются целые числа a и b, такие что a*p + b*q = 1. Затем производятся следующие действия: A = expo((p+1)/4,t,p-1)

B = expo((q+1)/4,t,q-1)

u = expo((x[t] mod(p)),A,p) g = expo((x[t] mod(q)),B,q) return(b*q*n+a*p*g) mod(n)

Схема вероятностного шифрования Блюма-Гольдвассера может быть сделана даже быстрее. Более тщательный анализ псевдослучайного генератора BBS [231,232,5] показывает, что можно использовать более, чем один наименьший значащий бит после каждой операции модульного возведения в квадрат. Получающаяся в результате псевдослучайная последовательность не ослабляется, если ее составлять из (приблизительно) log_2(l) младших значащих битов каждого x[i].

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

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

1.7. Гибридные системы

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

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

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