Hola, yo he leido varios textos de RSA y siempre he entendido todos; pero hay varias cosas que en todos se obvia y no entiendo porque.
n = p.q (p y q primos)
Es sabido que si tengo un numero m y lo elevo a e (llave publica) y despues lo elevo a d (llave privada), ese numero en mod p.q es el numero m original.
Entonces yo se que (m^e)^d = m mod n, pero en todos los textos dicen que para cifrar y decifrar hacen lo siguiente... calculan m^e mod(n) y es ese numero el que envian, que luego el destinatario eleva a la d y obtiene el m original en mod(n). Lo que no entiendo que obvian, es ¿porque el que cifro el mensaje, le envia al destinatario m^e mod(n) y no le envia m^e? Porque siempre explican que m^e y luego elevado a la 'd' me hace volver a 'm', pero no explican porque el m^e en mod(n) elevado a 'd' tambien me hace llegar a lo mismo.
Otra duda que tengo es, si todos los primos son conocidos porque todos son publicados, para factorizar el numero 'n' solo tienen que dividir 'n' entre los primos. Ahora, no entiendo porque le dicen imposibilidad de factorizar, si en realidad, solo estamos dividiendo n entre los primos grandes que tampoco son tantos tantos como para que tarde tanto. Lo que supongo (seguro esta mal) es que cada comprobacion de que n sea multiplo de primos grandes (o sea hacer la division) toma demasiado tiempo para cada uno, entonces hacerlo con 1000 por ejemplo llevaria una eternidad. No se si me explico.
Tambien tengo otra duda que seria, porque calcular n a partir de la multiplicacion de dos primos, y no de 5 o 6?, porque si es poco practico factorizar n que es producto de 2 primos grandes, supongo que seria mas dificil hacer lo mismo si n es producto de 5 o 6 primos grandes.
Y todavia no se porque necesariamente tienen que ser p y q primos, ya que phi(p.q) con p y q no necesariamente primos igual se puede calcular y creo que no hay contradicciones en los teoremas que se usan para todas las deducciones de RSA.
Lamento que sean tantas dudas, pero me intriga el tema y siempre en los textos se dan por sentado varias cosas.
gracias
Dos primos y no tres.
OLIM LACUS COLUERAM1 Septiembre 2006 - 4:10pm
Al ser n el producto de dos primos sabemos que uno de ellos es menor o igual que la raiz cuadrada de n.
Si fuese producto de tres sabriamos que al menos uno es menor que la raiz cúbica de tres, con lo que para la misma longitud de n sería más fácil de factorizar, al reducirse el espacio de factores posibles.
Y utilizar más primos sería todavía peor.
Pero en el punto 3, p y q no
rsalearner29 Agosto 2006 - 2:58am
Pero en el punto 3, p y q no necesitan que se cumpla el pequeño teorema de fermat, porque calculamos phi(n) que es la funcion de euler que no necesita que ambos sean primos.
Respecto al punto 2, no se especifica pork es dificil factorizar si por la complejidad en la division de numeros muy grandes, o por la cantidad de divisiones posibles de hacer.. o sea, si son primos grandes, se conocen todos...
respecto al punto 1, es cierto... que inocente. :P
saludos
Voy a intentarlo jeje...
tonilope27 Agosto 2006 - 10:08pm
Te había escrito un "tocho" pero se me borró al pinchar sin querer en un enlace.
Así que voy a resumirlo:
1º No se envía m^e ya que entonces se podría sacar m haciendo la raíz e-ésima de m^e
2º El algoritmo más eficiente conocido para factorizar enteros (General Number Field Sieve) http://en.wikipedia.org/wiki/General_number_field_sieve es todavía lento con los ordenadores actuales.
3º 'p' y 'q' tienen que ser primos porque si no, no cumplirían el Pequeño Teorema de Fermat.
4º Y lo de usar más factores primos para calcular el módulo ahora mismo no lo sé :(
Salu2 ;)