Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Более формально, пусть р и q — два случайно выбранных различных простых числа, сравнимых с 3 по модулю 4, которые вместе образуют секретный ключ. Их произведение п = р ¦ q является открытым ключом. Пространство сообщений открытого текста — это множество всех конечных двоичных строк произвольной длины. Любое сообщение может в этом случае шифроваться непосредственно без разбиения на части, используя при этом один из режимов, которые были описаны в § 3.4, ¦точно так же, как это было в случае с RSA. (Правда, это только чисто теоретически, поскольку на самом деле длина битовой строки, представляющей открытый текст не должна быть больше периода псевдослучайной последовательности, вырабатываемой BBS-генератором, хотя на практике этот период в столь большое число раз превышает размер модуля п, что позволяет фактически не ограничивать длину открытого текста.) Вероятностным пространством служит множество QRn, то есть множе*
68 Системы с открытый ключом
Глава 4
ство квадратичных вычетов по модулю п. Пространством сообщений шифрованного текста является множество пар, образованных квадратичными вычетами по модулю п и конечными двоичными строками.
Пусть m — некоторое разрядное сообщение. И пусть также Хо — это случайный квадратичный вычет по модулю п. Предположим далее, что BBSn>t{xо) и xt определяются точно так же, как в § 5. Тогда шифрование ш, использующее исходный вектор *о и открытый ключ п, задается в виде пары чисел {xt, m ф BBSn,t{xо)), где «ф» означает поразрядное сложение по модулю 2. Здесь BBSnt(xo) используется в качестве одноразового шифра к открытому тексту т. Значение Xt включается в шифртекст только для того, чтобы обеспечить законному получателю эффективное дешифрование, но тем самым никак не помогая в этом нарушителю. Напомним, что необходимым и достаточным условием для эффективного вычисления примитивных квадратных корней является знание сомножителей числа п [297]. Простейший алгоритм дешифрования заключается в вычислении всей псевдослучайной последовательности, начиная с xt, в обратном порядке, и используя для этого рекуррентное уравнение Xi = y/Xi+1 mod п. В результате такого вычисления сначала однозначно восстанавливается значение BBSnit{xо), а затем из известного шифртекста легко получается открытый текст.
Обозначим через I число разрядов модуля п. Эффективность только что описанного алгоритма шифрования полностью сопоставима с эффективностью алгоритма криптосхемы RSA, потому что в нем для каждого бита открытого текста используется одна операция модульного возведения в квадрат, в то время как в RSA для каждого (I — 1)-блока открытого текста требуется одно модульное возведение в степень, и при этом каждое возведение в степень требует I возведений в квадрат и, кроме того, I умножений (см. § 1). Простейший алгоритм дешифрования, который был предложен выше, не очень хорош, поскольку для каждого бита открытого текста он требует вычисления одного примитивного квадратного корня, а на каждое такое вычисление расходуется примерно столько же времени, сколько на одно модульное возведение в степень. К счастью, знание множителей п позволяет определять все отдельные биты случайной последовательности
Вероятностное шифро,а„„ 6д
непосредственно не только в прямом порядке так, как это описано в конце § 5, но и в обратном. Такое вычисление обходится примерно во столько же, во сколько обходится одно возведение в степень (или RSA-дешифрование одного блока), и позволяет законному получателю сообщения вычислить хо непосредственно из Xt, а затем для того, чтобы получить BBS„tt{xо), проделать то же самое в прямом порядке так же эффективно, как это сделал его отправитель.
Сейчас мы представим этот эффективный алгоритм вычисления Хо из xt при известном разложении п = р ¦ q. В качестве предварительного шага в нем сначала с помощью обобщенного алгоритма Евклида раз и навсегда вычисляются целые числа а и Ь, такие что ар + bq = 1. Затем выполняются следующие операции:
Схема вероятностного шифрования Блюма-Гольдвассер может быть сделана даже еще быстрее. Более тщательный анализ псевдослучайного генератора BBS [349, 350, 8, 117] показывает, что в нем после каждой операции модульного возведения в квадрат можно использовать более одного значащего бита очередного квадратичного вычета А именно, окончательная псевдослучайная последовательность не ослабится, если в нее для каждого индекса г будут выбираться (приблизительно) 1од2(1) первых значащих битов Xi. Благодаря такому улучшению вероятностное шифрование будет осуществляться быстрее, чем шифрование в RSA, примерно в 1од2{1) раз, причем то же самое справедливо и для дешифрования длинных сообщений (так как в этом случае достаточно проделать вычисление в обратном порядке только один раз). В заключение отметим, что криптосхема вероятностного шифрования не только быстрее, чем RSA, но и также доказано, что трудность ее раскрытия вычислительно
и expmod((xt mod р), а,р)
v expmod((xt mod q),/3,q)
return (bqu + apv) mod n
70 Системы с открытым ключом
