Коммерческие алгоритмы, заменившие DES

В ответ на проблемы с длиной ключа и производительностью, проявив­шиеся в Triple DES, многие криптографы и компании разработали новые блочные шифры. Наиболее популярными предложениями стали алгорит­мы RC2 и RC5 корпорации RSA Data Security, IDEA компании Ascom, Cast компании Entrust, Safer компании Cylink и Blowfish компании Counterpa­ne Systems.

Все эти алгоритмы были более быстрыми, чем Triple DES, и они могли работать с ключами большей длины и даже ключами переменной длины. В то время как DES и Triple DES требуют применения ключей определен­ной длины, новые алгоритмы позволяют использовать ключи различной длины. Вспомните, что нужно выбрать достаточно длинный ключ, чтобы сделать вашу систему неприступной для атак прямого перебора ключей или, по крайней мере, существенно снизить вероятность успеха таких атак. Когда-то считалось, что 56-битный ключ достаточно надежен. Одна­ко настал момент, когда ключи такой длины уже не обеспечивали доста­точную степень защиты, так что стал применяться 64-битный ключ. В DES нельзя увеличить длину ключа, коммерческие алгоритмы, пришедшие ему на смену, могут это делать.

Различные коммерческие альтернативы DES получили определенное распространение, и компании стали создавать программные продукты с использованием этих алгоритмов. Но ни один из них не стал стандартом, как DES и Triple DES.

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

План Национального института стандартов и технологий был офици­ально объявлен 2 января 1997 г., когда было предложено представить ал­горитмы для утверждения в качестве нового стандарта под названием AES. В качестве условия для участия в процессе создания AES разработчики должны были отказаться претендовать на право интеллектуальной собст­венности на выбранный в качестве стандарта алгоритм. Многие разработ­чики и компании выразили свое согласие, и 20 августа 1998 г. NIST назвал 15 кандидатов.

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

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

Наконец, 2 октября 2000 г. NIST объявил победителя: им стал алгоритм под названием Rijndael, разработанный двумя бельгийскими исследовате­лями: Винсентом Риджменом и Джоаном Дименом.

С этого момента алгоритм AES стал свободно доступен для реализации, применения и продажи. Как и DES, предполагалось, что AES станет меж­дународным стандартом. Можно ожидать, что в ближайшие годы это про­изойдет.

Системы с открытым ключом.

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

В 70-х годах прошлого столетия появился новый тип криптографических алго­ритмов — алгоритмы шифрования с открытым ключом (или асимметрич­ное шифрование). В таких системах все ключи "живут" парами: один исполь­зуется для шифрования, другой — для дешифрования. Самое интересное — зашифрованное сообщение не может быть дешифровано без знания второго ключа, даже если знать ключ, который использовался для шифрования.

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

Одним из наиболее популярных алгоритмов шифрования с открытым клю­чом является алгоритм RSA, названный по именам его авторов(см. далее). Для созда­ния шифра по их методу выбирается большое целое число п — произведение двух простых множителей, р и q. При кодировании используется некоторое целое число, традиционно обозначаемое е (от encode), а при декодировании нужно иметь другое число, обозначаемое d (от decode). Хотя d определяется по е однозначно, но для его определения нужно иметь разложение п на р и q; при очень больших п эта задача оказывается достаточно трудной.

Теперь перейдем к деталям. Пусть п = р • q, где р и q — два простых числа. Положим . Приведем следующие факты из теории чисел.

Лемма 1. Пусть а — число, взаимно простое с п. Тогда .

Доказательство. Пусть Ф(n) — множество всех чисел, не превосходя­щих п и взаимно простых с ним. Заметим, что |Ф(n) | == . Умножение числа из этого множества на а по модулю n есть биекция: если b • а = с • а, то, по­скольку а взаимно просто с п, разность с — b должна делиться на n. Таким образом,

откуда и следует утверждение леммы.

Лемма 2. Для каждого числа е, взаимно простого с , существует един­ственное d  1: п, для которого е • d = 1 (mod ).

Доказательство. Вспомним алгоритм Евклида. При установлении того, что общий наибольший делитель е и  равен 1, легко находятся (см. дальше пример) коэффициенты d и k, для которых d • е + k •  = 1. Это верно для любых взаимно простых е и . Однозначность определения d получается легко доказательством от противного.

Пример. Пусть е = 47 и  = 104. Имеем  = 2 е + 10. Далее, в соответ­ствии с алгоритмом Евклида е = 4 • 10 + 7, затем 10 = 1 • 7 + 3, 7 == 2 • 3 + 1. Последнее равенство переписывается так: 1 =7 - 2•3. Так как 3 == 10 - 1 • 7, то 1 = 3 • 7 - 2 • 10. Так как 7 = е - 4 • 10, то 1 = 3 • е - 14 • 10. Так как 10 ==  - 2 • е, то 1 = 31 • е - 14 .

 

Перейдем к описанию персонального шифра. Для каждого получателя вы­берем достаточно большое число п, которое имеет два простых делителя р и q. Например, n = 1 093 709 = 997 • 1097, хотя реально используются гораздо бо­лее длинные числа, которые разложить на множители очень трудно. По этим сомножителям находится  = pq — р — q + 1. В нашем случае  = 1091 616.

Получатель (хозяин шифра) выбирает какое-либо число е, взаимно простое с , и вычисляет "обратное" для него d. Если выбрать е = 397, то d = 145 777. Числа п и е сообщаются отправителям, это открытая часть системы шифро­вания.

Отправляемый текст перестраивается таким образом, чтобы он состоял из отдельных чисел в диапазоне от 1 до п. Каждое кодируемое число х  1 :п возводится в степень е по модулю п. Возведение числа в большую степень сильно упрощается, если используется двоичное разложение показателя сте­пени. Например, чтобы возвести число n в степень 397 = 110001101₂, нужно последовательно вычислить x², x⁴, x⁸, x¹⁶, x³², x⁶⁴, x¹²⁸, x²⁵⁶ и перемножить нужные пять сомножителей. Результат у передается получателю.

Получатель, имея число d, вычисляет у ^d по модулю п. Так как , то, если , результат возведения в степень равен .

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

"Рюкзак" Меркля-Хеллмана.

По шифруемой битовой строке ,составляется сумма , которая и является шифрованным текстом. Числа а, известны, они и являются открытым ключом. Секретный ключ со­стоит из взаимно простых чисел W и М, b_i, специальным образом выбранного набора чисел  и перестановки  порядка п. Числа а _i, связаны с b_i соот­ношением . Восстановление набора x по значению s по открытому ключу очень сложно, а по секретному ключу просто, благодаря особому свой­ству "сверхвозрастания" последовательности b_i: каждое следующее b_i больше суммы всех предыдущих, а М больше суммы всех b_i.

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

Рассмотрим более общие моменты.

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

Рис. 31.

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

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

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

Рис. 32.

 

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

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

Рис. 33.

 

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

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

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

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

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

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

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

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

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

Электронная подпись.

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

Пусть передается текст (число) x, который после преобразования превра­тился в "подпись" z = x^d. Получатель этой подписи имеет вторую часть клю­ча, т. е. е; он выполняет прямое преобразование и, так как , получает исходный текст.

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

Основной недостаток систем шифрования с открытым ключом — низкая скорость. Самая "быстрая" реализация алгоритма RSA в тысячи раз медлен­нее любого стандартного алгоритма симметричного шифрования. Поэтому для шифрования длинных сообщений, а также в системах реального времени пред­почитают использовать симметричное шифрование. На практике же использу­ются оба типа алгоритмов, скомбинированные так, чтобы нейтрализовать их недостатки. Такая схема называется цифровым конвертом (Digital Envelope).

Ее основная идея состоит в следующем:

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

2. Исходное сообщение шифруется с использованием ключа сессии.

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

4. Зашифрованное сообщение и цифровой конверт посылаются по нужно­му адресу.

Получатель сначала дешифрует цифровой конверт с помощью своего сек­ретного ключа. Затем с помощью ключа сессии он дешифрует само сообщение.

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

Алгоритмы-дайджесты в некотором роде похожи на алгоритмы шифрования тем, что тоже получают на входе обыкновенное "читаемое" сообщение и на выходе дают некоторый "нечитаемый" набор байтов: короткие (фиксированной длины) дайджест-сообщения (также называемые хешами (hash)) обычно на­много короче исходного сообщения. Их дешифрование не предусматривается.

Дайджесты выступают в роли своеобразных "контрольных сумм" сообще­ния, поскольку если в исходном сообщении изменить хотя бы один бит, то дайджест измененной информации будет отличаться от исходного дайджеста. Они используются при передаче информации в качестве индикатора правиль­ности принятой информации. Например, в стандарте цифровой подписи DSS (Digital Signature Standard) используется следующий механизм:

1. Получают дайджест исходного сообщения.

2. Зашифровывают дайджест с помощью секретного ключа ("подписыва­ют" дайджест).

3. Посылают "подписанный" дайджест и исходное сообщение получателю.

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

PGP и другие программы подобного рода накладывают цифровую подпись для обеспечения аутентификации сообщения. Закрытый ключ отправителя используется для зашифровки дайджеста сообщения, таким образом "подписывая" сообщение. Дайджест сообщения — это 160- или 128-битная криптографически стойкая односторонняя хэш-функция. В чем-то она похожа на "контрольную сумму" или код проверки ошибок CRC, который компактно представляет сообщение и используется для проверки сообщения на наличие изменений. В отличие от CRC, дайджест сообщения формируется таким образом, что злоумышленник не может сгенерировать поддельное сообщение с аналогичным дайджестом. Дайджест сообщения передается в зашифрованном закрытым ключом отправителя виде, составляя цифровую подпись сообщения.

На рис. 34 показано, как генерируется цифровая подпись.

Рис. 34.

 

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

Рис. 35.

 

Взлом защищенных файлов.

Атака на ключ

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

Допустим, ключ является числом меж­ду 0 и 100 000 000 000 (сто миллиардов). Атакующий берет шифротекст и передает его алгоритму шифрования вместе с предполагаемым ключом равным 0. Алгоритм делает свою работу и выдает результат. Если получен­ные данные имеют осмысленный вид, возможно, что 0 - это правильный ключ. Если данные выглядят бессмысленно, значит 0 не является правильным ключом. В этом случае нужно попробовать 1, затем 2, 3, 4 и т.д. (см. рис. 36).

Рис. 36 Атака методом прямого перебора

 

Помните, что алгоритм просто выполняет свои действия независимо от входных данных. У него нет способа узнать, является ли полученный ре­зультат правильным. Даже если значение близко к значению ключа,, быть может, отличается на 1, результат все равно будет бессмысленным. В связи с этим необходимо просматривать результаты, чтобы сказать, может ли быть использованное значение ключом. Искушенные атакующие пишут программы, просматривающие результат. Он представляет собой последо­вательность символов алфавита? Да? Передать этот ключ атакующему. Нет? Попробовать следующий ключ.

На пробу ключа обычно уходит достаточно мало времени. Атакующий может написать программу, которая перебирает за секунду большое коли­чество ключей. В конечном итоге, атакующий может попытаться испробо­вать каждое возможное число между 0 и 100 миллиардами, но это не обя­зательно потребуется. После того, как верный ключ найден, продолжать поиск не нужно. В среднем атакующий испробует половину всех возмож­ных ключей — в нашем примере, 50 миллиардов ключей, — прежде чем найдет правильный. Иногда это занимает больше времени, иногда меньше, но в среднем будет испробовано около половины всех возможных ключей.

Сколько времени потребуется атакующему, чтобы испробовать 50 мил­лиардов ключей? Три года? Три дня? Три минуты? Предположим, вы хо­тите сохранить ваш секрет по меньшей мере в течение трех лет, но атакую­щему понадобится всего три минуты, чтобы перебрать 50 миллиардов зна­чений. Что вы будете делать? Вы изберете больший диапазон значений ключей. Вместо того, чтобы выбирать число между 0 и 100 миллиардами, вы выберете число между 0 и 100 миллиардами миллиардов миллиардов миллиардов. Теперь атакующему придется испробовать в среднем гораздо больше ключей, прежде чем он найдет правильный.

Эта концепция диапазона возможных значений ключей известна как длина ключа.

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

40-битный ключ (шестнадцатеричное представление)	000000000000000000010000000002…6P5581D20C…FF FF FF FF FF
64-битный ключ (шестнадцатеричное представле­ние)	000000000000000000000000000000010000000000000002…59C671DD54E44092…FF FF FF FF FF FF FF
128-битный ключ (шестнадцатеричное представление)	000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000002…201486AE18845ACFE98098B2443C11D2 …FF FF FF FF FF FP FF FF FF FF FF FF FF FF FF FF

 

Каждый лишний бит в размере ключа в два раза увеличивает время, не­обходимое для выполнения атаки методом прямого перебора. Если на взлом 40-битного ключа потребуется 3 часа, то взлом 41-битного ключа займет 6 часов, 42-битного ключа — 12 часов и т.д. Почему? Каждый до­полнительный бит вдвое увеличивает число возможных значений ключей.

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

Следовательно, если вы хотите затруднить задачу атакующему, то выби­раете длинный ключ. Чем длиннее ключ, тем выше безопасность. Насколь­ко длинным должен быть ключ? В течение ряда лет RSA Laboratoriee предлагала принять участие в конкурсе. Первый человек или организация, которой удастся расшифровать определенное сообщение, получит денежный приз. Некоторые из таких конкурсов являлись своеобразными тестами для атак прямого перебора ключей. В 1997 г. 40-битный ключ был вскрыт за 3 часа, а 48-битный ключ — за 280 часов. В 1999 г. компании Electronic Frontier Foundation удалось определить 56-битный ключ за 24 часа. В каждом случае до того, как ключ был найден, было просмотрено более 56% ключей. В январе 1997 г. было предложено вскрыть 64-битный ключ. В де­кабре 2000 г. эта задача еще не была решена. Во всех этих случаях сотни или даже тысячи компьютеров совместно работали, чтобы взломать ключи. В действительности при взломе 56-битного ключа DES, который компания Electronic Frontier Foundation осуществила за 24 часа, один из этих компьютеров представлял собой специализированный взломщик DES. Такой компьютер делает только одно: проверяет ключи DES. Атакующий, который работает тайно, скорее всего, не может воспользоваться мощью сотен компьютеров и не будет иметь в своем распоряжении компьютера, специально созданного для взлома определенного алгоритма. Вот почему для большинства атакующих время, которое требуется для взлома ключа, будет существенно большим. С другой стороны, если атакующие работают в спецслужбе с огромными ресурсами, ситуация может быть иной.

Мы можем рассмотреть наихудший сценарий. Допустим, что просмотр 1% пространства ключей для 56-битного ключа занимает 1 секунду, а про­смотр 50% занимает 1 минуту (см. таблицу??). Каждый раз, когда мы до­бавляем бит к длине ключа, время поиска удваивается.

 

Таблица??. Наихудший сценарий. Сколько времени потребуется для взло­ма ключей различной длины при атаке, использующей прямой перебор

Количество битов	1% общего числа ключей	50% общего числа ключей
56	1 секунда	1 минута
57	2 секунды	2 минуты
58	4 секунды	4 минуты
64	4,2 минуты	4,2 часа
72	17,9 часов	44,8 дня
80	190,9 дней	31,4 лет
90	535 лет	321 век
108	140000 тысячелетий	8 миллионов тысячелетий
128	146 миллиардов тысячелетий	8 триллионов тысячелетий

 

На сегодняшний день наиболее распространенной длиной симметрично­го ключа является 128 битов. Если технические достижения будут этому способствовать, атакующие, использующие метод прямого перебора, смо­гут улучшить показатели (может быть, что им удастся сократить время на определение 128-битного ключа до нескольких лет), в этом случае придет­ся использовать 256-битные ключи.

Можно подумать, что раз компьютерная техника постоянно развивается, то постоянно придется увеличивать длину ключей. Не наступит ли время, когда потребуются ключи такой длины, что с ними станет слишком не­удобно работать. В ответ можно сказать, что вам почти наверняка никогда не придется использовать ключ длиной более 512 битов (64 байта). Вообра­зите, что каждый атом во Вселенной (всего их около 2³⁰⁰) является компь­ютером, и что каждый из этих компьютеров может проверить 2³⁰⁰ ключей в секунду. Для того чтобы просмотреть 1°/о ключей длиной 512 битов, по­требуется около 2¹⁶² тысячелетий. В настоящее время считается, что воз­раст Вселенной не превышает 2²⁴ тысячелетий. Другими словами, крайне маловероятно, что техника когда-нибудь разовьется до такой степени, что придется использовать слишком длинные ключи.

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

Атака на алгоритм.

Предположим, некто определил, что при использовании данного алго­ритма каждый 14-й бит шифротекста совпадает с каждым 12-м битом соот­ветствующего открытого текста. Другими словами, если 14-й бит шифро­текста равен 1, 12-й бит открытого текста также буДет равен 1, если 28-й бит шифротекста равен 0, то 24-й бит открытого текста также будет ра­вен 0, и т.д. При этом ключ не оказывает никакого влияния. Кроме того, атакующий видит, что если определенная комбинация битов присутствует в определенном месте шифротекста, соответствующая часть открытого текста должна иметь определенную структуру.

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

Вот другое возможное слабое место. Предположим, что атакующему из­вестен некий открытый Текст и соответствующий ему шифротекст. Допус­тим, что атакующий способен вычислить ключ на основе этой информа­ции. Но если атакующий знает открытый текст, зачем ему беспокоиться об отыскании ключа? Дело в том, что атакующий может знать или быть в со­стоянии предугадать только часть открытого текста. Вспомним записку, о которой мы говорили в начале главы. Атакующий может видеть шифро­текст, сообразить, что он представляет собой документ Word, и сделать предположение о некоторых служебных символах в его начале. Кроме того, атакующий может догадаться, что документ является сообщением электронной почты, исходя из стандартных слов “ТО: (Кому:)”, “FROM: (От:)” и “RE: (Ответ:)”. Короче говоря, если кто-либо может вычислить ключ, исходя из фрагментов шифротекста и соответствующего открытого текста, он легко восстановит все сообщение. Такой метод называется ата­кой на основе известного открытого текста.

Скомпрометированный пароль.

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

Некоторые рекомендации по защите пароля:

1. Нельзя использовать очевидные фразы, которые легко угадать, например, имена детей или супруги.

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

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

Подделка открытых ключей.

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

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