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

Размещено на http://www.allbest.ru/

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

1. Элементы криптографии. Классические шифрующие алгоритмы: шифры Полибия, Цезаря, Виженера

Криптограмфия -- наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) иаутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации.

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

Шифр Полибия

Шаг 1: Формирование таблицы шифрования

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

Шаг 2: Принцип шифрования

Для шифрования на квадрате находили букву текста и вставляли в шифровку нижнюю от неё в том же столбце. Если буква была в нижней строке, то брали верхнюю из того же столбца.

Шифр Цезаря

Шифр Цезаря, также известный, как шифр сдвига, код Цезаря или сдвиг Цезаря -- один из самых простых и наиболее широко известных методов шифрования.

Шифр Цезаря -- это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом 3 А была бы заменена на Г, Б станет Д, и так далее.

Шифр Виженера

Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет вид:

ATTACKATDAWN

Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

LEMONLEMONLE

Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.

Исходный текст: ATTACKATDAWN

Ключ: LEMONLEMONLE

Зашифрованный текст: LXFOPVEFRNHR

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

2. Кольца вычетов. Выделение мультипликативной группы кольца вычетов

Множество всех чисел сравнимых с a по модулю n называется классом вычетов a по модулю n, и обычно обозначается или . Таким образом, сравнение равносильно равенству классов вычетов .

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

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

Относительно этих операций множество является конечным кольцом, а для простого n -- конечным полем.

Приведённая система вычетов по модулю m -- множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из ц(m) чисел, где ц(·) -- функция Эйлера. Любые ц(m) попарно несравнимых по модулю m и взаимно простых с этим модулем чисел представляют собой приведенную систему вычетов.[1] В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m-1. Если (a,m)=1 и x пробегает приведенную систему вычетов по модулю m, то ax также принимает значения, образующие приведенную систему вычетов по этому модулю.[1]

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

3. Понятие группы. Свойства групп. Порядок элемента группы. Подгруппы. Фактор-группа

Грумппа в математике -- множество элементов с определённой на нём ассоциативной бинарной операцией, унарной операцией взятия обратного элемента и выделенным нейтральным элементом, связанное некоторыми естественными свойствами -- групповыми аксиомами[?].

Свойства групп:

· Обратный к данному элемент всегда определяется однозначно.

(a?1)?1 = a, aman = am+n, (am)n = amn.

(ab)?1 = b?1a?1.

· Верны законы сокращения:

,

.

· Обратный элемент к нейтральному есть сам нейтральный элемент.

· Группа содержит единственное решение x любого уравнения x · c = b или c · x = b; то есть в группе возможны однозначно определённые правое и левое «деление».

· Пересечение двух подгрупп группы G есть подгруппа группы G.

Порядок элемента g конечной группы G -- минимальное натуральное число m такое, что . Порядок определён для каждого элемента конечной группы.

Подгруппа Ї подмножество группы , само являющееся группой относительно операции, определяющей .

Подмножество группы является её подгруппой тогда и только тогда, когда:

1. содержит единичный элемент из

2. содержит произведение любых двух элементов из ,

3. содержит вместе со всяким своим элементом обратный к нему элемент .

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

Факторгруппа -- конструкция, дающая новую группу (факторгруппу) по группе и её нормальной подгруппе.

Факторгруппа группы по нормальной подгруппе обычно обозначается .

4. Свойства колец и полей. Мультипликативная группа кольца

Кольцом - алгебраическая структура, обобщающая свойства чисел в аспекте операций сложения и умножения.

Непосредственно из аксиом кольца можно вывести следующие свойства:

· Нейтральный элемент относительно сложения в кольце единственен. Для любого элемента кольца обратный к нему по сложению элемент единственен.

· , то есть 0 -- поглощающий элемент по умножению.

· , где -- элемент, обратный к по сложению.

·

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

· Характеристика поля всегда или простое число.

· Поле характеристики содержит подполе, изоморфное полю рациональных чисел .

· Поле простой характеристики содержит подполе, изоморфное полю вычетов .

· Количество элементов в конечном поле всегда равно -- степени простого числа.

· При этом для любого числа вида существует единственное (с точностью до изоморфизма) поле из элементов, обычно обозначаемое .

· В поле нет делителей нуля.

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

Приведённая система вычетов по модулю m -- множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из ц(m) чисел, где ц(·) -- функция Эйлера. Любые ц(m) попарно несравнимых по модулю m и взаимно простых с этим модулем чисел представляют собой приведенную систему вычетов.[1] В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m-1. Если (a,m)=1 и x пробегает приведенную систему вычетов по модулю m, то ax также принимает значения, образующие приведенную систему вычетов по этому модулю.[1]

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

5. Биективные функции. Однонаправленные функции

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

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

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

6. Аддитивные и мультипликативные группы. Циклические группы. Порядок циклической группы

Аддитивность (лат. additivus -- прибавляемый) -- свойство величин, состоящее в том, что значение величины, соответствующее целому объекту, равно сумме значений величин, соответствующих его частям, в некотором классе возможных разбиений объекта на части.

Аддитивная группа кольца - группа, образуемая всеми элементами данного кольца относительно операции сложения в кольце.

Мультипликативная группа поля -- это группа, содержащая все ненулевые элементы из , и операция в ней совпадает с операцией умножения в .

Группа называется циклической, если она может быть порождена одним элементом a, то есть все её элементы являются степенями a (или, если использовать аддитивную терминологию, представимы в виде na, где n -- целое число). Математическое обозначение: .

Порядок группы: Для элемента -- минимальное натуральное число такое, что . В случае, если такого не существует, считается, что имеет бесконечный порядок.

7. Представление кольца вычетов в виде прямой суммы

Пусть числа -- попарно взаимно простые, и

Тогда система

имеет единственное решение среди чисел , и это решение может быть представлено в одном из следующих видов:
1. либо

и обозначающем число, обратное числу относительно умножения по модулю :

2. либо

и числах последовательно определяемых из сравнений

8. Задача логарифмирования в конечном поле как математически трудная задача

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

.	(1)

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

Чаще всего рассматривается случай, когда , то есть группа является циклической, порождённой элементом . В этом случае уравнение всегда имеет решение. В случае же произвольной группы вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.

В произвольном конечном поле

Задача рассматривается в поле GF(q), где , -- простое.

1. Алгоритм исчисления индексов (index-calculus) эффективен, если невелико. В этом случае он имеет эвристическую оценку сложности .

2. Алгоритм Эль-Гамаля, появившийся в 1985 году, применим при и имеет сложность арифметических операций.

3. Алгоритм Копперсмита дискретного логарифмирования в конечном поле характеристики 2 стал первым субэкспоненциальным алгоритмом дискретного логарифмирования с константой в оценке сложности. Данный алгоритм появился в 1984 году -- до изобретения решета числового поля.

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

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

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

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

10. Регистр сдвига и линейные рекуррентные последовательности

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

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

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

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

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

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

Линейной рекуррентной последовательностью (линейной рекуррентной) называется всякая числовая последовательность , задаваемая линейным рекуррентным соотношением:

для всех

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

Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.

11. Симметричные и асимметричные шифрующие алгоритмы. Блочные и поточные шифры

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

Простая перестановка

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

Одиночная перестановка по ключу

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

Двойная перестановка

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

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

Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 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. Частотный анализ шифрованных текстов

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

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

Размещено на Allbest.ru

...