Цифровая подпись на базе RSA

Question

Цифровая подпись на базе RSA

Роман Черевко Знаток (253), закрыт 11 лет назад

Доброго времени суток, возник вопрос по данной тематике. Для создание цифровой подписи требуется посчитать пару ключей: открытый и закрытый. Для этого требуется найти:
1. P - которое мы генерируем и оно простое большое число
2. Q - как и P генерируем
3. N = P * Q.
4. M = (P - 1) * (Q - 1).
5. D - генерируем такое чтобы оно было взаимно простым с M.
6. E - которое выбираем по условию DE = 1 (MOD М).

Так вот вопрос: Что означает DE = 1 (mod М)? Честно говоря никогда не встречался с таким условием. Если кто знает, то подскажите и если не сложно приведите пример выполнения данного условия.

Answer 1

Число d, мультипликативно обратное к числу e по модулю M
Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
проще говоря, DE = 1 (mod М) означает, что остаток от деления DE на М должен быть равен 1

Следующий пример наглядно демонстрирует алгоритм шифрования RSA:
Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты возьмем небольшие числа - это сократит наши расчеты.
Выберем p=3 and q=11.
Определим n= 3*11=33.
Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).
Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2, С=3.
Теперь зашифруем сообщение, используя открытый ключ {7,33}
C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;
Теперь расшифруем данные, используя закрытый ключ {3,33}.
M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

Данные расшифрованы!

Answer 2

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

Answer 3

Все просто.

Если два числа a и b (a, b ∈ Z) при делении на число m (m ∈ N) дают один и тот же остаток r, где 0 <= r < m, то числа a и b называются сравнимыми по модулю m.

Сравнимость чисел a и b по модулю m принято записывать так:
a = b(mod m), и читать: a сравнимо с b по модулю m.