Брассар Д. - Современная криптология
Криптография - область знаний, изучающая тайнопись (= криптография) и методы ее раскрытия (= криптоанализ), по меткому выражению Рональда Райвеста (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-часовой ^тр^^овской лекции предыдущего года.
Поэтому она сравнительно небольшая - немногим более ста среднего формата страниц, из которых 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. Однонаправленные функции
Понятия однонаправленной функции и однонаправленной функции с потайным ходом являются центральными понятиями всей криптографии с открытым ключом.
Рассмотрим два произвольных множества X и Y . Функция f: X - Y называется однонаправленной, если f(x) может быть легко вычислена для каждого x из X, тогда как почти для всех у из Y вычисление такого x из X, что f(x) = у (при условии, что хотя бы один такой x существует), является сложным. Это понятие не нужно путать с функциями, которые являются математически необратимыми из-за того, что они не взаимнооднозначны или не на (т.е. из-за того, что существует несколько различных x, таких что f(x) = у, или их нет вовсе).
Наше нынешнее состояние знаний не позволяет нам доказать, что однонаправленные функции вообще существуют, так как их существование разрешило бы (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) = аЛш mod( n), где i mod(j) обозначает положительный остаток при делении i на j. Сразу не очевидно, что такую функцию можно вычислить эффективно, когда длина каждого из трех параметров a, n и m составляет несколько сотен знаков. То, что это возможно и в самом деле так, лучше всего увидеть на примере:
аЛ25=(((аЛ2*а)л2)л2)л2*а.
Он показывает, как можно вычислить аЛ25 c помощью лишь четырех возведений в квадрат и еще двух умножений. При вычислении аЛш 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) = aAm mod(n).
Необходимо убедиться в понимании различия между функциями f[a,n] и g[m,n].
Опять по аналогии с действительным анализом, операция обратная g[m,n] известна под названием взятия корня m-той степени из x по модулю n: даны целые числа m, n и x, найти такое целое а(если оно существует), что aAm mod(n) = x. Например, 5 это корень 4ой степени из 16 по модулю 21, так как мы уже видели, что 5А4 mod(21) = 16. Очевидно, что 2 также является корнем 4-ой степени из 16 по модулю 21.
