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

Шаг 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.
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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