Difference between revisions of "Криптографические генераторы. Поточные шифры и их криптоанализ"

From CryptoWiki
Jump to: navigation, search
(Комбинирующие генераторы)
 
(43 intermediate revisions by 4 users not shown)
Line 1: Line 1:
  
 
== Криптографические генераторы ==
 
== Криптографические генераторы ==
Криптографические генераторы используются для выработки ключей криптосистем и [[Гамма|гаммы]] для поточного шифрования.
+
[[Криптографический генератор|Криптографические генераторы]] используются для выработки ключей криптосистем и [[Гамма|гаммы]] для поточного шифрования.
 +
Необходимость создания и отказ от обычных программных обусловлен двумя основными причинами - незащищенные реализации и возможностью предугадать значение на обычном генераторе вследствие особенностей реализации, которая нацелена на получение статистически случайного распределения.
  
 
===Элементная база криптографических схем генераторов===
 
===Элементная база криптографических схем генераторов===
Базовым элементом [[Криптографическая схема генератора|криптосхем]] многих генераторов является линейный регистр сдвига с максимальной длиной периода, выходная [[Гамма|гамма]] которого (линейная рекуррентная последовательность) имеет хорошие статистические свойства. В силу того, что линейная рекуррентная последовательность не обладает нелинейными свойствами, возможно восстанавливать всю последовательность по ее сравнительно небольшому отрезку. Следовательно, линейный регистр сдвига нельзя рассматривать как хороший криптографический генератор, и использование линейного регистра сдвига при построении схем следует сочетать с различными функциональными узлами и элементами памяти.
+
Базовым элементом [[Криптографическая схема генератора|криптосхем]] многих [[Криптографический генератор|генераторов]] является [[Линейный регистр сдвига|линейный регистр сдвига]] с максимальной длиной периода, выходная [[Гамма|гамма]] которого (линейная рекуррентная последовательность) имеет хорошие статистические свойства. В силу того, что линейная рекуррентная последовательность не обладает нелинейными свойствами, возможно восстанавливать всю последовательность по ее сравнительно небольшому отрезку. Следовательно, [[Линейный регистр сдвига|линейный регистр сдвига]] нельзя рассматривать как хороший [[Криптографический генератор|криптографический генератор]], и использование [[Линейный регистр сдвига|линейного регистра сдвига]] при построении схем следует сочетать с различными функциональными узлами и элементами памяти.
  
 
===Фильтрующие генераторы===
 
===Фильтрующие генераторы===
 
Один из простейших способов усложнения последовательности над конечным множеством заключается в отображении ее ''n''-грамм в знаки другой последовательности с помощью так называемой фильтрующей функции.
 
Один из простейших способов усложнения последовательности над конечным множеством заключается в отображении ее ''n''-грамм в знаки другой последовательности с помощью так называемой фильтрующей функции.
  
Пусть ''P'' – конечное поле. Фильтрующим генератором называется [[Автономный автомат|автономный автомат]] [[File:формула 1.gif]], где ''h'' – линейная подстановка векторного пространства [[File:формула 2.gif]], реализуемая линейным регистром сдвига длины ''n'' над полем ''P'' c функцией обратной связи ''f'(x)'',[[File:формула 3.gif]]  – фильтрующая функция.
+
Пусть ''P'' – конечное поле. Фильтрующим [[Криптографический генератор|генератором]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]] называется [[Автономный автомат|автономный автомат]] [[File:формула 1.gif]], где ''h'' – линейная подстановка векторного пространства [[File:формула 2.gif]], реализуемая [[Линейный регистр сдвига|линейным регистром сдвига]] длины ''n'' над полем ''P'' c функцией обратной связи ''f'(x)'',[[File:формула 3.gif]]  – фильтрующая функция.
  
Фильтрующий генератор называется нелинейным, если нелинейна фильтрующая функция. [[Криптографическая схема генератора|Криптографическая схема]] фильтрующего генератора изображена на рисунке 1.
+
Фильтрующий [[Криптографический генератор|генератор]] называется нелинейным, если нелинейна фильтрующая функция. [[Криптографическая схема генератора|Криптографическая схема]] фильтрующего [[Криптографический генератор|генератора]] изображена на рисунке 1.
 
   [[File:рис1.jpg|frame|Рисунок 1. Криптографическая схема фильтрующего генератора|center]]
 
   [[File:рис1.jpg|frame|Рисунок 1. Криптографическая схема фильтрующего генератора|center]]
Фильтрующий генератор имеет наилучшие характеристики тогда, когда используется линейный регистр сдвига максимального периода и сбалансированная фильтрующая функция. Это гарантирует длину периода [[Гамма|гаммы]], равную [[File:формула 4.gif]], где ''k''=|''P''|, и сбалансированность числа единиц и числа нулей на периоде.
+
Фильтрующий [[Криптографический генератор|генератор]] имеет наилучшие характеристики тогда, когда используется [[Линейный регистр сдвига|линейный регистр сдвига]] максимального периода и сбалансированная фильтрующая функция. Это гарантирует длину периода [[Гамма|гаммы]], равную [[File:формула 4.gif]], где ''k''=|''P''|, и сбалансированность числа единиц и числа нулей на периоде.
  
Нелинейные свойства [[Гамма|гаммы]] обеспечиваются выбором нелинейной фильтрующей функции. Обозначим через ''d'' степень нелинейности фильтрующей функции. Известно [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]], что линейная сложность [[Гамма|гаммы]] фильтрующего генератора [[File:формула 5.gif]], где [[File:формула 6.gif]] – число различных конъюнкций от ''n'' переменных ранга от 0 до ''d''.
+
Нелинейные свойства [[Гамма|гаммы]] обеспечиваются выбором нелинейной фильтрующей функции. Обозначим через ''d'' степень нелинейности фильтрующей функции. Известно [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]], что [[Линейная сложность|линейная сложность]] [[Гамма|гаммы]] фильтрующего [[Криптографический генератор|генератора]] [[File:формула 5.gif]], где [[File:формула 6.gif]] – число различных конъюнкций от ''n'' переменных ранга от 0 до ''d''.
  
Оценка снизу линейной сложности [[Гамма|гаммы]] фильтрующего генератора зависит от более глубоких свойств фильтрующей функции. Например, для булевых бент-функций [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#KiSc83|[KiSc83]]] при ''n'', кратных 4, [[File:формула 7.gif]].
+
Оценка снизу [[Линейная сложность|линейной сложности]] [[Гамма|гаммы]] фильтрующего [[Криптографический генератор|генератора]] зависит от более глубоких свойств фильтрующей функции. Например, для булевых бент-функций [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#KiSc83|[KiSc83]]] при ''n'', кратных 4, [[File:формула 7.gif]].
  
Известна [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#BeGu85|[BeGu85]]] нижняя оценка для другого класса булевых функций, которая говорит о том, что для получения [[Гамма|гаммы]] с высокой линейной сложностью необходимо  использовать фильтрующую функцию достаточно большой степени нелинейности.
+
Известна [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#BeGu85|[BeGu85]]] нижняя оценка для другого класса булевых функций, которая говорит о том, что для получения [[Гамма|гаммы]] с высокой [[Линейная сложность|линейной сложностью]] необходимо  использовать фильтрующую функцию достаточно большой степени нелинейности.
  
Известно [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ru85|[Ru85]]], что доля фильтрующих генераторов, построенных на базе линейного регистра сдвига максимального периода длины ''n'', где ''n'' – простое, у которых линейная сложность достигает наибольшего значения, стремится к 1 с ростом ''n''.
+
Известно [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ru85|[Ru85]]], что доля фильтрующих [[Криптографический генератор|генераторов]], построенных на базе [[Линейный регистр сдвига|линейного регистра сдвига]] максимального периода длины ''n'', где ''n'' – простое, у которых [[Линейная сложность|линейная сложность]] достигает наибольшего значения, стремится к 1 с ростом ''n''.
  
 
===Комбинирующие генераторы===
 
===Комбинирующие генераторы===
Комбинирующий генератор является усложнением фильтрующего генератора. Он построен на основе ''m''>1 линейных регистров сдвига над полем ''P'' и комбинирующей функции [[File:формула 8.gif]], на вход которой поступают знаки линейных рекуррентных последовательностей, вырабатываемые линейными регистрами. Обозначим [[File:формула 9.gif]] – длина ЛРС-''j'', [[File:формула 10.gif]]. [[Криптографическая схема генератора|Криптографическая схема]] комбинирующего генератора на основе двух ЛРС изображена на рисунке 2.
+
Комбинирующий [[Криптографический генератор|генератор]] является усложнением фильтрующего [[Криптографический генератор|генератора]]. Он построен на основе ''m''>1 [[Линейный регистр сдвига|линейных регистров сдвига]] над полем ''P'' и комбинирующей функции [[File:формула 8.gif]], на вход которой поступают знаки линейных рекуррентных последовательностей, вырабатываемые [[Линейный регистр сдвига|линейными регистрами]]. Обозначим [[File:формула 9.gif]] – длина ЛРС-''j'', [[File:формула 10.gif]]. [[Криптографическая схема генератора|Криптографическая схема]] комбинирующего [[Криптографический генератор|генератора]] на основе двух [[Линейный регистр сдвига|ЛРС]] изображена на рисунке 2.
  
 
   [[File:рис2.jpg|frame|Рисунок 2. Криптографическая схема комбинирующего генератора|center]]
 
   [[File:рис2.jpg|frame|Рисунок 2. Криптографическая схема комбинирующего генератора|center]]
Комбинирующий генератора называется нелинейным, если нелинейна комбинирующая функция.
+
Комбинирующий [[Криптографический генератор|генератор]] называется нелинейным, если нелинейна комбинирующая функция.
  
Начальные состояния всех линейных регистров сдвига составляют начальное состояние генератора. Если начальное состояние каждого ЛРС отлично от нулевого, то соответствующее начальное состояние комбинирующего генератора называется неособенным.
+
Начальные состояния всех [[Линейный регистр сдвига|линейных регистров сдвига]] составляют начальное состояние [[Криптографический генератор|генератора]]. Если начальное состояние каждого [[Линейный регистр сдвига|ЛРС]] отлично от нулевого, то соответствующее начальное состояние комбинирующего [[Криптографический генератор|генератора]] называется неособенным.
  
Каждому полиному [[File:формула 11.gif]] над конечным полем ''P'' можно поставить в соответствие полином [[File:формула 12.gif]] над кольцом целых чисел, полученный из [[File:формула 13.gif]] заменой всех ненулевых коэффициентов на 1 и заменой сложения и умножения в поле ''P'' сложением и умножением в кольце [[File:формула 14.gif]]. Линейная сложность [[Гамма|гаммы]] комбинирующего генератора [[File:формула 15.gif]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]].
+
Каждому полиному [[File:формула 11.gif]] над конечным полем ''P'' можно поставить в соответствие полином [[File:формула 12.gif]] над кольцом целых чисел, полученный из [[File:формула 13.gif]] заменой всех ненулевых коэффициентов на 1 и заменой сложения и умножения в поле ''P'' сложением и умножением в кольце [[File:формула 14.gif]]. [[Линейная сложность|Линейная сложность]] [[Гамма|гаммы]] комбинирующего [[Криптографический генератор|генератора]] [[File:формула 15.gif]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]].
  
Для обеспечения наилучших криптографических свойств комбинирующего генератора необходимо, чтобы комбинирующая функция зависела существенно от всех переменных и использовались неособенные начальные состояния. Иначе данный комбинирующий генератор вырождается в комбинирующий генератор в меньшим числом ЛРС.
+
Для обеспечения наилучших криптографических свойств комбинирующего [[Криптографический генератор|генератора]] необходимо, чтобы комбинирующая функция зависела существенно от всех переменных и использовались неособенные начальные состояния. Иначе данный комбинирующий [[Криптографический генератор|генератор]] вырождается в комбинирующий [[Криптографический генератор|генератор]] с меньшим числом [[Линейный регистр сдвига|ЛРС]].
  
Если ''P'' – простое поле, и характеристические многочлены всех линейных регистров сдвига комбинирующего генератора примитивны и имеют попарно взаимно простые степени, то [[File:формула 16.gif]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#А01|[А01]]].
+
Если ''P'' – простое поле, и характеристические многочлены всех [[Линейный регистр сдвига|линейных регистров сдвига]] комбинирующего [[Криптографический генератор|генератора]] примитивны и имеют попарно взаимно простые степени, то [[File:формула 16.gif]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#А05|[А05]]].
  
При определенных линейных регистрах сдвига и комбинирующей функции можно обеспечить хорошие статистические свойства [[Гамма|гаммы]] комбинирующего генератора и большую длину ее периода. В частности, если ЛРС-1,…,ЛРС-''m'' генерируют последовательности, длины периодов которых [[File:формула 17.gif]] попарно взаимно просты, и комбинирующая функция биективна по каждой переменной, то [[File:формула 18.gif]].
+
При определенных [[Линейный регистр сдвига|линейных регистрах сдвига]] и комбинирующей функции можно обеспечить хорошие статистические свойства [[Гамма|гаммы]] комбинирующего [[Криптографический генератор|генератора]] и большую длину ее периода. В частности, если ЛРС-1,…,ЛРС-''m'' генерируют последовательности, длины периодов которых [[File:формула 17.gif]] попарно взаимно просты, и комбинирующая функция биективна по каждой переменной, то [[File:формула 18.gif]].
  
Примеры комбинирующих генераторов:
+
Примеры комбинирующих [[Криптографический генератор|генераторов]]:
  
1) генератор Геффе (Geffe);
+
1) [[Криптографический генератор|генератор]] Геффе (Geffe);
  
2) пороговый генератор.
+
2) пороговый [[Криптографический генератор|генератор]].
  
Генератор Геффе использует комбинацию 3 регистров. Комбинирующая функция [[File:формула 19.gif]]. Если все линейные регистры сдвига имеют максимальные периоды, и их длины [[File:формула 20.gif]] попарно взаимно просты, то период [[Гамма|гаммы]] равен произведению периодов линейных регистров сдвига, а линейная сложность [[Гамма|гаммы]] генератора равна [[File:формула 21.gif]].
+
[[Криптографический генератор|Генератор]] Геффе использует комбинацию 3 [[Линейный регистр сдвига|регистров]]. Комбинирующая функция [[File:формула 19.gif]]. Если все [[Линейный регистр сдвига|линейные регистры сдвига]] имеют максимальные периоды, и их длины [[File:формула 20.gif]] попарно взаимно просты, то период [[Гамма|гаммы]] равен произведению периодов [[Линейный регистр сдвига|линейных регистров сдвига]], а [[Линейная сложность|линейная сложность]] [[Гамма|гаммы]] [[Криптографический генератор|генератора]] равна [[File:формула 21.gif]].
  
Пороговый генератор использует комбинацию нечетного числа регистров. Комбинирующая функция, называемая функцией мажорирования, равна [[File:формула 22.gif]]. Длина периода [[Гамма|гаммы]] порогового генератора равна произведению периодов линейных регистров сдвига, а линейная сложность [[Гамма|гаммы]] генератора равна [[File:формула 23.gif]].
+
Пороговый [[Криптографический генератор|генератор]] использует комбинацию нечетного числа [[Линейный регистр сдвига|регистров]]. Комбинирующая функция, называемая функцией мажорирования, равна [[File:формула 22.gif]]. Длина периода [[Гамма|гаммы]] порогового [[Криптографический генератор|генератора]] равна произведению периодов [[Линейный регистр сдвига|линейных регистров сдвига]], а [[Линейная сложность|линейная сложность]] [[Гамма|гаммы]] [[Криптографический генератор|генератора]] равна [[File:формула 23.gif]].
  
 
===Генераторы гаммы с неравномерным движением===
 
===Генераторы гаммы с неравномерным движением===
Наилучшие криптографические свойства фильтрующих и комбинирующих генераторов достигаются при использовании фильтрующих и комбинирующих функций высокой степени нелинейности, что вызывает определенные сложности при их технической или программной реализации. Важной особенностью этих генераторов является то, что информация в элементах памяти криптосхемы обновляется равномерно, то есть в каждом такте функционирования. Если продвижение информации в некотором регистре зависит от последовательности, вырабатываемой другим регистром, то генерируемая [[Гамма|гамма]] усложняется. В связи с этим используется неравномерное движение информации в определенных узлах генератора, определяемое ключом генератора. Такие схемы также могут быть построены на основе преобразований, допускающих удобную реализацию, например, на основе линейных регистров сдвига.
+
Наилучшие криптографические свойства фильтрующих и комбинирующих [[Криптографический генератор|генераторов]] достигаются при использовании фильтрующих и комбинирующих функций высокой степени нелинейности, что вызывает определенные сложности при их технической или программной реализации. Важной особенностью этих [[Криптографический генератор|генераторов]] является то, что информация в элементах памяти [[Криптографическая схема генератора|криптосхемы]] обновляется равномерно, то есть в каждом такте функционирования. Если продвижение информации в некотором регистре зависит от последовательности, вырабатываемой другим регистром, то генерируемая [[Гамма|гамма]] усложняется. В связи с этим используется неравномерное движение информации в определенных узлах [[Криптографический генератор|генератора]], определяемое ключом [[Криптографический генератор|генератора]]. Такие схемы также могут быть построены на основе преобразований, допускающих удобную реализацию, например, на основе [[Линейный регистр сдвига|линейных регистров сдвига]].
  
Построенные по такому принципу генераторы [[Гамма|гаммы]] называются генераторами [[Гамма|гаммы]] с неравномерным движением. Изменение закона движения регистра приводит к изменению исходной [[Гамма|гаммы]].
+
Построенные по такому принципу [[Криптографический генератор|генераторы]] [[Гамма|гаммы]] называются [[Криптографический генератор|генераторами]] [[Гамма|гаммы]] с неравномерным движением. Изменение закона движения регистра приводит к изменению исходной [[Гамма|гаммы]].
  
Широко используемый способ достижения эффекта неравномерного движения –последовательное соединение m автоматов, где каждый предыдущий автомат называют управляющим по отношению к следующему, последний автомат – генерирующим. Если ''m''>2, то такое соединение автоматов называется каскадным. Другой способ – это несколько взаимно управляемых автоматов, совместно генерирующих [[Гамма|гамму]].
+
Широко используемый способ достижения эффекта неравномерного движения – последовательное соединение ''m'' автоматов, где каждый предыдущий автомат называют управляющим по отношению к следующему, последний автомат – генерирующим. Если ''m''>2, то такое соединение автоматов называется каскадным. Другой способ – это несколько взаимно управляемых автоматов, совместно генерирующих [[Гамма|гамму]].
  
 
====Генераторы «[[File:формула 24.gif]] шагов»====
 
====Генераторы «[[File:формула 24.gif]] шагов»====
Если в двухкаскадной схеме управляющий автомат есть фильтрующий генератор на базе линейного регистра сдвига длины ''n'' c фильтрующей функцией ''f''(''x''), а генерирующий автомат есть линейный регистр сдвига длины ''m'', отрабатывающий каждый такт в зависимости от управляющего знака [[File:формула 25.gif]] или [[File:формула 26.gif]] шагов, [[File:формула 27.gif]], то такой автомат называется генератором «[[File:формула 28.gif]] шагов» [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. При [[File:формула 29.gif]], [[File:формула 30.gif]] генератор «[[File:формула 31.gif]] шагов» называется генератором «стоп-вперед». Криптографическая схема генератора «[[File:формула 32.gif]] шагов» дана на рисунке 3.
+
Если в двухкаскадной схеме управляющий автомат есть фильтрующий [[Криптографический генератор|генератор]] на базе [[Линейный регистр сдвига|линейного регистра сдвига]] длины ''n'' c фильтрующей функцией ''f''(''x''), а генерирующий автомат есть [[Линейный регистр сдвига|линейный регистр сдвига]] длины ''m'', отрабатывающий каждый такт в зависимости от управляющего знака [[File:формула 25.gif]] или [[File:формула 26.gif]] шагов, [[File:формула 27.gif]], то такой автомат называется [[Криптографический генератор|генератором]] «[[File:формула 28.gif]] шагов» [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. При [[File:формула 29.gif]], [[File:формула 30.gif]] [[Криптографический генератор|генератор]] «[[File:формула 31.gif]] шагов» называется [[Криптографический генератор|генератором]] «стоп-вперед». [[Криптографическая схема генератора|Криптографическая схема генератора]] «[[File:формула 32.gif]] шагов» дана на рисунке 3.
 
   [[File:рис3.jpg|frame|Рисунок 3. Криптографическая схема генератора «[[File:формула 24.gif]] шагов»|center]]
 
   [[File:рис3.jpg|frame|Рисунок 3. Криптографическая схема генератора «[[File:формула 24.gif]] шагов»|center]]
Пусть линейные регистры сдвига имеют максимальные длины периодов. Обозначим [[File:формула 33.gif]] и [[File:формула 34.gif]] – состояния соответственно ЛРС-1 и ЛРС-2 в ''i''-м такте, ''i''=1,2,…
+
Пусть [[Линейный регистр сдвига|линейные регистры сдвига]] имеют максимальные длины периодов. Обозначим [[File:формула 33.gif]] и [[File:формула 34.gif]] – состояния соответственно ЛРС-1 и ЛРС-2 в ''i''-м такте, ''i''=1,2,…
Уравнения гаммообразования генератора имеют вид:
+
Уравнения гаммообразования [[Криптографический генератор|генератора]] имеют вид:
 
[[File:формула 35.gif|center]]
 
[[File:формула 35.gif|center]]
 
где [[File:формула 36.gif]] – суммарная глубина продвижения ЛРС-2 после первых ''i'' тактов функционирования [[File:формула 37.gif]].
 
где [[File:формула 36.gif]] – суммарная глубина продвижения ЛРС-2 после первых ''i'' тактов функционирования [[File:формула 37.gif]].
  
Величина [[File:формула 38.gif]] не зависит от ''x'' [[File:формула 45.gif]] число ''i'' кратно длине периода управляющей [[Гамма|гаммы]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. При ''i'', кратных [[File:формула 39.gif]], используем обозначение [[File:формула 40.gif]]. Длина периода [[Гамма|гаммы]], вырабатываемой генератором «[[File:формула 41.gif]] шагов», равна [[File:формула 42.gif]].
+
Величина [[File:формула 38.gif]] не зависит от ''x'' [[File:формула 45.gif]] число ''i'' кратно длине периода управляющей [[Гамма|гаммы]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. При ''i'', кратных [[File:формула 39.gif]], используем обозначение [[File:формула 40.gif]]. Длина периода [[Гамма|гаммы]], вырабатываемой [[Криптографический генератор|генератором]] «[[File:формула 41.gif]] шагов», равна [[File:формула 42.gif]].
  
Верхняя оценка линейной сложности [[Гамма|гаммы]] генератора имеет вид [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ny75|[Ny75]]]:
+
Верхняя оценка [[Линейная сложность|линейной сложности]] [[Гамма|гаммы]] [[Криптографический генератор|генератора]] имеет вид [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ny75|[Ny75]]]:
 
[[File:формула 43.gif|center]]
 
[[File:формула 43.gif|center]]
 
где [[File:формула 44.gif]] – длина периода выходной последовательности ЛРС-1.
 
где [[File:формула 44.gif]] – длина периода выходной последовательности ЛРС-1.
  
 
====Генераторы с перемежающимся шагом====
 
====Генераторы с перемежающимся шагом====
Усложнением генератора «стоп-вперед» является генератор с перемежающимся шагом [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. Его [[Гамма|гамма]] образуется как сумма [[Гамма|гамм]] двух генераторов «стоп-вперед» с генерирующими линейными регистрами сдвига ЛРС-2 и ЛРС-3 длины ''m'' и ''r'' соответственно. Оба генерирующих регистра имеют общий управляющий блок – фильтрующий генератор с фильтрующей функцией ''f''(''x'') на базе линейного регистра сдвига длины ''n''. Если в ''i''-м такте управляющий знак равен 1, то ЛРС-2 продвигается на 1 шаг, а ЛРС-3 простаивает, и при управляющем знаке 0 – наоборот. Ключом генератора являются начальные состояния всех линейных регистров сдвига.
+
Усложнением [[Криптографический генератор|генератора]] «стоп-вперед» является [[Криптографический генератор|генератор]] с перемежающимся шагом [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. Его [[Гамма|гамма]] образуется как сумма [[Гамма|гамм]] двух [[Криптографический генератор|генераторов]] «стоп-вперед» с генерирующими [[Линейный регистр сдвига|линейными регистрами сдвига]] ЛРС-2 и ЛРС-3 длины ''m'' и ''r'' соответственно. Оба генерирующих регистра имеют общий управляющий блок – фильтрующий [[Криптографический генератор|генератор]] с фильтрующей функцией ''f''(''x'') на базе [[Линейный регистр сдвига|линейного регистра сдвига]] длины ''n''. Если в ''i''-м такте управляющий знак равен 1, то ЛРС-2 продвигается на 1 шаг, а ЛРС-3 простаивает, и при управляющем знаке 0 – наоборот. Ключом [[Криптографический генератор|генератора]] являются начальные состояния всех [[Линейный регистр сдвига|линейных регистров сдвига]].
  
Пусть все три регистра имеют максимальные длины периодов. Обозначим [[File:формула 46.gif]], [[File:формула 47.gif]] и [[File:формула 48.gif]] – состояния соответственно ЛРС-1, ЛРС-2 и ЛРС-3 в ''i''-м такте, ''i''=1,2,… Тогда суммарная глубина продвижения ЛРС-2 после первых ''i'' тактов функционирования [[File:формула 49.gif]].
+
Пусть все три [[Линейный регистр сдвига|регистра]] имеют максимальные длины периодов. Обозначим [[File:формула 46.gif]], [[File:формула 47.gif]] и [[File:формула 48.gif]] – состояния соответственно ЛРС-1, ЛРС-2 и ЛРС-3 в ''i''-м такте, ''i''=1,2,… Тогда суммарная глубина продвижения ЛРС-2 после первых ''i'' тактов функционирования [[File:формула 49.gif]].
  
Уравнения гаммообразования генератора имеют вид:
+
Уравнения гаммообразования [[Криптографический генератор|генератора]] имеют вид:
 
[[File:формула 50.gif|center]]
 
[[File:формула 50.gif|center]]
  
Длина периода [[Гамма|гаммы]] генератора с перемежающимся шагом равна [[File:формула 51.gif]].
+
Длина периода [[Гамма|гаммы]] [[Криптографический генератор|генератора]] с перемежающимся шагом равна [[File:формула 51.gif]].
  
Если характеристические многочлены ЛРС-2 и ЛРС-3 различны и неприводимы, длины периодов выходных последовательностей ЛРС-2 и ЛРС-3 взаимно просты, то длина периода [[Гамма|гаммы]] генератора с перемежающимся шагом равна [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]] произведению длин периодов выходных последовательностей линейных регистров сдвига, а линейная сложность [[Гамма|гаммы]] подчиняется оценкам:
+
Если характеристические многочлены ЛРС-2 и ЛРС-3 различны и неприводимы, длины периодов выходных последовательностей ЛРС-2 и ЛРС-3 взаимно просты, то длина периода [[Гамма|гаммы]] [[Криптографический генератор|генератора]] с перемежающимся шагом равна [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]] произведению длин периодов выходных последовательностей [[Линейный регистр сдвига|линейных регистров сдвига]], а [[Линейная сложность|линейная сложность]] [[Гамма|гаммы]] подчиняется оценкам:
 
[[File:формула 52.gif|center]]
 
[[File:формула 52.gif|center]]
  
И генератор «[[File:формула 53.gif]] шагов», и генератор с перемежающимся шагом вскрывается опробованием начального состояния управляющего линейного регистра сдвига. В силу этого эффективная длина ключа генератора близка к длине управляющего регистра.
+
И [[Криптографический генератор|генератор]] «[[File:формула 53.gif]] шагов» и [[Криптографический генератор|генератор]] с перемежающимся шагом вскрываются опробованием начального состояния управляющего [[Линейный регистр сдвига|линейного регистра сдвига]]. В силу этого эффективная длина ключа [[Криптографический генератор|генератора]] близка к длине управляющего регистра.
  
 
====Каскадные генераторы Гольмана (Gollman)====
 
====Каскадные генераторы Гольмана (Gollman)====
Каскадный генератор Гольмана [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]], построенный на основе ''m'' линейных регистров сдвига с максимальными длинами периодов, привлекателен тем, что может быть использован для генерации [[Гамма|гаммы]] с огромной длиной периода и линейной сложностью. В этой конструкции первый регистр управляем вторым, второй – третьим и т. д.
+
Каскадный [[Криптографический генератор|генератор]] Гольмана [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]], построенный на основе ''m'' [[Линейный регистр сдвига|линейных регистров сдвига]] с максимальными длинами периодов, привлекателен тем, что может быть использован для генерации [[Гамма|гаммы]] с огромной длиной периода и [[Линейная сложность|линейной сложностью]]. В этой конструкции первый регистр управляет вторым, второй – третьим и т. д.
  
Если все линейные регистры сдвига имеют длину ''n'' и различные примитивные характеристические многочлены [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#GoCh89|[GoCh89]]], то длина периода ''m''-каскадного генератора равна [[File:формула 54.gif]], а линейная сложность равна [[File:формула 55.gif]].
+
Если все [[Линейный регистр сдвига|линейные регистры сдвига]] имеют длину ''n'' и различные примитивные характеристические многочлены [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#GoCh89|[GoCh89]]], то длина периода [[Гамма|гаммы]] ''m''-каскадного [[Криптографический генератор|генератора]] равна [[File:формула 54.gif]], а [[Линейная сложность|линейная сложность]] равна [[File:формула 55.gif]].
  
Вместе с тем, имеется корреляция между выходной [[Гамма|гаммой]] первого регистра и [[Гамма|гаммой]] генератора, позволяющая построить эффективный метод последовательного вскрытия начальных состояний линейных регистров сдвига [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Me93|[Me93]]].
+
Вместе с тем, имеется корреляция между выходной [[Гамма|гаммой]] первого регистра и [[Гамма|гаммой]] [[Криптографический генератор|генератора]], позволяющая построить эффективный метод последовательного вскрытия начальных состояний [[Линейный регистр сдвига|линейных регистров сдвига]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Me93|[Me93]]].
  
 
====Сжимающие генераторы====
 
====Сжимающие генераторы====
Другой принцип управления движением использован в сжимающем генераторе [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]], который построен на основе параллельно работающих линейных регистров сдвига с максимальными длинами периодов. Знаками [[Гамма|гаммы]] являются выходные значения, снимаемые с ячейки ЛРС-2, но только в те такты, когда управляющий знак ЛРС-1 равен 1, в остальные такты оба бита, генерируемые регистрами, игнорируются.
+
Другой принцип управления движением использован в сжимающем [[Криптографический генератор|генераторе]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]], который построен на основе параллельно работающих [[Линейный регистр сдвига|линейных регистров сдвига]] с максимальными длинами периодов. Знаками [[Гамма|гаммы]] являются выходные значения, снимаемые с ячейки ЛРС-2, но только в те такты, когда управляющий знак ЛРС-1 равен 1, в остальные такты оба бита, генерируемые регистрами, игнорируются.
  
[[Гамма|Гамма]] сжимающего генератора имеет хорошую длину периода и линейную сложность [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#CoKrMa94|[CoKrMa94]]]. Криптографические слабости обнаружены у него только в том случае, когда характеристические многочлены  содержат мало ненулевых коэффициентов. Реализация сжимающего генератора имеет высокую скорость.
+
[[Гамма|Гамма]] сжимающего [[Криптографический генератор|генератора]] имеет хорошую длину периода и [[Линейная сложность|линейную сложность]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#CoKrMa94|[CoKrMa94]]]. Криптографические слабости обнаружены у него только в том случае, когда характеристические многочлены  содержат мало ненулевых коэффициентов. Реализация сжимающего [[Криптографический генератор|генератора]] имеет высокую скорость.
  
 
===Генераторы с дополнительной памятью===
 
===Генераторы с дополнительной памятью===
При конструировании генераторов для уменьшения корреляции между [[Гамма|гаммой]] и некоторыми промежуточными последовательностями генератора, вырабатываемыми [[Автономный автомат|автономными автоматами]] (в простейшем случае линейными регистрами сдвига) используются дополнительные регистры памяти. Имеется несколько способов использования дополнительной памяти в криптографических схемах.
+
При конструировании [[Криптографический генератор|генераторов]] для уменьшения корреляции между [[Гамма|гаммой]] и некоторыми промежуточными последовательностями [[Криптографический генератор|генератора]], вырабатываемыми [[Автономный автомат|автономными автоматами]] (в простейшем случае [[Линейный регистр сдвига|линейными регистрами сдвига]]) используются дополнительные регистры памяти. Имеется несколько способов использования дополнительной памяти в [[Криптографическая схема генератора|криптографических схемах]].
  
 
====Генераторы Макларена-Марсальи (MacLaren-Marsaglia)====
 
====Генераторы Макларена-Марсальи (MacLaren-Marsaglia)====
В генераторах Макларена-Марсальи [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]] исходная последовательность усложняется с помощью регистра памяти и управляющих последовательностей.
+
В [[Криптографический генератор|генераторах]] Макларена-Марсальи [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]] исходная последовательность усложняется с помощью регистра памяти и управляющих последовательностей.
  
Пусть имеется ''m'' ячеек памяти, занумерованных числами от 0 до ''m''–1, в которые записываются элементы ''n''-множества ''X''. Для отображения входной последовательности над ''X'' в выходную последовательность над ''X'' используются 2 управляющие последовательности над кольцом [[File:формула 56.gif]] – для управления записи в память членов входной последовательности и управления считыванием из памяти членов выходной последовательности.
+
Пусть имеется регистр памяти длины ''m'', в который записываются элементы ''n''-множества ''X''. Для отображения входной последовательности над ''X'' в выходную последовательность над ''X'' используются 2 управляющие последовательности над кольцом [[File:формула 56.gif]] – для управления записи в память членов входной последовательности и управления считыванием из памяти членов выходной последовательности.
  
 
Обозначим [[File:формула 57.gif]] – длины периодов входной, выходной и управляющих последовательностей соответственно. Последовательность над множеством ''X'' называется полной, если она содержит все элементы множества ''X''.
 
Обозначим [[File:формула 57.gif]] – длины периодов входной, выходной и управляющих последовательностей соответственно. Последовательность над множеством ''X'' называется полной, если она содержит все элементы множества ''X''.
Line 110: Line 111:
  
 
====Регистр сдвига с обратной связью с переносом====
 
====Регистр сдвига с обратной связью с переносом====
Другой способ использования дополнительной памяти для усложнения характеристик [[Гамма|гаммы]] связан с конструкцией, получившей название регистра сдвига с обратной связью с переносом (РСОСП) [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. РСОСП – это автономный регистр сдвига, имеющий несколько ячеек дополнительной памяти, образующих регистр переноса. Наиболее простая разновидность РСОСП строится на базе двоичного линейного регистра сдвига и ячейки дополнительной памяти для записи целых чисел от 0 до [[File:формула 60.gif]], где ''r'' – число ячеек регистра, содержимое которых используется для вычисления обратной связи.
+
Другой способ использования дополнительной памяти для усложнения характеристик [[Гамма|гаммы]] связан с конструкцией, получившей название регистра сдвига с обратной связью с переносом (РСОСП) [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. РСОСП – это автономный регистр сдвига, имеющий несколько ячеек дополнительной памяти, образующих регистр переноса. Наиболее простая разновидность РСОСП строится на базе двоичного [[Линейный регистр сдвига|линейного регистра сдвига]] и ячейки дополнительной памяти для записи целых чисел от 0 до [[File:формула 60.gif]], где ''r'' – число ячеек регистра, содержимое которых используется для вычисления обратной связи.
 
    
 
    
 
Пусть в ячейках регистра записаны биты [[File:формула 61.gif]], а в дополнительной памяти записано число [[File:формула 62.gif]]. В следующем такте содержимое регистра сдвигается, крайний бит поступает на выход, при этом содержимое памяти и свободной после сдвига ячейки обновляется следующим образом:
 
Пусть в ячейках регистра записаны биты [[File:формула 61.gif]], а в дополнительной памяти записано число [[File:формула 62.gif]]. В следующем такте содержимое регистра сдвигается, крайний бит поступает на выход, при этом содержимое памяти и свободной после сдвига ячейки обновляется следующим образом:
  
1) вычисляется действительная сумма битов [[File:формула 63.gif]], где [[File:формула 64.gif]] – двоичные коэффициенты, из которых ''r'' коэффициентов равны 1, а остальные равны 0;
+
1) вычисляется [[File:формула 63.gif]], где [[File:формула 64.gif]] – двоичные коэффициенты, из которых ''r'' коэффициентов равны 1;
  
 
2) вычисляется [[File:формула 65.gif]];
 
2) вычисляется [[File:формула 65.gif]];
Line 122: Line 123:
 
Длина периода [[Гамма|гаммы]], вырабатываемой РСОСП, [[File:формула 68.gif]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]].
 
Длина периода [[Гамма|гаммы]], вырабатываемой РСОСП, [[File:формула 68.gif]] [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]].
  
Важной особенностью РСОСП является то, что для их анализа неприменим традиционный математический аппарат конечных полей. поэтому для изучения схем с переносом разработана теория, основанная на 2-адических числах [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ke76|[Ke76]]].
+
Важной особенностью РСОСП является то, что для их анализа неприменим традиционный математический аппарат конечных полей. Поэтому для изучения схем с переносом разработана теория, основанная на 2-адических числах [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ke76|[Ke76]]].
  
Использование в криптосхемах РСОСП заметно усложняет криптоаналитические атаки на основе корреляционного анализа последовательностей [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Go93|[Go93]]]. В связи с этим, представляются перспективными схемы типа каскадных генераторов Гольмана. построенных на базе нескольких РСОСП.
+
Использование в криптосхемах РСОСП заметно усложняет криптоаналитические атаки на основе корреляционного анализа последовательностей [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Go94|[Go94]]]. В связи с этим, представляются перспективными схемы типа каскадных [[Криптографический генератор|генераторов]] Гольмана, построенных на базе нескольких РСОСП.
  
 
== Поточные шифры и их криптоанализ ==
 
== Поточные шифры и их криптоанализ ==
  
'''Поточные шифры''' – это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточные шифры это одна из составляющих схем симметричного шифрования, общий вид которых, обычно, представлен в виде одного или нескольких регистров сдвига и нелинейной функции. Так как сам по себе [[линейный рекуррентный регистр]] (ЛРР) – линейное устройство, задача нелинейной функции (НЛФ) – внесение нелинейности в выходную последовательность.  
+
'''Поточный шифр''' – это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточные шифры это одна из составляющих схем симметричного шифрования, общий вид которых, обычно, представлен в виде одного или нескольких регистров сдвига и нелинейной функции[[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#С13|[С13]]]. Так как сам по себе [[Линейный рекуррентный регистр (ЛРР)|линейный рекуррентный регистр]] (ЛРР) – линейное устройство, задача нелинейной функции (НЛФ) – внесение нелинейности в выходную последовательность.  
 
Поточные шифры преобразуют открытый текст в шифртекст побитово. Простейшая реализация представлена на рисунке 4. Генерируется поток битов: [[File:form2.jpg]], называемый [[Гамма|гаммой]]. Поток битов открытого текста [[File:form3.jpg]] и поток [[Гамма|гаммы]]  подвергаются операции XOR, в результате получается поток битов шифртекста [[File:form4.jpg]] , где [[File:form5.jpg]], такой режим шифрования называется гаммированием. Для расшифрования используется аналогичная формула [[File:form6.jpg]].  
 
Поточные шифры преобразуют открытый текст в шифртекст побитово. Простейшая реализация представлена на рисунке 4. Генерируется поток битов: [[File:form2.jpg]], называемый [[Гамма|гаммой]]. Поток битов открытого текста [[File:form3.jpg]] и поток [[Гамма|гаммы]]  подвергаются операции XOR, в результате получается поток битов шифртекста [[File:form4.jpg]] , где [[File:form5.jpg]], такой режим шифрования называется гаммированием. Для расшифрования используется аналогичная формула [[File:form6.jpg]].  
 
   [[File:image1.jpg|frame|Рисунок 4. Процесс зашифрования и расшифрования|center]]
 
   [[File:image1.jpg|frame|Рисунок 4. Процесс зашифрования и расшифрования|center]]
Line 147: Line 148:
 
Известный отрезок открытого текста нарушитель может легко подменить другим, который расшифруется в заранее заданный отрезок текста той же длины.
 
Известный отрезок открытого текста нарушитель может легко подменить другим, который расшифруется в заранее заданный отрезок текста той же длины.
  
Условия для обеспечения высокого уровня защиты информации с помощью СПШ, управляющая [[Гамма|гамма]] должна иметь:
+
Условия для обеспечения высокого уровня защиты информации с помощью СПШ, управляющая [[Гамма|гамма]] должна иметь [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]] :
 
* большую длину периода;
 
* большую длину периода;
* высокую линейную сложность;
+
* высокую [[Линейная сложность|линейную сложность]];
* статистические характеристики [[мультиграмм]] близкие к соответствующим характеристикам идеальных случайных последовательностей.
+
* статистические характеристики [[Мультиграмма|мультиграмм]] близкие к соответствующим характеристикам идеальных случайных последовательностей.
  
 
=== Самосинхронизирующиеся поточные шифры ===
 
=== Самосинхронизирующиеся поточные шифры ===
[[
+
 
Самосинхронизирующиеся поточные шифры (ССПШ), для них характерна зависимость генерируемой [[Гамма|гаммы]] от предшествующих битов шифртекста. Каждое шифруемое сообщение начинается со случайного отрезка из  n знаков, который не несет содержательной нагрузки, он шифруестя, передается и затем расшифровывается. В силу несовпадения начальных состояний генераторов, этот отрезок расшифровывается некорректно, но после передачи n знаков генераторы синхронизируются.
+
Самосинхронизирующиеся поточные шифры (ССПШ), для них характерна зависимость генерируемой [[Гамма|гаммы]] от предшествующих битов шифртекста [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ф10|[Ф10]]]. Каждое шифруемое сообщение начинается со случайного отрезка из  n знаков, который не несет содержательной нагрузки, он шифруестя, передается и затем расшифровывается. В силу несовпадения начальных состояний генераторов, этот отрезок расшифровывается некорректно, но после передачи n знаков генераторы синхронизируются.
 
   [[File:image3.jpg|frame|Рисунок 6. Шифрование с использованием ССПШ|center]]
 
   [[File:image3.jpg|frame|Рисунок 6. Шифрование с использованием ССПШ|center]]
  
Line 161: Line 162:
 
Минусы ССПШ:
 
Минусы ССПШ:
 
* размножение ошибок
 
* размножение ошибок
Единичная ошибка в шифртекте порождает n ошибок в открытом тексте.
+
Единичная ошибка в шифртексте порождает n ошибок в открытом тексте.
 
* уязвимы по отношению к имитации сообщений
 
* уязвимы по отношению к имитации сообщений
 
Нарушитель может записать какой-то перехваченный им отрезок шифрованного текста и позже отправить его в адрес. После нескольких нестыковок в начале сообщения (до n знаков) посланный отрезок расшифруется верно, и получатель не сможет определить, что принял устаревшее сообщение.
 
Нарушитель может записать какой-то перехваченный им отрезок шифрованного текста и позже отправить его в адрес. После нескольких нестыковок в начале сообщения (до n знаков) посланный отрезок расшифруется верно, и получатель не сможет определить, что принял устаревшее сообщение.
Line 191: Line 192:
 
==== Аналитические атаки ====
 
==== Аналитические атаки ====
  
'''''Аналитические атаки''''' – это такие атаки, в которых алгоритм построения атаки основан на аналитических принципах вскрытия криптосхемы. Этот класс можно разбить на два подкласса: методы криптоанализа шифрующей [[Гамма|гаммы]] и методы криптоанализа процедуры ключевой инициализации и реинициализации. В первом подклассе, в силу специфики принципов построения поточных шифров, основным видом атак на данные схемы являются корреляционные атаки, основная идея которых состоит в нахождении корреляции между шифрующей [[Гамма|гаммой]] и различными линейными комбинациями ключа (регистра сдвига). Объектом исследования в корреляционных атаках выступают нелинейные функции, вносящие нелинейность в выходную последовательность регистра сдвига – таким образом, каждый раз, в зависимости от устройства применяемой нелинейной функции, реализации корреляционных атак будут различны и будут основаны на специфическом устройстве анализируемой функции.
+
'''''Аналитические атаки''''' – это такие атаки, в которых алгоритм построения атаки основан на аналитических принципах вскрытия криптосхемы. Этот класс можно разбить на два подкласса [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#С13|[С13]]]: методы криптоанализа шифрующей [[Гамма|гаммы]] и методы криптоанализа процедуры ключевой инициализации и реинициализации. В первом подклассе, в силу специфики принципов построения поточных шифров, основным видом атак на данные схемы являются корреляционные атаки, основная идея которых состоит в нахождении корреляции между шифрующей [[Гамма|гаммой]] и различными линейными комбинациями ключа (регистра сдвига). Объектом исследования в корреляционных атаках выступают нелинейные функции, вносящие нелинейность в выходную последовательность регистра сдвига – таким образом, каждый раз, в зависимости от устройства применяемой нелинейной функции, реализации корреляционных атак будут различны и будут основаны на специфическом устройстве анализируемой функции.
  
 
Предполагается, что криптоаналитику известно описание генератора (образующие полиномы, вид нелинейного преобразования), он обладает открытым и соответствующим ему закрытым текстом. Задача криптоаналитика – определение применяемого ключа (начального заполнения). На рисунке 7 показаны самые известные аналитические атаки к СПШ.
 
Предполагается, что криптоаналитику известно описание генератора (образующие полиномы, вид нелинейного преобразования), он обладает открытым и соответствующим ему закрытым текстом. Задача криптоаналитика – определение применяемого ключа (начального заполнения). На рисунке 7 показаны самые известные аналитические атаки к СПШ.
Line 211: Line 212:
 
5. Атаки, базирующиеся на восстановлении линейных полиномов.
 
5. Атаки, базирующиеся на восстановлении линейных полиномов.
  
6. Быстрая КА Чепыжова, Йоханссона, Смитса.
+
6. Быстрая КА Чепыжова, Йоханссона, Смитса (Johansson, Smits).
  
 
Под быстрыми КА понимают атаки, вычислительная сложность которых значительно меньше вычислительной сложности силовых атак.
 
Под быстрыми КА понимают атаки, вычислительная сложность которых значительно меньше вычислительной сложности силовых атак.
Line 253: Line 254:
 
====Статистические атаки====
 
====Статистические атаки====
  
'''''Статистические атаки''''' основаны на оценке статистических свойств шифрующей [[Гамма|гаммы]]. Этот класс делится на два подкласса: методы криптоанализа сложности последовательности и методы криптоанализа свойств шифрующей [[Гамма|гаммы]]. Методы первого подкласса направлены на выявление возможности генерации последовательности, аналогичной шифрующей  [[Гамма|гамме]], каким-либо другим способом, сложность реализации которого была бы меньшей по сравнению со способом генерации шифрующей [[Гамма|гаммы]]; в идеале, найденный способ должен быть применимым на практике. Данные методы используют концепции линейной сложности, профиля линейной сложности, квадратичного размаха. Методы второго подкласса направлены на выявление возможного дисбаланса в выходной последовательности криптосхемы с целью нахождения способа предположения следующего бита выходной последовательности с вероятностью лучшей, чем при случайном выборе. Данные методы оперируют различными статистическими тестами, выбор необходимого и достаточного количества тестов – прерогатива криптоаналитика.
+
'''''Статистические атаки''''' основаны на оценке статистических свойств шифрующей [[Гамма|гаммы]]. Этот класс делится на два подкласса: методы криптоанализа сложности последовательности и методы криптоанализа свойств шифрующей [[Гамма|гаммы]]. Методы первого подкласса направлены на выявление возможности генерации последовательности, аналогичной шифрующей  [[Гамма|гамме]], каким-либо другим способом, сложность реализации которого была бы меньшей по сравнению со способом генерации шифрующей [[Гамма|гаммы]]; в идеале, найденный способ должен быть применимым на практике. Данные методы используют концепции [[Линейная сложность|линейной сложности]], профиля [[Линейная сложность|линейной сложности]], квадратичного размаха. Методы второго подкласса направлены на выявление возможного дисбаланса в выходной последовательности криптосхемы с целью нахождения способа предположения следующего бита выходной последовательности с вероятностью лучшей, чем при случайном выборе. Данные методы оперируют различными статистическими тестами, выбор необходимого и достаточного количества тестов – прерогатива криптоаналитика.
  
 
Управляющая [[Гамма|гамма]] должна иметь большую длину периода (многократно превосходящую длину открытого текста) и не содержать длинных повторяющихся отрезков. В противном случае криптоанализ значительно упрощается.
 
Управляющая [[Гамма|гамма]] должна иметь большую длину периода (многократно превосходящую длину открытого текста) и не содержать длинных повторяющихся отрезков. В противном случае криптоанализ значительно упрощается.
Line 277: Line 278:
 
=== Минимальные требования криптографически стойкого поточного шифра ===
 
=== Минимальные требования криптографически стойкого поточного шифра ===
  
Минимальные требования для противостояния криптоаналитическим атакам при построении схем поточного шифрования:
+
Минимальные требования для противостояния криптоаналитическим атакам при построении схем поточного шифрования[[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#С13|[С13]]]:
 
* Каждый бит начального состояния регистра должен являться функцией от нелинейного преобразования всех бит ключа
 
* Каждый бит начального состояния регистра должен являться функцией от нелинейного преобразования всех бит ключа
  
 
* При построении нелинейных функций данные функции должны удовлетворять критериям стойкости: быть сбалансированными, обладать высокой нелинейностью, иметь высокую алгебраическую степень.
 
* При построении нелинейных функций данные функции должны удовлетворять критериям стойкости: быть сбалансированными, обладать высокой нелинейностью, иметь высокую алгебраическую степень.
  
* При длине ключа ''k'' бит внутренне состояние генератора (внутренняя память) доолжно быть не менее ''k'' бит.
+
* При длине ключа ''k'' бит внутренне состояние генератора (внутренняя память) должно быть не менее ''k'' бит.
  
 
* Минимальная длина регистра должна быть не менее ''l''=100 бит, образующий полином иметь приблизительно ''l''/2 ненулевых коэффициентов обратной связи.
 
* Минимальная длина регистра должна быть не менее ''l''=100 бит, образующий полином иметь приблизительно ''l''/2 ненулевых коэффициентов обратной связи.
  
* Для достижения максимальной линейной сложности степпень образующего полинома должна быть простым числом.
+
* Для достижения максимальной [[Линейная сложность|линейной сложности]] степень образующего полинома должна быть простым числом.
  
* Для генерации регистром последовательности максимальной длины и высокой линейной сложности данный регистр должен быть основан на примитивном полиноме обратной связи, кроме того, длина ''l'' ЛРР и алгебраический порядок d нелинейной функции должны быть достаточно велики, чтобы величина [[File:form1.jpg]] была значительно больше, чем длина шифрующей [[Гамма|гаммы]].
+
* Для генерации регистром последовательности максимальной длины и высокой [[Линейная сложность|линейной сложности]] данный регистр должен быть основан на примитивном полиноме обратной связи, кроме того, длина ''l'' ЛРР и алгебраический порядок d нелинейной функции должны быть достаточно велики, чтобы величина [[File:form1.jpg]] была значительно больше, чем длина шифрующей [[Гамма|гаммы]].
  
 
* При использовании нескольких регистров их длины должны быть взаимно-простыми.
 
* При использовании нескольких регистров их длины должны быть взаимно-простыми.
 +
 +
 +
Пример реализации алгоритма А5.1: [[File:A5.1.zip|frame|A5.1]]
  
 
== Глоссарий ==
 
== Глоссарий ==
Line 319: Line 323:
  
 
[[ Часть I. Основы криптографии (Криптографические примитивы) | Назад ]]
 
[[ Часть I. Основы криптографии (Криптографические примитивы) | Назад ]]
 +
==Пример реализации алгоритма А5.1 ==
 +
 +
Скачать исходный код данного приложения - [http://cryptowiki.net/index.php?title=File:A5.1.zip]

Latest revision as of 19:35, 4 January 2015

Contents

Криптографические генераторы

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

Элементная база криптографических схем генераторов

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

Фильтрующие генераторы

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

Пусть P – конечное поле. Фильтрующим генератором [Ф10] называется автономный автомат Формула 1.gif, где h – линейная подстановка векторного пространства Формула 2.gif, реализуемая линейным регистром сдвига длины n над полем P c функцией обратной связи f'(x),Формула 3.gif – фильтрующая функция.

Фильтрующий генератор называется нелинейным, если нелинейна фильтрующая функция. Криптографическая схема фильтрующего генератора изображена на рисунке 1.

Рисунок 1. Криптографическая схема фильтрующего генератора

Фильтрующий генератор имеет наилучшие характеристики тогда, когда используется линейный регистр сдвига максимального периода и сбалансированная фильтрующая функция. Это гарантирует длину периода гаммы, равную Формула 4.gif, где k=|P|, и сбалансированность числа единиц и числа нулей на периоде.

Нелинейные свойства гаммы обеспечиваются выбором нелинейной фильтрующей функции. Обозначим через d степень нелинейности фильтрующей функции. Известно [Ф10], что линейная сложность гаммы фильтрующего генератора Формула 5.gif, где Формула 6.gif – число различных конъюнкций от n переменных ранга от 0 до d.

Оценка снизу линейной сложности гаммы фильтрующего генератора зависит от более глубоких свойств фильтрующей функции. Например, для булевых бент-функций [KiSc83] при n, кратных 4, Формула 7.gif.

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

Известно [Ru85], что доля фильтрующих генераторов, построенных на базе линейного регистра сдвига максимального периода длины n, где n – простое, у которых линейная сложность достигает наибольшего значения, стремится к 1 с ростом n.

Комбинирующие генераторы

Комбинирующий генератор является усложнением фильтрующего генератора. Он построен на основе m>1 линейных регистров сдвига над полем P и комбинирующей функции Формула 8.gif, на вход которой поступают знаки линейных рекуррентных последовательностей, вырабатываемые линейными регистрами. Обозначим Формула 9.gif – длина ЛРС-j, Формула 10.gif. Криптографическая схема комбинирующего генератора на основе двух ЛРС изображена на рисунке 2.

Рисунок 2. Криптографическая схема комбинирующего генератора

Комбинирующий генератор называется нелинейным, если нелинейна комбинирующая функция.

Начальные состояния всех линейных регистров сдвига составляют начальное состояние генератора. Если начальное состояние каждого ЛРС отлично от нулевого, то соответствующее начальное состояние комбинирующего генератора называется неособенным.

Каждому полиному Формула 11.gif над конечным полем P можно поставить в соответствие полином Формула 12.gif над кольцом целых чисел, полученный из Формула 13.gif заменой всех ненулевых коэффициентов на 1 и заменой сложения и умножения в поле P сложением и умножением в кольце Формула 14.gif. Линейная сложность гаммы комбинирующего генератора Формула 15.gif [Ф10].

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

Если P – простое поле, и характеристические многочлены всех линейных регистров сдвига комбинирующего генератора примитивны и имеют попарно взаимно простые степени, то Формула 16.gif [А05].

При определенных линейных регистрах сдвига и комбинирующей функции можно обеспечить хорошие статистические свойства гаммы комбинирующего генератора и большую длину ее периода. В частности, если ЛРС-1,…,ЛРС-m генерируют последовательности, длины периодов которых Формула 17.gif попарно взаимно просты, и комбинирующая функция биективна по каждой переменной, то Формула 18.gif.

Примеры комбинирующих генераторов:

1) генератор Геффе (Geffe);

2) пороговый генератор.

Генератор Геффе использует комбинацию 3 регистров. Комбинирующая функция Формула 19.gif. Если все линейные регистры сдвига имеют максимальные периоды, и их длины Формула 20.gif попарно взаимно просты, то период гаммы равен произведению периодов линейных регистров сдвига, а линейная сложность гаммы генератора равна Формула 21.gif.

Пороговый генератор использует комбинацию нечетного числа регистров. Комбинирующая функция, называемая функцией мажорирования, равна Формула 22.gif. Длина периода гаммы порогового генератора равна произведению периодов линейных регистров сдвига, а линейная сложность гаммы генератора равна Формула 23.gif.

Генераторы гаммы с неравномерным движением

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

Построенные по такому принципу генераторы гаммы называются генераторами гаммы с неравномерным движением. Изменение закона движения регистра приводит к изменению исходной гаммы.

Широко используемый способ достижения эффекта неравномерного движения – последовательное соединение m автоматов, где каждый предыдущий автомат называют управляющим по отношению к следующему, последний автомат – генерирующим. Если m>2, то такое соединение автоматов называется каскадным. Другой способ – это несколько взаимно управляемых автоматов, совместно генерирующих гамму.

Генераторы «Формула 24.gif шагов»

Если в двухкаскадной схеме управляющий автомат есть фильтрующий генератор на базе линейного регистра сдвига длины n c фильтрующей функцией f(x), а генерирующий автомат есть линейный регистр сдвига длины m, отрабатывающий каждый такт в зависимости от управляющего знака Формула 25.gif или Формула 26.gif шагов, Формула 27.gif, то такой автомат называется генератором «Формула 28.gif шагов» [Ф10]. При Формула 29.gif, Формула 30.gif генератор «Формула 31.gif шагов» называется генератором «стоп-вперед». Криптографическая схема генератора «Формула 32.gif шагов» дана на рисунке 3.

Рисунок 3. Криптографическая схема генератора «Формула 24.gif шагов»

Пусть линейные регистры сдвига имеют максимальные длины периодов. Обозначим Формула 33.gif и Формула 34.gif – состояния соответственно ЛРС-1 и ЛРС-2 в i-м такте, i=1,2,… Уравнения гаммообразования генератора имеют вид:

Формула 35.gif

где Формула 36.gif – суммарная глубина продвижения ЛРС-2 после первых i тактов функционирования Формула 37.gif.

Величина Формула 38.gif не зависит от x Формула 45.gif число i кратно длине периода управляющей гаммы [Ф10]. При i, кратных Формула 39.gif, используем обозначение Формула 40.gif. Длина периода гаммы, вырабатываемой генератором «Формула 41.gif шагов», равна Формула 42.gif.

Верхняя оценка линейной сложности гаммы генератора имеет вид [Ny75]:

Формула 43.gif

где Формула 44.gif – длина периода выходной последовательности ЛРС-1.

Генераторы с перемежающимся шагом

Усложнением генератора «стоп-вперед» является генератор с перемежающимся шагом [Ф10]. Его гамма образуется как сумма гамм двух генераторов «стоп-вперед» с генерирующими линейными регистрами сдвига ЛРС-2 и ЛРС-3 длины m и r соответственно. Оба генерирующих регистра имеют общий управляющий блок – фильтрующий генератор с фильтрующей функцией f(x) на базе линейного регистра сдвига длины n. Если в i-м такте управляющий знак равен 1, то ЛРС-2 продвигается на 1 шаг, а ЛРС-3 простаивает, и при управляющем знаке 0 – наоборот. Ключом генератора являются начальные состояния всех линейных регистров сдвига.

Пусть все три регистра имеют максимальные длины периодов. Обозначим Формула 46.gif, Формула 47.gif и Формула 48.gif – состояния соответственно ЛРС-1, ЛРС-2 и ЛРС-3 в i-м такте, i=1,2,… Тогда суммарная глубина продвижения ЛРС-2 после первых i тактов функционирования Формула 49.gif.

Уравнения гаммообразования генератора имеют вид:

Формула 50.gif

Длина периода гаммы генератора с перемежающимся шагом равна Формула 51.gif.

Если характеристические многочлены ЛРС-2 и ЛРС-3 различны и неприводимы, длины периодов выходных последовательностей ЛРС-2 и ЛРС-3 взаимно просты, то длина периода гаммы генератора с перемежающимся шагом равна [Ф10] произведению длин периодов выходных последовательностей линейных регистров сдвига, а линейная сложность гаммы подчиняется оценкам:

Формула 52.gif

И генератор «Формула 53.gif шагов» и генератор с перемежающимся шагом вскрываются опробованием начального состояния управляющего линейного регистра сдвига. В силу этого эффективная длина ключа генератора близка к длине управляющего регистра.

Каскадные генераторы Гольмана (Gollman)

Каскадный генератор Гольмана [Ф10], построенный на основе m линейных регистров сдвига с максимальными длинами периодов, привлекателен тем, что может быть использован для генерации гаммы с огромной длиной периода и линейной сложностью. В этой конструкции первый регистр управляет вторым, второй – третьим и т. д.

Если все линейные регистры сдвига имеют длину n и различные примитивные характеристические многочлены [GoCh89], то длина периода гаммы m-каскадного генератора равна Формула 54.gif, а линейная сложность равна Формула 55.gif.

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

Сжимающие генераторы

Другой принцип управления движением использован в сжимающем генераторе [Ф10], который построен на основе параллельно работающих линейных регистров сдвига с максимальными длинами периодов. Знаками гаммы являются выходные значения, снимаемые с ячейки ЛРС-2, но только в те такты, когда управляющий знак ЛРС-1 равен 1, в остальные такты оба бита, генерируемые регистрами, игнорируются.

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

Генераторы с дополнительной памятью

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

Генераторы Макларена-Марсальи (MacLaren-Marsaglia)

В генераторах Макларена-Марсальи [Ф10] исходная последовательность усложняется с помощью регистра памяти и управляющих последовательностей.

Пусть имеется регистр памяти длины m, в который записываются элементы n-множества X. Для отображения входной последовательности над X в выходную последовательность над X используются 2 управляющие последовательности над кольцом Формула 56.gif – для управления записи в память членов входной последовательности и управления считыванием из памяти членов выходной последовательности.

Обозначим Формула 57.gif – длины периодов входной, выходной и управляющих последовательностей соответственно. Последовательность над множеством X называется полной, если она содержит все элементы множества X.

Если входная и управляющие последовательности являются периодическими, при этом управляющие последовательности полны [Ф10], то выходная последовательность также периодическая, причем Формула 58.gif, где Формула 59.gif.

Регистр сдвига с обратной связью с переносом

Другой способ использования дополнительной памяти для усложнения характеристик гаммы связан с конструкцией, получившей название регистра сдвига с обратной связью с переносом (РСОСП) [Ф10]. РСОСП – это автономный регистр сдвига, имеющий несколько ячеек дополнительной памяти, образующих регистр переноса. Наиболее простая разновидность РСОСП строится на базе двоичного линейного регистра сдвига и ячейки дополнительной памяти для записи целых чисел от 0 до Формула 60.gif, где r – число ячеек регистра, содержимое которых используется для вычисления обратной связи.

Пусть в ячейках регистра записаны биты Формула 61.gif, а в дополнительной памяти записано число Формула 62.gif. В следующем такте содержимое регистра сдвигается, крайний бит поступает на выход, при этом содержимое памяти и свободной после сдвига ячейки обновляется следующим образом:

1) вычисляется Формула 63.gif, где Формула 64.gif – двоичные коэффициенты, из которых r коэффициентов равны 1;

2) вычисляется Формула 65.gif;

3) младший бит числа Формула 66.gif записывается в свободную ячейку регистра сдвига, а набор остальных битов, соответствующий числу Формула 67.gif, является новым содержимым памяти.

Длина периода гаммы, вырабатываемой РСОСП, Формула 68.gif [Ф10].

Важной особенностью РСОСП является то, что для их анализа неприменим традиционный математический аппарат конечных полей. Поэтому для изучения схем с переносом разработана теория, основанная на 2-адических числах [Ke76].

Использование в криптосхемах РСОСП заметно усложняет криптоаналитические атаки на основе корреляционного анализа последовательностей [Go94]. В связи с этим, представляются перспективными схемы типа каскадных генераторов Гольмана, построенных на базе нескольких РСОСП.

Поточные шифры и их криптоанализ

Поточный шифр – это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточные шифры это одна из составляющих схем симметричного шифрования, общий вид которых, обычно, представлен в виде одного или нескольких регистров сдвига и нелинейной функции[С13]. Так как сам по себе линейный рекуррентный регистр (ЛРР) – линейное устройство, задача нелинейной функции (НЛФ) – внесение нелинейности в выходную последовательность. Поточные шифры преобразуют открытый текст в шифртекст побитово. Простейшая реализация представлена на рисунке 4. Генерируется поток битов: Form2.jpg, называемый гаммой. Поток битов открытого текста Form3.jpg и поток гаммы подвергаются операции XOR, в результате получается поток битов шифртекста Form4.jpg , где Form5.jpg, такой режим шифрования называется гаммированием. Для расшифрования используется аналогичная формула Form6.jpg.

Рисунок 4. Процесс зашифрования и расшифрования

Различают синхронные и самосинхронизирующиеся поточные шифры.

Синхронные поточные шифры

Для синхронных поточных шифров (СПШ) характерна независимость последовательности гаммы от открытого текста при зашифровании и шифртекста при расшифровании.

Рисунок 5. Шифрование с использованием с СПШ

Плюсы СПШ:

  • не размножают искажений знаков текста, которые довольно часто имеют место при передаче по каналам связи.

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

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

Минусы СПШ:

  • не защищает от умышленной подмены отрезка сообщения на другой отрезок той же длины.

Известный отрезок открытого текста нарушитель может легко подменить другим, который расшифруется в заранее заданный отрезок текста той же длины.

Условия для обеспечения высокого уровня защиты информации с помощью СПШ, управляющая гамма должна иметь [Ф10] :

  • большую длину периода;
  • высокую линейную сложность;
  • статистические характеристики мультиграмм близкие к соответствующим характеристикам идеальных случайных последовательностей.

Самосинхронизирующиеся поточные шифры

Самосинхронизирующиеся поточные шифры (ССПШ), для них характерна зависимость генерируемой гаммы от предшествующих битов шифртекста [Ф10]. Каждое шифруемое сообщение начинается со случайного отрезка из n знаков, который не несет содержательной нагрузки, он шифруестя, передается и затем расшифровывается. В силу несовпадения начальных состояний генераторов, этот отрезок расшифровывается некорректно, но после передачи n знаков генераторы синхронизируются.

Рисунок 6. Шифрование с использованием ССПШ

Плюсы ССПШ:

  • размешивание статистики открытого текста;

Минусы ССПШ:

  • размножение ошибок

Единичная ошибка в шифртексте порождает n ошибок в открытом тексте.

  • уязвимы по отношению к имитации сообщений

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

Криптоанализ

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

Методы криптоанализа схем поточного шифрования можно разделить на три класса:

  • аналитические атаки;
  • статистически атаки;
  • силовые атаки.

Силовые атаки

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

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

Несколько сложнее с атакой на основе только лишь шифртекста. В этом случае необходимо наличие какой-либо дополнительной информации об открытом тексте, например [П09]:

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

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

Аналитические атаки

Аналитические атаки – это такие атаки, в которых алгоритм построения атаки основан на аналитических принципах вскрытия криптосхемы. Этот класс можно разбить на два подкласса [С13]: методы криптоанализа шифрующей гаммы и методы криптоанализа процедуры ключевой инициализации и реинициализации. В первом подклассе, в силу специфики принципов построения поточных шифров, основным видом атак на данные схемы являются корреляционные атаки, основная идея которых состоит в нахождении корреляции между шифрующей гаммой и различными линейными комбинациями ключа (регистра сдвига). Объектом исследования в корреляционных атаках выступают нелинейные функции, вносящие нелинейность в выходную последовательность регистра сдвига – таким образом, каждый раз, в зависимости от устройства применяемой нелинейной функции, реализации корреляционных атак будут различны и будут основаны на специфическом устройстве анализируемой функции.

Предполагается, что криптоаналитику известно описание генератора (образующие полиномы, вид нелинейного преобразования), он обладает открытым и соответствующим ему закрытым текстом. Задача криптоаналитика – определение применяемого ключа (начального заполнения). На рисунке 7 показаны самые известные аналитические атаки к СПШ.

Рисунок 7. Аналитические атаки
  • Корреляционные атаки (КА)

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

Среди атак данного класса выделяют следующие атаки:

1. Базовые КА.

2. Атаки, базирующиеся на низковесовых проверках четности.

3. Атаки, базирующиеся на использовании конволюционных кодов.

4. Атаки, использующие технику турбо кодов.

5. Атаки, базирующиеся на восстановлении линейных полиномов.

6. Быстрая КА Чепыжова, Йоханссона, Смитса (Johansson, Smits).

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

Коррелляционная атака достаточно легко применима в случае, если булевы функции усложнения, используемые в генераторах (фильтрующие функции, комбинирующие функции, функции мажорирования) имеют хорошие линейные приближения. Считается, что она эффективна, если существует линейное приближение, верное для δ всех наборов таблицы истинности функции, где δ>0,5.

  • Компромисс «время-память»

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

1. Строится большой словарь, включающий все возможные пары «состояние-выход».

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

  • «Предполагай и определяй»

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

1. Предполагается содержимое ячеек регистра.

2. Определяется полное заполнение регистра путем применения линейной рекурренты регистра на основе принятых допущений.

3. Генерируется выходная последовательность. Если она эквивалентна шифрующей гамме, предположение считается верным, иначе – переход к шагу 1.

  • Инверсионные атаки

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

  • Ключевая загрузка, инициализация/реинициализация

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

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

Атака с помощью вставки символа. Пусть открытый текст X.jpg c помощью гаммы K.jpg преобразуется в шифртекст Y.jpg в соответствии с вышеуказанными уравнениями шифрования. Криптоаналитику известен шифртекст, но не известны открытый текст и гамма. Предположим также, что криптоаналитик располагает криптограммой, полученной зашифрованием с помощью той же гаммы видоизмененного открытого текста вставкой в некоторой позиции известного бита x′. Пусть видоизмененный открытый текст есть Seq1.jpg и соответствующий шифртекст есть Seq2.jpg По двум шифртекстам можно определить, начиная с момента вставки, и гамму, и открытый текст.

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

Статистические атаки

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

Управляющая гамма должна иметь большую длину периода (многократно превосходящую длину открытого текста) и не содержать длинных повторяющихся отрезков. В противном случае криптоанализ значительно упрощается.

Анализ шифров, использующих гамму с одинаковыми повторяющимися отрезками.

Рассмотрим поточный шифр, реализующий модульное гаммирование с уравнениями шифрования

1x.jpg, i=1,2,…

Пусть криптоаналитик располагает криптограммами 2.jpg и 3.jpg, соответствующими открытым текстам 4.jpg и 5.jpg при использовании одинаковых отрезков гаммы. Требуется восстановить открытые тексты.

Разность данных криптограмм не зависит от гаммы:

6.jpg, i=1,2,…

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

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

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

Минимальные требования криптографически стойкого поточного шифра

Минимальные требования для противостояния криптоаналитическим атакам при построении схем поточного шифрования[С13]:

  • Каждый бит начального состояния регистра должен являться функцией от нелинейного преобразования всех бит ключа
  • При построении нелинейных функций данные функции должны удовлетворять критериям стойкости: быть сбалансированными, обладать высокой нелинейностью, иметь высокую алгебраическую степень.
  • При длине ключа k бит внутренне состояние генератора (внутренняя память) должно быть не менее k бит.
  • Минимальная длина регистра должна быть не менее l=100 бит, образующий полином иметь приблизительно l/2 ненулевых коэффициентов обратной связи.
  • Для достижения максимальной линейной сложности степень образующего полинома должна быть простым числом.
  • Для генерации регистром последовательности максимальной длины и высокой линейной сложности данный регистр должен быть основан на примитивном полиноме обратной связи, кроме того, длина l ЛРР и алгебраический порядок d нелинейной функции должны быть достаточно велики, чтобы величина Form1.jpg была значительно больше, чем длина шифрующей гаммы.
  • При использовании нескольких регистров их длины должны быть взаимно-простыми.


Пример реализации алгоритма А5.1: File:A5.1.zip

Глоссарий

Библиографический указатель

Перейти к списку литературы по разделу "Криптографические генераторы. Поточные шифры и их криптоанализ".


Авезова Я.Э., Гендугова Д.В., 2013 г.

Назад

Пример реализации алгоритма А5.1

Скачать исходный код данного приложения - [1]