Доказательство

Чтобы доказать, что рашифрованное сообщение совпадает с изначальным нам нужно доказать, что:

$(m^e \pmod n)^d \pmod n = m$

или так как $m$ < $n$

$(m^e \pmod n)^d ≡ m \pmod n$

Воспользуемся свойством умножения по модулю:

$m^{e·d} ≡ m \pmod n$

В тоже время $e$, $d$ связаны тождеством $e·d ≡ 1 \pmod \phi$, значит:

$e·d = 1 + k·φ$, где $k$ - целое

$e·d = 1 + k·(p - 1)·(q - 1)$

Тогда,

$m^{1 + k·(p - 1)·(q - 1)} ≡ m \pmod n$ или

$m^{1 + k·(p - 1)·(q - 1)} ≡ m \pmod {p·q}$

Чтобы это доказать, рассмотрим сперва следующие выражения:

$m^{1 + k·(p - 1)·(q - 1)} ≡ m \pmod p$

$m^{1 + k·(p - 1)·(q - 1)} ≡ m \pmod q$

Слегка преобразуем их

$m·m^{(p - 1) \cdot k·(q - 1)} ≡ m \pmod p$

$m·(mq - 1)k·(p - 1) ≡ m \pmod q$

Опять воспользуемся свойством умножения по модулю:

$m·(mp - 1 \pmod p)k·(q - 1) ≡ m \pmod p$ $m·(mq - 1 \pmod q)k·(p - 1) ≡ m \pmod q$

p, q - простые числа по условию задачи. Согласно малой теореме Ферма:

mp - 1 ≡ 1 mod p mq - 1 ≡ 1 mod q

Следовательно:

m·1k·(q - 1) ≡ m mod p m·1k·(p - 1) ≡ m mod q

Сократим

m ≡ m mod p m ≡ m mod q