Algoritmo para factorizar RSA.
Publicado por chemary (2 intervenciones) el 27/07/2009 18:44:39
Algoritmo para factorizar RSA:
Hola, buenas tardes.
Antes de exponer el asunto principal quiero decir que no soy un profesional ni de las matemáticas ni de la criptografía, solo un matemático aficionado, y como tal, desde que en los años ochenta en el instituto conocí los números primos he seguido de cerca cualquier investigación al respecto incluida la aplicación de éstos a la criptografía.
Paso a detallar el sistema que he seguido para acotar la búsqueda de la factorización aplicada a los rsa.
- -- --- ----- ------- ----------- ------------- -----------------
Tenemos un número rsa, llamémosle n, que es producto de dos números primos desconocidos p y q. p*q=n con p<q.
Dado que es un prodcuto podemos hallar un número m tal que p<m<q, siendo m la media geométrica de p y q, es decir m=[raíz(n)] (los corchetes indican que el contenido ha de ser un número entero).
Ya tenemos una cota máxima m para empezar la búsqueda, pero sería todavía muy dura esa búsqueda, así que trato de hallar p' y q' tal que: p'<p<m<q<q'.
Para calcular p' y q' hago lo siguiente: r=e^(1/raíz(LN(m)). Y p'=[m/r] y q'=[m*r].
Así tenemos p'<p<m<q<q'.
Buscando sólo los primos entre p' y m hallaremos q, q=n/p.
Aún me queda investigar si esta fórmula es válida para p y q muy distantes entre sí, pero funciona en p' y q' cuando log(pi(m)/(pi(m)-pi(p')))<=3. (log; es el logaritmo decimal). (pi(x) es el contador de primos, pi(x)=x/ln(x).
¿Es una buena aproximación para resolver el problema de la facrorización rsa?.
Hola, buenas tardes.
Antes de exponer el asunto principal quiero decir que no soy un profesional ni de las matemáticas ni de la criptografía, solo un matemático aficionado, y como tal, desde que en los años ochenta en el instituto conocí los números primos he seguido de cerca cualquier investigación al respecto incluida la aplicación de éstos a la criptografía.
Paso a detallar el sistema que he seguido para acotar la búsqueda de la factorización aplicada a los rsa.
- -- --- ----- ------- ----------- ------------- -----------------
Tenemos un número rsa, llamémosle n, que es producto de dos números primos desconocidos p y q. p*q=n con p<q.
Dado que es un prodcuto podemos hallar un número m tal que p<m<q, siendo m la media geométrica de p y q, es decir m=[raíz(n)] (los corchetes indican que el contenido ha de ser un número entero).
Ya tenemos una cota máxima m para empezar la búsqueda, pero sería todavía muy dura esa búsqueda, así que trato de hallar p' y q' tal que: p'<p<m<q<q'.
Para calcular p' y q' hago lo siguiente: r=e^(1/raíz(LN(m)). Y p'=[m/r] y q'=[m*r].
Así tenemos p'<p<m<q<q'.
Buscando sólo los primos entre p' y m hallaremos q, q=n/p.
Aún me queda investigar si esta fórmula es válida para p y q muy distantes entre sí, pero funciona en p' y q' cuando log(pi(m)/(pi(m)-pi(p')))<=3. (log; es el logaritmo decimal). (pi(x) es el contador de primos, pi(x)=x/ln(x).
¿Es una buena aproximación para resolver el problema de la facrorización rsa?.
Valora esta pregunta
0