Создание ключей алгоритма RSA

RSA-ключи генерируются следующим образом:

1. Выбираются два различных случайных простых числа p и q
2. Вычисляется их произведение n = pq.
3. Вычисляется значение функции Эйлера от числа n:

φ(n) = (p − 1)(q − 1).

1. Выбирается целое число e (1 < e < φ(n)), взаимно простое со значением функции φ(n).
2. Вычисляется число d, мультипликативно обратное к числу e по модулю φ(n), то есть число, удовлетворяющее условию:

или: de = 1 + kφ(n), где k — некоторое целое число.

Примечание: Можно вычислять и так (e*d) mod ((p-1)*(q-1)) = 1. Результат операции i mod j — остаток от целочисленного деления i на j, то есть если имеем (d*3) mod 20 = 1. Значит d будет, например 7. (Может быть и другим, например 27).

1. Пара e, n публикуется в качестве открытого ключа RSA
2. Пара d, n играет роль секретного ключа RSA.

Провести шифрование своих инициалов алгоритмом RSA

Рассчитываем ключ RSA:

Берем два простых числа p и q, к примеру 7 и 11, n = 7*11=77, φ(n) = (p − 1)(q − 1)= (7 − 1)(11 − 1)=60; e=49 (49 не имеет общих делителей с 60=φ(n) и меньше него);

(e*d) mod ((p-1)*(q-1)) = 1;

(49*d) mod (60) = 1;

d=49, так как 49*49 mod 60 = 1;

e,n=49,77 – открытый ключ; d,n=49,77 закрытый ключ.

Шифро-текс: ДМ, Д=5 М=14, согласно порядковому номеру в алфавите. Зашифруем отрытым ключом e,n=49,77, получим:

C1=(5^49)mod 77=75;

C2=(14^49)mod 77=70;

Дешифровка происходит закрытым ключом d,n=49,77:

М1=(75^49)mod 77=5;

М2=(70^49)mod 77=14;

Таким образом 5,14 соответствует шифр 75,70.

18. Определение и требования хеш-функции

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

Хэш-код создается функцией Н:
h = H (M)
Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.

Хэш-функция Н, которая используется для аутентификации сообщений, должна обладать следующими свойствами:

1. Хэш-функция Н должна применяться к блоку данных любой длины.
2. Хэш-функция Н создает выход фиксированной длины.
3. Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М.
4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h.
5. Для любого данного х вычислительно невозможно найти y x, что H (y) = H (x).
6. Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x).

 

Простые хеш-функции

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

Одним из простейших примеров хэш-функции является побитовый XOR каждого блока:

Где

Сi - i-ый бит хэш-кода, 1 <= i <= n.

k - число n-битных блоков входа.

bij - i-ый бит в j-ом блоке.

- операция XOR.

В результате получается хэш-код длины n, известный как продольный избыточный контроль. Это эффективно при случайных сбоях для проверки целостности данных.

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

• Установить n-битный хэш-код в ноль.
• Для каждого n-битного блока данных выполнить следующие операции:
• сдвинуть циклически текущий хэш-код влево на один бит;
• выполнить операцию XOR для очередного блока и хэш-кода.

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

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

Хотя простого XOR или ротационного XOR (RXOR) недостаточно, если целостность обеспечивается только зашифрованным хэш-кодом, а само сообщение не шифруется, подобная простая функция может использоваться, когда все сообщение и присоединенный к нему хэш-код шифруются. Но и в этом случае следует помнить о том, что подобная хэш-функция не может проследить за тем, чтобы при передаче последовательность блоков не изменилась. Это происходит в силу того, что данная хэш-функция определяется следующим образом: для сообщения, состоящего из последовательности 64-битных блоков Х₁, Х₂,..., Х_N, определяется хэш-код С как поблочный XOR всех блоков, который присоединяется в качестве последнего блока:

Затем все сообщение шифруется, включая хэш-код, в режиме СВС для создания зашифрованных блоков Y₁, Y₂,..., Y_N+1. По определению СВС имеем:

Но X_N+1 является хэш-кодом:

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

Первоначальный стандарт, предложенный NIST, использовал простой XOR, который применялся к 64-битным блокам сообщения, затем все сообщение шифровалось, используя режим СВС.