Генераторы на основе линейных регистров сдвига (фильтрующие, комбинирующие, с неравномерным движением).

⇐ ПредыдущаяСтр 50 из 69Следующая ⇒

Все генераторы выдают последовательности некоторого вида:

Линейный регистр сдвига (ЛРС)

– начальные члены последовательности.

– преобразование регистра сдвига с обратной связью (Линейное преобразование)

Набор чисел: называется i-ым состоянием регистра сдвига.

Функция – булева функция обратной связи.

– точки съема регистра (номера ячеек, с которых производится съем). j – точка съема ↔ a_j_-1=1

С крайней ячейки всегда есть съём, иначе часть регистра не используется => a₀=1

– максимальный период.

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

Для того, чтобы ЛРС имел максимальный период, необходимо чтобы был примитивен, т.е. неприводим; (делит без остатка); (не делит без остатка), где

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

Строятся на основе ЛРС и некоторой функции усложнения – n-местная функция. Нет смысла брать линейную функцию j, т.к. суперпозиция линейных функций есть линейная функция. Следовательно, необходимо брать функцию, имеющую высокую степень нелинейности. Если , то . Так если K = 2, то линейная сложность будет иметь порядок »n²- немногим лучше, чем n.

- все эти функции имеют степень нелинейности меньше, чем K

Проблема: сохранить период последовательности, так как он может сократиться.

Линейная сложность последовательности – минимальная длина ЛРС (линейного регистра сдвига), который способен сгенерировать данную последовательность.

Для последовательности длины N максимальная линейная сложность N-1.

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

Есть несколько различных регистров, выходные последовательности этих регистров поступают на некоторую объединяющую функцию усложнения. Если длина регистров равна n₁, n₂, …n_y, то линейная сложность последовательности .

Фильтрующие и комбинирующие генераторы относятся к схемам с равномерным движением регистра (все регистры сдвигаются ровно на один знак каждый такт работы).

Схемы с неравномерным движением регистров. Генераторы «стоп-вперед»

Схема работы выглядит следующим образом. Первый регистр движется равномерно (1 знак за 1 шаг). Если знак равен 0, то регистр 2 не движется и выдает тот знак, который у него был до этого. Если же знак равен 1, то регистр 2 сдвигается (отрабатывает) 1 такт и на выходе выдается значение функции обратной связи

«0» - оставляем, что было.

«1» - прокручиваем новое.

- суммарное число продвижений.

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

Слабости: По выходной последовательности можно судить о входе.

5. Криптография с открытым ключом. Предпосылки появления. Однонаправленные и однонаправленные функции с секретом и их применение. Схемы шифрования с открытым ключом и цифровой подписи. Основные принципы. Схемы шифрования и подписи RSA и Рабина. Схемы открытого шифрования Эль Гамаля. Сравнение криптосистем с открытым и секретным ключом. Новые схемы шифрования.

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

Каждый из корреспондентов системы обладает ключом , состоящим из открытого ключа и секретного ключа . Открытый ключ определяет правило зашифрования , а секретный ключ — правило расшифрования . Эти правила связаны соотношением для любого открытого текста М и любого шифрованного текста С. Знание открытого ключа не позволяет за приемлемое время (или с приемлемой сложностью) определить секретный ключ.

Обозначим правила зашифрования и расшифрования (на выбранном ключе k) произвольного корреспондента A символами и соответственно. Корреспондент В, желая послать конфиденциальное сообщение М корреспонденту А, получает копию , вычисляет шифротекст , который направляет по каналу связи корреспонденту А. Получив сообщение С, корреспондент А применяет к нему преобразование D_A, получая открытый текст .

Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL, в SSH.

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

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

В качестве примера однонаправленной функции рассмотрим широко известную функцию дискретного возведения в степень: , где – целое число от 1 до включительно, а вычисление производится по модулю , где – очень большое простое число; – целое число ( .

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

Применение. Одним из первых применений однонаправленных функций было решение задачи обеспечения безопасности и использования пароля, по которому осуществляется доступ пользователя к ресурсам и услугам в автоматизированных системах. Открытое значение вместе с именем пользователя может быть помещено в список паролей доступа, хранящихся в ЭВМ. Законный пользователь для получения доступа в автоматизированную систему предъявляет свое число . ЭВМ вычисляет по этому числу значение однонаправленной функции и сравнивает с хранящимся значением . При совпадении этих значений пользователь становится идентифицированным и получает требуемый доступ. Использовать односторонние функции для шифрования сообщений с целью их защиты не имеет смысла, так как обратно расшифровать зашифрованное сообщение уже не получится. Для целей шифрования используются специальные односторонние функции – односторонние функции с секретом

Однонаправленные функции с секретом. Однонаправленная функция с секретом - это особый тип однонаправленной функции, с секретной лазейкой. Ее легко вычислить в одном направлении и трудно - в обратном. Но если вам известен секрет, вы можете легко рассчитать и обратную функцию. То есть, легко вычислить f(x) по заданному x, но трудно по известному f(x)вычислить x. Однако существует небольшая секретная информация y, позволяющая, при знании f(x) и y, легко вычислить x.

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

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

На основе однонаправленной функции с секретом строятся: криптосистема открытого распространения ключей Диффи-Хэллмана, криптосистема шифрования и криптосистема цифровой подписи сообщений Эль-Гамаля, криптосистема цифровой подписи сообщений Шнорра, криптосистема шифрования и криптосистема цифровой подписи сообщений RSA, криптосистема цифровой подписи сообщений Рабина, класс ранцевых систем шифрования информации Меркля-Хэллмана, класс систем шифрования информации Мак-Эллиса.

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

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

Пусть, например, пользователь А хочет отправить пользователю Б подписанное сообщение. Процедура создания и проверки подписи состоит из следующих шагов:

1. Пользователь А посылает пользователю Б свой открытый ключ U по любому каналу связи, например, по электронной почте.

2. Пользователь А шифрует сообщение М своим закрытым ключом R и получает зашифрованное сообщение С.

3. Зашифрованное сообщение пересылается пользователю Б.

4. Пользователь Б расшифровывает полученное сообщение С, используя открытый ключ пользователя А. Если сообщение расшифровалось, значит, оно подписано пользователем А.

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

ЭП, вычисленные по хеш-коду документа, представляют собой некоторый числовой код, который необходимо пристыковывать к подписываемому документу. Само сообщение при этом не шифруется и передается в открытом виде вместе с электронной подписью отправителя.

Если пользователь А хочет отправить пользователю Б сообщение М, дополненное присоединенной электронной подписью, то процедура создания и проверки подписи должна состоять из следующих шагов:

1. Пользователь А посылает пользователю Б свой открытый ключ U по любому каналу связи.

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

3. Затем пользователь А шифрует хеш-код сообщения h своим закрытым ключом R и получает электронную подпись С.

4. Исходное сообщение М вместе с электронной подписью С пересылаются пользователю Б.

5. Пользователь Б вычисляет хеш-код h полученного сообщения М, а затем проверяет электронную подпись С, используя открытый ключ пользователя А.

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

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

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

Алгоритм RSA работает следующим образом: берутся два достаточно больших простых числа p и q и вычисляется их произведение n = p*q. Затем выбирается число e, удовлетворяющее условию 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1). Затем вычисляется число d таким образом, что (e*d)mod (p - 1)*(q – 1)=1. (n; e) – открытый ключ, (n; d). – секретный ключ.

Если бы существовали эффективные методы разложения на сомножители, то, разложив n на сомножители p и q, можно было бы получить секретный ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой – практически неразрешимой – задаче разложения n на сомножители, так как в настоящее время эффективного способа поиска сомножителей не существует.

Шифрование

Предположим, А хочет послать Б сообщение M. А создает зашифрованный текст С, возводя сообщение M в степень e и умножая на модуль n: C = M^е (mod n), где e и n – открытый ключ Б. Затем А посылает С (зашифрованный текст) Б. Чтобы расшифровать полученный текст, Б возводит полученный зашифрованный текст C в степень d и умножает на модуль n: M = С^d(mod n); зависимость между e и d гарантирует, что Б вычислит M верно. Так как только Б знает d, то только он имеет возможность расшифровать полученное сообщение.

Электронная подпись

Предположим, А хочет послать Б сообщение M, причем таким образом, чтобы Б был уверен, что сообщение не было взломано и что автором сообщения действительно является А. А создает электронную подпись S возводя M в степень d и умножая на модуль n: S = M^d (mod n), где d и n – частный ключ А. A посылает M и S Б.

Чтобы проверить подпись, Б возводит S в степень e и умножает на модуль n: M = S^e( mod n), где e и n – открытый ключ.

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

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

Генерация ключей

1.Выбираются два случайных больших простых числа p и q, которые удовлетворяют условию . Такой специальный вид простых чисел сильно ускоряет процедуру извлечения корней по модулю р и q.

2.Вычисляется . n - открытый ключ. Числа p и q - закрытый ключ.

Шифрование

Для шифрования используется открытый ключ n. Для шифрования сообщения m нужно вычислить: - зашифрованное сообщение.

Для расшифровки нужен закрытый ключ - числа p и q. Процесс выглядит следующим образом:

1.Сначала, используя алгоритм Эвклида, из уравнения находим числа и .

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

Один из этих корней r, -r, s, -s является истинным открытым текстом m.

Электронная подпись

Схема ЭП Рабина основана на сложности вычисления квадратных корней по модулю n, представляющему собой произведение двух больших простых чисел p и q. Секретным ключом является пара чисел p и q.

Форматирование открытого ключа n осуществляется путем перемножения чисел p и q. n=pq.

Вычисление подписи S к сообщению , где включает следующие шаги:

1. Генерируется случайная последовательность , где , которая объединяется с сообщением: .

Последовательности битов сопоставляется число а< n. Проверяется выполнение условий и . Если одно из соотношений не выполняется, то генерируется новое случайное число R, и процедура повторяется до тех пор, пока не будет найдено такое значение а, для которого оба условия выполняются, т. е. получено а, являющееся квадратичным вычетом по mod n.

2. Вычисляются значения .

3. По китайской теореме об остатках вычисляется квадратный корень .

4. В качестве подписи к М берется пара чисел (R, Z).

Проверка подлинности подписи осуществляется следующим образом:

1. Вычисляется значение а':

2. Сравниваются значения а = и а', если а = а', то подпись признается подлинной.

Для схемы Рабина доказано, что ее стойкость эквивалентна сложности задачи разложения модуля. Эта схема обладает свойством восстановления сообщения, причем при проверке подписи одновременно проверяется и подлинность сообщения за счет того, что к подписи присоединяется число R, добавленное к сообщению.

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

Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < Р. Числа Р и G могут быть распространены среди группы пользователей.

Затем выбирают случайное целое число X, причем 1< Х< Р. Число Х является секретным ключом и должно храниться в секрете.

Далее вычисляют Y = G^X mod P. Открытым ключом является тройка (P, G, Y).

Для того чтобы зашифровать сообщение М, выбирают случайное целое число К, 1< К< Р-1, такое, что числа К и (Р-1) являются взаимно простыми.

Затем вычисляют числа a=G^KmodP, b = Y^K М mod P.

Пара чисел (а, b) является шифротекстом. Заметим, что длина шифротекста вдвое больше длины исходного открытого текста М.

Для того чтобы расшифровать шифротекст (а, b), вычисляют М = ba^X^-1mod Р. Для практических вычислений больше подходит следующая формула: М = b*a^p^-1-^Xmod Р.

ГОСТ Р34.10-1994, принятый в 1994 году в РФ, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа.

Шифр Эль-Гамаля на эллиптической кривой.

Любую систему, основанную на дискретном логарифмировании, легко можно перенести на эллиптические кривые. Основной принцип построения таких криптосистем состоит в замене операции Y = G^X mod P на y=[X]G mod P. Отличие состоит в том, что Y – это число, а y – точка, и таким образом, требуется переходить от точки к числу.

Для пользователей выбираются общая эллиптическая кривая Ер(a, b) и точка G на ней такие, что G, [2]G, [3]G, ..., [n]G суть разные точки и [q]G = О для некоторого простого числа q.

Каждый пользователь сети выбирает число k, 0 < k < q, которое хранит как свой секретный ключ, и вычисляет точку на кривой D = [k]G, которая будет его открытым ключом. Параметры кривой и список открытых ключей передаются всем пользователям сети.

Допустим, пользователь А хочет передать сообщение пользователю В. Будем считать, что сообщение представлено в виде числа m < р. Пользователь А выполняет следующие действия:

1. выбирает случайное число r, 0 < r < q;

2. вычисляет R = [r]G, Р = [r]D_B = (х, у);

3. шифрует С = mх mod р;

4. посылает пользователю В шифротекст (R, С).

Пользователь В, после получения (R, С) выполняет следующие действия:

1. вычисляет Q = k_BR = (х, у);

2. дешифрует М' = С*x^–1 mod р.

Т.к. Q = [k_B]R = [k_B] ([r]G) = [r] ([k_B]G) = [r]D_B = P, поэтому M=M'. Координата x точки Q остается секретной для злоумышленника, так как он не знает числа r. Злоумышленник может попытаться вычислить r из точки Р, но для этого ему нужно решить проблему дискретного логарифмирования на кривой, что считается невозможным. Наиболее вероятно использование рассмотренного алгоритма для передачи в качестве числа М секретного ключа для блочного или поточного шифра. В этом случае разумно выбирать параметры кривой так, чтобы log q примерно вдвое превышал длину ключа шифра.

⇐ Предыдущая 45 46 47 48 495051 52 53 54 Следующая ⇒