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

Цифровая подпись на базе RSA
Доброго времени суток, возник вопрос по данной тематике. Для создание цифровой подписи требуется посчитать пару ключей: открытый и закрытый. Для этого требуется найти:
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 М)? Честно говоря никогда не встречался с таким условием. Если кто знает, то подскажите и если не сложно приведите пример выполнения данного условия.

  • Число 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(В);

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

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

    Если два числа 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.

    Источник: http://easymath.com.ua/show_material.php?subp=div&type=theory