PALS: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Следующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
← Новая страница: «{{В инкубаторе}} {{Инкубатор, пишу}} <!-- Начинайте писать ниже этой строки --> '''Сюд...»
(нет различий)

Версия от 15:02, 24 января 2020

Сюда поместите название статьи —PALS


PALS- потоковый шифр ,спроектирован как управляемый часами с новым механизмом изменения шагов,основанным на теории систем таким образом,что используемые в нем структуры устойчивы к обычным атакам. Алгоритм PALS использует основной ключ длиной 256 бит и 32-битный ключ сообщения. Наиболее важными критериями,учитываемыми при разработке PALS, являются устойчивость к известным атакам,максимальный период, высокая линейная сложность и хорошие статистические свойства.В результате выходной поток ключей очень похож на совершенно случайные последовательности и устойчив к обычным атакам,таким как корреляционные атаки,алгебраическая атака,атака «разделяй и властвуй»,атака компромисса времени и памяти и атаки AIDA/ куба.[1]

Базовая структура PALS представляет собой комбинированный генератор с памятью, управляемый часами.[1]

Введение

Для построения бесконечной псевдослучайной последовательности с использованием случайной последовательности конечной длины, был предложен новый потоковый шифр PALS, разработанный как комбинированный генератор с управлением по часам с памятью. Начальный вектор из 1600 битов генерируется путем объединения 256-битного главного ключа с ключом сообщения. LFSR длиной 32 бита используется для генерации ключа сообщения. Для получения 256-битной последовательности 32-битный ключ сообщения подвергался функции stream-5 восемь раз. Ключ сеанса получается путем побитового XOR, получающегося в результате 256-битной последовательности с основным ключом. Основной период смены ключа в этой структуре составляет до 4,25 года. Генерация ключевого потока в алгоритме PALS основана на теории систем и полных случайных последовательностях.-[2]

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

Потоковые шифры работают с изменяющимся во времени преобразованием отдельных цифр открытого текста.[4]

Потоковые шифры на основе LFSR

Основное использование LFSR в потоковом шифре - это создание псевдослучайной последовательности. Мы знаем, что LFSR может генерировать бесконечный поток битов. В наиболее распространенной форме для построения потокового шифра используются несколько LFSR. Но LFSR проявляет линейное свойство. Таким образом, понятие нелинейности было введено для преодоления недостатка линейного свойства путем нерегулярного изменения тактовой частоты LFSR.[5]

Потоковый шифр на основе LFSR использует в основном три класса pRNG (генераторов псевдослучайных чисел), а именно нелинейную комбинацию, нелинейный фильтр и генераторы с управлением по часам. Почти все потоковые шифры на основе LFSR следуют любым из этих нелинейных методов или используют комбинацию этих методов с некоторыми дополнительными усилиями, такими как добавление счетчика или комбинации различных LFSR с NLFSR. [5]

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

Регистры сдвига с линейной обратной связью (LFSR) в двоичных генераторах ключей для криптографических приложений обычно объединяются функциями без памяти. Такие структуры уязвимы для атак корреляции «разделяй и властвуй», основанных на поэтапной корреляции между последовательностью потока ключей и набором последовательностей LFSR.[7]

Разрушение линейности

Одним из общих методов разрушения линейности, присущей LFSR, является использование нескольких LFSR параллельно. Поток ключей генерируется как нелинейная функция от выходных данных LFSR. Такие генераторы потока ключей называются нелинейными комбинированными генераторами, и их называют объединяющей функцией. Функция должна удовлетворять нескольким критериям, чтобы противостоять определенным конкретным криптографическим атакам.[8]

Генератор потока ключей

Основной подход к проектированию генератора потока ключей с использованием LFSR прост. Сначала вы выбираете один или несколько LFSR, как правило, различной длины и с различными полиномами обратной связи. (Если длины все относительно простые, а полиномы обратной связи все примитивные, весь генератор имеет максимальную длину.) Ключ - это начальное состояние LFSR. Каждый раз, когда вы хотите получить бит, сдвиньте LFSR один раз (это иногда называется синхронизацией). Выходной бит является функцией, предпочтительно нелинейной, некоторых битов LFSR. Эта функция называется функцией объединения, а весь генератор называется генератором комбинации. (Если выходной бит является функцией одного LFSR, генератор называется генератором фильтров.) Большая часть теоретической основы для такого рода вещей была заложена Селмером и Нилом Цирлером.[4]

Генераторы с часовым управлением

Некоторые генераторы имеют LFSR с разной частотой; иногда тактирование одного генератора зависит от мощности другого. Все они являются электронными версиями машинных шифров до Второй мировой войны и называются генераторами с часовым управлением [3]. Управление тактовыми импульсами может иметь прямую связь, когда выход одного LFSR контролирует тактирование другого, или обратную связь, где выход одного LFSR контролирует свое собственное тактирование. Хотя эти генераторы, по крайней мере теоретически, подвержены встраиванию и вероятностным атакам корреляции, многие на данный момент защищены.[9][10] Ян Касселлс, когда-то возглавлявший чистую математику в Кембридже и бывший криптоаналитик Блетчли Парк, сказал, что «криптография - это смесь математики и путаницы и без путаницы математика может быть использована против вас ». Он имел в виду, что в потоковых шифрах вам нужна какая-то математическая структура, такая как LFSR, для обеспечения максимальной длины и других свойств, а затем некоторая сложная нелинейная путаница,чтобы не дать кому-то получить доступ к регистру и решить его.[4]

В генераторах нелинейных комбинаций и генераторах нелинейных фильтров компоненты LFSR регулярно синхронизируются; то есть перемещение данных во всех LFSR контролируется одним и тем же тактом. Основная идея генераторов, управляемых синхронизацией, состоит в том, чтобы ввести нелинейность в генераторы потока ключей на основе LFSR, имея выход одного LFSR, управляющий тактированием (т. е. пошагово) второго LFSR. Поскольку второй LFSR синхронизируется нерегулярно, надежда состоит в том, что атаки, основанные на регулярном движении LFSR, могут быть сорваны.[8]

Преимущества потоковых шифров

Потоковый шифр является важной категорией симметричных алгоритмов шифрования; Более того, синхронные потоковые шифры не страдают от распространения ошибок, потому что каждый бит независимо шифруется / дешифруется от любого другого. По сравнению с блочными шифрами большинство потоковых шифров, как правило, намного быстрее и имеют большую эффективность программного обеспечения. Благодаря этим функциям потоковые шифры становятся лучшим выбором для нескольких протоколов связи, особенно используемых в беспроводной области.[11]

Регистры сдвига с линейной обратной связью (LFSR) довольно эффективны в аппаратном обеспечении и являются основными строительными блоками этого шифра.[11]

Описание алгоритма PALS

Управление ключами

Основная цель PALS - построить бесконечную (вычислительную) псевдослучайную последовательность, используя случайную последовательность конечной длины. Поскольку длина основного ключа алгоритма шифрования составляет 256 бит и намного короче его исходного состояния (1600 бит), этот ключ должен быть расширен соответствующим способом для получения начального вектора. Нам также необходимо использовать новый ключ для шифрования каждого сообщения, но мы не можем изменить основной ключ для каждого сообщения. Учитывая эти ограничения, необходимо разработать алгоритм генерации ключа, который генерирует начальный вектор путем объединения основного ключа системы и ключа, называемого ключом сообщения.[1]

Каждое новое сообщение шифруется одним и тем же ключом.[1]

Для этого генерируется сеансовый ключ с ключом сообщения и основным ключом длиной 256 бит. Затем сеансовый ключ расширяется до 1600 бит (начальный вектор). Блок-схема начальной генерации вектора показана на рис. 1.[1]

Генератор ключей сообщений

Ключ сообщения должен быть сгенерирован таким образом, чтобы он не повторялся в течение периода смены основного ключа. Если мы предположим, что этот алгоритм должен использоваться 24 часа в сутки без перерыва, и каждую секунду требуется 32-битный ключ сообщения, то через 4,25 года генерируется и используется полный период ключа сообщения, и он снова возвращается в исходное состояние.[1]

Таким образом, основной период смены ключа в этой структуре составляет до 4,25 года.[2] Очевидно, что основной ключ должен измениться намного быстрее, чем этот период в криптосистемах.[1]

Но в любом случае расчеты показывают, что если основные ключи изменяются с интервалами в четыре года, мы не будем беспокоиться о создании повторяющихся сеансовых ключей. В алгоритме PALS LFSR длиной 32 бита используется для генерации ключа сообщения, функция обратной связи которого является следующим примитивным полиномом:[1]

C(x)=x^32+x^29+x^24+x^23+x^21+x^19+x^17+x^16+x^14+x^13+x^11+x^9+x^6+x^3+1

Генератор ключей сеанса

Функция скремблирования должна быть спроектирована так, чтобы воздействовать на все биты ключа сообщения на главном ключе для генерации ключа сеанса. При фиксированном главном ключе изменение битов ключа каждого сообщения должно изменять каждый из битов основного ключа со средней вероятностью 50% (эффект лавины). Эта функция скремблирования создается сетью замещения-перестановки (SPN). Для этого 32-битный ключ сообщения вводится в блок перестановок (P-Box) и получается новая 32-битная последовательность. Результирующие 32 бита делятся на 8 четырехбитных фрагментов, и каждый фрагмент входит в блок замены (S-box4 × 4). Выходы S-блоков объединяются соответственно и создают 32-битную последовательность. Чтобы добиться хорошей диффузии по всем выходным битам путем изменения входных данных, эту операцию необходимо повторить не менее 5 раз. Как показано на рис. 2, эта итерационная функция называется Scram-5.[1]

Поскольку длина основного ключа этого алгоритма составляет 256 бит, нам нужно использовать функцию Scram-5 восемь раз, чтобы получить 256-битную последовательность. Ключ сеанса получается путем побитового XOR, получающегося в результате 256-битной последовательности с основным ключом (рис.3).[1]

Начальный векторный генератор

Длина LFSR, используемых в генераторе потока ключей, составляет 1600 бит. Итак, нам нужна 1600-битная последовательность для их начального состояния. Как показано на рисунке 4, мы использовали LFSR из 256 битов, примитивный многочлен степени 256 и четыре S-блока для генерации начального вектора.[1]

Начальное состояние этого LFSR - это 256-битный сеансовый ключ, который генерирует восемь битов в любые часы. Четыре 8 × 8-битных S-блока встроены в функцию обратной связи LFSR, и один из них выбран и используется для соответствующей диффузии ввода-вывода.[1]

Содержимое ступеней 128 и 129 используется для выбора одного из S-блоков ( последовательность 00 выберет первый S-блок, 01 второй S-блок, 10 третий S-блок и 11 четвертый S-блок). После генерации 320 бит (40 тактов) диффузия достигается с доверительной вероятностью 95%. Поэтому необходимо отбросить первые 320-бит, а следующие 1600-бит используются в качестве начального состояния генератора потока ключей.[1]

Как инициализировать генератор потока ключей

Чтобы инициализировать восемь LFSR, используемых в генераторе потока ключей PALS, первые 165 битов сеансового ключа делятся на 163 трехбитных набора следующим образом:

{1,2,3}, {2,3,4}, {3,4,5}, ..., {163,164,165}. Каждый набор представляет собой десятичное число от 0 до 7 и указывает один из 8 LFSR. Например, если первый набор равен 5, то первый бит начального вектора должен быть помещен в первую ступень шестого LFSR. Аналогично, 163 бита исходного вектора заменяются в восьми LFSR. Затем оставшиеся 1437 бит начального вектора заменяются на пустых этапах LFSR соответственно. Эта процедура используется только для первого ключа сообщения в начале связи. Если ключ сообщения должен отправляться повторно при отправке сообщения, для синхронизации между получателем и передатчиком, для ключей следующего сообщения начальный вектор XOR для содержимого каждого LFSR от 1 до 8 соответственно. Так как в алгоритме Deb et al. [5], биты основного ключа непосредственно формируют начальное состояние LFSR, необходимая сложность не достигается, и криптоаналитики могут получить взаимосвязь между битами ввода и вывода. Другими словами, начальные местоположения битов ясны в выходной последовательности.[1]

Возможные применения

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

Достоинства PALS

Основным преимуществом предлагаемого алгоритма является высокая безопасность.[1] PALS устойчив к различным типам атак.[2]




См. также


Примечания

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Design of a New Stream Cipher: PALS.
  2. ↑ 1 2 3 S. Smys, Robert Bestak, Álvaro Rocha. Inventive Computation Technologies. — Springer Nature, 2019-11-02. — 949 с. — ISBN 978-3-030-33846-6.
  3. ↑ 1 2 D. Gollmann, W. G. Chambers. Clock-controlled shift registers: a review (англ.) // IEEE Journal on Selected Areas in Communications. — Vol. 7, iss. 4. — P. 525–533. — ISSN 0733-8716.
  4. ↑ 1 2 3 Schneier, B. Applied Cryptography: Protocols, Algorithms and Source Code in C 2nd (1996).
  5. ↑ 1 2 3 J. K. Mandal, Goutam Saha, Debdatta Kandar, Arnab Kumar Maji. Proceedings of the International Conference on Computing and Communication Systems: I3CS 2016, NEHU, Shillong, India. — Springer, 2018-03-29. — 818 с. — ISBN 978-981-10-6890-4.
  6. ↑ Asad Khan, Amir Khan, Fauzan Mirza. Transform Domain Analysis of Sequences. — 2015-03-03.
  7. ↑ Jovan Dj. Golić. Correlation properties of a general binary combiner with memory (англ.) // Journal of Cryptology. — 1996-03-01. — Vol. 9, iss. 2. — P. 111–126. — ISSN 1432-1378. — doi:10.1007/BF00190805.
  8. ↑ 1 2 Menezes A., Van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press. (1997).
  9. ↑ J.D. Golic. Towards Fast Correlation Attacks on Irregularly Clocked Shift Registers (1995).
  10. ↑ Jovan Dj. Golić, Luke O'Connor. Embedding and probabilistic correlation attacks on clock-controlled shift registers (англ.) // Advances in Cryptology — EUROCRYPT'94 / Alfredo De Santis. — Berlin, Heidelberg: Springer, 1995. — P. 230–243. — ISBN 978-3-540-44717-7. — doi:10.1007/BFb0053439.
  11. ↑ 1 2 Hadia M. S. El Hennawy, Alaa E. A. Omar, Salah M. A. Kholaif. LEA: Link Encryption Algorithm Proposed Stream Cipher Algorithm (англ.) // Ain Shams Engineering Journal. — 2015-03-01. — Vol. 6, iss. 1. — P. 57–65. — ISSN 2090-4479. — doi:10.1016/j.asej.2014.08.001.

Литература

Ссылки


[[:Категория:]]


en:

Источник — https://ru.wikipedia.org/w/index.php?title=PALS&oldid=104734946