PALS: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
КоноВл (обсуждение | вклад) Нет описания правки |
КоноВл (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''PALS''' — [[потоковый шифр]], спроектирован как управляемый часами с новым механизмом изменения шагов, основанным на теории систем таким образом, что используемые в нём структуры устойчивы к обычным атакам. Алгоритм PALS использует основной ключ длиной 256 бит и 32-битный ключ сообщения. Наиболее важными критериями, учитываемыми при разработке PALS, являются устойчивость к известным атакам, максимальный период, высокая линейная сложность и хорошие статистические свойства. В результате выходной поток ключей очень похож на совершенно случайные последовательности и устойчив к обычным атакам, таким как корреляционные атаки, алгебраическая атака, атака «разделяй и властвуй», атака компромисса времени и памяти и атаки AIDA/ куба.<ref name=":0">{{Cite web|url=https://arxiv.org/pdf/1807.01115.pdf|title=Design of a New Stream Cipher: PALS|author=Mohammadreza Ashouri|website=|date=2018|publisher=}}</ref> |
'''PALS''' — [[потоковый шифр]], спроектирован как управляемый часами с новым механизмом изменения шагов, основанным на теории систем таким образом, что используемые в нём структуры устойчивы к обычным атакам. Алгоритм PALS использует основной ключ длиной 256 бит и 32-битный ключ сообщения. Наиболее важными критериями, учитываемыми при разработке PALS, являются устойчивость к известным атакам, максимальный период, высокая линейная сложность и хорошие статистические свойства. В результате выходной поток ключей очень похож на совершенно случайные последовательности и устойчив к обычным атакам, таким как [[корреляционные атаки]], [[XSL-атака|алгебраическая атака]], [[атака «разделяй и властвуй»]], [[атака компромисса времени и памяти]] и [[атаки AIDA/ куба]].<ref name=":0">{{Cite web|url=https://arxiv.org/pdf/1807.01115.pdf|title=Design of a New Stream Cipher: PALS|author=Mohammadreza Ashouri|website=|date=2018|publisher=}}</ref> |
||
Базовая структура PALS представляет собой комбинированный генератор с памятью, управляемый часами.<ref name=":0" /> |
Базовая структура PALS представляет собой комбинированный генератор с памятью, управляемый часами.<ref name=":0" /> |
||
| Строка 27: | Строка 27: | ||
=== Генераторы с часовым управлением === |
=== Генераторы с часовым управлением === |
||
Некоторые генераторы имеют РСЛОС с разной частотой; иногда тактирование одного генератора зависит от мощности другого. Все они являются электронными версиями машинных шифров до Второй мировой войны и называются генераторами с часовым управлением<ref name=":2" />. Управление тактовыми импульсами может иметь прямую связь, когда выход одного РСЛОС контролирует тактирование другого, или обратную связь, где выход одного РСЛОС контролирует свое собственное тактирование. Хотя эти генераторы, по крайней мере теоретически, подвержены встраиванию и вероятностным атакам корреляции, многие имеют защиту.<ref>{{Cite web|url=https://link.springer.com/content/pdf/10.1007/3-540-49264-X_20.pdf|title=Towards Fast Correlation Attacks on Irregularly Clocked Shift Registers|author=J.D. Golic|website=|date=1995|publisher=}}</ref><ref>{{Статья|ссылка=https://link.springer.com/chapter/10.1007/BFb0053439|автор=Jovan Dj. Golić, Luke O'Connor|заглавие=Embedding and probabilistic correlation attacks on clock-controlled shift registers|год=1995|ответственный=Alfredo De Santis|язык=en|место=Berlin, Heidelberg|издание=Advances in Cryptology — EUROCRYPT'94|издательство=Springer|страницы=230–243|isbn=978-3-540-44717-7|doi=10.1007/BFb0053439}}</ref> Ян Касселлс, когда-то возглавлявший чистую математику в Кембридже и бывший криптоаналитик Блетчли Парк, сказал, что "криптография — это смесь математики и путаницы и без путаницы математика может быть использована против вас ". Он имел в виду, что в потоковых шифрах вам нужна какая-то математическая структура, такая как РСЛОС, для обеспечения максимальной длины и других свойств, а затем некоторая сложная нелинейная путаница, чтобы не дать кому-то получить доступ к регистру и решить его.<ref name=":3" /> |
Некоторые генераторы имеют РСЛОС с разной частотой; иногда тактирование одного генератора зависит от мощности другого. Все они являются электронными версиями машинных шифров до [[Вторая мировая война|Второй мировой войны]] и называются [[Генераторам с часовым управлением|генераторами с часовым управлением]]<ref name=":2" />. Управление тактовыми импульсами может иметь прямую связь, когда выход одного РСЛОС контролирует тактирование другого, или обратную связь, где выход одного РСЛОС контролирует свое собственное тактирование. Хотя эти генераторы, по крайней мере теоретически, подвержены встраиванию и вероятностным атакам корреляции, многие имеют защиту.<ref>{{Cite web|url=https://link.springer.com/content/pdf/10.1007/3-540-49264-X_20.pdf|title=Towards Fast Correlation Attacks on Irregularly Clocked Shift Registers|author=J.D. Golic|website=|date=1995|publisher=}}</ref><ref>{{Статья|ссылка=https://link.springer.com/chapter/10.1007/BFb0053439|автор=Jovan Dj. Golić, Luke O'Connor|заглавие=Embedding and probabilistic correlation attacks on clock-controlled shift registers|год=1995|ответственный=Alfredo De Santis|язык=en|место=Berlin, Heidelberg|издание=Advances in Cryptology — EUROCRYPT'94|издательство=Springer|страницы=230–243|isbn=978-3-540-44717-7|doi=10.1007/BFb0053439}}</ref> Ян Касселлс, когда-то возглавлявший чистую математику в Кембридже и бывший криптоаналитик Блетчли Парк, сказал, что "криптография — это смесь математики и путаницы и без путаницы математика может быть использована против вас ". Он имел в виду, что в потоковых шифрах вам нужна какая-то математическая структура, такая как РСЛОС, для обеспечения максимальной длины и других свойств, а затем некоторая сложная нелинейная путаница, чтобы не дать кому-то получить доступ к регистру и решить его.<ref name=":3" /> |
||
В генераторах нелинейных комбинаций и генераторах нелинейных фильтров компоненты РСЛОС регулярно синхронизируются; то есть перемещение данных во всех РСЛОС контролируется одним и тем же тактом. Основная идея генераторов, управляемых синхронизацией, состоит в том, чтобы ввести нелинейность в генераторы потока ключей на основе РСЛОС, имея выход одного РСЛОС, управляющий тактированием (то есть пошагово) второго РСЛОС. Поскольку второй РСЛОС синхронизируется нерегулярно, надежда состоит в том, что атаки, основанные на регулярном движении РСЛОС, могут быть сорваны.<ref name=":5" /> |
В генераторах нелинейных комбинаций и генераторах нелинейных фильтров компоненты РСЛОС регулярно синхронизируются; то есть перемещение данных во всех РСЛОС контролируется одним и тем же тактом. Основная идея генераторов, управляемых синхронизацией, состоит в том, чтобы ввести нелинейность в генераторы потока ключей на основе РСЛОС, имея выход одного РСЛОС, управляющий тактированием (то есть пошагово) второго РСЛОС. Поскольку второй РСЛОС синхронизируется нерегулярно, надежда состоит в том, что атаки, основанные на регулярном движении РСЛОС, могут быть сорваны.<ref name=":5" /> |
||
Версия от 17:04, 1 февраля 2020
PALS — потоковый шифр, спроектирован как управляемый часами с новым механизмом изменения шагов, основанным на теории систем таким образом, что используемые в нём структуры устойчивы к обычным атакам. Алгоритм PALS использует основной ключ длиной 256 бит и 32-битный ключ сообщения. Наиболее важными критериями, учитываемыми при разработке PALS, являются устойчивость к известным атакам, максимальный период, высокая линейная сложность и хорошие статистические свойства. В результате выходной поток ключей очень похож на совершенно случайные последовательности и устойчив к обычным атакам, таким как корреляционные атаки, алгебраическая атака, атака «разделяй и властвуй», атака компромисса времени и памяти и атаки AIDA/ куба.[1]
Базовая структура PALS представляет собой комбинированный генератор с памятью, управляемый часами.[1]
Введение
Для построения бесконечной псевдослучайной последовательности с использованием случайной последовательности конечной длины, был предложен новый потоковый шифр PALS, разработанный как комбинированный генератор с управлением по часам с памятью. Начальный вектор из 1600 битов генерируется путем объединения 256-битного главного ключа с ключом сообщения. Регистр сдвига с линейной обратной связью(РСЛОС) длиной 32 бита используется для генерации ключа сообщения. Для получения 256-битной последовательности 32-битный ключ сообщения подвергался функции scram-5 восемь раз. Ключ сеанса получается путем побитового XOR, получающегося в результате 256-битной последовательности с основным ключом. Основной период смены ключа в этой структуре составляет до 4,25 года. Генерация ключевого потока в алгоритме PALS основана на теории систем и полных случайных последовательностях.[2]
Алгоритмы потокового шифрования часто необходимы для приложений с высокой скоростью передачи данных, а алгоритмы, использующие сдвиговые регистры, могут быть использованы в быстрых реализациях. Регистры сдвига с линейной обратной связью максимальной длины обеспечивают последовательности с длинными периодами и хорошими статистическими свойствами, но не могут использоваться напрямую, поскольку их линейность делает их подверженными атакам с использованием алгебраических методов.[3]
Потоковые шифры работают с изменяющимся во времени преобразованием отдельных цифр открытого текста.[4]
Потоковые шифры на основе регистров сдвига с линейной обратной связью
Основное использование РСЛОС в потоковом шифре — это создание псевдослучайной последовательности. Известно, что РСЛОС может генерировать бесконечный поток битов. В наиболее распространенной форме для построения потокового шифра используются несколько РСЛОС. Но РСЛОС проявляет линейное свойство. Таким образом, понятие нелинейности было введено для преодоления недостатка линейного свойства путем нерегулярного изменения тактовой частоты РСЛОС.[5]
Потоковый шифр на основе РСЛОС использует в основном три класса генераторов псевдослучайных чисел, а именно нелинейную комбинацию, нелинейный фильтр и генераторы с управлением по часам. Почти все потоковые шифры на основе РСЛОС следуют любым из этих нелинейных методов или используют комбинацию этих методов с некоторыми дополнительными усилиями, такими как добавление счетчика или комбинации различных РСЛОС со сдвиговыми регистрами с нелинейной обратной связью.[5]
РСЛОС широко использовались для генерации последовательности из-за их встроенной рекурсивной структуры, более быстрых реализаций и хорошо изученного поведения в разнообразных приложениях связи, теории кодирования и криптологии. В криптографических алгоритмах линейная повторяемость РСЛОС модифицируется нелинейным фильтрованием для достижения более высоких линейных сложностей и хороших статистических свойств. Некоторые из классических схем включают генераторы фильтров, комбинированные генераторы, генераторы с управляемыми часами и термоусадочные генераторы.[6]
Регистры сдвига с линейной обратной связью (РСЛОС) в двоичных генераторах ключей для криптографических приложений обычно объединяются функциями без памяти. Такие структуры уязвимы для атак корреляции «разделяй и властвуй», основанных на поэтапной корреляции между последовательностью потока ключей и набором последовательностей РСЛОС.[7]
Разрушение линейности
Одним из общих методов разрушения линейности, присущей РСЛОС, является использование нескольких РСЛОС параллельно. Поток ключей генерируется как нелинейная функция от выходных данных РСЛОС. Такие генераторы потока ключей называются нелинейными комбинированными генераторами, и их называют объединяющей функцией. Функция должна удовлетворять нескольким критериям, чтобы противостоять определённым конкретным криптографическим атакам.[8]
Генератор потока ключей
Основной подход к проектированию генератора потока ключей с использованием РСЛОС прост. Сначала вы выбираете один или несколько РСЛОС, как правило, различной длины и с различными полиномами обратной связи. (Если длины все относительно простые, а полиномы обратной связи все примитивные, весь генератор имеет максимальную длину). Ключ — это начальное состояние РСЛОС. Каждый раз, когда вы хотите получить бит, сдвиньте РСЛОС один раз (это иногда называется синхронизацией). Выходной бит является функцией, предпочтительно нелинейной, некоторых битов РСЛОС. Эта функция называется функцией объединения, а весь генератор называется генератором комбинации. (Если выходной бит является функцией одного РСЛОС, генератор называется генератором фильтров.) Большая часть теоретической основы для такого рода вещей была заложена Селмером и Нилом Цирлером.[4]
Генераторы с часовым управлением
Некоторые генераторы имеют РСЛОС с разной частотой; иногда тактирование одного генератора зависит от мощности другого. Все они являются электронными версиями машинных шифров до Второй мировой войны и называются генераторами с часовым управлением[3]. Управление тактовыми импульсами может иметь прямую связь, когда выход одного РСЛОС контролирует тактирование другого, или обратную связь, где выход одного РСЛОС контролирует свое собственное тактирование. Хотя эти генераторы, по крайней мере теоретически, подвержены встраиванию и вероятностным атакам корреляции, многие имеют защиту.[9][10] Ян Касселлс, когда-то возглавлявший чистую математику в Кембридже и бывший криптоаналитик Блетчли Парк, сказал, что "криптография — это смесь математики и путаницы и без путаницы математика может быть использована против вас ". Он имел в виду, что в потоковых шифрах вам нужна какая-то математическая структура, такая как РСЛОС, для обеспечения максимальной длины и других свойств, а затем некоторая сложная нелинейная путаница, чтобы не дать кому-то получить доступ к регистру и решить его.[4]
В генераторах нелинейных комбинаций и генераторах нелинейных фильтров компоненты РСЛОС регулярно синхронизируются; то есть перемещение данных во всех РСЛОС контролируется одним и тем же тактом. Основная идея генераторов, управляемых синхронизацией, состоит в том, чтобы ввести нелинейность в генераторы потока ключей на основе РСЛОС, имея выход одного РСЛОС, управляющий тактированием (то есть пошагово) второго РСЛОС. Поскольку второй РСЛОС синхронизируется нерегулярно, надежда состоит в том, что атаки, основанные на регулярном движении РСЛОС, могут быть сорваны.[8]
Преимущества потоковых шифров
Потоковый шифр является важной категорией симметричных алгоритмов шифрования; Более того, синхронные потоковые шифры не страдают от распространения ошибок, потому что каждый бит независимо шифруется / дешифруется от любого другого. По сравнению с блочными шифрами большинство потоковых шифров намного быстрее и имеют большую эффективность программного обеспечения. Благодаря этим функциям потоковые шифры имеют преимущества при выборе протоколов связи, особенно используемых в беспроводной области.[11]
Регистры сдвига с линейной обратной связью (РСЛОС) довольно эффективны в аппаратном обеспечении и являются основными строительными блоками этого шифра.[11]
Описание алгоритма PALS
Управление ключами
Основная цель PALS — построить бесконечную (вычислительную) псевдослучайную последовательность, используя случайную последовательность конечной длины. Поскольку длина основного ключа алгоритма шифрования составляет 256 бит и намного короче его исходного состояния (1600 бит), этот ключ должен быть расширен соответствующим способом для получения начального вектора. Нам также необходимо использовать новый ключ для шифрования каждого сообщения, но мы не можем изменить основной ключ для каждого сообщения. Учитывая эти ограничения, необходимо разработать алгоритм генерации ключа, который генерирует начальный вектор путем объединения основного ключа системы и ключа, называемого ключом сообщения.[1]
Каждое новое сообщение шифруется одним и тем же ключом.[1]
Для этого генерируется сеансовый ключ с ключом сообщения и основным ключом длиной 256 бит. Затем сеансовый ключ расширяется до 1600 бит (начальный вектор). Блок-схема начальной генерации вектора показана на рис. 1.[1]
Генератор ключей сообщений
Ключ сообщения должен быть сгенерирован таким образом, чтобы он не повторялся в течение периода смены основного ключа. Если мы предположим, что этот алгоритм должен использоваться 24 часа в сутки без перерыва, и каждую секунду требуется 32-битный ключ сообщения, то через 4,25 года генерируется и используется полный период ключа сообщения, и он снова возвращается в исходное состояние.[1]
Таким образом, основной период смены ключа в этой структуре составляет до 4,25 года.[2] Очевидно, что основной ключ должен измениться намного быстрее, чем этот период в криптосистемах.[1]
Но в любом случае расчеты показывают, что если основные ключи изменяются с интервалами в четыре года, мы не будем беспокоиться о создании повторяющихся сеансовых ключей. В алгоритме PALS РСЛОС длиной 32 бита используется для генерации ключа сообщения, функция обратной связи которого является следующим примитивным полиномом:[1]
C(x)=x32+x29+x24+x23+x21+x19+x17+x16+x14+x13+x11+x9+x6+x3+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]
Начальный векторный генератор
Длина РСЛОС, используемых в генераторе потока ключей, составляет 1600 бит. Итак, нам нужна 1600-битная последовательность для их начального состояния. Как показано на рисунке 4, мы использовали РСЛОС из 256 битов, примитивный многочлен степени 256 и четыре S-блока для генерации начального вектора.[1]
Начальное состояние этого РСЛОС — это 256-битный сеансовый ключ, который генерирует восемь битов в любые часы. Четыре 8 × 8-битных S-блока встроены в функцию обратной связи РСЛОС, и один из них выбран и используется для соответствующей диффузии ввода-вывода.[1]
Содержимое ступеней 128 и 129 используется для выбора одного из S-блоков (последовательность 00 выберет первый S-блок, 01 второй S-блок, 10 третий S-блок и 11 четвёртый S-блок). После генерации 320 бит (40 тактов) диффузия достигается с доверительной вероятностью 95 %. Поэтому необходимо отбросить первые 320-бит, а следующие 1600-бит используются в качестве начального состояния генератора потока ключей.[1]
Как инициализировать генератор потока ключей
Чтобы инициализировать восемь РСЛОС, используемых в генераторе потока ключей PALS, первые 165 битов сеансового ключа делятся на 163 трехбитных набора следующим образом:
{1,2,3}, {2,3,4}, {3,4,5}, …, {163,164,165}. Каждый набор представляет собой десятичное число от 0 до 7 и указывает один из 8 РСЛОС. Например, если первый набор равен 5, то первый бит начального вектора должен быть помещен в первую ступень шестого РСЛОС. Аналогично, 163 бита исходного вектора заменяются в восьми РСЛОС. Затем оставшиеся 1437 бит начального вектора заменяются на пустых этапах РСЛОС соответственно. Эта процедура используется только для первого ключа сообщения в начале связи. Если ключ сообщения должен отправляться повторно при отправке сообщения, для синхронизации между получателем и передатчиком, для ключей следующего сообщения начальный вектор XOR для содержимого каждого РСЛОС от 1 до 8 соответственно. Так как в алгоритме Deb et al.[5], биты основного ключа непосредственно формируют начальное состояние РСЛОС, необходимая сложность не достигается, и криптоаналитики могут получить взаимосвязь между битами ввода и вывода. Другими словами, начальные местоположения битов ясны в выходной последовательности.[1]
Возможные применения
PALS может использоваться во многих приложениях, особенно в финансовой криптографии, благодаря соответствующим функциям безопасности.[1]
Достоинства PALS
Основным преимуществом предлагаемого алгоритма является высокая безопасность.[1] PALS устойчив к различным типам атак.[2]
При разработке PALS основными критериями должны стать устойчивость к известным атакам, максимальный период, высокая линейная сложность и хорошие статистические свойства. Поток ключей PALS подобен совершенно случайным последовательностям и устойчив к обычным атакам, таким как алгебраическая атака, атака компромисса времени и памяти, атака «разделяй и властвуй», различающая атака, AIDA / куб атаки и различные типы корреляционных атак.[1]
Примечания
- ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Mohammadreza Ashouri. Design of a New Stream Cipher: PALS (2018).
- ↑ 1 2 3 S. Smys, Robert Bestak, Álvaro Rocha. Inventive Computation Technologies. — Springer Nature, 2019-11-02. — 949 с. — ISBN 978-3-030-33846-6.
- ↑ 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.
- ↑ 1 2 3 Schneier, B. Applied Cryptography: Protocols, Algorithms and Source Code in C 2nd (1996).
- ↑ 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.
- ↑ Asad Khan, Amir Khan, Fauzan Mirza. Transform Domain Analysis of Sequences. — 2015-03-03.
- ↑ 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.
- ↑ 1 2 Menezes A., Van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press. (1997).
- ↑ J.D. Golic. Towards Fast Correlation Attacks on Irregularly Clocked Shift Registers (1995).
- ↑ 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.
- ↑ 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.
 | Статья является кандидатом в добротные статьи с 1 февраля 2020. |