Autor Tema: RSA No es Magia  (Leído 159 veces)

Phicar

  • :P
  • Administrador
  • Mensajes: 283
  • (1+sqrt(5))/2
    • MSN Messenger - diego_villahacker@hotmail.com
    • Ver Perfil
    • Phicar's Blog
    • Email
RSA No es Magia
« : agosto 14, 2010, 05:15:49 pm »
Acabo de salir de clase de certificacion y pos escribi esto porque la verdad esa mierda es muy aburrida xDDDDDDDDDDDD

Bueno pa los que vieron mi post de RSA en el foro de Cripto o les importa un culo y conocen el algoritmo pero ni puta idea de el por que esa vaina funciona pos home les traje el recuerdo y la sorpresa ;)

pa empezar definamos concepticos

la funcion totient euler relaciona un numero y la cantidad de coprimos desde 1 hasta el numero antecedente del numero en funcion...Sabiendo pues que un numero a es coprimo con b si su

GCD(a,b)=1...osease no hay comunes divisores entre a y b ;)

resulta que un par de matematicos fermat y euler hicieron uno un teorema y el otro la generalizacion de el teorema..

Fermat inicio con un teorema asi

Sea a un numero natural cualquiera y o un numero primo ap mod p = a Siempre y pues usando la aritmetica modular se tiene lo siguiente(demostrado por induccion por Euler)

ap-1 mod p = 1

ahora euler viendo el teorema de Fermat y demostrandolo Uso solo la notacion de su funcion (PHI)

donde phi(n)= (n es primo)?n-1:mult((p-1)/p); para todo p divisor primo de n....

siendo que en el teorema de fermat p era primo entonces tenemos que p-1 era la famosa funcion

para lo cual

aPhi(p) mod p = 1

Ahora pasado esta vaina veamos lo siguiente..si recuerdan RSA tiene dos claves la publica que se compone por (e,n) y la privada que se compone por (d,n)

donde n = pq con pq primos grandes ;)....

ahora. Nosotros calculabamos a e como un numero coprimo a Phi(n) osease que GCD(Phi(n),e)=1..
y calculabamos d como que la multiplicacion de e*d al dividirla por Phi(n) nos diera 1..en otros terminos

ed mod Phi(n) = 1

ahora, nosotros cifrabamos asi

Sea C el numero a cifrar y Z el numero cifrado

Z = Ce mod n
C = Zd mod n
para lo cual teniamos que C = Ced mod n por ley de exponentes en los reales :)...

ahora podemos ver lo siguiente... por la definicion de n podemos cambiar la expresion por

C = Ced mod pq

y podemos cambiar a ed de la siguiente manera...  ed mod Phi(n)=1 -> por definicion de division
sea k un numero natural...
ed = k * Phi(n) +1

tenemos
C = Ck * Phi(n) +1 mod pq   ; pero por definicion de Phi(n) tenemos
C = Ck * (p-1)(q-1) +1 mod pq ; Pero arreglando la vaina con propiedades de los reales, tenemos
C = C(p-1)k*(q-1) * C1 mod pq  ; por propiedades distribuyo el modulo en los factores..

C = C(p-1)k*(q-1) mod pq  * C mod pq

sabemos pro congruencia que M no es 0 por modulo p para lo cual

C = C(p-1)k*(q-1) mod p  * C

pero por teorema de fermat sabemos que eso es 1 por lo cual

C = 1k*(q-1) mod p  * C

para lo cual C = C  QED...

;)...

Los dejo....nada es magia y esperen AES ;)...jejejeje
:)

my.opera.com/phicar