Математические основы криптологии


Перестановка «Магический квадрат»



Скачать 298,92 Kb.
страница7/7
Дата26.03.2020
Размер298,92 Kb.
#143647
1   2   3   4   5   6   7
Связанные:
Математические основы криптологии

Перестановка «Магический квадрат»


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

Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифровки сообщения используется закрытый ключ.[1]Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

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



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

Блочный шифр — разновидность симметричного шифра [1] , оперирующего группами бит фиксированной длины — блоками, характерный размер которых меняется в пределах 64 — 256 бит. Если исходный текст (или его остаток) меньше размера блока, перед шифрованием его дополняют. Фактически, блочный шифр представляет собой подстановку на алфавите блоков, которая, как следствие, может быть моно- или полиалфавитной. [2] Блочный шифр является важной компонентой многих криптографических протоколов и широко используется для защиты данных, передаваемых по сети.

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

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

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

Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом: .

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




12. Гаммирование. Псевдослучайные последовательности
Гамми́рование — симметричный метод шифрования, основанный на «наложении» гамма-последовательности (случайной числовой последовательности, используемой для зашифровывания и расшифровывания данных) на открытый текст. Обычно это суммирование в каком-либо конечном поле, например в поле GF(2) такое суммирование принимает вид обычного «исключающего ИЛИ».

Псевдослуча́йная после́довательность (ПСП) — последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.

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

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданномураспределению (обычно равномерному).

13. Системы шифрования с открытым ключом


Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифровки сообщения используется закрытый ключ.[1]

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

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

Процедуры шифрования и дешифрования выполняются по следующим формулам
C = Тe mod n,

Т = Cd mod n.


где Т, C - числовые эквиваленты символов открытого и шифрованного сообщения.
14. Шифры гаммирования
Гамми́рование — симметричный метод шифрования, основанный на «наложении» гамма-последовательности (случайной числовой последовательности, используемой для зашифровывания и расшифровывания данных) на открытый текст. Обычно это суммирование в каком-либо конечном поле, например в поле GF(2) такое суммирование принимает вид обычного «исключающего ИЛИ».

В аддитивных шифрах символы исходного сообщения заменяются числами, которые складываются по модулю с числами гаммы. Ключом шифра является гамма, символы которой последовательно повторяются. Шифр с бесконечной случайной гаммой, например, «одноразовый блокнот» является криптографически абсолютно стойким.

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

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

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

Метод сложения по модулю . Перед шифрованием символы сообщения заменяются их номерами в алфавите. Основание модуля определяет количество символов в используемом алфавите. Шифрование выполняется по формуле


,
при этом полученный -й символ остаётся -м, а не нулевым. Затем выполняется замена полученных чисел на буквы шифрограммы. Дешифрирование выполняется по формуле
,
где – это символы исходного сообщения, – символы зашифрованного сообщения, – символы гаммы.
15. Использование регистров сдвига для получения псевдослучайных последовательностей
Регистр сдвига с линейной обратной связью (РСЛОС, англ. Linear feedback shift register, LFSR) — регистр сдвига битовых слов, у которого входной (вдвигаемый) бит является линейной булевой функцией состояния остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами и применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии.

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

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

Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как ) и наиболее часто применяется в таких регистрах.

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

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

В течение каждого такта времени выполняются следующие операции:


  • содержимое ячейки формирует очередной бит выходной последовательности битов;

  • новое содержимое ячейки определяется битом обратной связи, являющегося значением функции обратной связи (обычно сложение по модулю ) с определёнными коэффициентами (принимающими значение 0 и 1) битов ячеек ;

  • содержимое -й ячейки перемещается в ячейку для любого ;

  • содержимое -й ячейки принимает значение вычисленного бита.



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

Таким образом, в качестве функции обратной связи берётся логическая операция XOR (исключающее ИЛИ), то есть:



  • на первом шаге:

  • на втором шаге:



  • на -м шаге: , причём некоторые коэффициенты (но не все, иначе вырожденный случай) равны 0.

16. Понятие о псевдослучайных последовательностях. Использование псевдослучайных последовательностей при гаммировании


Псевдослуча́йная после́довательность (ПСП) — последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.

Под гаммированием понимают процесс наложения по определенному закону гаммы шифра на открытые данные. Гамма шифра - это псевдослучайная последовательность, выработанная по заданному алгоритму для зашифрования открытых данных и расшифрования зашифрованных данных.
17. Однонаправленные функции. Асимметричное шифрование
Односторонняя функция (англ. one-way function, OWF) это функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.

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

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

Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифровки сообщения используется закрытый ключ.

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

Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой , что зная и , можно вычислить .
18. Регистры сдвига и линейные рекуррентные последовательности
См. вопрос №10.
19. Группы подстановок. Циклы. Знакопеременная и знакопостоянная группы
Множество всех перестановок множества X (то есть биекций X →X) с операцией композиции образуют группу, которая называется симметрической группой или группой перестановок X.

Обычно обозначается S(X). Если X = {1, 2,…, n}, то S(X) обозначается через Sn.

Нейтральным элементом в симметрической группе является тождественная перестановка id, определяемая как тождественное отображение: id(x) = x.

Циклом длины называется такая подстановка которая тождественна на всём множестве кроме подмножества и Обозначается . Число перестановок, содержащих k циклов, - есть числа Стирлинга первого рода



Знакопеременной группой подстановок степени n (обозн. ) называется подгруппа симметрической группы степени , содержащая только чётные перестановки.

  • Индекс подгруппы знакопеременной группы в симметрической равен 2:

  • Знакопеременная группа является нормальной подгруппой симметрической группы (следует из предыдущего утверждения).

  • Порядок знакопеременной группы равен:

  • Знакопеременная группа является коммутантом симметрической группы:

  • Знакопеременная группа разрешима тогда и только тогда, когда её порядок не больше 4. Точнее, - четверной группе Клейна, а при .

20. Модулярная арифметика. Таблицы Кэли. Возведение в степень в модулярной арифметике


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






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

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

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

Вычисление степени числа а по модулю n


а х mod n
можно выполнить как ряд умножений и делений. Существует способ сделать это быстрее. Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более).

{ Пример. Нужно вычислить а 8 mod n.

Не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(а • а • а • а • а • а • а • а) mod n.


Вместо этого выполняют три малых умножения и три малых приведения по модулю:
((а 2 mod n.)2 mod n.)2 mod n.
Тем же способом вычисляют
а 16 mod n. = (((а 2 mod n.)2 mod n.)2 mod n.)2 mod n. }
Вычисление
а х mod n,
где х не является срепенью 2, лишь немного сложнее. Двоичная запись числа х позволяет представить число х как сумму степеней 2:
х = 12 (10) = 11001 (2).

Поэтому 25 = 2 4 + 2 3 + 2 0.

Тогда а 25 mod n. = (а • а 24) mod n. = (а • а 8 • а 16) mod n =

= (а • ((а 2) 2) 2 • (((а 2) 2) 2 ) 2) mod n = ((((а 2 • а) 2) 2 ) 2 • а) mod n.

При накоплении промежуточных результатов потребуется только шесть умножений:
(((((((а 2 mod n) • а) mod n)2 mod n)2 mod n)2 mod n) • а) mod n.
Этот метод уменьшает трудоемкость вычислений до 1,5хk операций в стреднем, где k – длина числа в битах.

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


21. Основная теорема арифметики. Простые и составные числа. Наибольший общий делитель и наименьшее общее кратное

Основна́я теоре́ма арифме́тики утверждает:

Каждое натуральное число можно представить в виде , где — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

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

Наибольшим общим делителем (НОД) для двух целых чисел и называется наибольший из их общих делителей.[1] Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел или не ноль.

Алгоритм Евклида.

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть















Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.

Наиме́ньшее о́бщее кра́тное (НОК, lcm) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка.

Если известен наибольший общий делитель, можно использовать его связь с НОК:



22. Определение простоты большого числа. Вероятностный алгоритм Миллера-Рабина

Общие тесты простоты


  • Перебор делителей

  • Теорема Вильсона

  • Тест Ферма (основан на малой теореме Ферма)

  • Тест Миллера

  • Тест Миллера — Рабина, вероятностный тест, широко применяемый на практике

  • Тест Соловея — Штрассена

  • Тест простоты Люка

  • Тест Агравала — Каяла — Саксены (Тест AKS), первый полиномиальный детерминированный тест простоты

  • Тест BPSW (англ.), вероятностный тест

  • ECPP (англ.), Elliptic curve primality proving - детерминированный тест

  • APRT+CL (англ.), - детерминированный тест простоты Адлемана-Померанса-Румели, усовершенствованный Коэном (англ.) и Ленстрой.

Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.

Пусть — нечётное число большее 1. Число однозначно представляется в виде , где нечётно. Целое число , , называется свидетелем простоты числа , если выполняется одно из условий:



или существует целое число , , такое, что

Теорема Рабина утверждает, что составное нечётное число имеет не более различных свидетелей простоты, где — функция Эйлера.

Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины , где m — проверяемое число.

Для данного m находятся такие целое число s и целое нечётное число t, что . Выбирается случайное число a, 1 < a < m. Если a не является свидетелем простоты числа m, то выдается ответ «m — составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. После нахождения r свидетелей простоты, выдается ответ «m — вероятно простое», и алгоритм завершается.

Алгоритм может быть записан на псевдокоде следующим образом:

Ввод: m > 2, нечётное натуральное число, которое необходимо проверить на простоту;

r — количество раундов.

Вывод: составное, означает, что m является составным числом;

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

Представить m − 1 в виде 2s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2.

цикл А: повторить r раз:

Выбрать случайное целое число a в отрезке [2, m − 2]

x ← at mod m, вычисляется с помощью алгоритма возведения в степень по модулю (англ.)

если x = 1 или x = m − 1, то перейти на следующую итерацию цикла А

цикл B: повторить s − 1 раз

x ← x2 mod m

если x = 1, то вернуть составное

если x = m − 1, то перейти на следующую итерацию цикла A

вернуть составное

вернуть вероятно простое

Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа m, то вероятность того, что m составное, не превосходит .

23. Понятие функции. Отображения. Биективные функции. Однонаправленные функции


Функция (отображение, оператор, преобразование) — математическое понятие, отражающее связь между элементами множеств. Можно сказать, что функция — это «закон», по которому каждому элементу одного множества (называемого областью определения) ставится в соответствие некоторый элемент другого множества (называемого областью значений).

Отображение - закон, по которому каждому элементу некоторого заданного множества X ставится в соответствие вполне определенный элемент другого заданного множества Y (при этом X может совпадать с Y)



Биекция — это отображение, которое является одновременно и сюръективным, и инъективным. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением(соответствием), одно-однозначным отображением. Однонаправленной называется такая функция , для которой легко определить значение функции , но практически невозможно отыскать для заданного такое , что .

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


24. Алгоритм Евклида
См. вопрос №21

25. Частотный анализ шифрованных текстов


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

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




Скачать 298,92 Kb.

Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7




База данных защищена авторским правом ©psihdocs.ru 2022
обратиться к администрации

    Главная страница