Шрифт:
d•е = 1 по модулю ф(n).
Зашифрованное послание М шифруется следующим образом: М = mе (mod n).
Алгоритм подразумевает, что исходное сообщение m может быть получено как m = Md = (me)d (mod n). Проверка этого уравнения как раз и демонстрирует работу алгоритма RSA. Мы воспользуемся теоремой Ферма и функцией Эйлера.
Рассмотрим два случая.
1. Если (m, n) = 1, то с функцией Эйлера имеем: mф(n) 1 (mod n).
Начнем с того, что d•е = 1 по модулю ф(n) эквивалентно соотношению е•d — 1 = 0 (mod ф(n)) то есть существует целое значение k, такое, что е•d — 1 = k•ф(n) или е•d = k•ф(n) + 1. Используя это и формулу Эйлера, получим:
(me)d = med = m kф(n)+1= m kф(n)•m = (m ф(n))k•m
Это и есть нужный нам результат.
2. Если НОД (m,n)
Пусть m содержит только множитель р. Тогда, во-первых, m кратно р, то есть существует целое число r, такое, что m = rр. Поэтому mde
mde — m = Ар. (1)
Во-вторых, мы имеем:
(me)d = med = mk ф(n)+1 = m k ф(n)•m = (mф(n))k•m = (m(q-1))k(p-1)•m.
Так как НОД (m, n) = р, НОД (m, q) = 1, то по теореме Ферма m(q-1)
Подставим это в предыдущее выражение.
(me)d = med = mk ф(n)+1 = m k ф(n)•m = (mф(n))k•m = (m(q-1))k(p-1)•m
Откуда мы заключаем, что существует значение В, такое что:
mde — m = Вq. (2)
Из (1) и (2) следует, что разность (mde — m) делится на n = рq, поэтому
mde — m
Аналогично это доказывается для случая, когда m содержит только множитель q.
В случае, когда m кратно и р, и q одновременно, результат тривиален. Следовательно,
(mе)d
Таким образом, мы продемонстрировали математическую основу алгоритма RSA.
Список литературы
Fernandez, S., Classical Cryptography. Sigma Review No. 24, April 2004.
Garfunkel, S., Mathematics in Daily Life, Madrid, COMAP, Addison-Wesley, UAM, 1998.
Gomez, J., From the Teaching to the Practice of Mathematics Barcelona, Paidos, 2002.