Гаммирование. Общее понятие и применение

Гам­ми­ро­ва­ние яв­ля­ет­ся так­же ши­ро­ко при­ме­няе­мым крип­то­гра­фи­че­ским пре­об­ра­зо­ва­ни­ем.

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

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

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

T_i+1:=(a∙T_i+b) mod c,

где T_i – предыдущее псевдослучайное число, T_i+1 – следующее псевдослучайное число, а коэффициенты a,b,c постоянны и хорошо известны.

Обычно с=2ⁿ, где n – разрядность процессора, a mod 4=1, а b – нечётное. В этом случае последовательность псевдослучайных чисел имеет период c.

Процесс шифрования осуществляется следующим образом: шифруемое сообщение представляется в виде последовательности слов S_0, S₁,…, каждое длины n, которые складываются по модулю 2 со словами последовательностиT₀, T₁, …, то есть

С_i:=S_i Å T_i

Последовательность T₀, T₁, …, называется гаммой шифра. Å – логическая операция XOR.

Примечание: Логическая операция XOR (сложение по модулю 2, исключающее «или») имеет следующую таблицу истинности:

XOR

Процесс расшифровывания заключается в том, чтобы ещё раз сложить шифрованную последовательность с той же гаммой шифра: S_i:= С_i Å T_i.

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

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

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

T_i:= С_i Å S_i. И далее вся правая часть гаммы шифра определяется по указанной формуле датчика псевдослучайных чисел.

10. Генераторы случайных чисел: типы, применение. Число инициализации.

ГПСЧ — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от генератора и составляет около 2^n/2, где n — размер внутреннего состояния в битах. Если порождаемая последовательность сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.

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

Если в качестве источника энтропии использовать текущее время, то для получения натурального числа от 0 до N достаточно вычислить остаток от деления текущего времени в миллисекундах на число N+1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.

Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом, функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

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

Криптостойкий ГПСЧ — это ГПСЧ с определенными свойствами, позволяющими использовать его в криптографии. Требования к КСГПСЧ можно разделить на 2 группы — во первых, они должны проходить статистические тесты на случайность, во вторых, они должны сохранять непредсказуемость даже если часть их исходного или текущего состояния становится известна криптоаналитику.

Каждый КСГПСЧ должен удовлетворять «тесту на следующий бит».Т.е.: не должно существовать полиномиального алгоритма, который, зная первые k бит случайной последовательности, сможет предказать k+1 бит с вероятностью более 50%. Доказано, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.

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

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

Рассмотрим три класса реализации КСГПСЧ: На основе криптографических алгоритмов, На основе вычислительно сложных математических задач, Специальные реализации. В последних часто используются дополнительные источники энтропии, поэтому, строго говоря, они не являются «чистыми» генераторами, так как их выход не полностью определяется исходным состоянием. Это позволяет дополнительно защититься от атак, направленных на определение исходного состояния.

Реализации на основе криптографических алгоритмов

Безопасный блочный шифр можно преобразовать в КСГПСЧ запустив его в режиме счетчика. Таким образом, выбрав случайный ключ, можно получать следующий случайный блок применяя алгоритм к последовательным натуральным числам. Счет можно начинать с произвольного натурального числа. Очевидно, что периодом будет не больше чем 2ⁿ для n-битного блочного шифра. Также очевидно, что безопасность такой схемы полностью зависит от секретности ключа. Криптографически стойкая хеш-функция также может быть преобразованна в КСГПСЧ. В таком случае исходное значение счетчика должно оставаться в секрете.

Большинство потоковых шифров работают на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется (почти всегда с помощью операции XOR) с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только если в самом потоковом шифре используется надежный КСГПСЧ (что не всегда так). Опять же, начальное состояние счетчика должно оставаться секретным.

Реализации на основе математических задач

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

на задаче дискретного логарифма.

Специальные реализации

с учетом криптографической стойкости, например

Алгоритм Ярроу который пытается определить энтропию входных данных. Он используется в FreeBSD, OpenBSD и Mac OS X

Алгоритм Fortuna, наследник алгоритма Ярроу.

Специальный файл ОС UNIX /dev/random, в частности, /dev/urandom, реализованный в Linux.

Функция CryptGenRandom предоставленная в CryptoAPI компании Microsoft

Дата добавления: 2015-04-23