El mensaje cifrado, M, se cifra según M — m e (mód. «). El algoritmo presupone que el mensaje original m se obtiene por m = M d = (me)d (mód. n). Verificar esta igualdad equivale a demostrar la validez de RSA . Para ello se combinan el teorema de Fermat y el teorema de Euler. Considérense dos casos: 1) Si m cd (m,n) = 1 por el teorema de Euler m = 1 (mód. rí). Partimos de la relación la cual es equivalente ze -d — l = 0 (mód. (p(n)),es decir, existe un valor k, entero, de manera que e-d — 1 = fe • (p(n), es decir, e-d — í = k- (p(n) + 1. C on ello tenem os, aplicando el teorema de Euler, la igualdad: (me Y — m ei - ■ m = (m’*’*”) )k ■ m = P • m (mód. n) = m (mód. n). Es decir, el resultado que se buscaba. 2) Si m cd (m, n) ¿ 1, com o que n = p -q ,m contendrá com o factor únicamente a p, únicamente a q, o a ambos a la vez. En el primer caso, a) m será múltiplo de p , es decir, existe un entero r de manera que m = r-p. C on lo cual se tiene que y en consecuencia mde = 0 (mód.p), y finalmente: m* = m (mód. p), es decir, existe un valor A de manera que: mie —m — A p . (1) En el segundo caso, b) se tiene que (mey = med = mk(n)+1 = ■ m = ■ m = = ( m ^ -m (mód. n) = m. C om o m cd (w ,n )= p eí m cá(m ,q) — í y por el teorema de Fermat rn ^ 'i = 1 (mód. q). Aplicado a la igualdad de partida: (meY = m ed = • m = (m^('> )k ■ m = = (^jíí-i) -m (mód. n) = — m (mód. q), con lo que se determina que existe un valor B de manera que m* - m = B