¿Por qué funciona el cifrado RSA? Para el método de criptografía RSA, la fórmula M = Cd mod pq se supone produce el texto plano mensaje original, M...

¿Por qué funciona el cifrado RSA? Para el método de criptografía RSA, la fórmula M = Cd mod pq se supone produce el texto plano mensaje original, M, cuando el mensaje cifrado es C. ¿Cómo puede estar seguro de que no siempre es así? Recuerde que requerimos que M pq y sabemos que C M e mod pq. Así, por sustitución, Cd mod pq = (Me mod pq)d mod pq. Por teorema 8.4.3(4), (Me mod pq)d ≡ Med (mod pq). Así C d mod pq M ed (mod pq) y así es suficiente para demostrar que M M ed (mod pq). Recuerde que d se eligió como un inverso positivo para módulo e, (p ฀ 1)(q ฀ 1), que existe ya que MCD(e, (p ฀ 1)(q ฀ 1)) 1. En otras palabras, ed 1 (mod (p ฀ 1)(q ฀ 1)), o, equivalentemente, ed 1 k(p ฀ 1)(q ฀ 1) para algún entero positivo k. Por tanto, Med = M1+k(p−1)(q−1) = M(M p−1)k(q−1) = M(Mq−1)k(p−1) Si p ∤ M, entonces por el pequeño teorema de Fermat, M p ฀ 1 1 (mod p) y así Med = M(M p−1)k(q−1) ≡ M(1)k(q−1) (mod p) = M (mod p). Similarmente, si q ∤ M, entonces por el pequeño teorema de Fermat, M q ฀ 1 1 (mod q) y así Med = M(Mq−1)k(p−1) ≡ M(1)k(p−1) = M (mod q). Así, si M es primo relativo a pq, M ed M (mod p) y M ed M (mod q). Si M no es primo relativo a pq, entonces ya sea p M o q M. Sin perder generalidad, suponga que p M. Se deduce que M ed 0 M (mod p). Además, ya que M pq, q M y así, como anteriormente, M ed M (mod q). Por tanto, en este caso también, M ed M (mod p) y M ed M (mod q). Por el teorema 8.4.1, p (M ed ฀ M) y q (M ed ฀ M), y, por definición de divisibilidad, M ed ฀ M pt para algún entero t. Por sustitución, q pt, y puesto que q y p son números primos distintos, aplicando el lema de Euclides se obtiene q t. Así t qu para algún entero u por definición de divisibilidad. Por sustitución, M ฀ M ed pt p(qu) (pq)u, donde u es un entero y así, pq (M ฀ M ed) por definición de divisibilidad. Así M ฀ M ed 0 (mod pq) por definición de congruencia, o, equivalentemente, M M ed (mod pq). Ya que M pq, esta última congruencia imp