Регистр сдвига с обратной связью по переносу
Регистр сдвига с обратной связью по переносу (англ. feedback with carry shift register, FCSR) — регистр сдвига битовых слов, арифметический аналог регистра сдвига с линейной обратной связью, отличается от него наличием регистра переноса. Применяется для генерации псевдослучайных последовательностей битов, а также использовался для создания потокового шифра F-FCSR.
Содержание
История
В 1994 регистр сдвига с обратной связью по переносу был изобретен Горески (англ. Goresky) и Клаппером (англ. Klapper), а также независимо от них Марсаглией (англ. Marsaglia) и Заманом (англ. Zaman), Кутюром (англ. Couture) и Л’Экуером (англ. L’Ecuyer). Причем Клаппер и Горески хотели использовать его для криптоанализа суммирующего генератора. С другой стороны, Марсаглия, Заман, Кутюр, Л’Экуер были нацелены найти хороший генератор случайных чисел для решения таких задач, как использование квази-Монте-Карло метода.[1]
Описание
В FCSR есть сдвиговый регистр, функция обратной связи и регистр переноса. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию.[2]
Вместо выполнения операции XOR над всеми битами отводной последовательности эти биты складываются друг с другом и с содержимым регистра переноса. Результат <math> mod </math> <math>2</math> и становится новым битом. Результат, деленный на <math> 2 </math>, становится новым содержимым регистра переноса.[3]
<math>m</math> - значение регистра переноса
- <math>\sigma={q_1}{a_{k-1}}+\cdots+{q_k}{a_0}+m</math>
- <math>{a_k}={\sigma} {mod}{2}</math>
- <math>{m^\prime}=[{\sigma}/2]</math>
<math>({a_k},\cdots, {a_1})</math> - новое состояние регистра
<math>m^\prime</math> - новое значение регистра переноса
Пример
Рассмотрим пример 3-битового регистра с ответвлениями в первой и второй позициях. Пусть его начальное значение <math>\left[0,\;0,\;1\right]</math>, а начальное содержимое регистра переноса равно <math>[0]</math>. Выходом будет являться крайний правый бит сдвигового регистра. Дальнейшие состояния регистра приведены в таблице ниже:
| Номер шага | Сдвиговый регистр | Регистр переноса |
|---|---|---|
| 0 | <math>\left[0,\;0,\;1\right] </math> | 0 |
| 1 | <math>\left[1,\;0,\;0\right]</math> | 0 |
| 2 | <math>\left[0,\;1,\;0\right]</math> | 0 |
| 3 | <math>\left[1,\;0,\;1\right]</math> | 0 |
| 4 | <math>\left[1,\;1,\;0\right]</math> | 0 |
| 5 | <math>\left[1,\;1,\;1\right]</math> | 0 |
| 6 | <math>\left[0,\;1,\;1\right]</math> | 1 |
| 7 | <math>\left[1,\;0,\;1\right]</math> | 1 |
| 8 | <math>\left[0,\;1,\;0\right]</math> | 1 |
| 9 | <math>\left[0,\;0,\;1\right]</math> | 1 |
| 10 | <math>\left[0,\;0,\;0\right]</math> | 1 |
| 11 | <math>\left[1,\;0,\;0\right]</math> | 0 |
Конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом равным <math>10</math>. Стоит также упомянуть, что регистр переноса является не битом, а числом. Его размер должен быть не меньше <math>\log_2 t</math>, где <math>t</math> - число ответвлений. В примере только три отвевления, поэтому регистр переноса однобитовый. Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения <math>0, 1, 2 </math> или <math> 3 </math>.[3]
Свойства
В отличие от LFSR, для FCSR существует задержка, прежде чем он перейдёт в циклический режим, то есть начнёт генерировать циклически повторяемую последовательность. В зависимости от выбранного начального состояния возможны 4 различных случая:[3]
- Начальное состояние может оказаться частью максимального периода.
- Начальное состояние может перейти в последовательность максимального периода, после некоторой начальной задержки.
- Начальное состояние может после начальной задержки породить последовательность нулей.
- Начальное состояние может после начальной задержки породить последовательность единиц.
Опытным путём можно проверить, чем закончится конкретное начальное состояние. Нужно запустить FCSR на некоторое время. (Если <math>m</math> - начальный объем памяти, а <math>t</math> - количество ответвлений, то достаточно <math>{~\log_2 t}+{~\log_2 m}+1</math> тактов.) Если выходной поток вырождается в бесконечную последовательность нулей и единиц за <math>n</math> бит, где <math>n</math> - длина FCSR, то не стоит использовать это начальное состояние. [3]
Также, стоит отметить, что ряд ключей генератора на базе FCSR будут слабыми, так как начальное состояние FCSR соответствует ключу потокового шифра. [3]
Максимальный период FCSR равен <math>q-1</math> , где <math>q</math> - целое число связи. Это число задает ответвления и определяется как:
<math>q={2q_1}+{{2^2}q_2}+{{2^3}q_3}+\cdots+{{2^n}q_n}-1</math>
<math>q</math> - должно быть простым числом, для которого 2 является примитивным корнем.[3] [1]
Связь с LFSR
Также, как анализ LFSR основан на сложении примитивных многочленов mod 2, анализ FCSR основан на сложении чисел, называемых 2-adic. В мире 2-adic чисел существуют аналоги для всего. Точно также, как определяется линейная сложность, можно определить 2-adic сложность. Существует 2-adic аналог и для алгоритма Берлекэмпа-Мэсси. Это означает, что число возможных потоковых шифров по крайней мере удвоилось. Все что можно делать с LFSR, можно делать и с FCSR.[3]
Варианты реализации
Конфигурация Галуа
Конфигурация Галуа состоит из:
- n - битного главного регистра <math>M=(m_0,\cdots,{m_{n-1}})</math> , с некоторыми фиксированными ответвлениями <math>d_0, \cdots, d_{n-1}</math>
- n-1 - битного регистра переноса <math>C=(c_0,\cdots,c_{n-2})</math>
В момент времени t состояние <math>(M,C)</math> изменяется следующим образом:
1. <math> x_i=m_{i+1} + {c_i}{d_i} + {m_0}{d_i}</math> , для всех <math>0 \leq i < n </math> , с <math>m_{n}=0</math> и <math>c_{n-1}=0</math> и где <math>m_0</math> представляет бит обратной связи.
2. обновляется состояние: <math>m_i \leftarrow {x_i}mod2 </math> , для всех <math>i \in [0 \dots n-1] </math> и <math>c_i \leftarrow {x_i}div2 </math> , для всех <math>i \in [0 \dots n-2] </math> .[4][5]
Конфигурация Фибоначчи
Конфигурация Фибоначчи состоит из:
- n - битного главного регистра <math>M=(m_0,\cdots,{m_{n-1}})</math>
- ответвления <math>(d_0, \cdots, d_{n-1})</math> связаны с регистром переноса <math>c</math> , состоящего из <math> w_H(d) </math> битов, где <math> w_H(d) </math> вес Хамминга для <math>d=(1+|q|)/2</math>
Состояние <math>(M,c)</math> изменяется следующим образом:
1. <math> x = c+ \sum^{n-1}_{i=0} {{m_i}{d_{n-1-i}}} </math> ;
2. обновляем состояние: <math> M \leftarrow (m_1, \dots , m_{n-1}, x mod2) </math> , <math> c \leftarrow x div2 </math> .[4][5]
Возможные варианты использования в генераторах
Чередующиеся генераторы "стоп-пошел"
Основная статья: Генератор "стоп-пошел"
В нём используются три регистра сдвига различной длины. Здесь Регистр-1 управляет тактовой частотой 2-го и 3-го регистров, то есть Регистр-2 меняет своё состояние, когда выход Регистра-1 равен единице, а Регистр-3 - когда выход Регстра-1 равен нулю.[3]
Эти регистры используют FCSR вместо некоторых LFSR, и операция XOR может быть заменена сложением с переносом.
- Генератор "стоп-пошел" FCSR : Регистр-1, Регистр-2, Регистр-3 - это FCSR. Объединяющая функция - XOR.
- Генератор "стоп-пошел" FCSR/LFSR : Регистр-1 - FCSR; Регистр-2, Регистр-3 - LFSR. Объединяющая функция - сложение с переносом.
- Генератор "стоп-пошел" FCSR/LFSR : Регистр-1 - LFSR; Регистр-2, Регистр-3 - FCSR. Объединяющая функция - XOR.[3]
Каскадные генераторы
Основная статья: Каскад Голлманна
Данная схема представляет собой улучшенную версию генератора «стоп-пошёл». Он состоит из последовательности регистров, тактирование каждого из которых управляется предыдущим регистром. Если выходом Регистра-1 в момент времени является 1,то тактируется Регистр-2. Если выходом Регистра-2 в момент времени является 1, то тактируется Регистр-3, и так далее. Выход последнего регистра является выходом генератора.[3]
Существует два способа использовать FCSR в каскадных генераторах:
- Каскад FCSR. Каскад Голлманна с FCSR вместо LFSR.
- Каскад FCSR/LFSR. Каскад Голлманна с генераторами, меняющими LFSR на FCSR и наоборот.[3]
Комбинированные генераторы
Эти генераторы используют переменное количество FCSR и/или LFSR и множество функций, объединяющих регистры. Операция XOR разрушает алгебраические свойства FCSR, поэтому имеет смысл использовать эту операцию для их объединения.[3]
- Генератор четности FCSR. Все регистры - FCSR, а объединяющая функция - XOR.
- Генератор четности LFSR/FCSR. Используется смесь LFSR и FCSR, а объединяющая функция - XOR.
- Пороговый генератор FCSR. Все регистры - FCSR, а объединяющая функция - мажорирование.
- Пороговый генератор LFSR/FCSR. Используется смесь LFSR и FCSR, а объединяющая функция - мажорирование.
- Суммирующий генератор FCSR. Все регистры - FCSR, а объединяющая функция - сложение с переносом.
- Суммирующий генератор LFSR/FCSR. Используется смесь LFSR и FCSR, а объединяющая функция - сложение с переносом.[3]
Применение
Регистры сдвига с обратной связью по переносу могут служить основой при создании различных генераторов (некоторые из них описывались выше), а также различных потоковых шифров.
F-FCSR
Основная статья : F-FCSR .
F-FCSR — семейство поточных шифров, основанное на использовании регистра сдвига с обратной связью по переносу(FCSR) с линейным фильтром на выходе. Идея шифра была предложена Терри Бергером, Франсуа Арно и Седриком Лараду. F-FCSR был представлен на конкурсе eSTREAM, был включен в список победителей конкурса в апреле 2008, но в дальнейшем была выявлена криптографическая слабость и в сентябре 2008 F-FCSR был исключен из списка eSTREAM.
См. также
Напишите отзыв о статье "Регистр сдвига с обратной связью по переносу"
Примечания
- ↑ 1 2 [download.springer.com/static/pdf/864/chp%253A10.1007%252F11423461_3.pdf?auth66=1418911000_068addc30c0d3e79e30641e6ee203237&ext=.pdf A. Klapper A Survey of Feedback with Carry Shift Registers]
- ↑ A. Klapper and M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, in Journal of Cryptology vol. 10, pp. 111-147, 1997, [www.springerlink.com/content/bnxf4xc81ltqdlfm/?p=d309beafbf334b32b24164de4503446a&pi=3]
- ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Б. Шнайер, 2013.
- ↑ 1 2 A. Klapper and M. Goresky, Fibonacci and Galois Representations of Feedback with Carry Shift Registers, 2004, [www.cs.uky.edu/~klapper/pdf/galois.pdf]
- ↑ 1 2 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier and Benjamin Pousse, A new approach for FCSRs, [link.springer.com/chapter/10.1007%2F978-3-642-05445-7_27]
Литература
- Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — Триумф, 2013. — 816 с. — ISBN 978-5-89392-527-2.
Отрывок, характеризующий Регистр сдвига с обратной связью по переносу
– Какая вы смешная! – проговорил он, нагибаясь к ней, еще более краснея, но ничего не предпринимая и выжидая.Она вдруг вскочила на кадку, так что стала выше его, обняла его обеими руками, так что тонкие голые ручки согнулись выше его шеи и, откинув движением головы волосы назад, поцеловала его в самые губы.
Она проскользнула между горшками на другую сторону цветов и, опустив голову, остановилась.
– Наташа, – сказал он, – вы знаете, что я люблю вас, но…
– Вы влюблены в меня? – перебила его Наташа.
– Да, влюблен, но, пожалуйста, не будем делать того, что сейчас… Еще четыре года… Тогда я буду просить вашей руки.
Наташа подумала.
– Тринадцать, четырнадцать, пятнадцать, шестнадцать… – сказала она, считая по тоненьким пальчикам. – Хорошо! Так кончено?
И улыбка радости и успокоения осветила ее оживленное лицо.
– Кончено! – сказал Борис.
– Навсегда? – сказала девочка. – До самой смерти?
И, взяв его под руку, она с счастливым лицом тихо пошла с ним рядом в диванную.
Графиня так устала от визитов, что не велела принимать больше никого, и швейцару приказано было только звать непременно кушать всех, кто будет еще приезжать с поздравлениями. Графине хотелось с глазу на глаз поговорить с другом своего детства, княгиней Анной Михайловной, которую она не видала хорошенько с ее приезда из Петербурга. Анна Михайловна, с своим исплаканным и приятным лицом, подвинулась ближе к креслу графини.
– С тобой я буду совершенно откровенна, – сказала Анна Михайловна. – Уж мало нас осталось, старых друзей! От этого я так и дорожу твоею дружбой.
Анна Михайловна посмотрела на Веру и остановилась. Графиня пожала руку своему другу.
– Вера, – сказала графиня, обращаясь к старшей дочери, очевидно, нелюбимой. – Как у вас ни на что понятия нет? Разве ты не чувствуешь, что ты здесь лишняя? Поди к сестрам, или…
Красивая Вера презрительно улыбнулась, видимо не чувствуя ни малейшего оскорбления.
– Ежели бы вы мне сказали давно, маменька, я бы тотчас ушла, – сказала она, и пошла в свою комнату.
Но, проходя мимо диванной, она заметила, что в ней у двух окошек симметрично сидели две пары. Она остановилась и презрительно улыбнулась. Соня сидела близко подле Николая, который переписывал ей стихи, в первый раз сочиненные им. Борис с Наташей сидели у другого окна и замолчали, когда вошла Вера. Соня и Наташа с виноватыми и счастливыми лицами взглянули на Веру.
Весело и трогательно было смотреть на этих влюбленных девочек, но вид их, очевидно, не возбуждал в Вере приятного чувства.
– Сколько раз я вас просила, – сказала она, – не брать моих вещей, у вас есть своя комната.
Она взяла от Николая чернильницу.
– Сейчас, сейчас, – сказал он, мокая перо.
– Вы всё умеете делать не во время, – сказала Вера. – То прибежали в гостиную, так что всем совестно сделалось за вас.
Несмотря на то, или именно потому, что сказанное ею было совершенно справедливо, никто ей не отвечал, и все четверо только переглядывались между собой. Она медлила в комнате с чернильницей в руке.
– И какие могут быть в ваши года секреты между Наташей и Борисом и между вами, – всё одни глупости!
– Ну, что тебе за дело, Вера? – тихеньким голоском, заступнически проговорила Наташа.
Она, видимо, была ко всем еще более, чем всегда, в этот день добра и ласкова.
– Очень глупо, – сказала Вера, – мне совестно за вас. Что за секреты?…
– У каждого свои секреты. Мы тебя с Бергом не трогаем, – сказала Наташа разгорячаясь.
– Я думаю, не трогаете, – сказала Вера, – потому что в моих поступках никогда ничего не может быть дурного. А вот я маменьке скажу, как ты с Борисом обходишься.
– Наталья Ильинишна очень хорошо со мной обходится, – сказал Борис. – Я не могу жаловаться, – сказал он.
– Оставьте, Борис, вы такой дипломат (слово дипломат было в большом ходу у детей в том особом значении, какое они придавали этому слову); даже скучно, – сказала Наташа оскорбленным, дрожащим голосом. – За что она ко мне пристает? Ты этого никогда не поймешь, – сказала она, обращаясь к Вере, – потому что ты никогда никого не любила; у тебя сердца нет, ты только madame de Genlis [мадам Жанлис] (это прозвище, считавшееся очень обидным, было дано Вере Николаем), и твое первое удовольствие – делать неприятности другим. Ты кокетничай с Бергом, сколько хочешь, – проговорила она скоро.
– Да уж я верно не стану перед гостями бегать за молодым человеком…
– Ну, добилась своего, – вмешался Николай, – наговорила всем неприятностей, расстроила всех. Пойдемте в детскую.
Все четверо, как спугнутая стая птиц, поднялись и пошли из комнаты.
– Мне наговорили неприятностей, а я никому ничего, – сказала Вера.
– Madame de Genlis! Madame de Genlis! – проговорили смеющиеся голоса из за двери.
Красивая Вера, производившая на всех такое раздражающее, неприятное действие, улыбнулась и видимо не затронутая тем, что ей было сказано, подошла к зеркалу и оправила шарф и прическу. Глядя на свое красивое лицо, она стала, повидимому, еще холоднее и спокойнее.
В гостиной продолжался разговор.
– Ah! chere, – говорила графиня, – и в моей жизни tout n'est pas rose. Разве я не вижу, что du train, que nous allons, [не всё розы. – при нашем образе жизни,] нашего состояния нам не надолго! И всё это клуб, и его доброта. В деревне мы живем, разве мы отдыхаем? Театры, охоты и Бог знает что. Да что обо мне говорить! Ну, как же ты это всё устроила? Я часто на тебя удивляюсь, Annette, как это ты, в свои годы, скачешь в повозке одна, в Москву, в Петербург, ко всем министрам, ко всей знати, со всеми умеешь обойтись, удивляюсь! Ну, как же это устроилось? Вот я ничего этого не умею.
– Ах, душа моя! – отвечала княгиня Анна Михайловна. – Не дай Бог тебе узнать, как тяжело остаться вдовой без подпоры и с сыном, которого любишь до обожания. Всему научишься, – продолжала она с некоторою гордостью. – Процесс мой меня научил. Ежели мне нужно видеть кого нибудь из этих тузов, я пишу записку: «princesse une telle [княгиня такая то] желает видеть такого то» и еду сама на извозчике хоть два, хоть три раза, хоть четыре, до тех пор, пока не добьюсь того, что мне надо. Мне всё равно, что бы обо мне ни думали.
– Ну, как же, кого ты просила о Бореньке? – спросила графиня. – Ведь вот твой уже офицер гвардии, а Николушка идет юнкером. Некому похлопотать. Ты кого просила?
– Князя Василия. Он был очень мил. Сейчас на всё согласился, доложил государю, – говорила княгиня Анна Михайловна с восторгом, совершенно забыв всё унижение, через которое она прошла для достижения своей цели.
– Что он постарел, князь Василий? – спросила графиня. – Я его не видала с наших театров у Румянцевых. И думаю, забыл про меня. Il me faisait la cour, [Он за мной волочился,] – вспомнила графиня с улыбкой.
– Всё такой же, – отвечала Анна Михайловна, – любезен, рассыпается. Les grandeurs ne lui ont pas touriene la tete du tout. [Высокое положение не вскружило ему головы нисколько.] «Я жалею, что слишком мало могу вам сделать, милая княгиня, – он мне говорит, – приказывайте». Нет, он славный человек и родной прекрасный. Но ты знаешь, Nathalieie, мою любовь к сыну. Я не знаю, чего я не сделала бы для его счастья. А обстоятельства мои до того дурны, – продолжала Анна Михайловна с грустью и понижая голос, – до того дурны, что я теперь в самом ужасном положении. Мой несчастный процесс съедает всё, что я имею, и не подвигается. У меня нет, можешь себе представить, a la lettre [буквально] нет гривенника денег, и я не знаю, на что обмундировать Бориса. – Она вынула платок и заплакала. – Мне нужно пятьсот рублей, а у меня одна двадцатипятирублевая бумажка. Я в таком положении… Одна моя надежда теперь на графа Кирилла Владимировича Безухова. Ежели он не захочет поддержать своего крестника, – ведь он крестил Борю, – и назначить ему что нибудь на содержание, то все мои хлопоты пропадут: мне не на что будет обмундировать его.
Графиня прослезилась и молча соображала что то.
– Часто думаю, может, это и грех, – сказала княгиня, – а часто думаю: вот граф Кирилл Владимирович Безухой живет один… это огромное состояние… и для чего живет? Ему жизнь в тягость, а Боре только начинать жить.
– Он, верно, оставит что нибудь Борису, – сказала графиня.
– Бог знает, chere amie! [милый друг!] Эти богачи и вельможи такие эгоисты. Но я всё таки поеду сейчас к нему с Борисом и прямо скажу, в чем дело. Пускай обо мне думают, что хотят, мне, право, всё равно, когда судьба сына зависит от этого. – Княгиня поднялась. – Теперь два часа, а в четыре часа вы обедаете. Я успею съездить.
И с приемами петербургской деловой барыни, умеющей пользоваться временем, Анна Михайловна послала за сыном и вместе с ним вышла в переднюю.
– Прощай, душа моя, – сказала она графине, которая провожала ее до двери, – пожелай мне успеха, – прибавила она шопотом от сына.
– Вы к графу Кириллу Владимировичу, ma chere? – сказал граф из столовой, выходя тоже в переднюю. – Коли ему лучше, зовите Пьера ко мне обедать. Ведь он у меня бывал, с детьми танцовал. Зовите непременно, ma chere. Ну, посмотрим, как то отличится нынче Тарас. Говорит, что у графа Орлова такого обеда не бывало, какой у нас будет.
– Mon cher Boris, [Дорогой Борис,] – сказала княгиня Анна Михайловна сыну, когда карета графини Ростовой, в которой они сидели, проехала по устланной соломой улице и въехала на широкий двор графа Кирилла Владимировича Безухого. – Mon cher Boris, – сказала мать, выпрастывая руку из под старого салопа и робким и ласковым движением кладя ее на руку сына, – будь ласков, будь внимателен. Граф Кирилл Владимирович всё таки тебе крестный отец, и от него зависит твоя будущая судьба. Помни это, mon cher, будь мил, как ты умеешь быть…
– Ежели бы я знал, что из этого выйдет что нибудь, кроме унижения… – отвечал сын холодно. – Но я обещал вам и делаю это для вас.
Несмотря на то, что чья то карета стояла у подъезда, швейцар, оглядев мать с сыном (которые, не приказывая докладывать о себе, прямо вошли в стеклянные сени между двумя рядами статуй в нишах), значительно посмотрев на старенький салоп, спросил, кого им угодно, княжен или графа, и, узнав, что графа, сказал, что их сиятельству нынче хуже и их сиятельство никого не принимают.
– Мы можем уехать, – сказал сын по французски.
– Mon ami! [Друг мой!] – сказала мать умоляющим голосом, опять дотрогиваясь до руки сына, как будто это прикосновение могло успокоивать или возбуждать его.
