книги / Практическая криптография

10.6 Управление файлом начального числа

203

10.6.1Запись в файл начального числа

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

ф у н к ц и я W R I T B S E E D F I L E

вход: 1Z Состояние ГПСЧ; изменяется этой функцией.

/Файл, в который нужно записать энтропию.

w r if c e ( / , R A N D O M D A T A (R, 6 4 ) )

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

10.6.2 Обновление файла начального числа

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

ф у н к ц и я U P D A T E S E E D F I L E

вход: TZ Состояние ГПСЧ; изменяется этой функцией.

/Файл, который нужно обновить.

s *- read(f)

assert length(s) = 64

R E S E E D (£7, s )

w r i t e ( / , R A N D O M D A T A (Я, 6 4 ) )

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

Функция U P D A T E S E E D F I L E должна следить за тем, чтобы никто не смог использовать ГПСЧ в промежутке между обновлением состояния генерато­ ра и записью в файл начального числа новых данных. Проблема состоит в том, что после перезагрузки компьютера файл начального числа считыва­ ется функцией U P D A T E S E E D F I L E , которая применяет содержимое файла для обновления состояния генератора. Предположим, злоумышленник запраши­ вает у генератора случайные данные до того, как функция U P D A T E S E E D F I L E успеет перезаписать файл начального числа. Получив от генератора затребо­ ванные случайные данные, злоумышленник тут же перезагружает компью­ тер, так и не дав функции U P D A T E S E E D F I L E перезаписать файл. В резуль­ тате при следующей перезагрузке компьютера функция считает из файла начального числа те же самые данные, что и в прошлый раз, и обновит с их

204	Глава 10. Генерация случайных чисел

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

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

10.6.3Когда нужно считывать и перезаписывать файл начального числа?

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

Когда компьютер функционирует, он собирает энтропию из различных источников. Мы хотим, чтобы эта энтропия каким-то образом влияла и на файл начального числа. Одно из очевидных решений — перезаписывать файл начального числа во время выключения компьютера. Поскольку некоторые компьютеры никогда не выключаются в корректном порядке, файл началь­ ного числа следует периодически перезаписывать и во время работы компью­ тера. Мы не будем обсуждать детали этого процесса, потому что они совсем неинтересны и часто зависят от конкретной платформы. Важно гарантиро­ вать, чтобы ГПСЧ регулярно обновлял файл начального числа после того, как он соберет достаточное количество энтропии. Вполне разумно обновлять файл начального числа при каждом выключении компьютера, а также, на­ пример, каждые 10 минут.

10.6.4 Архивирование

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

10.6 Управление файлом начального числа

205

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

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

10.6.5Атомарность операций обновления файловой системы

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

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

206	Глава 10. Генерация случайных чисел

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

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

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

10.6.6 Первая загрузка

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

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

10.7 Так что же делать?

207

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

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

10.7Так что же делать?

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

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

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

208	Глава 10. Генерация случайных чисел

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

вваших силах. Удачи!

10.8Выбор случайных элементов

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

Когда мы выбираем случайный элемент, то неявно предполагаем, что этот элемент выбирается равновероятным случайным образом из заданного мно­ жества элементов (если только не указано другого вероятностного распре­ деления). Это означает, что возможность выбора каждого элемента должна обладать в точности одной и той же вероятностью6. Реализовать данное усло­ вие в программном обеспечении намного сложнее, чем кажется на первый взгляд.

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

Если п = 0, тогда у нас вообще нет элементов и мы получаем простую ошибку. Если п = 1, у нас нет вариантов выбора и мы вновь получаем про­ стой случай. Если п = 2к, мы можем просто получить от генератора к бит случайных данных и интерпретировать их как простое число в диапазоне 0 ,..., п — 1. Полученное число будет случайным и выбранным равновероят­ ным образом. (Возможно, вам придется получить от генератора целое коли­ чество байт и отбросить несколько бит последнего байта, чтобы оставшееся число бит равнялось к, но реализовать такую схему очень просто.)

Что делать, если п не является степенью двух? Некоторые программы вы­ бирают случайное 32-битовое число и подсчитывают его значение по модулю п. К сожалению, использование данного алгоритма приводит к смещению ре­ зультирующего распределения вероятностей. В качестве примера рассмотрим п = 5 и определим т := |232/5 j. Если мы равновероятным образом выберем случайное 32-битовое число и подсчитаем его значение по модулю 5, то каж­ дое из чисел 1, 2, 3 и 4 будет встречаться с вероятностью тп/232, а число 0 —

6Е сл и мы разрабатываем систему со 128-битовым уровнем безопасности, то можем поз­ волить себе отклонение в 2“ 128 от равномерного распределения, но реализовать точное равномерное распределение все-таки проще.

10.8 Выбор случайных элементов

209

с вероятностью (тп + 1)/232. В данном случае отклонение от равномерного распределения вероятностей невелико, однако оно может быть и значитель­ ным. Умному злоумышленнику не составит труда распознать отклонение за те 2128 шагов, которые мы отводим ему на осуществление атаки.

Чтобы правильно выбрать случайное число из произвольного диапазона, следует воспользоваться методом проб и ошибок. Например, чтобы сгенери­ ровать случайное число в диапазоне 0 ,..., 4, мы вначале генерируем слу­ чайное число в диапазоне 0 ,..., 7. Последняя операция возможна, поскольку 8 является степенью двух. Если полученное число окажется больше или рав­ но 5, мы отбросим его и выберем новое число в диапазоне 0 ,..., 7. Так будет продолжаться до тех пор, пока полученное случайное число не попадет в же­ лаемый диапазон 0 ,..., 4. Другими словами, мы генерируем случайное число, состоящее из нужного количества бит и отбрасываем все неподходящие числа.

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

1. Пусть к — наименьшее целое число, для которого 2к > п.

2. Воспользуйтесь генератором псевдослучайных чисел, чтобы получить /с-битовое случайное число К. Это число будет находиться в диапазоне 0 ,..., 2к — 1. Возможно, вам придется сгенерировать целое число байт

и отбросить часть последнего байта, но это несложно реализовать.

3.Если К > п, вернитесь к шагу 2.

4.Число К является требующимся результатом.

Описанный алгоритм может оказаться не совсем эффективным. В худшем случае нам придется отбросить примерно половину попыток, поэтому попро­ буем немного улучшить предложенное решение. Вернемся к примеру с п = 5. Поскольку 232 — 1 делится на 5, мы можем выбрать случайное число из диа­ пазона 0 ,..., 232 — 2 и подсчитать значение полученного числа по модулю 5. Чтобы выбрать число из диапазона 0,... , 232 - 2, мы снова воспользуемся “неэффективным” методом проб и ошибок, однако на сей раз вероятность того, что полученное случайное число придется отбросить, очень мала.

Общее правило состоит в том, чтобы выбрать удобное к, для которого 2к > п. Определим q := |_2fc/nJ •Вначале выберем случайное число г в диапа­ зоне 0 ,..., nq —1, используя метод проб и ошибок. Когда подходящее г будет найдено, окончательный результат подсчитывается как (г mod п).

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

Глава 11

Простые числа

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

соткрытым ключом. К сожалению, изучение этого материала требует опре­ деленного знания математики. Не секрет, что порой хочется пропустить по­ дробные объяснения и ограничиться лишь уравнениями и формулами, но мы хорошо осознаем, что этого делать не следует. Чтобы использовать какой-ни­ будь инструмент, вы должны понимать его свойства. Это очень легко, когда речь идет о чем-нибудь наподобие функции хэширования. У нас есть “идеаль­ ная” модель функции хэширования, и мы требуем, чтобы реальная функция хэширования вела себя точно так же, как эта модель. Для систем с открытым ключом все гораздо сложнее. У нас нет идеальной модели криптографиче­ ской системы с открытым ключом. На практике вам придется иметь дело

сматематическими свойствами подобных систем и, чтобы чувствовать себя уверенно, необходимо понимать эти свойства. Короткого пути здесь нет; вы должны понимать математику. Это не так сложно, как кажется; единствен­ ное, что от вас требуется, — это знание школьной программы математики на уровне старших классов (а точнее, математики, которую изучали авторы этой книги, когда были в старших классах).

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

11.1 Делимость и простые числа

Число а является делителем числа Ъ(это записывается как а|Ь и читается “а делит 6”), если 6 делится на а без остатка. Например, число 7 является делителем числа 35, поэтому можно записать, что 7|35. Число называется

11.1 Делимость и простые числа

211

простым (prime), если у него есть только два делителя: единица и само это число. Например, число 13 является простым, так как у него есть только два делителя: 1 и 13. Перечислить первые несколько простых чисел несложно — это 2, 3, 5, 7, 11, 13 и т.д. Любое число, большее единицы, которое не яв­ ляется простым, называется составным (composite). Число 1 не является ни простым, ни составным.

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

Ниже приведена простая лемма о делимости.

Лемма 1. Если а\Ь и Ъ\с, тогда а|с.

Доказательство. Если а\Ь, тогда существует целое число s, такое, что as = Ь. (Действительно, если Ьделится на а, тогда оно должно быть крат­ ным а.) Если Ь|с, тогда существует целое число t, такое, что bt = с. Но из этого следует, что с = bt = (as)t = a(st), а значит, а является делителем с. (Чтобы понять ход последнего рассуждения, просто убедитесь в том, что каждый из знаков равенства использован корректно. Логическое умозаклю­ чение состоит в том, что первый элемент с должен быть равен последнему элементу a(st).) □

Лемма является констатацией факта. Доказательство объясняет, почему эта лемма верна. Маленький квадратик справа обозначает конец доказатель­ ства. Математики вообще любят использовать всевозможные символы1. Это очень простая лемма, и доказательство должно быть понятно всем, кто пом­ нит, что означает запись а\Ь.

Простые числа исследовались математиками еще тысячи лет назад. Даже сегодня, если требуется определить все простые числа до миллиона, мы ис­ пользуем алгоритм, разработанный более 2000 лет назад Эратосфеном, дру­ гом Архимеда. (Эратосфен также был первым человеком, измерившим точ­ ный диаметр Земли. Спустя 1700 лет Колумб будто бы использовал намного меньшую — и неверную — оценку диаметра земного шара, когда собирался достичь Индии западным путем.) Евклид, еще один великий древнегреческий математик, привел гениальное доказательство того, что количество простых чисел бесконечно. Это доказательство настолько замечательно, что мы ре­ шили включить его в нашу книгу. Оно поможет быстро вернуть ваши мысли в лоно математики.

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

212	Глава 11. Простые числа

Прежде чем переходить к доказательству теоремы Евклида, приведем еще одну простую лемму.

Л е м м а 2 . Пусть п — положительное число, большее единицы. Пусть d — наименьший делитель числа п, больший единицы. Тогда d — простое число. Доказательство. Прежде всего следует убедиться в том, что определение числа d корректно. (Если существует такое положительное число п, у кото­ рого нет наименьшего делителя, то определение d дано некорректно и лемма теряет смысл.) Мы знаем, что п является делителем п и п > 1. Таким обра­ зом, у числа п должен существовать и наименьший делитель, больший 1.

Чтобы доказать, что d является простым числом, используем стандарт­ ный математический прием — reductio ad absurdum, или доказательство от противного (proof by contradiction). Чтобы доказать утверждение X , предпо­ ложим, что оно неверно, и покажем, что это предположение в конце концов приводит к противоречию. Если предположение о том, что X неверно, при­ водит к противоречию, это, очевидно, означает, что X верно.

Внашем случае предположим, что d не является простым числом. Тогда

унего должен быть делитель е, такой, что 1 < е < d. Но мы знаем из лем­ мы 1, что если е|d и d\n, то е|п, поэтому е является делителем п и е < d. Но это противоречит тому, что d является наименьшим делителем п. Поскольку мы пришли к противоречию, наше предположение должно быть неверным,

а значит, d является простым числом.

□

Пусть вас не беспокоит несколько запутанный метод доказательства — к нему нужно привыкнуть.

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

Теорема 1 (Евклида). Существует бесконечное количество простых чисел.

Доказательство. Еще раз воспользуемся доказательством от противного. Предположим, что количество простых чисел конечно, а значит, их можно записать в виде конечного списка. Обозначим эти числа как Р1,Р2?РЗ)___,рь где к — количество простых чисел. Введем число п := р\р2Рг •••Рк + 1 (про­ изведение всех простых чисел плюс 1).

Возьмем наименьший делитель числа п, больший единицы, и снова обо­ значим его как d. Мы знаем, что d — это простое число (согласно лемме 2) и d\n. Но ни одно простое число из нашего конечного списка простых чисел не является делителем п. Действительно, все числа р* являются делителями числа (п — 1), а п при делении на любое из этих чисел дает остаток 1. Мы получили, что d является простым числом, но его нет в списке всех простых чисел. Это противоречит тому, что список pi,Рг> рз> •••>Рк содержит все суще­ ствующие простые числа, а значит, наше предположение о конечности этого