gndolfo escribió:wabo escribió:Despúes de este lapso, sigamos donde lo dejamos --> hilo_factorizacion-en-numeros-primos-usando-java_1237120_s50#p1716173389
Existe algun motivo por el que en lugar de argumentar sobre la viabilidad del proyecto, nos tapamos los oidos y gritamos? Creo que precisamente la parte mas interesante tiene lugar en los ultimos post (los borrados y los que permanecen), justo cuando todo el mundo deja de darse plamaditas en la espalda, pues pueden ayudar a la gente a comprender el funcionamiento de la encriptacion y por que pierden el tiempo.
No se si hay algun motivo concreto por el que no quieres que la gente se informe / se plantee nada. Pero creo que lo primero que deberian saber todos los colaboradores es lo que se trata de hacer, como se va a hacer y, lo mas importante, porque es no sirve de nada y les va a hacer perder el tiempo. Luego, a partir de ahi, ya cada uno que decida si quiere seguir adelante o no.
En este post se explican bastantes cosas, y en anteriores, si viven, tambien. Luego, bien informado, cada cual es libre de hacer lo que quiera con su tiempo, dinero y maquina.
hilo_factorizacion-en-numeros-primos-usando-java_1237120_s90#p1716173389
![[+risas]](/images/smilies/nuevos/risa_ani3.gif "más risas")
alex-unstable escribió:mellon escribió:alex-unstable escribió:¿Podemos hablar un poco de factorizaciones y encriptación?
¿De que tipo de factorizacion y cifrados quieres hablar?
Salu2
De éstos, por ejemplo. Y de vuestra opinión al respecto sobre la abordabilidad del proyecto, aunque ya sé que como yo, tienes tus dudas. Aunque supongo que los que deberían tomar parte ahora son los que creen que sí es factible.
Me refiero a esto que pedías
mellon escribió:Dejando de banda la ridiculez de la idea en si. Cuando querais datos concretos sobre PORQUE es MATEMATICAMENTE imposible factorizar el RSA-2048, lo discutimos sin flamewars de radicalismos de la Scene.
Matemáticamente irrealizable no, pero no abordable sí. xD
Un saludo
)ov3rwrite escribió:NeDark escribió:ov3rwrite escribió:PD2: Por cierto, ¿qué significa "Jur..."?
Y aquí es donde pones algo, que se te ha olvidado....
¿O es que tú tampoco sabes lo que significa?
NeDark escribió:ov3rwrite escribió:PD2: Por cierto, ¿qué significa "Jur..."?
...
PD: No esperes respuesta, nunca ha habido ninguna contestación.
NeDark escribió:gndolfo escribió:Me decanto por un amago de intervencion
"Juraria que puedo aportar algo" -> "Juraria que..." -> "Juraria..." -> "Jur... (bah, al carajo, no tengo nada que decir)"
WTF???
. ov3rwrite escribió:Hola, he leído por ahí algo que puede ser de interés para el tema:
Voy a citar unas fuentes y las comentamos de forma objetiva, si gustáis. f5inet, espero tu participación.
Voy citando texto y fuente y añadiendo explicación / traducción para el que le interese.
La última factorización de números RSA de la que se tiene noticia es la del RSA-200, que tiene además el record de ser la factorización de enteros más grande jamás hecha, por un grupo de la Universidad de Bonn. Esto es debido a que el número entero a factorizar es:RSA-200 = 2799783391122132787082946763872260162107044678695542853756000992932612840010
7609345671052955360856061822351910951365788637105954482006576775098580557613
579098734950144178863178946295187237869221823983
Osea, 200 dígitos decimales, que codificados resultan en 663 bits.
La factorización da:RSA-200 = 3532461934402770121272604978198464368671197400197625023649303468776121253679
423200058547956528088349
× 7925869954478333033347085841480059687737975857364219960734330341455767872818
152135381409304740185467
Estos dos números, son de 100 dígitos cada uno. Realizar este cálculo ha llevado (cito textualmente):Thorsten Kleinjung escribió:
Sieving has been done on a variety of machines. We estimate that
lattice sieving would have taken 55 years on a single 2.2 GHz Opteron
CPU.
Note that this number could have been improved if instead of the PIII-
binary which we used for sieving, we had used a version of the
lattice-siever optimized for Opteron CPU's which we developed in the
meantime.
The matrix step was performed on a cluster of 80 2.2 GHz Opterons
connected via a Gigabit network and took about 3 months.
We started sieving shortly before Christmas 2003 and continued until
October 2004. The matrix step began in December 2004.
Para el primer paso del algoritmo, sleving, u obtención de los números a usar, un único procesador Opteron a 2.2 GHz tardaría 55 años. No he encontrado la cantidad de máquinas que han usado para el sieving, pero debido a que han tardado bastante menos de 55 años, han debido usar unos cuantos más.
Para el siguiente paso, el de la resolución de ecuaciones usando una matriz (gigante), que ocupaba más de 2 GB en memoria, según he podido leer, han usado un cluster de 80 opterons conectados por una gigabit ethernet (osea, los nodos del cluster se comunicaban con los otros a velocidades de 1 Gbps). Y han tardado "sólo" 3 meses. En la etapa anterior se tiraron más de un año.
Ellos han usado el algoritmo GNFS (General number field sieve). Se ha probado que éste es el algoritmo más eficiente para encontrar factorizaciones de enteros con una longitud mayor a 100 dígitos. No me voy a poner a hablar sobre el método, básicamente porque yo tampoco lo entiendo muy bien. Pero se basa en la generación de polinomios irreducibles para resolver la factorización en un tiempo polinomial. Esto de polinomial significa que el tiempo que inviertas en resolver el problema nunca va a ser mayor que lo indicado por el polinomio indicado. Para esto caso es:
Siendo n la cantidad de dígitos que posee el número a factorizar.
Abajo tenéis todos los links, por si queréis consultarlo más en profundidad.
También, he decidido a mirarme el código y voy a comentar algunas cosas.// TODO code application logic here
//RSA-100 N= 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
//RSA-100 P*Q= 37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061
Vale, esto es un comentario que indica que va a intentar factorizar el entero para RSA-100, que es N. Y debajo pone la solución a lo que va a resolver, osea, P y Q. Osea, ejecutando ese código ya sabes de antemano lo que te va a dar. El RSA-100 es el más "débil" de los RSA y fue factorizado en Abril de 1991 por Arjen K. Lenstra. La factorización se resolvió en unos cuantos días usando una MasPar (un computador paralelo). Para ello usó el algoritmo de tamizado cuadrático múltipolinomial. (multiple-polynomial quadratic sieve algorithm) o simplemente msieve .Si este código lo ejecutas en un ordenador actual doméstico, tampoco le debería llevar más el resolverlo. Unas 130 horas.
Ahora, empleas esta función para sacar la raíz cuadrada del número, y a partir de ahí buscar. Usas esta función:// Newton Raphson - shift
private static BigInteger nrsqrt(BigInteger n) {
// Uses the fact that the square root, any base, usually has 1/2
// the digits of the number to take root of to get a close first
// guess. NR converges fast when close to the actual value.
//
// If I used the number itself instead of the TWO I started with
// it would of probably been better since I saw somewhere that
// initial values close to a minimum can cause it to not converge.
//
// All of this was from various mail forum posts I googled.
// It seems correct and despite not eliminating the one divide it
// seems fast enough for a BigInteger squareroot.
//
// At least for now.
//
BigInteger t = n.shiftRight(BigInteger.valueOf(n.bitLength()).shiftRight(1).intValue()),
result = null;
for (;;) {
result = t.add(n.divide(t)).shiftRight(1);
if (t.compareTo(result) == 0) break;
t = result;
}
return result;
}
Como dice, explota el hecho de que una raíz cuadrada normalmente tiene la mitad de sus dígitos iguales al número del que quieres hacer la raíz, para hacer una aproximación inicial. No sé el orden de este algoritmo ni me he puesto a calcularlo, espero que el creador lo sepa. Como el mismo código lo he encontrado aquí, supongo que se le podrá preguntar. Por cierto, es de muy mal gusto coger código de alguien y no citarlo con un comentario.
El caso es que:
1) No sé cual es el algoritmo qué usas, en que teoremas está basado ni el orden del mismo. Por favor, te pido si puedes que nos lo aclares.
2) Tampoco sé de qué manera puede ayudar el resolver el RSA-100 por este método, cuando está probado que no es eficiente para números de más de 100 dígitos. Además, tampoco se por qué ibas a empezar a resolver algo que ya sabes lo que da en paralelo por este método para intentar romper una RSA de muchos más dígitos, como será la que usa Sony. No sé exactamente cual, pero no creo que se hayan andado con chiquitas y estén usando, como poco, una RSA-1024, que consta de 309 dígitos decimales. (si no es que han usado un 617 o un 2048).
3) No quiero desanimar a nadie, pero creo que un proyecto así sólo puede ser llevado a cabo dentro de una empresa / universidad.
Aún así tengo otras dudas que plantearé cuando las anteriores sean resueltas.
Un saludo.
PD: Esto también es una cuenta prestada.
PD2: Links
RSA-Numbers --> http://en.wikipedia.org/wiki/RSA_numbers
Anuncio de la factorización del RSA - 200 --> http://www.crypto-world.com/announcements/rsa200.txt
GNFS --> http://en.wikipedia.org/wiki/GNFSmellon escribió:[(...)
PD= Nadie me ha respondido sobre la supuesta clave de RSA de Sony
Salu2
mellon, creo que nadie lo sabe a ciencia cierta y aunque es de suponer, ya que hoy por hoy es de las más usadas, tienes razón al remarcar que no tenemos ni idea
saludos!
![[risita]](/images/smilies/nuevos/sonrisa_ani1.gif "risita")
gndolfo escribió:Jur... a todos
Estamos bastante centrados, pero hasta que no resolvamos estas preguntas (negrita y azul), todo lo que podamos hacer son ridiculas especulaciones.ov3rwrite escribió:Hola, he leído por ahí algo que puede ser de interés para el tema:
Voy a citar unas fuentes y las comentamos de forma objetiva, si gustáis. f5inet, espero tu participación.
Voy citando texto y fuente y añadiendo explicación / traducción para el que le interese.
La última factorización de números RSA de la que se tiene noticia es la del RSA-200, que tiene además el record de ser la factorización de enteros más grande jamás hecha, por un grupo de la Universidad de Bonn. Esto es debido a que el número entero a factorizar es:RSA-200 = 2799783391122132787082946763872260162107044678695542853756000992932612840010
7609345671052955360856061822351910951365788637105954482006576775098580557613
579098734950144178863178946295187237869221823983
Osea, 200 dígitos decimales, que codificados resultan en 663 bits.
La factorización da:RSA-200 = 3532461934402770121272604978198464368671197400197625023649303468776121253679
423200058547956528088349
× 7925869954478333033347085841480059687737975857364219960734330341455767872818
152135381409304740185467
Estos dos números, son de 100 dígitos cada uno. Realizar este cálculo ha llevado (cito textualmente):Thorsten Kleinjung escribió:
Sieving has been done on a variety of machines. We estimate that
lattice sieving would have taken 55 years on a single 2.2 GHz Opteron
CPU.
Note that this number could have been improved if instead of the PIII-
binary which we used for sieving, we had used a version of the
lattice-siever optimized for Opteron CPU's which we developed in the
meantime.
The matrix step was performed on a cluster of 80 2.2 GHz Opterons
connected via a Gigabit network and took about 3 months.
We started sieving shortly before Christmas 2003 and continued until
October 2004. The matrix step began in December 2004.
Para el primer paso del algoritmo, sleving, u obtención de los números a usar, un único procesador Opteron a 2.2 GHz tardaría 55 años. No he encontrado la cantidad de máquinas que han usado para el sieving, pero debido a que han tardado bastante menos de 55 años, han debido usar unos cuantos más.
Para el siguiente paso, el de la resolución de ecuaciones usando una matriz (gigante), que ocupaba más de 2 GB en memoria, según he podido leer, han usado un cluster de 80 opterons conectados por una gigabit ethernet (osea, los nodos del cluster se comunicaban con los otros a velocidades de 1 Gbps). Y han tardado "sólo" 3 meses. En la etapa anterior se tiraron más de un año.
Ellos han usado el algoritmo GNFS (General number field sieve). Se ha probado que éste es el algoritmo más eficiente para encontrar factorizaciones de enteros con una longitud mayor a 100 dígitos. No me voy a poner a hablar sobre el método, básicamente porque yo tampoco lo entiendo muy bien. Pero se basa en la generación de polinomios irreducibles para resolver la factorización en un tiempo polinomial. Esto de polinomial significa que el tiempo que inviertas en resolver el problema nunca va a ser mayor que lo indicado por el polinomio indicado. Para esto caso es:
Siendo n la cantidad de dígitos que posee el número a factorizar.
Abajo tenéis todos los links, por si queréis consultarlo más en profundidad.
También, he decidido a mirarme el código y voy a comentar algunas cosas.// TODO code application logic here
//RSA-100 N= 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
//RSA-100 P*Q= 37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061
Vale, esto es un comentario que indica que va a intentar factorizar el entero para RSA-100, que es N. Y debajo pone la solución a lo que va a resolver, osea, P y Q. Osea, ejecutando ese código ya sabes de antemano lo que te va a dar. El RSA-100 es el más "débil" de los RSA y fue factorizado en Abril de 1991 por Arjen K. Lenstra. La factorización se resolvió en unos cuantos días usando una MasPar (un computador paralelo). Para ello usó el algoritmo de tamizado cuadrático múltipolinomial. (multiple-polynomial quadratic sieve algorithm) o simplemente msieve .Si este código lo ejecutas en un ordenador actual doméstico, tampoco le debería llevar más el resolverlo. Unas 130 horas.
Ahora, empleas esta función para sacar la raíz cuadrada del número, y a partir de ahí buscar. Usas esta función:// Newton Raphson - shift
private static BigInteger nrsqrt(BigInteger n) {
// Uses the fact that the square root, any base, usually has 1/2
// the digits of the number to take root of to get a close first
// guess. NR converges fast when close to the actual value.
//
// If I used the number itself instead of the TWO I started with
// it would of probably been better since I saw somewhere that
// initial values close to a minimum can cause it to not converge.
//
// All of this was from various mail forum posts I googled.
// It seems correct and despite not eliminating the one divide it
// seems fast enough for a BigInteger squareroot.
//
// At least for now.
//
BigInteger t = n.shiftRight(BigInteger.valueOf(n.bitLength()).shiftRight(1).intValue()),
result = null;
for (;;) {
result = t.add(n.divide(t)).shiftRight(1);
if (t.compareTo(result) == 0) break;
t = result;
}
return result;
}
Como dice, explota el hecho de que una raíz cuadrada normalmente tiene la mitad de sus dígitos iguales al número del que quieres hacer la raíz, para hacer una aproximación inicial. No sé el orden de este algoritmo ni me he puesto a calcularlo, espero que el creador lo sepa. Como el mismo código lo he encontrado aquí, supongo que se le podrá preguntar. Por cierto, es de muy mal gusto coger código de alguien y no citarlo con un comentario.
El caso es que:
1) No sé cual es el algoritmo qué usas, en que teoremas está basado ni el orden del mismo. Por favor, te pido si puedes que nos lo aclares.
2) Tampoco sé de qué manera puede ayudar el resolver el RSA-100 por este método, cuando está probado que no es eficiente para números de más de 100 dígitos. Además, tampoco se por qué ibas a empezar a resolver algo que ya sabes lo que da en paralelo por este método para intentar romper una RSA de muchos más dígitos, como será la que usa Sony. No sé exactamente cual, pero no creo que se hayan andado con chiquitas y estén usando, como poco, una RSA-1024, que consta de 309 dígitos decimales. (si no es que han usado un 617 o un 2048).
3) No quiero desanimar a nadie, pero creo que un proyecto así sólo puede ser llevado a cabo dentro de una empresa / universidad.
Aún así tengo otras dudas que plantearé cuando las anteriores sean resueltas.
Un saludo.
PD: Esto también es una cuenta prestada.
PD2: Links
RSA-Numbers --> http://en.wikipedia.org/wiki/RSA_numbers
Anuncio de la factorización del RSA - 200 --> http://www.crypto-world.com/announcements/rsa200.txt
GNFS --> http://en.wikipedia.org/wiki/GNFSmellon escribió:[(...)
PD= Nadie me ha respondido sobre la supuesta clave de RSA de Sony
Salu2
mellon, creo que nadie lo sabe a ciencia cierta y aunque es de suponer, ya que hoy por hoy es de las más usadas, tienes razón al remarcar que no tenemos ni idea
saludos!
0verl0ad escribió:Hola amigos, soy nuevo en el foro y me he visto atraído por este hilo, que sin duda plantea cuestiones muy interesantes, aunque bajo mi punto de vista irrealizables. Me gustaría remarcar el contenido de este mensaje del amigo gndolfo, en el que se hace referencia a algo que alguien puso pero que no sé porqué no puedo encontrar.
Creo que alguien de los fundadores del proyecto debería posicionarse en un corto espacio de tiempo a favor de dicho postulado (y admitir el error de emprender semejante proyecto) o bien en contra (y aportar evidencias, claro).
[...]
Por cierto, hay un error cuando dice "explota el hecho de que una raíz cuadrada normalmente tiene la mitad de sus dígitos iguales al número del que quieres hacer la raíz, para hacer una aproximación inicial." En realidad supongo que quería decir que tiene más o menos la mitad de dígitos que el número del que quieres hacer la raíz. Vaya fallo.
Saludos! Y seguimos leyéndonos por aquí, estoy estudiando y hago MUCHOS descansos
