Современная криптология

Дж. Брассар

Криптография - область знаний, изучающая тайнопись (= криптография) и методы ее раскрытия (= криптоанализ), по меткому выражению Рональда Райвеста (R.L.Rivest - профессор Массачусетского технологического института (MIT), один из авторов знаменитой криптосистемы RSA) является "повивальной бабкой" всей computer science вообще. Однако до недавнего времени сам термин "криптология" был в нашей стране под запретом. Его даже нельзя было произносить тем, кто профессионально работал в этой области, не говоря уже о каких бы то ни было открытых публикациях на эту тему. В открытых организациях, как учебных, так и научно-исследовательских, никто криптологией официально не занимался.

Слово "криптология" впервые появилось у нас в переводной статье Дж.Л.Месси "Введение в современную криптологию" в тематическом выпуске ТИИЭР, т.76, #5 за 1988 год. Освещающая классические вопросы криптологии она может служить хорошим введением в предмет.

В том же, 1998 году увидела свет и рецензируемая книга. Она была издана в "Springer-Verlag" в серии "Lecture Notes in Computer Science", в которой издаются труды основных ежегодно проводимых конференций по криптологии - CRYPTO'XX и EUROCRYPT'XX (где XX - это две последние цифры года конференции). Автор книги - известный канадский специалист в области криптологии, профессор факультета информатики и исследования операций Монреальского университета, а сама книга - значительно расширенный и дополненный вариант его 3,5-часовой CompCon'овской лекции предыдущего года. Поэтому она сравнительно небольшая - немногим более ста среднего формата страниц, из которых 17 занимает библиография.

Книжка очень емкая, написана с большим мастерством, неформально, обычным "человеческим" языком, на концептуальном уровне, и в этом смысле отражает все, или почти все, многочисленные теоретические и, в особенности, практические аспекты современной криптологии, многие из которых на Западе уже стали или становятся (там это быстро!) частью (их) простой повседневной жизни. Поэтому слово "modern" в заглавии вполне оправдано. В значительно меньшей степени в книге представлены вопросы криптоанализа, что вполне объяснимо, так как для этого необходимы некоторые специальные знания, которых выбранный автором уровень изложения не предполагает.

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

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

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

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

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

Такой перевод терминов "diffusion" и "confusion" в цитированной ранее статье Дж.Л.Месси, но соответственно - "распыление" и "запутывание" в книге К.Шеннона "Работы по теории информации и кибернетике", ИЛ, М, 1963. В следующих двух параграфах рассматривается известный алгоритм шифрования DES с точки зрения его практического использования.

Четвертая, центральная глава книги посвящена основополагающим понятиям и методам криптографии с открытым ключом. В ней вводятся и обсуждаются понятия однонаправленной функции и однонаправленной функции с потайным ходом, или, иначе, лазейкой. И, поскольку само существование таких фукций является основным открытым вопросом всей современной криптологии, связанным с фундаментальной проблемой P ?= NP, приводятся функции, которые с огромной долей уверенности, какая только вообще возможна в настоящее время, следует признать таковыми. Описывается, как осуществляется открытое распределение ключей по Диффи-Хеллману и общая теория криптосистем с открытым ключом. Следующий параграф посвящен исторически первой практически реализуемой системе шифрования и цифровой подписи - знаменитой RSA. Далее рассматриваются вопросы генерации псевдослучайных последовательностей и условия существования так называемых криптографически сильных генераторов, после чего на их основе - схемы вероятностного шифрования. Завершает главу небольшой параграф о гибридных системах.

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

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

Библиография книги включает 250 названий.

Введение

Определения и классификация

Цель криптографической системы заключается в том, чтобы зашифровать осмысленный исходный текст (также называемый открытым текстом, получив в результате совершенно бессмысленный на взгляд шифрованный текст, или, коротко, шифртекст (называемый также криптограммой). Получатель, которому он предназначен, должен быть способен расшифровать (говорят также "дешифровать") этот шифртекст, восстановив, таким образом, соответствующий ему открытый текст. При этом противник (называемый также криптоаналитиком) должен быть неспособен раскрыть исходный текст. Существует важное отличие между расшифрованием (дешифрованием) и раскрытием шифртекста. Раскрытием криптосистемы называется результат работы криптоаналитика, приводящий к возможности эффективного раскрытия любого, зашифрованногос помощью данной криптосистемы, открытого текста. Степень неспособности криптосистемы к раскрытию называется ее стойкостью.

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

Криптосистемы ограниченного использования

Криптосистемы общего использования

с секретным ключом

с открытым ключом

Будем говорить, что криптографическая система является криптосистемой ограниченного использования, если ее стойкость основывается на сохранении в секрете самого характера алгоритмов шифрования и дешифрования. Простейшим историческим примером такой системы можно считать так называемый шифр Цезаря, который представляет из себя простую замену каждого символа открытого текста третьим следующим за ним символом алфавита. Здесь и везде далее в книге автор, естественно, имеет в виду английский алфавит. (с циклическим переносом, когда это необходимо). Например, слово "cleartext" превращается в "fohduwhaw". Криптосистемы ограниченного использования обычно разрабатываются любителями и почти всегда являются детской забавой для опытного криптоаналитика-профессионала. Гораздо важнее то, что такие системы вообще не используются для конфиденциальной связи в современной ситуации, когда должна обеспечиваться работа большого числа абонентов.

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

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

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

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

Одним из очевидных требований обеспечения стойкости общей криптографической системы является огромное количество возможных ключей, не позволяющее провести исчепывающий поиск (в котором осуществляется попытка систематического дешифровывания заданного шифртекста, используя при этом каждый из возможных ключей до тех пор, пока не получится некий осмысленный открытый текст). Например, при наивном подходе шифр Цезаря можно рассматривать как пример общей криптосистемы (с ключом k=3), шифрование в которой заключается в замене каждого очередного символа открытого текста k-ым после него символом соответствующего алфавита, где~k~ - некий секретный ключ. Но такое обобщение является бесполезным, потому что оно предоставляет возможность использования лишь 25 нетривиальных ключей, и тем самым обеспечивает простоту полного перебора для любого, кто предположительно знает метод шифрования (по крайней мере, если шифрованное сообщение имеет достаточную избыточность, чтобы у него была единственная осмысленная расшифровка).

Однако необходимо осознавать, что большое число ключей само по себе стойкости криптосистемы не обеспечивает. Так, например, еще одно обобщение шифра Цезаря состоит в том, что в качестве ключа выбирается произвольная перестановка всех 26 букв алфавита, наподобие ( EROX ... WM), а шифрование каждого символа открытого текста производится в соответствии с этой перестановкой ( A (E, B ( R, ... , Z (M).

При таком шифровании открытый текст "BAD DAY" преобразуется в шифртекст "REX XEW". Заметив, что существует 26! различных перестановок из 26 символов, которое является числом большим, чем 4 times 10^ 26, можно было бы предположить, что полный перебор на таком множестве ключей невозможен, потому что, если опробовать каждый возможный ключ, когда в течении каждой секунды проверяется миллиард ключей, это заняло бы десять миллиардов лет! Тем не менее, подобный (одноалфавитный) шифр простой замены является довольно легким для криптоанализа, хотя бы только из-за разницы в частотах, с которыми в естественном языке встречаются различные символы открытого текста. Известны намного более надежные криптографические системы, которые были разработаны и со значительно меньшим ключевым пространством.

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

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

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

В 1976 году Уитфрид Диффи (Diffie) и Мартин Хеллман (Hellman) заложили основы для преодоления этой трудности, предложив понятие криптографии с открытым ключом. Сходное понятие было независимо открыто Ральфом Мерклем (Merkle). Вскоре последовала его первая практическая реализация, предложенная Рональдом Ривестом (Rivest), Эди Шамиром (Shamir) и Леонардом Адлеманом (Adleman).

Секретная связь по незащищенным каналам связи между двумя совершенно незнакомыми друг с другом сторонами наконец-то стала возможна.

Основное наблюдение, которое, собственно, и привело к криптографии с открытым ключом, заключалось в следующем -- тот, кто зашифровывает сообщение, не обязательно должен быть способен его расшифровывать. В таких системах каждый пользователь выбирает свой собственный секретный ключ, на основании которого получает пару алгоритмов. Затем он делает один из них доступным каждому из возможных респондентов, объявляя этот алгоритм своим открытым алгоритмом шифрования, в то время как другой, соответствующий первому и являющийся его личным алгоритмом дешифрования, хранит в строгом секрете. Это позволяет даже совершенно незнакомому, например, с абонентом сети по имени Алиса пользователю применять ее общедоступный алгоритм шифрования, чтобы зашифровать предназначенное для нее сообщение; однако, лишь сама Алиса сможет расшифровать его после получения с помощью своего секретного алгоритма дешифрования.

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

Шафи Гольдвассер (Goldwasser) и Сильвио Микэли (Micali) ввели понятие вероятностного шифрования, которое является очень интересной разновидностью криптографии с открытым ключом. Когда какое-то сообщение шифруется при помощи вероятностного шифрования, то в этом случае при криптоанализе шифртекта, по существу, становится одинаково трудно выяснить о сообщении любую информацию, которая позволила бы восстановить весь его открытый текст. Кроме того, существует вероятностная схема шифрования, которая является более быстрой, чем предложенная до этого схема шифрования с открытым ключом RSA. Подобные криптографические системы называются "вероятностныи" в связи с тем, что в них шифрование сообщений, которые имеют один и тот же исходный текст и шифруются с использованием одного и того же ключа, может в разное время привести к совершенно различным шифртекстам.

Предлагались и разные другие подходы к проблеме распределения ключей. Например, бесключевая криптография Альперна (Alpern) и Шнейдера (Schneider) может эффективно использоваться в сети связи, которая скрывает происхождение (но не содержание) сообщени. В идентификационной криптосистеме Шамира (Shamir) отпадает необходимость в распределении ключей, но требуется наличие некоего центра, которому должно быть доверена генерация секретных ключей.

В заключение отметим только, что Беннет (Bennet) и Брассард (Brassard), опираясь на работу Уиснера (Wiesner), разработали теорию квантовой криптографии, которая предлагает совершенно иную базу для современной криптологии и в своих утверждениях о секретности основывается скорее на квантовой физике, нежели на математике или теории вычислительной сложности. Квантовой криптографии посвящена заключительная глава этой книги.

Г л а в а 1

1.1. Однонаправленные функции

Понятия однонаправленной функции и однонаправленной функции с "потайным ходом" являются центральными понятиями всей криптографии с открытым ключом.

Рассмотрим два произвольных множества X и Y . Функция f: X -> Y называется однонаправленной, если f(x) может быть легко вычислена для каждого x из X, тогда как почти для всех y из Y вычисление такого x из X, что f(x) = y (при условии, что хотя бы один такой x существует), является сложным. Это понятие не нужно путать с функциями, которые являются математически необратимыми из-за того, что они не взаимнооднозначны или не "на" (т.е. из-за того, что существует несколько различных x, таких что f(x) = y, или их нет вовсе). Наше нынешнее состояние знаний не позволяет нам доказать, что однонаправленные функции вообще существуют, так как их существование разрешило бы (P = NP)- проблему [121]. Более того, теория NP-полноты не кажется вполне компетентной для того, чтобы обеспечить даже простое обоснование их существования [45,108,141].

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

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

Конечно, необходимо понимать, что "не в состоянии" означает "не в состоянии за приемлемое время (такое, как время человеческой жизни или возраст вселенной)".

Другим важным примером кандидата на однонаправленную функцию является модульное возведение в степень или модульное экспонирование (с фиксированными основанием и модулем). Пусть n и a - целые числа, такие что 1 < a < n, и пусть Zn = { 0,1,2,...,n-1 }. Тогда модульное возведение в степень ( относительно основания a и модуля n) это такая функция f[a,n]: Zn -> Zn, определяемая как f[a,n](m) = a^m mod( n), где i mod(j) обозначает положительный остаток при делении i на j. Сразу не очевидно, что такую функцию можно вычислить эффективно, когда длина каждого из трех параметров a, n и m составляет несколько сотен знаков. То, что это возможно и в самом деле так, лучше всего увидеть на примере:



a^25=(((a^2*a)^2)^2)^2*a.

Он показывает, как можно вычислить a^25 c помощью лишь четырех возведений в квадрат и еще двух умножений. При вычислении a^m mod(n) произведение по модулю n желательно делать после каждого возведения в квадрат и каждрого умножения, чтобы избежать получения очень больших целых чисел. Если экспонента m является числом длиной в L битов, то следующему рекурсивному алгоритму, для того чтобы вычислить a^m mod(n), требуется от L до 2L модульных умножений (считая умножением и возведение в квадрат):



function expo(a,m,n)

if m=0 then return 1

if m четно then return ((expo(a,m/2,n)^2 mod(n))

else return((a*expo(a,m-1,n) mod(n))

По аналогии с действительным анализом обратная операция известна как задача дискретного логарифмирования: даны целые числа a, n и x, требуется найти такое целое m (если оно существует), что a^m mod(n) = x. Например, 5^4 mod(21) = 16. Следовательно, 4 это дискретный логарифм 16 с основанием 5 по модулю 21. При желании можно проверить, что, например, число 3 вообще не имеет логарифма с основанием 5 по модулю 21. Несмотря на то, что вычисление больших модульных экспонент может быть осуществлено эффективно, в настоящее время неизвестно ни одного алгоритма для вычисления дискретных логарифмов больших чисел за приемлемое время даже на самых быстродействующих компьютерах.

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

Очевидно, что однонаправленные функции не могут непосредственно использоваться в качестве криптосистем (когда m шифруется как f(m)), поскольку тогда даже законный получатель не сможет раскрыть открытый текст! Позднее мы увидим, что несмотря на это они полезны для защиты паролей.

Более употребимым в криптографии является понятие однонаправленной функции с потайным ходом. Функция f: X -> Y называется однонаправленной функцией с потайным ходом, если она может эффективно вычисляться как в прямую так и в обратную сторону, более того, может быть даже известен эффективный алгоритм вычисления f такой, что полное знание того, как этот алгоритм работает, не дает никакой возможности разработать эффективный алгоритм вычисления обратной ей функции.

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

Наш первый кандидат на однонаправленную функцию с потайным ходом очень похож на нашего второго кандидата на просто однонаправленную функцию: модульное возведение в степень с фиксированной экспонентой и модулем. Пусть m и n - целые числа, а Zn определено так же, как и ранее. Тогда модульное возведение в степень (относительно экспоненты m и модуля n) есть функция g[m,n]: Zn -> Zn, определенная следующим образом: g[m,n](a) = a^m mod(n).

Необходимо убедиться в понимании различия между функциями f[a,n] и g[m,n].

Опять по аналогии с действительным анализом, операция обратная g[m,n] известна под названием взятия корня m-той степени из x по модулю n: даны целые числа m, n и x, найти такое целое a(если оно существует), что a^m mod(n) = x. Например, 5 это корень 4-ой степени из 16 по модулю 21, так как мы уже видели, что 5^4 mod(21) = 16. Очевидно, что 2 также является корнем 4-ой степени из 16 по модулю 21. Можете ли Вы найти другие корни 4-ой степени из 16 по модулю 21 ? Найдите целое число x, которое не имеет корней 4-ой степени по модулю 21.

В том случае, когда экспонента m и модуль n фиксированы, мы уже приводили эффективный алгоритм вычисления g[m,n](a) для любого основания a.

В противоположность задаче дискретного логарифмирования, тем не менее, известно, что существует также и эффективный алгоритм взятия корня m-ой степени их x по модулю n (или выяснения, что его не существует) для любого заданного x. Любопытный феномен заключается в том, что неизвестно, как эффективно построить этот эффективный алгоритм при заданных лишь m и n. Другими словами, функция g[m,n] в действительности не является однонаправленной, поскольку мы знаем, что она может быть эффективно обращена, но несмотря на этот факт мы не знаем, как это сделать!

Тем не менее, легко построить эффективный алгоритм вычисления m-ого корня по модулю n при условии, что известно разложение n на простые множители. Именно по этой причине g[m,n] и является кандидатом на однонаправленную функцию с потайным ходом, для которой m и n используются как открытая информация, тогда как разложение служит в качестве секретного потайного хода. Мы еще увидим, каким образом это может быть использовано, когда будем изучать знаменитую криптосистему RSA(раздел 1.4).

Важный специальный случай модульного возведения в степень имеет место, когда экспонента равна 2 и когда модуль является числом специального вида. Для понимания этого второго примера кандидата на однонаправленную функцию с потайным ходом необходимы дополнительные сведения из теории чисел. Если p и q два различных больших простых числа примерно равного размера, и если оба p и q сравнимы с 3 по модулю 4, то мы будем говорить, что их произведение n = p*q является целым числом Блюма. Определим Zn* как множество целых между 1 n-1, которые не делятся ни на p ни на q. Наконец, определим QRn как подмножество Zn*, состоящее из чисел, которые являются совершенными квадратами по модулю n. Элементы QRn известны как квадратичные вычеты по модулю n.

В качестве небольшого примера рассмотрим p = 19 и q = 23, таким образом n=437. В этом случае 135 является элементом Zn*, в то время как 133 нет(поскольку 133 = 19*7). Кроме того 135 не является квадратичным вычетом по модулю 437, так как не существует целого числа a такого, что a^2 = 135 (mod 437), тогда как 139 является квадратичным вычетом, так как 24^2 = = 576 = 139 (mod437).

Сформулируем без доказательства несколько необходимых для понимания дальнейшего теорем.

Число элементов в Zn* равно (p-1)*(q-1), и ровно одну четвертую часть из них составляют квадратичные вычеты. Каждый квадратичный вычет допускает в точности четыре различных "квадратичных корня" в Zn*, из которых лишь один единственный сам является квадратичным вычетом. Этот особый корень мы назовем главным квадратичным корнем.

В нашем примере 24 это главный квадратичный корень из 139 по модулю 437, а другими тремя корнями являются 185,252 и 413. Имеющий криптографическое значение факт заключается в том, что способность определять квадратические корни по модулю n оказывается вычислительно эквивалентной умению раскладывать n на множители. Иначе говоря, тот кто знает разложение n на множители может эффективно вычислять главные квадратичные корни по модулю n, тогда как такие вычисления столь же трудны сколь и факторизация n для того, кто этого разложения еще не знает. Наш второй кандидат на однонаправленную функцию с потайным ходом теперь должен быть очевиден. Вы случайно выбираете p и q и вычисляете n = p*q, которые открыто объявляете. После этого любой может эффективно вычислить квадраты по модулю n, но только ваш друг может эффективно обратить эту операцию (в предположении, что факторизация трудна).

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

Для более основополагающих сведений по вычислительной теории чисел мы отсылаем к [165].

1.2.Открытое распространение ключей

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

Точнее, хотелось бы иметь такой протокол, с помощью которого А и В обменивались бы сообщениями m1(от А к B), m2(от B к A), ..., до тех пор пока А и В окончательно не условятся о некотором ключе k таким образом, чтобы определить k из знания только m1, m2,... было бы практически невозможно. Подчеркнем еще раз, что этого необходимо добиться даже несмотря на то что А и В заранее не обмениваются никакой информацией, которая не была бы известна подслушивателю.

Первый протокол, который достигает этой кажущейся невозможной цели, был предложен Диффи (W. Diffie) и Хеллманом (M.E. Hellman)[101] в 1976 году. Он основывается на задаче дискретного логарифмирования, рассмотренной в разделе 1.1. Пусть n некоторое большое целое число, и пусть g другое целое, лежащее строго между 1 и n-1. В качестве первого щага протокола Диффи-Хеллмана A и B уславливаются об n и g посредством несекретного канала связи (альтернативно n и g могли бы быть стандартными параметрами, применяемыми всеми пользователями системы).

Затем А выбирает некоторое большое целое число x и вычисляет X = g^x mod(n). Соответственно, В выбирает y и вычисляет Y = g^y mod(n). После этого А и В обмениваются X и Y по тому же несекретному каналу связи, храня при этом в секрете x и y ( x знает только А, а y - только В). Наконец, А вычисляет Y^x mod(n); соответственно, В вычисляет X^y mod(n). Оба эти значения равны между собой, так как каждое из них равно g^(x*y) mod(n). Это и есть именно тот ключ k, который они хотели совместно выработать.

Нарушитель сталкивается с задачей вычисления k из информации, пересылаемой по несекретному каналу: g, n, X, Y. Очевидным подходом для нарушителя было бы вычислить x из g, n и X (или, по крайней мере, некоторое такое x', что g^x' mod(n)=X, так как любое такое x' дает Y^x' mod(n) = k). Однако, это в точности задача определения дискретного логарифма, которая считается практически невыполнимой. Еще никто не придумал способа вычислять k эффективно из g, n, X, Y, но и никто не смог доказать, что это невозможно, или хотя бы, что не существует лучшего способа сделать это, чем вычислить сначала дискретный логарифм. Поэтому, вообще говоря, правомерно предполагать, что вычисление k может быть осуществлено эффективно, даже если задача дискретного логарифмирования действительно оказалась бы практически невыполнимой.

Выбор g и n может оказывать существенное влияние на эффективность и надежность представленного выше проекта системы. Для того чтобы сократить размер возможных окончательных значений k, важно чтобы функция модульного возведения в степень f[g,n]: Zn -> Zn (как она определена в разделе 1.1.) была настолько почти взаимнооднозначной, насколько это возможно. В том случае, когда n является простым числом, всегда существует такое g, что g^x mod(n) принимает каждое из значений в промежутке от 1 до n-1, когда x пробегает значения из того же интервала. Такие g, известные как генераторы циклической группы Zn и были бы искомыми. В этом случае надежнее выбрать n таким образом, чтобы (n-1)/2 также было простым [191]. Кроме того можно было бы все указанные операции проводить в полях Галуа GF(2^k), методы вычисления в которых выходят далеко за рамки этого обзора [28]. Они предоставляют возможность намного более эффективно осуществлять умножение (а следовательно и возведение в степень), так как позволяют избежать при вычислениях необходимости переносов и приведений по модулю. Размер ключа в этом случае будет, однако, существенно длинее.

Несмотря на то, что очень большие дискретные логарифмы возможно и являются трудновычислимыми, хотелось бы предупредить читателя, что для их вычисления существуют алгоритмы намного лучшие, чем исчерпывающий поиск. Самые лучшие из известных в настоящее время алгоритмов, когда n является простым числом, описаны в [80], или в [186] при вычислениях в GF(2^k). Но такие поля должны тщательно анализироваться при выборе размера ключа. Злополучная аппаратная реализация была однажды разработана в Hewlitt-Packard, используя GF(2^127) [247]. И ключи в ней были быстро раскрыты с помощью [29].

В предположении, что n и g являются стандартными параметрами, интересной альтернативой описанному ранее интерактивному протоколу заключается в учреждении и использовании для распространения некоторого единого для всех справочника. Каждый пользователь записывает в этот справочник свой собственный X, вычисленный как g^x mod(n) для своего случайно выбранного секретного x. Это позволяет двум пользователям сформировать их совместный секретный ключ даже до того как они поговорят друг с другом с самого начала. Основной недостаток такого доступа к справочнику состоит в том, что он не поддерживает пользователей в изменении своих секретных ключей достаточно часто. Мы намереваемся вернуться к этой теме в разделе 1.7.

Другим подходом к проблеме распространения ключей является предложенная Беннетом (C.H.Bennet) и Брассардом (G.Brassard) квантовая криптография. Ее надежность не зависит от недоказанных предположений о вычислительной сложности, основанных на трудности вычислений каких бы то ни было функций.

Она остается таковой даже тогда, когда нарушитель имеет неограниченные вычислительные ресурсы, или если все-таки P = NP [17,18,19,20,21].

1.3. Криптосистемы с открытым ключом. Теория.

Система открытого распространения ключей, так как она описана в разделе 1.2, позволяет двум сторонам сформировать совместную часть некоторой распределенной секретной информации. Однако, ни одна из сторон не имеет никакого непосредственного влияния на то, какой окажется эта информация.

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

Криптосистемы с открытым ключом используются непосредственно для передачи исключительно важных сообщений. Во многом подобные криптосистемам с секретным ключом криптосистемы с открытым ключом состоят из: пространства ключей K, а для каждого k из K, из пространств открытых сообщений Mk, пространств шифртекстов Ck и пар функций Ek: Mk -> Ck и Dk: Ck -> Mk, таких что Dk(Ek(m)) = m для любого открытого текста m из Mk. Снова, как и в криптосистемах с секретным ключом, эффективные алгоритмы для вычисления как Ek, так и Dk, должны легко получаться для каждого ключа k. Мы будем называть алгоритмы, полученные таким образом, естественными алгоритмами. Важной новой отличительной особенностью является то, что Ek должна быть однонаправленной функцией с потайным ходом: необходимо, чтобы было практически невозможно построить никакого эффективного алгоритма для вычисления Dk (но только естественного алгоритма), зная описание естественного алгоритма для вычисления Ek.

В частности, это означает, что k не должно появляться в явном виде в естественном алгоритме шифрования.

Криптографические системы с открытым ключом используются следующим образом. Каждый пользователь раз и навсегда выбирает некоторый случайный ключ k из K. Он использует этот ключ для получения обоих естественных алгоритмов Ek и Dk. Затем он делает публично доступным свой алгоритм шифрования Ek, возможно посредством использования при этом некоторого справочника, но хранит в тайне свой алгоритм дешифрования Dk.

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

В противоположность криптосистемам с секретным ключом, заметим, что если пользователь А, закодировав некоторое сообщение m для пользователя В, сохранил шифртекст С, но потерял открытый текст (или забыл все, что в нем содержалось), то он не будет иметь никаких преимуществ перед нарушителем в раскрытии m из С.

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

* Атака на основе выбранного шифртекста: против определенного пользователя, чьи функции суть Ek и Dk, криптоаналитик задается выбранными шифрованными сообщениями С1, С2, ..., Ci и подбирает соответствующие m[1] = Dk(C1), m[2] = = Dk(C2),..., m[i] = Dk(Ci), при условии, что они существуют. Он хочет определить k, или какой-нибудь эффективный алгоритм вычисления Dk, или(за неимением такой возможности), пытается найти m[i+1] из некоторого нового шифртекста С[i+1] = Ek(m[i+1]).

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

В результате получается, что мы не знаем, как доказать существование криптосистем с открытым ключом. Это может быть не более, чем причудливый способ поговорить о пустом множестве, даже несмотря на то, что возможная осуществимость этого понятия была уже формально продемонстрирована в относительных утверждениях [49,46,47].

Поэтому точно так же, как это было в случае однонаправленных функций (с потайным ходом), мы должны быть удовлетворены кандидатами на криптосистемы с открытым ключом. Два наилучших из известных таких кандидата были спроектированы вскоре после того, как Диффи и Хеллман ввели понятие криптографии с открытым ключом [100,101].

Одна из них, так называемая ранцевая криптосистема Меркля(R.C. Merkle) и Хеллмана [180,147], была вскоре раскрыта [99,104,209,3,59,166,60]. И хотя существуют еще не раскрытые варианты первоначальной схемы, им, по видимому, не стоит доверять. Брикель(E.F. Brickell) написал очень детальную историю криптоанализа ранцевой криптографической системы [61].

Другая, наилучшая из известных криптосистем с открытым ключом, все еще остается несокрушимой, и мы сейчас опишем ее в некоторых деталях. Были предложены и другие системы, такие как системы Макэлиса(R.J. McEliece) [177] и ЭльГамаля(T. ElGamal) [105]. Мы не будем обсуждать их здесь. По поводу исчерпывающего обзора криптографии с открытым ключом обращайтесь к [167].

1.4. Криптосистема RSA

Самой первой криптосистемой с открытым ключом из вообще предложенных в открытой литературе была система Райвеста (R.L.Rivest), Шамира (A.Shamir) и Эдльмана (L.M.Adleman)[205]. Она стала известна под названием RSA или MIT криптосистемы. Основана она на вере в то, что модульное возведение в степень при фиксированных экспоненте и модуле является однонаправленной функцией с потайным ходом (см. раздел 4.1). Для первоначального ознакомления с этой криптосистемой обращайтесь к [120].

Пусть p и q - два больших различных простых числа, и пусть n = p*q и e некоторое целое, взаимно простое с (p-1)*(q-1). Тогда каждая такая тройка k = объявляется личным(секретным) ключом для криптосистемы RSA.

Оба соответствующих пространства открытых текстов Mk и зашифрованных сообщений Ck суть Zn - множество неотрицательных целых, меньших n. Если подлинное сообщение окажется слишком длинным, чтобы принадлежать Zn, его необходимо разбить на части и зашифровать, используя режим шифрования со сцеплением блоков, описанный в разделе 3.5.

Соответствующая ключу k функция шифрования Ek: Mk -> Ck определяется как Ek(m) = m^e mod(n). Для того, чтобы полностью определить естественный алгоритм ее вычисления достаточно записать e и n в открытый справочник. Такая пара называется открытым ключом, который легко вычисляется с помощью личного ключа .

Вспомним из раздела 1.1, что Ek является кандидатом на однонаправленную функцию с потайным ходом, и хотя существует эффективный алгоритм вычисления обратной ей функции Dk, мы не знаем, как получить его эффективно, задаваясь только естественным алгоритмом вычисления Ek (т.е. только для заданных n и e).

Однако эффективный алгоритм вычисления Dk легко получить, задав дополнительную секретную информацию p и q. С этой целью, используя обобщеные алгоритмы Евклида для нахождения наибольшего общего делителя, чтобы вычислить целое число d, такое что e*d = 1 mod ф(n), где ф(n) = (p-1)*(q-1). По известной теореме Эйлера m^(e*d) = m mod(n) для каждого целого числа m и, следовательно, (m^e)^d mod(n) = m, при условии что 0 <= m < n, что обеспечивается, когда m принадлежит Mk.

Функция дешифрования Dk: Ck -> Mk в связи с этим определяется как Dk(c) = m^d mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. (Для заданных p и q существует даже более эффективный алгоритм вычисления Dk, основанный на китайской теореме об остатках [193]).

Суммируя все сказанное, тогда каждый пользователь криптосистемы RSA должен раз и навсегда выбрать случайно подходящие целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете. Это дает возможность любому другому пользователю шифровать посылаемые ему сообщения, которые только он и может расшифровать. Для того чтобы эта идея была реализована практически, решающим является удовлетворение требование, чтобы генерация больших случайных простых чисел и вычисление d были легкоосуществимы. К счастью, проверка чисел на простоту оказывается действительно легче их разложения на множители, благодаря вероятностным алгоритмам СоловеяШтрассена (R. Solovay - V. Strassen)[223] и Рабина (M.O. Rabin)[197].

По поводу более связанного с криптографией вопроса генерации простых чисел (а не проверки на простоту) обращайтесь к [81,13]. Относительно описания расширенного алгоритма Евклида для вычисления d смотрите [4,94] (если же вы предпочитаете переоткрыть расширенный алгоритм Евклида самостоятельно, то можете найти полезными те указания, которые даны к задаче 8.5.12b [52]).

В качестве небольшого примера, пусть p = 19 и q = 23, так что n = 437 и ф(n) = 396. Пусть также e = 13, и поэтому d = 61, так как 13*61 = 793 = 2ф(n)+1. Тогда сообщение в открытом текте m = 123 будет зашифровано как c = 123^13 mod(437) = 386. Действительно, 386^61 mod(437) = 123. Особо отметим ситуацию, когда криптоаналитик, перехвативший шифртекст c = Ek(m), посланный известному пользователю, знает естественный алгоритм шифрования Ek, используемый отправителем для вычисления c. Это предположение имеет два важных следствия. Если бы нарушитель угадал в точности открытый текст сообщения m, то он смог бы вычислить Ek(m) точно так же, как и получатель, и сравнить полученный результат с c, чтобы проверить свое предположение. Такая угроза является опасной, если число возможных открытых текстов сравнительно невелико, учитывая возможность исчерпывающего поиска.

Эта трудность может быть до некоторой степени преодолена путем разбавления коротких сообщений случайными битами, однако использование вероятностного шифрования (раздел 4.6) является более приемлемым решением. Смотрите также [206].

Другое следствие из знания нарушителем открытого алгоритма шифрования более специфично для криптосистемы RSA. Он знает, что c = m^e mod(n) для известных значений c, e и n (но не знает m). Если бы он мог разложить n (раскрыв таким образом личный секретный ключ законного получателя c), то он мог бы получить ф(n) = (p-1)*(q-1) и, применив расширенный алгоритм Евклида, вычислить d, а затем и m = c^d mod(n). К счастью, неизвестно алгоритма, который смог бы разложить на множители двухсотзначное десятичное число за приемлемое время, и, таким образом, считается абсолютно надежным выбирать и p и q длиной примерно в сто знаков.

При выборе p и q необходима особая тщательность для того, чтобы не предоставить никаких зацепок известным алгоритмам факторизации. В частности, наибольший общий делитель p-1 и q-1 должен быть небольшим, а оба p-1 и q-1 должны иметь большие простые делители.

Блэкли (G.R. Blakley) и Борош (I. Borosh) предлагают выбирать p и q так, чтобы (p-1)/2 и (q-1)/2 были бы простыми [31]. Для более широкого обсуждения этих вопросов рекомендуем [94]. Гордон (J.A. Gordon) предлагает эффективные способы выбора подходящих сильных простых чисел [139].

Даже если факторизация и трудна, неизвестно является ли столь же трудным и раскрытие RSA. Возможно, что d может быть вычислено из открытой информации e и n, вообще, без разложения n на множители. Возможно также и то, что значение d (а,следовательно, и значения множителей числа n) действительно практически трудновычислимы из e и n, даже если существует иной эффективный алгоритм раскрытия m из e, n и m^e mod(n). Были предложены другие криптосистемы с открытым ключом, для которых было доказано, что раскрытие открытого текста из доступной нарушителю информации в них, столь же трудно, сколь и разложение на множители больших чисел [196,240], но такие криптосистемы тотчас же раскрываются при атаке на основе выбранного шифртекста.

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

Пользователи RSA должны быть осведомлены о том, что эта криптосхема является слабой при некоторых видах атак на основе выбранного шифртекста [86,95]. Предположим, например, что нарушитель перехватил некоторое c = m^e mod(n), где e и n открытая информация. Ему хотелось бы определить m. При атаке на основе выбранного шифртекста, ему предоставляется возможность передать некоторое c' законному получателю с тем, чтобы получить в ответ соответствующее m', такое, что c'= m'^e mod(n). Разумно ожидать, что получатель может уклониться от ответа, если нарушитель попытается использовать непосредственно c'= c (в противном случае никакая криптосистема, вероятно, не может быть надежной). Однако, нарушитель может замаскировать свой вопрос, выбрав случайно некоторое x из Zn* и вычислив c'= (x^e)*c mod(n).

Исходный открытый текст m может быть тогда получен эффективно (используя обобщенный алгоритм Евклида), поскольку m = m'*x^(-1) mod(n). Неизвестно, может ли более хитроумная атака на основе выбранного шифртекста действительно раскрыть RSA в том смысле, что позволит нарушителю вычислить множители n или, хотя бы, секретную экспоненту дешифрования d.

Если бы это было так, то последующие шифртексты можно было бы расшифровывать без необходимости обращения к законному получателю. Для первого знакомства в связи с этом смотри [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, но официальная документация о ней пока еще недоступна.

1.5. Генерация псевдослучайных битов

Последовательность называется псевдослучайной, если она выглядит, как бессистемнаая и случайная, хотя на самом деле создавалась с помощью сугубо детерминированного процесса, известного под названием псевдослучайного генератора. Такие генераторы задаются действительно случайной начальной последовательностью, называемой исходной, и детерминировано получают из нее намного более длинную псевдослучайную последовательность. В этом смысле псевдослучайные генераторы можно рассматривать как распространители случайности. В качестве энциклопедии по классической выработке псевдослучайных последовательностей и тестам, цель которых заключается в том, чтобы различать псевдослучайные последовательности от истинно случайных, рекомендуем [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]: криптоаналитик, который знает как работает генератор, но не знает, какой исходный вектор в действительности используется, не может сделать ничего лучшего, чем подбрасывать правильную монету, для того чтобы угадать первый бит, выработанный генератором, даже после просмотра всей сгенерированной затем последовательности (если только он не окажется очень удачливым или же сможет проделать практически невыполнимые вычисления).

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

Полная уместность генераторов непредикативных влево была установлена Яо(A. Yao), который доказал, что любой такой генератор является криптографически сильным [243]. Наконец, Л.Левин дал необходимые и достаточные условия для существования таких генераторов [170].

Теперь мы приведем описание более простого и в вычислительном отношении более эффективного кандидата на криптографически сильный псевдослучайный генератор, который известен как BBS генератор, названный так в честь Л. Блюма(L.Blum), М. Блюма(M. Blum) и Шуба(M. Shub) [33].

Он основывается на втором кандидате на однонаправленную функцию с потайным ходом, описанном в разделе 1.1. Напомним, что n называется целым числом Блюма, если оно является произведением двух различных простых p и q, оба из которых сравнимы с 3 по модулю 4. Напомним также, что возведение в квадрат по модулю n является перестановкой квадратичных остатков по модулю n, и считается, что она является однонаправленной функцией с потайным ходом, так как было доказано, что трудность ее обращения (т.е. вычисления примитивных корней) вычислительно эквивалента разложению n на множители.

В предположении, что факторизация n трудна, может быть доказана даже более сильная теорема: для почти всех квадратичных остатков x, подбрасывание правильной монеты приводит к наилучшей возможной оценке первого значащего разряда x, который, однако, может быть легко вычислен при знании x^2 mod(n) [231,232,5].

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

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

Пусть n - целое Блюма с неизвестным разложением на множители. Выберем в качестве исходного числа случайный квадратичный остаток x[0] (для того, чтобы это сделать, выберем случайное целое x взаимно простое с n и вычислим x[0] = x^2 mod(n)). Для i >= 0 определим рекурсивно x[i+1] = x[i]^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 любого заданного квадратичного остатка y мог бы быть определен следующим образом. Вычисляем псевдослучайную последовательность BBS[n,t-1](y) и представляем ее как BBS[n,t](x) с удаленым первым своим битом. Отгадываем этот пропущенный бит и замечаем, что по определению он и является первым значащим битом x, который мы искали.

Из этого следует, что BBS-генератор должен быть непредикативным влево в предположении, что факторизация n трудна. Следовательно, по теореме Яо, он является криптографически сильным.

Дополнительное привлекательное свойство этого генератора заключается в том, что он обеспечивает прямое определение тех отдельных битов, которые он вырабатывает, для всех, кто знает разложение n на множители. Для этого заметим, что x[i] = x[0]^(2^i) mod(n). По теореме Эйлера x^ф(n) = 1 mod(n), где ф(n) = (p-1)(q-1).

Следовательно, x[i] = [x[0]^((2^i) mod ф(n))] mod(n), вычисляется эффективно из исходного числа x[0] и требуемого индекса i посредством двух применений быстрого алгоритма модульного возведения в степень.

1.6. Вероятностное шифрование.

Криптография с открытым ключом в значительной степени решает проблему распространения ключей, которая является довольно серьезной для криптографии с секретным ключом. Однако, как мы указывали выше, при перехвате шифртекста 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 является открытам ключом. Пространство сообщений открытого текста - это множество