Генерация псевдослучайных битов
Для первого знакомства в связи с этом смотри [98].
Несмотря на все свои преимущества перед криптографическими системами с секретным ключом, RSA все же значительно медленнее, чем DES. Напомним, что аппаратная реализация DES в настоящее время способна достигать скорости 20 мегабит в секунду.
Это заставляет рассматривать коммерческую применимость даже самых быстрых RSA устройств шифрования скорее как плохую. На вентильной матрице Кочанского (M.
Kochanski) [159,222] можно достичь примерно 5 килобит в секунду с 512-ти битовым ключом (что является безусловно наименьшим пределом на размер ключа, который вообще можно рассматривать).
Есть сообщение в [185] о более быстрой реализации, принадлежащей Омуре (J. Omura), но и она все еще более чем в тысячу раз медленнее, чем DES.
Существует также знаменитая микросхема Райвеста, которая так никогда и не была отлажена [202,203] и проект Брикеля, который при реализации теоретически смог бы достичь 25 килобит в секунду. О еще более быстрой реализации сообщается в [207].
Читайте также [187].
Необходимо заметить, что программная реализация еще медленнее. Самый быстрый, из известных автору, имеющий коммерческое применение RSA шифратор - это CryptoCom компании Algorithmic Research для IBM PC.
Он шифрует очень быстро, так как всегда использует число 3 в экспоненте в качестве открытого ключа (что обычно очень опасно [143], хотя и не настолько в данной ситуации, т.к. здесь RSA используется только для обмена DES ключами). Один 512-ти битовый блок он дешифрует примерно за 9 секунд, или при разбивке записи, со скоростью около 57 бит в секунду! (В действительности CryptoCom - гибридная система, так что на самом деле она работает немного быстрее за большой промежуток времени (смотри раздел 4.7).
Была объявлена намного более быстрая реализация RSA на IBM PC, но официальная документация о ней пока еще недоступна.
Генерация псевдослучайных битов
Последовательность называется псевдослучайной, если она выглядит, как бессистемнаая и случайная, хотя на самом деле создавалась с помощью сугубо детерминированного процесса, известного под названием псевдослучайного генератора. Такие генераторы задаются действительно случайной начальной последовательностью, называемой исходной, и детерминировано получают из нее намного более длинную псевдослучайную последовательность. В этом смысле псевдослучайные генераторы можно рассматривать как распространители случайности.
В качестве энциклопедии по классической выработке псевдослучайных последовательностей и тестам, цель которых заключается в том, чтобы различать псевдослучайные последовательности от истинно случайных, рекомендуем [158].
Случайность и криптография очень сильно взаимосвязаны. Основная цель криптосистем состоит в том, чтобы преобразовать неслучайные осмысленные открытые тексты в кажущийся случайным беспорядок. Эта способность может быть использована для генерации псевдослучайных последовательностей следующим образом.
Пусть Ek некоторый алгоритм шифрования, и пусть x[0] произвольный открытый текст.
Рассмотрим последовательность, определяемую как x[i+1] = Ek(x[i]) для i 0. Если Ek является подходящим для криптографических целей, то похоже, что x[1], x[2],... - это последовательность без явной системности (хотя очевидно, что она непременно должна зациклиться). Для того чтобы уменьшить корреляцию в этой последовательности, может быть предпочтительнее сохранять только несколько битов из каждого x[i].
Отношение между случайностью и криптографией в другой связи является более интересным. Даже самые лучшие криптосистемы были бы бесполезны, если бы криптоаналитик мог угадывать используемый ключ(это замечание относится к криптосистемам как с секретным, так и с открытым ключом). Не существует лучшего способа предотвратить эту угрозу, чем выбирать ключ действительно случайным образом.
Отсутствие этого в телеграммных ключах было главной причиной раскрытия Энигмы (Enigma) [122,201].
Как крайний пример, рассмотрим одноразовый шифр. Общеизвестно, что эта криптосхема обдадает совершенной секретностью, если шифр в ней выбирается случайно, и в то же время может быть раскрыта без большого труда, если шифром является обычный текст на английском языке.
Напомним, что основное неудобство одноразовых шифров состоит в том, что шифр должен быть не только случайным, но и иметь в точности такую же длину, как и шифруемое сообщение, и при этом использоваться только один раз.
Режим Выходной Обратной Связи, описанный в разделе 3.5, прекрасно объединяет эти два понятия вместе: он использует криптосистему для генерации псевдослучайной последовательности из короткого исходного вектора (k и s0, из которых секретно только k), и эта последовательность используется как одноразовый шифр для реальных сообщений открытого текста. Преимущество этого подхода заключается в том, что секретный ключ намного короче, чем открытый текст, и может быть повторно использован столько раз, сколько угодно, так как s0 каждый раз меняется (напомним, что s0 задается открытым образом как часть шифртекста, так что для обеспечения надежности необходимо только однажды передать ключ k). Неизбежной платой за использование короткого ключа является, конечно, потеря совершенной секретности.
Однако, может быть, этот режим внешней обратной связи является не более, чем принятие желаемой за действительную Эвристикой?
Скажем, что псевдослучайный генератор является криптографически сильным, если последовательность, которую он вырабатывает из короткого секретного исходного ключа, является по существу точно такой же, как и по-настоящему случайная последовательность, предназначенная для той же цели, для какой она используется как одноразовый шифр.
Под словами по существу точно такой же мы понимаем, что никакое практически легкоосуществимое вычисление не может позволить криптоаналитику получить никакой информации об открытом тексте при перехвате его шифртекста(за исключением разве что с пренебрежимо малой вероятностью). Другими словами, такой генератор ведет себя так же, как если бы был совершенно секретной по Шеннону криптосхемой, до тех пор, пока криптоаналитик не затратит чрезмерно большое количество времени.
Такие генераторы могут использоваться для реализации криптосистем с секретным ключом, если обе стороны договорились об исходном секретном векторе, который они собираются использовать при условии, что они никогда не будут использовать один и тот же исходный вектор дважды.
Намного менее очевидно, что криптографически сильные псевдослучайные генераторы могут быть использованы при реализации криптосистем с открытым ключом, но в следующем разделе мы покажем, что такое тоже возможно.
Первый шаг к обоснованию таких генераторов был сделан Шамиром (A. Shamir) [210]. Ключевое понятие псевдослучайных генераторов - непредикативность влево - было впоследствии введено Блюмом (M. Blum) и Микэли (S.
Micali) [41]: криптоаналитик, который знает как работает генератор, но не знает, какой исходный вектор в действительности используется, не может сделать ничего лучшего, чем подбрасывать правильную монету, для того чтобы угадать первый бит, выработанный генератором, даже после просмотра всей сгенерированной затем последовательности (если только он не окажется очень удачливым или же сможет проделать практически невыполнимые вычисления).
Как и обычно, мы не знаем существуют ли такие генераторы, но первый кандидат был предложен Блюмом и Микэли, которые доказали, что их генератор является непредикативным влево в предположении, что трудноосуществимым является определение дискретных логарифмов.
Полная уместность генераторов непредикативных влево была установлена Яо(А. Yao), который доказал, что любой такой генератор является криптографически сильным [243].
Наконец, Л.Левин дал необходимые и достаточные условия для существования таких генераторов [170].
Теперь мы приведем описание более простого и в вычислительном отношении более эффективного кандидата на криптографически сильный псевдослучайный генератор, который известен как BBS генератор, названный так в честь Л. Блюма(L.Blum), М. Блюма(М. Blum) и Шуба(М.
Shub) [33].
Он основывается на втором кандидате на однонаправленную функцию с потайным ходом, описанном в разделе 1.1. Напомним, что n называется целым числом Блюма, если оно является произведением двух различных простых p и q, оба из которых сравнимы с 3 по модулю 4. Напомним также, что возведение в квадрат по модулю n является перестановкой квадратичных остатков по модулю n, и считается, что она является однонаправленной функцией с потайным ходом, так как было доказано, что трудность ее обращения (т.е. вычисления примитивных корней) вычислительно эквивалента разложению n на множители.
В предположении, что факторизация n трудна, может быть доказана даже более сильная теорема: для почти всех квадратичных остатков x, подбрасывание правильной монеты приводит к наилучшей возможной оценке первого значащего разряда x, который, однако, может быть легко вычислен при знании xA2 mod(n) [231,232,5].
Другими словами, практически трудно вычислить не только сам примитивный квадратный корень, но даже и получить вероятностную информацию о его первом значащем бите (подобно следующему: Я не убежден, но верю, что этот бит должен быть нулем, а не единицей).
Теперь мы готовы описать BBS-генератор и доказать при соответствующем предположении, что он является криптографически сильным.
Пусть n - целое Блюма с неизвестным разложением на множители. Выберем в качестве исходного числа случайный квадратичный остаток x[0] (для того, чтобы это сделать, выберем случайное целое x взаимно простое с n и вычислим x[0] = хЛ2 mod(n)).
Для i = 0 определим рекурсивно x[i+1] = х[і]Л2 mod(n) и пусть b[i] - первый значащий бит x[i]. Для любого целого t первые t битов, сгенерированные из x0, таким образом, и будут искомой псевдослучайной последовательностью BBS[n,t](x0) = b[0]b[1]b[2]...b[t-1].
То что BBS-генератор непредикативен влево означает, что никто не может отгадать b[0], зная n и b[1]b[2]...b[t-1]. Если бы это было не так, первый значащий бит неизвестного примитивного квадратного корня x любого заданного квадратичного остатка у мог бы быть определен следующим образом. Вычисляем псевдослучайную последовательность BBS[n,t-1](y) и представляем ее как BBS[n,t](x) с удаленым первым своим битом.
Отгадываем этот пропущенный бит и замечаем, что по определению он и является первым значащим битом x, который мы искали.
Из этого следует, что BBS-генератор должен быть непредикативным влево в предположении, что факторизация n трудна. Следовательно, по теореме Яо, он является криптографически сильным.
Дополнительное привлекательное свойство этого генератора заключается в том, что он обеспечивает прямое определение тех отдельных битов, которые он вырабатывает, для всех, кто знает разложение n на множители. Для этого заметим, что x[i] = х[0]л(2лі) mod(n).
По теореме Эйлера хЛФ(п) = 1 mod(n), где Ф(п) = (p-1)(q-1).
Следовательно, x[i] = [х[0]л((2лі) mod Ф(п))] mod(n), вычисляется эффективно из исходного числа x[0] и требуемого индекса i посредством двух применений быстрого алгоритма модульного возведения в степень.
Вероятностное шифрование.
Криптография с открытым ключом в значительной степени решает проблему распространения ключей, которая является довольно серьезной для криптографии с секретным ключом. Однако, как мы указывали выше, при перехвате шифртекста c = Ek(m) всегда становится известной некоторая информация об открытом тексте m, поскольку криптоаналитик может вычислить без посторонней помощи открытую функцию шифрования Ek для любого отвечающего ему открытого текста.
Задавая произвольно m' по своему выбору, он может легко выяснить, верно ли, что m = m', так как это справедливо только, если Ek(m') = c.
Даже если определение m из c и в самом деле было бы трудно осуществимым из знания только естественного алгоритма шифрования, что мы не знаем, как доказать, нельзя сказать сколь велика и какова должна быть эта частичная утечка информации об m.
Используя метафору Гольдвассера (S. Goldwasser), применение криптографии с открытым ключом подобно прятанию верблюда под одеялом: можно утаить, какой верблюд на самом деле спрятан, но не число его горбов.
Целью вероятностного шифрования - понятия, введенного Гольдвассером и Микэли (S. Micali) [132] - является кодирование сообщений таким образом, чтобы никакое легковыполнимое вычисление на основе шифртекста не могло бы дать какой бы то ни было информации о соответствующем открытом тексте (кроме, разве что, с пренебрежимо малой вероятностью).
Это напоминает системы совершенной секретности в смысле Шеннона, с дополнительными преимуществами коротких ключей и возможностью для каждого пользователя обнародовать свои алгоритмы открытого шифрования.
Конечно, от таких систем нельзя ожидать настоящей совершенной секретности, они вообще несекретны против криптоаналитика, обладающего неограниченной вычислительной мощностью.
Основное техническое различие между вероятностным шифрованием и системами с открытым ключом состоит в том, что естественные алгоритмы шифрования являются при этом вероятностными, а не детерминированными. Одно и то же сообщение в открытом тексте может привести к возникновению большого числа различных шифртекстов.
В результате криптоаналитик, имеющий по его предположению истинный открытый текст не сможет долго проверять свою догадку посредством его шифрования (с помощью естественного алгоритма законного получателя) и сравнения полученного результата с переданным шифртекстом.
Формально система вероятностного шифрования состоит из пространства ключей K и для каждого k из K - пространств сообщений открытых текстов Ck, вероятностных пространств Rk и пар функций Ek: (Mk х Rk) - Ck и Dk: Ck - Mk, таких что Dk(Ek(m,r)) = m для любого сообщения открытого текста m из Mk и случайного числа r из Rk.
С помощью любого k из K должны легко получаться эффективные естественные алгоритмы для вычисления как Ek, так и Dk, но должен трудно получаться любой эффективный алгоритм вычисления Dk при заданном только естественном алгоритме вычисления Ek.
Используемая таким образом система вероятностного шифрования в известной степени очень похожа на систему с открытым ключом. Раз и навсегда каждый пользователь выбирает ключ k из K, который используется для получения обоих естественных алгоритмов вычисления Ek и Dk.
Он делает алгоритм шифрования Ek публично доступным и сохраняет в секрете алгоритм дешифрования Dk. В том случае, когда другой пользователь захочет послать ему свое сообщение m, он находит Ek в справочнике, случайно выбирает некоторое r из Rk и вычисляет шифртекст c = Ek(m,r). Используя свой секретный потайной ход, только законный получатель может легко определить m из c.
Как следствие большого числа шифртекстов, соответствующих каждому открытому тексту, при использовании вероятностного шифрования неизбежно некоторое раскрытие данных. Заметим, что для криптосистемы RSA, это было не так.
Несмотря на все свои замечательные теоретические свойства, оригинальная система вероятностного шифрования Голдвассера - Микали претерпевала столь громадное раскрытие данных, что не имела большого практического значения. И мы не будем описывать ее здесь.
Несмотря на это, вероятностное кодирование достигло такого состояния, при котором сейчас существует схема даже более эффективная, чем 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 квадратов и еще 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 определенно предоставляет некоторую частичную информацию, и может таковой даже если используется случайное шифрование).
С другой стороны, эта схема вообще несекретна относительно атаки на основе выбранного шифртекста. Мы предлагаем читателю самому определить почему это так.
Гибридные системы
Несмотря на все преимущества криптографии с открытым ключом и вероятностного шифрования, ни одна из их реализаций, предложенных до сих пор не может конкурировать в скорости с системами с секретным ключом, такими, например, как DES. Когда необходимо передать большое количество информации, может оказаться, что использование RSA было бы слишком медленным, тогда как использование DES было бы либо невозможным (из-за отсутствия разделенного секретного ключа), либо не отвечающим требованиям секретности.
В такой ситуации может быть полезным использование компромиса. Гибридная криптосистема использует криптосистему с открытым ключом один раз в начале передач сообщений для того, чтобы выделить небольшую часть информации, которая затем используется как ключ к шифратору или дешифратору для тех текущих сообщений, которые проходят через криптосистему с секретным ключом.
Если сообщение достаточно длинное, предпочтительно использовать криптосистему с открытым ключом несколько раз в течении этой передачи, с тем чтобы секретные ключи почаще менялись. Без особого замедления протокола это значительно повышает стойкость гибридной системы по двум причинам: криптосистему с секретным ключом раскрыть легче (при атаке только на основе шифртекста, которая является единственным типом атаки, имеющим смысл в этой ситуации), если доступен большой шифртекст, но даже если криптоаналитику и удастся определить один из секретных ключей, он сможет расшифровать лишь соответствующую часть сообщения.
