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


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



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

Шаг 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. содержит вместе со всяким своим элементом обратный к нему элемент .

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

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

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


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


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

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



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

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

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



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

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

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

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

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

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

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

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

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

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




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


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

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



В качестве примера однонаправленной функции рассмотрим широко известную функцию дискретного возведения в степень: , где – целое число от 1 до включительно, а вычисление производится по модулю , где – очень большое простое число; – целое число ( ).
6. Аддитивные и мультипликативные группы. Циклические группы. Порядок циклической группы
Аддитивность (лат. additivus — прибавляемый) — свойство величин, состоящее в том, что значение величины, соответствующее целому объекту, равно сумме значений величин, соответствующих его частям, в некотором классе возможных разбиений объекта на части.

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

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

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

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

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


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

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

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

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

2. либо

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


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


.

(1)

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

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


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

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




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

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