Кpиптогpафия от папиpуса до компьютеpа

       

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


Пусть известен участок ключа {g1, g2, ... G(2n+2)), полученного с помощью рекуррентного соотношения длиной n. Здесь Gi и другие переменные рассматриваются как биты, то есть над полем GF(2). В этом случае есть возможность восстановить весь ключ, реконструировав рекуррентное соотношение. Рекуррентное соотношение:

        

Cn*Gi + C(n-1)G(i+1) + ... + C0*G(i+n) = О

выполняется при i=1, 2, ... n+1. Поэтому имеем систему из n+1 линейных уравнений с n+1 неизвестными, при решении которой получаем коэффициенты использованного рекуррентного соотношения Ci, позволяющие продлить известный участок ключа вперед или назад на любую длину. Фактически неизвестных коэффициентов только n-1, так как Co=Cn=1. Есть ряд алгоритмов решения этой системы, но и обычный метод исключения переменных тоже хорош, так как при вычислениях в конечных полях ошибок округления нет, а полученная система линейных уравнений не вырождена. Допустим имеется участок гаммы ...10101111... из 8 бит. Степень больше 4 мы реконструировать не сможем, а меньшая недопустима, так как подряд встречаются 4 единицы. Поэтому, составив систему из 4 уравнений:

         С4+С2=1 C3+С1=1 C4+C2+C1=l C3+C2+C1=1

и решая ее, получаем С4=1, C3=1, C2=0 и C1=0, что отвечает многочлену х**4+х**3+1. Таким образом, получаем еще один довод в пользу дополнительного усиления шифра многоалфавитной замены дополнительной перестановкой, потому что иначе участок последовательности можно попытаться вскрыть, отгадывая текст исходного сообщения. Для длины рекуррентного соотношения n=60 и кодировании символов группами по 5 бит достаточно отгадать 24 символа, чтобы свести задачу к подбору перестановки. На первый взгляд кажется, что невозможно отгадать столь длинный участок текста. Однако большую помощь в этом может оказать ориентировочное знание содержания исходного сообщения, в котором могут встречаться устойчивые словосочетания большой длины, напри- мер, "государства среднеазиатского региона". Эта область достаточно сложна и деликатна, чтобы углубляться в нее дальше. Отметим лишь достоинство блочных шифров, заключающееся в том, что желающим их расколоть криптоаналитикам при достаточной длине блока ничего не остается, как вести атаку прямым подбором ключа, так как надежда отгадать кусок исходного текста большой длины весьма химерична. Кроме того, так как избыточность исходного текста существенно ослабляет шифр, то нужно перед шифрованием преобразовать его, используя оптимальный код, уменьшающий избыточность. Естественно, что для этого непригодны стандартные программы сжатия и архивации как ARC, ZIP и им подобные, так как создают в файле заголовок с множеством полей, содержимое которых легко предсказать. Необходимо пользоваться собственным сжатием, согласованным с программой шифрования, как это сделано в системе PCSecure.

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



Кpиптогpафия от папиpуса до компьютеpа

       

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


Пусть известен участок ключа {g1, g2, ... G(2n+2)), полученного с помощью рекуррентного соотношения длиной n. Здесь Gi и другие переменные рассматриваются как биты, то есть над полем GF(2). В этом случае есть возможность восстановить весь ключ, реконструировав рекуррентное соотношение. Рекуррентное соотношение:

        

Cn*Gi + C(n-1)G(i+1) + ... + C0*G(i+n) = О

выполняется при i=1, 2, ... n+1. Поэтому имеем систему из n+1 линейных уравнений с n+1 неизвестными, при решении которой получаем коэффициенты использованного рекуррентного соотношения Ci, позволяющие продлить известный участок ключа вперед или назад на любую длину. Фактически неизвестных коэффициентов только n-1, так как Co=Cn=1. Есть ряд алгоритмов решения этой системы, но и обычный метод исключения переменных тоже хорош, так как при вычислениях в конечных полях ошибок округления нет, а полученная система линейных уравнений не вырождена. Допустим имеется участок гаммы ...10101111... из 8 бит. Степень больше 4 мы реконструировать не сможем, а меньшая недопустима, так как подряд встречаются 4 единицы. Поэтому, составив систему из 4 уравнений:

         С4+С2=1 C3+С1=1 C4+C2+C1=l C3+C2+C1=1

и решая ее, получаем С4=1, C3=1, C2=0 и C1=0, что отвечает многочлену х**4+х**3+1. Таким образом, получаем еще один довод в пользу дополнительного усиления шифра многоалфавитной замены дополнительной перестановкой, потому что иначе участок последовательности можно попытаться вскрыть, отгадывая текст исходного сообщения. Для длины рекуррентного соотношения n=60 и кодировании символов группами по 5 бит достаточно отгадать 24 символа, чтобы свести задачу к подбору перестановки. На первый взгляд кажется, что невозможно отгадать столь длинный участок текста. Однако большую помощь в этом может оказать ориентировочное знание содержания исходного сообщения, в котором могут встречаться устойчивые словосочетания большой длины, напри- мер, "государства среднеазиатского региона". Эта область достаточно сложна и деликатна, чтобы углубляться в нее дальше. Отметим лишь достоинство блочных шифров, заключающееся в том, что желающим их расколоть криптоаналитикам при достаточной длине блока ничего не остается, как вести атаку прямым подбором ключа, так как надежда отгадать кусок исходного текста большой длины весьма химерична. Кроме того, так как избыточность исходного текста существенно ослабляет шифр, то нужно перед шифрованием преобразовать его, используя оптимальный код, уменьшающий избыточность. Естественно, что для этого непригодны стандартные программы сжатия и архивации как ARC, ZIP и им подобные, так как создают в файле заголовок с множеством полей, содержимое которых легко предсказать. Необходимо пользоваться собственным сжатием, согласованным с программой шифрования, как это сделано в системе PCSecure.



Содержание раздела






Содержание раздела