ISAAC (Indirection, Shift, Accumulate, Add and Count) — генератор псевдослучайных чисел, разработанный в 1996 году Робертом Дж.
Дженкинсом младшим, как развитие разработанных им же алгоритмов IA и IBAA. Этот генератор относят к разряду криптостойких генераторов псевдослучайных чисел, хотя полное и строгое доказательство проведено не было.
Американский программист Роберт Джон Дженкинс младший в 1993 году поступил в Беркли, чтобы получить там степень доктора в области теоретической информатики, после окончания Университета Карнеги-Меллон в 1989 году и четырёх лет работы в Oracle. Несмотря на то, что учёба в Беркли стала серьёзным испытанием для Дженкинса — ему пришлось бросить её уже через год — именно здесь он начал свою работу по изучению генераторов псевдослучайных чисел в рамках курса Мануэля Блюма по криптографии. В июле 1993 года Дженкинс стал экспериментировать с псевдослучайными числами для процессоров Intel 486 и уже к апрелю 1994 был разработан ISAAC. Правда, статья, описывающая его работу, была опубликована лишь спустя два года, в феврале 1996 года.
Алгоритм шифрования RC4 состоит из двух этапов: генерации псевдослучайной последовательности битов и побитового суммирования по модулю два этой последовательности с открытым текстом.
На этапе генерации псевдослучайной последовательности важную роль играет n — размер S-блока, массива данных, который фактически определяет внутреннее состояние RC4. Также в RC4 используются следующие переменные: i и j — итераторы, пробегающие значений, массив Key длины length, в котором специальным образом хранится ключ, и массив S (он же S-блок). Выходные данные: массив z — псевдослучайная последовательность.
Рассмотрим алгоритм на примере n = 8. Сначала массив S заполняется числами от 0 до , массив Key — последовательностью n-битовых слов. Если длина ключа меньше длины S, то последовательность повторяется, пока её длина не станет равна . Затем алгоритм работает следующим образом:
i = 0; j = 0; пока i < 256 //256 = 2^n j = (j + S[i] + Key[i mod length]) mod 256; поменять местами S[i] и S[j]; i++;
После этого этапа — этапа инициализации — следует этап собственно генерации псевдослучайной последовательности:
i = 0; j = 0; пока i < 256 j = (j + S[i]) mod 256; поменять местами S[i] и S[j]; z[i] = S[(S[i] + S[j]) mod 256]; i++;
На выходе получается последовательность длины n, с помощью которой шифруется потом открытый текст.
IA (Indirection, Addition) — алгоритм, который был разработан Дженкинсом таким образом, чтобы он мог удовлетворять следующим требованиям:
Входные данные алгоритма IA: массив S, состоящий из элементов от 0 до , случайным образом распределённых по массиву, итераторы i и j. Массив выходных данных z — результат работы алгоритма. Также значения ячеек в массиве — то есть длины слов — должны быть больше, чем бит, Дженкинс в своих работах берёт K = 32 бит — именно такой длины слова используются во всех описываемых здесь алгоритмах.
IBAA (Indirection, Barrelshift, Accumulate and Add) — алгоритм, созданный Дженкинсом на основе IA. Автор полагает наличие следующих преимуществ у IBAA в дополнение к преимуществам, уже имеющимся у IA:
В отличие от RC4 и IA, работа IBAA основана на циклических сдвигах битовых данных влево. В реализации IBAA используется тот же набор переменных, что и в IA, с той лишь разницей, что добавляются аккумуляторы a и b, а также barrelshift function — функция, осуществляющая упомянутый выше циклический сдвиг.
barrel(j) — сдвигает циклически в массиве из 32 бит все биты влево на 19 бит. Также это можно задать формулой , где
— побитовый XOR
Под операцией >> здесь подразумевается арифметический сдвиг вправо.
ISAAC (Indirection, Shift, Accumulate, Add and Count) — алгоритм псевдослучайных чисел, принцип работы которого труднее запомнить, чем принципы работы IA и IBAA, зато он имеет по сравнению с ними целый ряд преимуществ. При проектировании ISAAC к нему был предъявлен следующий список требований:
В отличие от большинства генераторов псевдослучайных чисел, в основе работы которых лежат потоковые шифры, ISAAC разработан без использования линейных регистров сдвига с обратной связью.
Среднее количество машинных инструкций, требуемых для получения 32-битного значения — 18,75. 64-битная версия ISAAC (ISAAC-64) требует 19 инструкций для получения одного 64-битного значения.
Так же, как и в предыдущих алгоритмах, в ISAAC есть массив S, определяющий внутреннее состояние системы, так же состоящий из случайно расположенных в массиве элементов от 0 до длины K бит, итератор i и три переменные a, b и c, отвечающие за предыдущие состояния генератора, массив выходных данных z той же длины, что и S. Однако помимо этих переменных здесь вводятся также переменные , которые определяют значение функции, зависящей от обоих итераторов:
.
В своей статье Дженкинс полагает .
Схема работы генератора на произвольном шаге при n = 8, K = 32 выглядит следующим образом:
c = c + 1; b = b + c; i = 0; пока i < 255 x = S[i]; a = f(a, i) + S[i + 128 mod 256]; S[i] = a + b + S[x>>2 mod 256]; z[i] = x + S[S[i]>>10 mod 256]; b = z[i]; i++;
На своём персональном сайте автор ISAAC объявил конкурс на взлом генератора — первый, кто сможет указать число, использованное в качестве зерна (англ. seed) для генерации первых 2560 значений, выдаваемых генератором, получит от Дженкинса приз в 1000$. Однако пока с этой задачей никто не смог справиться. Тем не менее, ISAAC был рассмотрен в работах ряда криптоаналитиков.
В 2001 году была опубликована статья, в которой Марина Пудовкина описывала атаку, основанную на открытых текстах, с помощью которой можно найти начальное состояние генератора по небольшому сегменту выходных данных, а также давала точную оценку сложности такой атаки. При помощи описанного в статье алгоритма, Пудовкиной удалось снизить сложность взлома до , в то время как сложность полного перебора . По её расчётам, при сложность взлома полным перебором равна , в то время как с помощью алгоритма Пудовкиной это число могло быть уменьшено до . Такая сложность, тем не менее, всё ещё слишком большая, чтобы можно было назвать ISAAC уязвимым генератором псевдослучайных чисел, резюмирует в своей статье криптоаналитик.
В своей работе 2006 года Омассон описывает четыре множества «слабых» начальных состояний , которые могут пересекаться между собой. Слабыми считаются такие состояния, для которых часть элементов случайны, а остальные элементы равны одному и тому же значению. Если — начальное состояние, то можно определить с помощью соотношения: , тогда определяется как , множество — как , в то время как задаётся следующим образом: . Автор рассматривал алгоритм ISAAC при тех же значениях, которые даны выше (то есть n = 8, K = 32) и вычислил для каждого из множеств число слабых состояний. Для это число составило состояний, для — состояний, для — , же является подмножеством . Наличие таких состояний ещё не говорит о том, что ISAAC можно легко взломать, однако они — потенциальные слабые места алгоритма, поэтому Омассон предложил модифицированную версию ISAAC — ISAAC+.
На вход на некотором шаге подаются те же, что и в ISAAC, числа a, b и c, массив S, составленный из 256 32-битных слов, на выходе — массив z той же размерности, что и S. В описании функции вместо логических битовых сдвигов >> и << используются циклические >>> и <<<, то есть применяется функция
Также поменялся способ инициации S[i] и z[i] на каждом шаге — в обоих случаях используется побитовый XOR. То есть вместо
S[i] = a + b + S[x>>2 mod 256]; z[i] = x + S[S[i]>>10 mod 256];
в ISAAC+ используется:
S[i] = a ⊕ b + S[x>>>2 mod 256]; z[i] = x + a ⊕ S[S[i]>>>10 mod 256];
В том же 2006 году Пол и Прэнил опубликовали статью, в которой изучали атаку распознавания (англ. distinguishing attack) на некоторые потоковые RC4-подобные генераторы, в том числе IA и ISAAC. В своей работе они показывают, что сложность взлома ISAAC составляет всего . Омассон не оставил без внимания эту атаку и указал на ошибочность инициации алгоритма Полом и Пренилом, из-за которой и появилась возможность так сильно уменьшить сложность его взлома.
Многие реализации ISAAC работают достаточно быстро и надежно, поэтому этот генератор псевдослучайных чисел стал довольно распространённым. ISAAC используется, например, в Unix-утилите shred (Unix) для зашифровки переписанных данных. Генератор случайных чисел на основе ISAAC реализован в одной из наиболее распространённых математических библиотек Java — Apache Commons Math.
This article uses material from the Wikipedia Русский article ISAAC, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Если не указано иное, содержание доступно по лицензии CC BY-SA 4.0. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Русский (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.