Отправитель и получатель. Сообщения и шифрование 4 глава

2.6 Цифровые подписи

Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Что же так притягательно в подписи [1392]?

1. Подпись достоверна. Она убеждает получателя документа в том, что подписавший сознательно подписал документ.

2. Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.

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

4. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изменить.

5. От подписи не возможно отречься. Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ.

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

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

Подпись документа с помощью симметричных криптосистем и посредника

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

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

(1) Алиса шифрует свое сообщение Бобу ключом K_A и посылает его Тренту.

(2) Трент, зная ключ K_A, расшифровывает сообщение.

(3) Трент добавляет к расшифрованному сообщению утверждение, что он получил это сообщение от Алисы, и шифрует это новое сообщение ключом K_B.

(4) Трент посылает новое сообщение Бобу.

(5) Боб расшифровывает сообщение ключом K_B. Он может прочитать и сообщение Алисы, и подтверждение Трента, что сообщение отправлено именно Алисой.

Откуда Трент узнает, что сообщение пришло именно от Алисы, а не от какого-то самозванца? Он делает этот вывод из шифрования сообщения.

Также ли это хорошо, как подпись на бумаге? Посмотрим на требуемые свойства:

1. Эта подпись достоверна. Трент - это заслуживающий доверия посредник, и Трент знает, что сообщение получено от Алисы. Подтверждение Трента служит доказательством для Боба.

2. Эта подпись неподдельна. Только Алиса (и Трент, но ему все верят) знает K_A, поэтому только Алиса могла послать Тренту сообщение, зашифрованное ключом K_A. Если кто-нибудь попытается выдать себя за Алису, Трент сразу заметит это на этапе (2) и не заверит подлинность.

3. Эту подпись нельзя использовать повторно. Если Боб попытается взять подтверждение Трента и присоединить его к другому сообщению, Алиса закричит "Караул!" Посредник (Трент или кто-то совсем другой, имеющий доступ к той же информации) попросит Боба предъявить его сообщение и шифрованное сообщение Алисы. Затем посредник зашифрует сообщение ключом K_A и увидит, что оно не соответствует шифрованному сообщению, переданному Бобом. Боб, конечно же, не сможет создать правильное шифрованное сообщение, потому что он не знает ключа K_A.

4. Подписанный документ нельзя изменить. Если Боб попытается, получив документ, изменить его, Трент обнаружит мошенничество уже описанным способом.

5. От подписи невозможно отказаться. Если впоследствии Алиса заявит, что она никогда не посылала сообщение, подтверждение Трента докажет обратное. Помните, все доверяют Тренту, все, сказанное им - истина.

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

(1) Боб берет сообщение и утверждение Трента, что сообщение получено от Алисы, шифрует их ключом K_B и посылает обратно Тренту.

(2) Трент расшифровывает полученный пакет с помощью ключа K_B.

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

(4) Трент шифрует полученный от Боба пакет ключом K_C, который он выделил для Кэрол, и посылает Кэрол шифрованный пакет.

(5) Трент расшифровывает полученный пакет с помощью ключа K_C. Теперь она может прочитать и сообщение, и подтверждение Трента, что сообщение отправлено Алисой.

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

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

Деревья цифровых подписей

Ральф Меркл предложил систему цифровых подписей, основанную на криптографии с секретным ключом, создающей бесконечное количество одноразовых подписей, используя древовидную структуру [1067,1068]. Основной идеей этой схемы является поместить корень дерева в некий открытый файл, удостоверяя его таким образом. Корень подписывает одно сообщение и удостоверяет подузлы дерева. Каждый из этих узлов подписывает одно сообщение и удостоверяет свои подузлы, и так далее.

Подпись документа с помощью криптографии с открытыми ключами

Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В некоторых алгоритмах - примером является RSA (см. раздел 19.3) - для шифрования может быть использован или открытый, или закрытый ключ. Зашифруйте документ своим закрытым ключом, и вы получите надежную цифровую подпись. В других случаях - примером является DSA (см. раздел 20.1) - для цифровых подписей используется отдельный алгоритм, который невозможно использовать для шифрования. Эта идея впервые была изобретена Диффи и Хеллманом [496] и в дальнейшем была расширена и углублена в других работах [1282, 1328, 1024, 1283, 426]. Хороший обзор этой области приведен в [1099]. Основной протокол прост:

(1) Алиса шифрует документ своим закрытым ключом, таким образом подписывая его.

(2) Алиса посылает подписанный документ Бобу.

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

Этот протокол гораздо лучше предыдущего. Трент не нужен ни для подписи документов, ни для ее проверки. (Он нужен для подтверждения, что открытый ключ принадлежит именно Алисе.) Трент не нужен сторонам даже для разрешения споров: Если Боб не смог осуществить этап (3), то он знает, что подпись неправильна. Такая подпись соответствует всем требованиям:

1. Эта подпись достоверна. Когда Боб расшифровывает сообщение с помощью открытого ключа Алисы, он знает, что она подписала это сообщение.

2. Эта подпись неподдельна. Только Алиса знает свой закрытый ключ.

3. Эту подпись нельзя использовать повторно. Подпись является функцией документа и не может быть перенесена на другой документ.

4. Подписанный документ нельзя изменить. После любого изменения документа подпись не сможет больше подтверждаться открытым ключом Алисы.

5. От подписи невозможно отказаться. Бобу не требуется помощь Алисы при проверке ее подписи.

Подпись документа и метки времени

На самом деле, при определенных условиях Боб сможет смошенничать. Он может повторно использовать документ и подпись совместно. Это не имеет значения, если Алиса подписала контракт (одной копией подписанного контракта больше, одной меньше), но что если Алиса поставила цифровую подпись под чеком?

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

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

Подпись документа с помощью криптографии с открытыми ключами и однонаправленных хэш-функций

На практике алгоритмы с открытыми ключами часто недостаточно эффективны для подписи больших документов. Для экономии времени протоколы цифровой подписи нередко используют вместе с однонаправленными хэш-функциями [432, 433]. Алиса подписывает не документ, а значение хэш-функции для данного документа. В этом протоколе однонаправленная хэш-функция и алгоритм цифровой подписи согласовываются заранее.

(1) Алиса получает значение однонаправленной хэш-функции для документа.

(2) Алиса шифрует это значение своим закрытым ключом, таким образом подписывая документ.

(3) Алиса посылает Бобу документ и подписанное значение хэш-функции.

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

Скорость заметно возрастает и, так как вероятность получить для двух различных документов одинаковое 160‑битное значение хэш-функции составляет только один шанс из 2¹⁶⁰, можно безопасно приравнять подпись значения хэш-функции и подпись документа. Должна использоваться только однонаправленная хэш-функция, иначе создать разные документы с одним и тем же значением хэш-функции нетрудно, и подпись одного документа приведет к ошибочной подписи сразу многих документов.

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

Алгоритмы и терминология

Существует множество алгоритмов цифровой подписи. Все они представляют собой алгоритмы с открытыми ключами с закрытой частью для подписи документов и с открытой - для проверки подписи. Иногда процесс подписи называют шифрованием с закрытым ключом, а процесс проверки подписи - дешифрированием с открытым ключом. Это может ввести в заблуждение, являясь справедливым только для одного алгоритма, RSA. У других алгоритмов - другие реализации. Например, использование однонаправленных хэш‑функций и меток времени иногда приводит к появлению дополнительных этапов при подписании и проверке подписи. Многие алгоритмы можно использовать для цифровой подписи, но нельзя для шифрования.

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

S_K(M)

а проверка подписи с помощью соответствующего открытого ключа как:

V_K(M)

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

Несколько подписей

Как Алисе и Бобу одновременно подписать один и тот же документ? В отсутствие однонаправленных хэш‑функций существует две возможности. Алиса и Боб могут подписать различные копии одного и того же документа. Полученное сообщение будет в два раза длиннее первоначального документа. Или Алиса подписывает документ, а затем Боб подписывает подпись Алисы. Этот способ работает, но проверить подпись Алисы, не проверяя при этом подписи Боба, невозможно.

С помощью однонаправленных хэш‑функций реализовать несколько подписей просто:

(1) Алиса подписывает значение хэш‑функции документа.

(2) Боб подписывает значение хэш‑функции документа.

(3) Боб посылает свою подпись Алисе.

(4) Алиса посылает Кэрол документ, свою подпись и подпись Боба.

(5) Кэрол проверяет подписи Алисы и Боба.

Алиса и Боб могут выполнить этапа (1) и (2) или параллельно, или последовательно. На этапе (5) Кэрол может проверить любую подпись независимо от другой.

Невозможность отказаться от цифровой подписи

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

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

Хотя с подобным злоупотреблением ничего нельзя сделать, можно предпринять некоторые действия, гарантирующие то, что старые подписи не будут признаны недостоверными из-за разногласий по новым подписям. (Например, Алиса может "потерять" свой ключ, чтобы не платить Бобу за подержанную машину, которую он вчера ей продал и, в результате, сделает недействительным свой банковский счет.) Получателю нужно проставлять метки времени для полученных документов [453]. Общая схема протокола приведена в [2, 8]:

(1) Алиса подписывает сообщение.

(2) Алиса создает заголовок, содержащий некоторую идентификационную информацию. Она присоединяет к заголовку подписанное сообщение, подписывает все вместе и посылает Тренту.

(3) Трент проверяет внешнюю подпись и подтверждает идентификационную информацию. Он добавляет метку времени к подписанному сообщению Алисы и идентификационной информации. Затем он подписывает все вместе и посылает пакет Алисе и Бобу.

(4) Боб проверяет подпись Трента, идентификационную информацию и подпись Алисы.

(5) Алиса проверяет сообщение, которое Трент послал Бобу. Если она не признает свое авторство, она быстро заявляет об этом.

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

Использование цифровых подписей

Одним из самых ранних предложенных применений цифровых подписей было упрощение проверки соблюдения договоров о ядерных испытаниях [1454, 1467]. Соединенные Штаты и Советский Союз (кто-нибудь помнит Советский Союз?) разрешили друг другу разместить на чужой территории сейсмографы для слежения за ядерными испытаниями. Проблема была в том, что каждая из сторон должна была уверена в том, что другая сторона не подделала данные этих сейсмографов. Одновременно, другая сторона должна была быть уверена, что эти датчики посылают только ту информацию, которая нужна для слежения за ядерными испытаниями.

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

2.7 Цифровые подписи и шифрование

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

(1) Алиса подписывает сообщение с помощью своего закрытого ключа.

S_A(M)

(2) Алиса шифрует подписанное сообщение открытым ключом Боба и посылает его Бобу.

E_B (S_A(M))

(3) Боб расшифровывает сообщение с помощью своего закрытого ключа.

D_B (E_B (S_A(M)))= S_A(M)

(4) Боб проверяет подпись с помощью открытого ключа Алисы и восстанавливает сообщение.

V_A (S_A(M))= M

Подпись перед шифрованием выглядит естественно. Когда Алиса пишет письмо, она подписывает его и затем кладет в конверт. Если она положит письмо в конверт неподписанным, то Боб может забеспокоиться, вдруг письмо было тайно подменено. Если Боб покажет Кэрол письмо Алисы и конверт, Кэрол может обвинить Боба, что он врет о том, какое письмо в каком конверте пришло.

В электронной корреспонденции точно также является разумным использование подписи перед шифрованием [48]. Это не только более безопасно - враг не сможет удалить подпись из шифрованного сообщения и добавить свою собственную - но существуют и юридические соображения: если подписываемый текст не виден подписывающему, когда он ставит подпись, то юридическая сила подписи невелика [1312]. Существуют также некоторые криптографические способы вскрытия такой последовательности действий, использующей подписи RSA (см. раздел 19.3).

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

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

Возвращение сообщения при приеме

Рассмотрим реализацию этого протокола с дополнительной возможностью подтверждения сообщений - получив сообщение, Боб обязательно возвращает подтверждение приема.

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

E_B (S_A(M))

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

V_A (D_B (E_B (S_A(M))))= M

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

E_A (S_B(M))

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

Если для шифрования и проверки цифровой подписи используется один и тот же алгоритм, то существует возможность вскрытия [506]. В таких случаях операция цифровой подписи - противоположность операции шифрования: V_X = E_Xи S_X = D_X.

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

E_A (D_B (E_B (D_A(M))))= E_M (D_A(M))

Даже в этом случае, следуя протоколу, Боб посылает Мэллори полученное сообщение:

E_M (D_B (E_M (D_A(M))))

Теперь Мэллори остается только расшифровать сообщение с помощью своего закрытого ключа, зашифровать его открытым ключом Боба, расшифровать снова с помощью своего закрытого ключа и зашифровать открытым ключом Алисы. Voilа! Мэллори получает M.

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

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

Обнаружение вскрытия, основанного на возвращении сообщения

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

(1) Алиса подписывает сообщение.

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

(3) Боб расшифровывает сообщение с помощью своего закрытого ключа

(4) Боб проверяет подпись Алисы.

Вскрытия криптографии с открытыми ключами

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

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

Даже если открытые ключи хранятся в надежной базе данных, Мэллори может подменить их при передаче. Чтобы воспрепятствовать этому, Трент должен подписывать каждый открытый ключ, используя свой собственный закрытый ключ. Трента, который действует подобным образом, часто называют Органом сертификации ключей или Центром распределения ключей (Key Distribution Center,KDC). На практике KDC подписывает сложное сообщение, состоящее из имени пользователя, его открытого ключа и другой информации о пользователе. Это подписанное сложное сообщение и хранится в базе данных KDC. Когда Алиса получает ключ Боба, она проверяет подпись KDC, удостоверяясь в правильности ключа.

При окончательном анализе видно, что и это только затрудняет, но не делает невозможным мошенничество Мэллори. Алиса же должна откуда-то получить открытый ключ KDC. Мэллори нужно подменить этот ключ своим открытым ключом, испортить базу данных и заменить правильные ключи своими (подписанными его закрытым ключом, как если бы он и был KDC), и его дело сделано. Но, даже подписи на бумаге могут быть подделаны, если Мэллори всерьез возьмется за дело. Подробно обмен ключами рассматривается в разделе 3.1.

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

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

Генераторы случайных чисел на самом деле совсем не случайны, потому что им и не нужно быть такими. Для большинства приложений, например, компьютерных игр, требуется так мало случайных чисел, что их неслучайность вряд ли будет заметна. Однако, криптография очень чувствительна к свойствам генераторов случайных чисел. Примените плохой генератор, и у вас появятся таинственные корреляции и странные результаты [1231, 1238]. Если ваша безопасность зависит от генератора случайных чисел, таинственные корреляции и странные результаты являются абсолютно не тем, чего бы вы желали добиться.

Проблема в том, что генератор случайных чисел не создает случайной последовательности. Он, возможно, не выдает ничего даже отдаленно напоминающего случайную последовательность. Конечно, невозможно создавать на компьютере что-то по настоящему случайное. Дональд Кнут приписывал фон Нейману следующие слова: "Каждый, кто занимается арифметическими методами получения случайных чисел, определенно грешит" [863]. Компьютеры - это детерминированные бестии: закладывается известный материал, выполняются полностью предсказуемые действия, и что-то отличное выползает с другого конца. Подача одного и того же на вход в двух различных случаях приведет к одному и тому же результату. Заложите одинаковые исходные данные в два идентичных компьютера, и оба они подсчитают одно и то же. Компьютер может находиться только в ограниченном числе состояний (очень большом, но все же ограниченном), и выдаваемый результат всегда будет строго определяться исходными данными и текущим состоянием компьютера. Это значит, что любой генератор случайных чисел на компьютере (по меньшей мере, на конечном автомате), по определению, периодичен. А все, что периодично, по определению, предсказуемо. А все, что предсказуемо, не может быть случайным. Для настоящего генератора случайных чисел нужно подавать на вход что-нибудь случайное, компьютер же не может обеспечить это требование.

Псевдослучайные последовательности

Лучшее, что может сделать компьютер - это генератор псевдослучайных последовательностей.Что это такое? Многие пытались дать его формальное определение, но я уклонюсь от этого. Псевдослучайная последовательность - это что-то, выглядящее как случайное. Период последовательности должен быть достаточно велик, поэтому конечная последовательность разумной длины - которая в действительности и используется - не периодична. Если вам нужен миллиард случайных бит, не пользуйтесь генератором последовательности, повторяющейся каждые шестнадцать тысяч бит. Эти относительно короткие непериодические подпоследовательности должны быть, насколько это возможно, неотличимы от случайных последовательностей. Например, в них должно быть примерно одинаковое количество единиц и нулей, около половины серий (последовательностей одинаковых бит) должны быть единичной длины, четверть - состоять из двух бит, восьмая часть - из трех, и т.д. Эти последовательности должны быть несжимаемы. Распределение длин серий для нулей и единиц должно быть одинаковым [643, 863, 99, 1357]. Эти свойства могут быть измерены опытным путем и затем сравнены с ожидаемыми статистически с помощью статистики хи-квадрат. Для наших целей генератор последовательности считается псевдослучайным, если он обладает следующим свойством: