[Proyecto] Factorize Reverse School Way

Archivado
1, 2, 3
he aqui mi proyecto para romper la clave privada de Sony.

actualmente es MUY lento, pero me he esforzado en que el codigo sea altamente vectorizable, para usar los SPE para ayudar a romper la clave de 2048bits por fuerza bruta.

lo dejo por si alguien quiere echarle un vistazo y comentar algo.

/*
RSA-200 =
2799783391122132787082946763872260162107044678695
5428537560009929326128400107609345671052955360856
0618223519109513657886371059544820065767750985805
57613579098734950144178863178946295187237869221823983

Factors =

35324619344027701212726049781984643686711974001976250
23649303468776121253679423200058547956528088349

and

79258699544783330333470858414800596877379758573642
19960734330341455767872818152135381409304740185467

#define DEFN "27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983"
*/

/*
RSA-160 =
21527411027188897018960152013128254292577735888456
75980170497676778133145218859135673011059773491059
60249790711158521430207931466520284014061994699492
7570407753

Factors =
45427892858481394071686190649738831656137145778469
793250959984709250004157335359

and

47388090603832016196633832303788951973268922921040
957944741354648812028493909367

#define DEFN "2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753"
*/

#define DEFN "99400891"
//#define DEFN "10957693037" //numero a factorizar=104677*104681
//#define DEFN "2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753"

#define MAXDIG 10 //hasta 2048 bits
#define LOOPRESUME 1000000 //haz un resumen cada millon de tests

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

//declaracion de tipos
typedef struct _node
{
        char P[MAXDIG];
        char Q[MAXDIG];
        char PrevProduct[MAXDIG];
        int carry;
        int digits;
        struct _node *next;
} node;

//declaracion de funciones
void possible_push(char *P, char *Q, int digits, char *PrevProduct);
void possible_pop(node *test);
void factorize(node *test);
char* multiply_for_test(node *test);
void stream_multiply_by_int(char *stream,int times); //ojo, lo devuelve en la variable pasada por puntero
void stream_shift_right(char *stream, int pos); //ojo, lo devuelve en la variable pasada por puntero
void stream_add(char *stream1, char *stream2); //devuelve la suma en stream1, machacando contenido
int stream_is_equal(char *stream1, char *stream2); //verdadero si stream1=stream2
int stream_is_greater(char *stream1, char *stream2); //verdadero si stream1>stream2
int stream_significant_numbers(char *stream); //devuelve el numero de numeros significativos (o sea, excluyendo ceros a la izquierda)

//declaracion de variables globales
char N[MAXDIG];
int digitsN;
node *possibles;
int stacklen;

//MAIN
int main(void)
{
    int i,count;
    char stemp[MAXDIG], mul_zero[MAXDIG], stream_uno[MAXDIG], stream_tres[MAXDIG], stream_siete[MAXDIG], stream_nueve[MAXDIG];
    char toint[3];
    node test;
    clock_t cpstart, cpend;
    time_t start,end;

    start=time(NULL);
    stacklen=0;
    //parse N
    for(i=0;i<MAXDIG;i++)
        N[i]=0;
    strcpy(stemp,DEFN);
    count=strlen(DEFN);
    for(i=0;i<strlen(DEFN);i++)
    {
        toint[0]=stemp[i];
        toint[1]=0;
        N[strlen(DEFN)-i-1]=atoi(toint);
    }
    digitsN=strlen(DEFN);
    //N parseado y listo para continuar...
    possibles=NULL;

    memset(mul_zero,0,MAXDIG*sizeof(char));
    memset(stream_uno,0,MAXDIG*sizeof(char));
    stream_uno[0]=1;
    memset(stream_tres,0,MAXDIG*sizeof(char));
    stream_tres[0]=3;
    memset(stream_siete,0,MAXDIG*sizeof(char));
    stream_siete[0]=7;
    memset(stream_nueve,0,MAXDIG*sizeof(char));
    stream_nueve[0]=9;
    //comprobamos ultimo digito
    if(N[0]==1) {
        possible_push(stream_uno,stream_uno,1,mul_zero);
        possible_push(stream_tres,stream_siete,1,mul_zero);
        possible_push(stream_nueve,stream_nueve,1,mul_zero);
    }
    if(N[0]==3) {
        possible_push(stream_siete,stream_nueve,1,mul_zero);
        possible_push(stream_uno,stream_tres,1,mul_zero);
    }
    if(N[0]==7) {
        possible_push(stream_uno,stream_siete,1,mul_zero);
        possible_push(stream_tres,stream_nueve,1,mul_zero);
    }
    if(N[0]==9) {
        possible_push(stream_uno,stream_nueve,1,mul_zero);
        possible_push(stream_tres,stream_tres,1,mul_zero);
        possible_push(stream_siete,stream_siete,1,mul_zero);
    }

    count=0;
    cpstart=clock();
    while (possibles!=NULL) {
        possible_pop(&test);
        factorize(&test);

        count=count+1;
        if (count>LOOPRESUME)
        {
            count-=LOOPRESUME;
            cpend=clock();
            printf("\nIntentando Factorizar:\n");
            printf("test P = ");
            for(i=test.digits-1;i>=0;i--)
                printf("%d",test.P[i]);
            printf("\n");
            printf("test Q = ");
            for(i=test.digits-1;i>=0;i--)
                printf("%d",test.Q[i]);
            printf("\nElementos en pila: %d\nloops/seg: %d\n",stacklen,(int)((double)LOOPRESUME/((cpend-cpstart)/(double)CLOCKS_PER_SEC)));
            cpstart=clock();
        }
        end=time(NULL);
        if (difftime(end,start)>30)
            exit(EXIT_SUCCESS);
    }
    printf("realizadas %d iteraciones\n",count);

    printf("END!\n");
    return 0;
}

void possible_push(char *P, char *Q, int digits, char *PrevProduct)
{
    node *nuevo;

    //reserva memoria
    nuevo=malloc(sizeof(node));
    memset(nuevo,0,sizeof(node)); //inicializa a 0
    //copia datos
    memcpy(nuevo->P,P,digits);
    memcpy(nuevo->Q,Q,digits);
    nuevo->digits=digits;
    memcpy(nuevo->PrevProduct,PrevProduct,MAXDIG*sizeof(char));
    //añade el nuevo nodo al principio de la lista
    nuevo->next=possibles;
    possibles=nuevo;
    stacklen++;
}

void possible_pop(node *test)
{
    node *temp;
    //quita y regresa el primer nodo de la lista. apunta el principio de la lista al segundo nodo
    temp=possibles;
    possibles=temp->next;
    temp->next=NULL;
    stacklen--;

    memcpy(test,temp,1*sizeof(node));
    free(temp);
}

void factorize(node *test)
{
    char *mult;
    int i,j;

    if(test->digits==MAXDIG)
    {
        return;
    }

    //primero comprueba a ver si es imposible que el producto sea el que buscamos
    i=stream_significant_numbers(test->P);
    j=stream_significant_numbers(test->Q);
    i+=j;
    if(i>MAXDIG)
    {
        return;
    }

    //comprueba que el P*Q del nodo pasado sea igual que el producto que andamos buscando
    mult=multiply_for_test(test);
    if(stream_is_equal(mult,N))
    {
        int i;
        //este es el momento mas importante... HEMOS ENCONTRADO LA FACTORIZACION
        printf("factorizacion encontrada\n");//ya imprimiremos mas adelante
        printf("P = ");
        for(i=test->digits-1;i>=0;i--)
            printf("%d",test->P[i]);
        printf("\n");
        printf("Q = ");
        for(i=test->digits-1;i>=0;i--)
            printf("%d",test->Q[i]);
        printf("\n");
        exit(EXIT_SUCCESS);
    }
    if(stream_is_greater(mult,N))
    {
        //si el mult obtenido es mayor que N, mejor abandonamos directamente este nodo,
        //porque no nos lleva a ninguna parte seguir calculando posibles valores, si siempre va a sobrepasar
        free(mult);
        return;
    }
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            test->P[test->digits]=i;
            test->Q[test->digits]=j;
            possible_push(test->P,test->Q,test->digits+1,mult);
        }
    }
    //lo anterior es mejorable. si usamos algun metodo para en lugar de encolar 100 valores, encolamos menos
    //haciendo alguna operacion con el carry
    free(mult);
}


char* multiply_for_test(node *test)
{
    char *mult, *temp;

    mult=malloc(MAXDIG*sizeof(char));
    temp=malloc(MAXDIG*sizeof(char));
    memset(mult,0,MAXDIG*sizeof(char));
    memset(temp,0,MAXDIG*sizeof(char));
    //cojemos la multiplicacion previa
    memcpy(mult,test->PrevProduct,MAXDIG);
    //sacamos Q sin el numero nuevo y lo multiplicamos por el numero nuevo añadido a P
    memcpy(temp,test->Q,test->digits-1);
    stream_multiply_by_int(temp,test->P[test->digits-1]);
    stream_shift_right(temp,test->digits-1);
    stream_add(mult,temp);
    memset(temp,0,MAXDIG*sizeof(char));
    //sacamos P sin el numero nuevo y lo multiplicamos por el numero nuevo añadido a Q
    memcpy(temp,test->P,test->digits-1);
    stream_multiply_by_int(temp,test->Q[test->digits-1]);
    stream_shift_right(temp,test->digits-1);
    stream_add(mult,temp);
    memset(temp,0,MAXDIG*sizeof(char));
    //sacamos el numero nuevo de P y Q y lo multiplicamos entre si
    memcpy(temp,test->P,test->digits);
    memset(temp,0,test->digits-1*sizeof(char));
    stream_multiply_by_int(temp,test->Q[test->digits-1]);
    stream_shift_right(temp,test->digits-1);
    stream_add(mult,temp);
    //listo, en mult tenemos ahora la multiplicacion de P y Q usando en el proceso el resultado de la antigua multiplicacion
    free(temp);

    return mult;
}

void stream_multiply_by_int(char *stream,int times)
{
    int i;
    register int tmp,carry;

    carry=0;
    for(i=0;i<MAXDIG;i++)
    {
        tmp=(stream[i]*times)+carry;
        carry=0;
        while(tmp>9)
        {
            tmp-=10;
            carry++;
        }
        stream[i]=tmp;
    }
}

void stream_shift_right(char *stream, int pos)
{
    int i;

    for(i=MAXDIG-pos-1;i>=0;i--)
    {
        stream[i+pos]=stream[i];
    }
    for(i=0;i<pos;i++)
    {
        stream[i]=0;
    }
}

void stream_add(char *stream1, char *stream2) //el resultado se devuelve en stream1
{
    int i;

    for(i=0;i<MAXDIG;i++)
    {
        stream1[i]+=stream2[i];
        if(stream1[i]>9)
        {
            stream1[i]-=10;
            stream1[i+1]++;
        }
    }
}

int stream_is_equal(char *stream1, char *stream2) //verdadero si stream1=stream2
{
    int i;

    for (i=0;i<MAXDIG;i++) {
        if(stream1[i]!=stream2[i])
        {
            return 0;
        }
    }
    return 1;
}

int stream_is_greater(char *stream1, char *stream2) //verdadero si stream1>stream2
{
    int i;

    for(i=MAXDIG-1;i>0;i--)
    {
        if(stream1[i]>stream2[i])
        {
            return 1;
        }
        if(stream1[i]<stream2[i])
        {
            return 0;
        }
    }
    //si llega a salir, es que son iguales, pero no creo que sea el caso, porque eso se comprueba antes
    return 0;
}

int stream_significant_numbers(char *stream)
{
    int i;

    for(i=MAXDIG-1;i>=0;i--)
    {
        if (stream[i]!=0)
        {
            return i+1;
        }
    }
    return 0;
}
¿No es practicamente imposible poder romper dicho cifrado?
Digo practicamente imposible porque con muchos ordenadores procesando se tardarian años.
lo mismo decian del cifrado SSL y fijate la noticia de hace 2 dias...
f5inet escribió:lo mismo decian del cifrado SSL y fijate la noticia de hace 2 dias...


Si pero con 200 ps3 funcionando a la vez XDDD

Ahora aportando algo, he leido el codigo, y el resultado solo te lo muestra por pantalla, por si las moscas (y sabiendo que siempre pasan cosas) porque no haces que te lo guarde en un archivo????

Un saludo
cuantas ps3 ay que poner en funcionamiento y cuanto tiempo pa romper esta clave
¿Y si se usara BOINC o algún sistema de computación distribuída pana poder usar también los PC, MACs... para romperla?
rextell y 6502: esa es la idea, usar algun sistema de procesamiento distribuido, pero antes hay que optimizar y vectorizar el codigo.
pues vamos,todos lo que sepan algo de programacion,a por ese codigo xD!
si reuniesemos unas cuantas ps3(unas ... 50?) trabajando a la vez,durante algunos dias seguidos,quiza... si hay alguien que sepa hacer los calculos,por favor,hacerlos y decir si seria viable la idea(seria estupendo [boing] )

Saludos , y gracias f5inet!
Yo no entiendo mucho pero habria posibilidad de ejecutar dicho codigo en diferentes ps3 por la conexion a internet. La idea seria de conectar las maximas consolas posibles como han hecho con la ssl. Si se puede hacer yo tengo la mia para el experimento
Tambien habria que depurar el codigo de tal manera que los resultados lo grabara en memoria.
.
EXCELENTE IDEA

Creo que los mod deberían prestar un poquito de atención a esto, y a ver si entre todos podemos ayudar. Lo suyo sería que algunos gurús del mundillo nos ayudasen. Yo por el momento se lo voy a comentar a Hermes y a alek.

Si se depura y adapta el código a PC, contad con un C2D T5500 a 1,83 Ghz para tenerlo las 24h del dia encendido.
Contar con mi icore7 haber si hacemos algo.
La verdad es que mi experiencia en criptografía y en romper claves es mínima, asi que con el algoritmo poco podré ayudar, aun así decir al autor que podra contar con unas cuantas máquinas para probarlo cuando este lista la computación distribuída

count=count+1;
        if (count>LOOPRESUME)


Aquí estaría bien usar la directiva __builtin_expect para indicar que es más probable que count sea mayor que LOOPRESUME no sea que el predictor de saltos la fastidie, en el CELL los saltos mal previstos son 18-19 ciclos.
no podria hacerse una red por linux como la de folding home? yo no entiendo de esto, pero podriamos juntar 200 ps3(yo me ofrezco) gracias a internet y usar la capacidad de procesamiento y usarlo en este proyecto. seria posible?

UN SALUDO [hallow] [+furioso]
Roxas01 escribió:no podria hacerse una red por linux como la de folding home? yo no entiendo de esto, pero podriamos juntar 200 ps3(yo me ofrezco) gracias a internet y usar la capacidad de procesamiento y usarlo en este proyecto. seria posible?

UN SALUDO [hallow] [+furioso]


Eso es precisamente lo que quiere hacer f5inet pero primero quiere tener optimizado el algoritmo.
Bueno aki uno k estuvo como espectador en el anterior intento...

si vais enserio deberiais leer estos posts k ay muxa info:

hilo_proyecto-compartido-descifrar-backup-de-ps3_935955

hilo_Conectar-2-Ps3-en-red---Posible--quot-debilidad-quot--del-Cell---quot-Hermano-dame-la-mano-quot-_922638

abia otro hilo k creo k se llamaba "Crear app distributiva" pero no lo encuentro... y ay tambien se intento esto...
ffelagund escribió:
Whitehat_AoD escribió:
f5inet escribió:lo mismo decian del cifrado SSL y fijate la noticia de hace 2 dias...


Si pero con 200 ps3 funcionando a la vez XDDD

Ahora aportando algo, he leido el codigo, y el resultado solo te lo muestra por pantalla, por si las moscas (y sabiendo que siempre pasan cosas) porque no haces que te lo guarde en un archivo????

Un saludo
Usa la filosofia *nix: nombre_de_archivo_ejecutable > archivo_de_salida.txt


Okeyyy, la resaca por la mañana no me deja leer bien codigos ajenos jajajajaja.

Voy a ver si pego un bocao y hechamos una manita a nuestro amigo, que ahora mismo no estoy con ningun proyecto y me apetece hacer algo por al humanidad XDDD
contad con mi ps3 :D :D
quien quiera ponerse a programar el cell de PS3, en el wiki teneis un 'mini howto' de como instalar y configurar el SDK del cell (ahora llamado IBM Multicore Acceleration SDK).

la idea es hacer el codigo especificamente diseñado para cell, no obstante, mirare la posibilidad de adaptarlo para SSE2/3 y sacar alguna version para windows...

la idea es que la aplicacion guarde su estado en una base de datos MySQL o SQLite, pero aun esta muy en pañales, ni tan siquiera le he metido multithreading ni el algoritmo esta optimizado (la madre del cordero, la funcion 'factorize'. aun tiene cosas por implementar para desechar factores inservibles que por el momento se siguen calculando, por ejemplo, por cada loop mete 100 posibles factores nuevos, mientras que con una optimizacion usando el 'carry' solo meteria 7-12 posibles factores nuevos por loop, es una aceleracion de 10x con esa simple optimizacion)
El ssl se ha roto usando una vulnerabilidad en md5.
Y no es por desanimar pero hay dos puntos claves:
La clave hay que buscarla entre 2^2048 posibilidades (osea es un numero con 600 cifras).Para almacenar todas las posibles combinaciones en un disco duro: 2048^2 -> (2^12)^2 -> 2^144, cada 2^10 cambiamos la base (kilo,mega,giga,tera,peta,exa y ya no se seguir) osea los exa son 2^60 y aun no hemos llegado ni a la mitad. Necesitarias 10^(3*8) disdos duros de 1 tera para almacenar todas las claves. No te estas haciendo a la idea de lo inmenso que es esto.
Es un delito y podrias acabar en la carcel. Aqui no vale la excusa de la consola es mia y hago lo que quiero, estas intentando conseguir la firma digital de sony y por eso ni has pagado ni pagaras, y por lo tanto es un delito.

Que no es por desanimar, y como ves te lo he argumentando para que veas porque no se ha tomado nunca esta via (ni se tomara). Se especula que en el futuro con la informatica cuantica todas estas claves sera posibles romperlas en muy pocas horas debido a las propiedades cuanticas de la materia (si una particula puede tener n estados los tendra todos y ninguno, asi que cuando tu crees un algoritmo para allar la clave se superpondran los estados obtinendo la respuesta en un tiempo infimo). Y si asi no te haces a la idea piensa en las progresiones dibujadas en una grafica, el hallar una clave crea una progresion exponencial con una pendiente cada vez mas pronunciada.
Lo siento pero , no way.
PauSaDRaMaTiCa escribió:El ssl se ha roto usando una vulnerabilidad en md5.
Y no es por desanimar pero hay dos puntos claves:
La clave hay que buscarla entre 2^2048 posibilidades (osea es un numero con 600 cifras).Para almacenar todas las posibles combinaciones en un disco duro: 2048^2 -> (2^12)^2 -> 2^144, cada 2^10 cambiamos la base (kilo,mega,giga,tera,peta,exa y ya no se seguir) osea los exa son 2^60 y aun no hemos llegado ni a la mitad. Necesitarias 10^(3*8) disdos duros de 1 tera para almacenar todas las claves. No te estas haciendo a la idea de lo inmenso que es esto.
Es un delito y podrias acabar en la carcel. Aqui no vale la excusa de la consola es mia y hago lo que quiero, estas intentando conseguir la firma digital de sony y por eso ni has pagado ni pagaras, y por lo tanto es un delito.

Que no es por desanimar, y como ves te lo he argumentando para que veas porque no se ha tomado nunca esta via (ni se tomara). Se especula que en el futuro con la informatica cuantica todas estas claves sera posibles romperlas en muy pocas horas debido a las propiedades cuanticas de la materia (si una particula puede tener n estados los tendra todos y ninguno, asi que cuando tu crees un algoritmo para allar la clave se superpondran los estados obtinendo la respuesta en un tiempo infimo). Y si asi no te haces a la idea piensa en las progresiones dibujadas en una grafica, el hallar una clave crea una progresion exponencial con una pendiente cada vez mas pronunciada.
Lo siento pero , no way.


se que es imposible, mas nada me impide intentarlo... y tecnicamente no es 'sacar la clave privada de sony', sino factorizar un numero, de todas maneras, si es imposible, no hay porque asustarse, ¿no?
yo lo intentaria solo por experimentar y somos muchos los q nos podriamos juntar.
hola, queria decir, que hace un mes o asi vi un articulo en el periodico, decia que para este año q acaba de entrar o mediados del otro empezarian a comerciarse super-ordenadores de tamaño reducido, osea tamaño torre, a un precio reducido de entre 4000 y 6000 euros, que es bastante dinero pero para el ordeandor q es no es nada, y son capaces de hacer calculos bestiales por lo q lei, estan pensados para universidades, empresas... pero seguro q ay gente con dinero para comprarse alguno y con un par de esos se podria intentar romper esa clave no? creo q usaban gpu en vez de cpu, lo digo por si alguien mas lo leyo y tiene mas datos, q estaria bien intentar romperla con esos bichos.
tambien se puede usar gpgpu para intentar factorizar el numero, pero es un nicho de mercado inferior y no esta standarizado (nVidia tiene CUDA, AMD/ATI tiene AMD Stream/brook+, OSX tiene openCL...) asi que habria que programar 3 variantes del algoritmo especializado para cada tecnologia, y ademas, dichas variaciones solo funcionan con versiones especificas de los drivers graficos y solo para determinadas tarjetas graficas de gama media/alta (nVidia >=G80, AMD/ATI tarjetas >=HD2400, OSX intel integradas >=X3000). si bien es cierto que GPGPU acelera de forma dramatica estos calculos, supongo que con los 6SPU disponibles en en CELL de PS3 y en todo caso con alguna ayuda de las instrucciones SSE2/3 de los procesadores x86 la cosa puede ser 'dimensionable'.
f5inet escribió:
PauSaDRaMaTiCa escribió:El ssl se ha roto usando una vulnerabilidad en md5.
Y no es por desanimar pero hay dos puntos claves:
La clave hay que buscarla entre 2^2048 posibilidades (osea es un numero con 600 cifras).Para almacenar todas las posibles combinaciones en un disco duro: 2048^2 -> (2^12)^2 -> 2^144, cada 2^10 cambiamos la base (kilo,mega,giga,tera,peta,exa y ya no se seguir) osea los exa son 2^60 y aun no hemos llegado ni a la mitad. Necesitarias 10^(3*8) disdos duros de 1 tera para almacenar todas las claves. No te estas haciendo a la idea de lo inmenso que es esto.
Es un delito y podrias acabar en la carcel. Aqui no vale la excusa de la consola es mia y hago lo que quiero, estas intentando conseguir la firma digital de sony y por eso ni has pagado ni pagaras, y por lo tanto es un delito.

Que no es por desanimar, y como ves te lo he argumentando para que veas porque no se ha tomado nunca esta via (ni se tomara). Se especula que en el futuro con la informatica cuantica todas estas claves sera posibles romperlas en muy pocas horas debido a las propiedades cuanticas de la materia (si una particula puede tener n estados los tendra todos y ninguno, asi que cuando tu crees un algoritmo para allar la clave se superpondran los estados obtinendo la respuesta en un tiempo infimo). Y si asi no te haces a la idea piensa en las progresiones dibujadas en una grafica, el hallar una clave crea una progresion exponencial con una pendiente cada vez mas pronunciada.
Lo siento pero , no way.


se que es imposible, mas nada me impide intentarlo... y tecnicamente no es 'sacar la clave privada de sony', sino factorizar un numero, de todas maneras, si es imposible, no hay porque asustarse, ¿no?


[tadoramo] [tadoramo] [tadoramo] [sati] , esto molaria hacerlo en la campus party o algo asi que hay muchaaa gente XD
Algunas ideas para optimizar el proceso seria:
    Montar un servidor dedicado para que distribuyese el trabajo entre todas las PS3
    Crear algun livecd con las utils necesarias (desconozco si se puede) asi muchos usuarios contribuirian porque no seria necesario grandes conocimientos.
todoloquese escribió:pues vamos,todos lo que sepan algo de programacion,a por ese codigo xD!
si reuniesemos unas cuantas ps3(unas ... 50?) trabajando a la vez,durante algunos dias seguidos,quiza... si hay alguien que sepa hacer los calculos,por favor,hacerlos y decir si seria viable la idea(seria estupendo [boing] )

Saludos , y gracias f5inet!

em no es por anda
pero si alguién pudiera hacer que ejecutaramos por linux un programa en erde para descifrar
pongo la mano en el fuego de que podría llegar a un millón de consolas trabajando
habría mucho hype ...^^

edit: esque no tienen porque darse cuenta....muahahaha
buenas a todos,lo primero feliz año 2009 y lo segundo que conteis con mi play3 mi ordenador y conlo que haga falta para hacer esto.... [oki] [oki] [oki] [oki] [oki] [oki] [oki] [oki]

saludos a todos
f5inet escribió:tambien se puede usar gpgpu para intentar factorizar el numero, pero es un nicho de mercado inferior y no esta standarizado (nVidia tiene CUDA, AMD/ATI tiene AMD Stream/brook+, OSX tiene openCL...) asi que habria que programar 3 variantes del algoritmo especializado para cada tecnologia, y ademas, dichas variaciones solo funcionan con versiones especificas de los drivers graficos y solo para determinadas tarjetas graficas de gama media/alta (nVidia >=G80, AMD/ATI tarjetas >=HD2400, OSX intel integradas >=X3000). si bien es cierto que GPGPU acelera de forma dramatica estos calculos, supongo que con los 6SPU disponibles en en CELL de PS3 y en todo caso con alguna ayuda de las instrucciones SSE2/3 de los procesadores x86 la cosa puede ser 'dimensionable'.


Bueno, tras contactar con jiXo este me ha dicho que es inviable. Por la diferencia exponencial que supone pasar de 128 bits (SSL+vulnerabilidad) a 2048.

Pero no me rindo [oki] .

Dificultad de descifrado en progresión cuadrática:
128 16384
256 65536
512 262144
1024 1048576
2048 4194304

Dificultad de descifrado en progresión cúbica:
128 2097152
256 16777216
512 134217728
1024 1073741824
2048 8589934592

Dificultad de descifrado real:
128 5,2829e+269
256 3,2317e+616
512 1,4002e+1387
1024 3,5249e+3082
2048 4,0155e+6781

Ahora unos cuantos cálculos (corregidme si están mal, hace mucho que no toco las mates [qmparto] ):
Nº bits^Nº variables (=Nº bits)= Dificultad (Dif.)
Dif./Horas=Eficiencia (Efi.)
Efi./Nº consolas= Eficiencia por consola

Suponiendo una eficiencia = a la del SSL:

128^128=5,2829453113566524635233978491652e+269
5,2829453113566524635233978491652e+269/48=1,1006136065326359299007078852427e+268
1,1006136065326359299007078852427e+268/200=5,50306803266317964950353942621e+265

Eficiencia x consola=5,50306803266317964950353942621e+265

Ahora con 2048...:

Dif./(Eficiencia por consola x Nº consolas)=Horas

4,015524852720233816377636290185e+6781/1,1006136065326359299007078852427e+268=3,6484419499143848905827864083213e+6513 horas

[+risas] Muchas...

Con 2000 PS3...:

4,015524852720233816377636290185e+6781/1,100613606532635929900707885242e+269=3,6484419499143848905827864083213e+6512 horas

[+risas] Muchas...

Con 20000 PS3...:

3,6484419499143848905827864083213e+6511 horas

[+risas] Muchas...

Con 2000000 PS3...:

3,6484419499143848905827864083213e+6509 horas

Suponiendo un conjunto equivalente a 5000000 de PS3 (que ya es decir)...:

4,015524852720233816377636290185e+6781/2,751534016331589824751769713105e+273=1,4593767799657539562331145633285e+6508 horas

que pasado a dias son...: 6,0807365831906414843046440138688e+6506
que pasado a años son...: 1,6659552282714086258368887709227e+6504
que pasado a siglos son: 1,6659552282714086258368887709224e+6502
que pasado a milenios son...: 1,6659552282714086258368887709224e+6501
etc...

Ahora veamos que pasa si aumentamos la eficiencia de cada consola ^3:

Efi. x con. =1,6665357930466537453696075320511e+797

Con 2000000 de PS3...:

4,015524852720233816377636290185e+6781/3,3330715860933074907392150641021e+803=1,2047520579738971813626047301199e+5978 horas

Ahora veamos que pasa si aumentamos la eficiencia de cada consola ^10:

Efi. x con. =???

Con 2000000 de PS3...:

4,015524852720233816377636290185e+6781/5,0942331137728876306338618306587e+2663=7,8824913643307115949224372046706e+4117 horas

[+risas] Muchas...

Ahora veamos que pasa si aumentamos la eficiencia de cada consola ^100:

Efi. x con. = 1,1494449822416587561782485510956e+26574

Con 2000000 de PS3...:

4,015524852720233816377636290185e+6781/2,2988899644833175123564971021912e+26580=1,7467233816137586204196183549569e+4123 horas

que pasado a dias son...: 7,27801409005732758508174314565e+4121
que pasado a años son...: 1,9939764630294048178306145604521e+4119
etc...

[+risas] Muchos...

-----------------------------------------

Ahora supongamos una base de 2000000 de PS3 (o potencia equivalente) que trabajasen durante 1 año de forma ininterrumpida... veamos cuán eficientes tendrían que ser:

Dif./(Horas*Nº con.)=Efi. x con.

4,015524852720233816377636290185e+6781/(8760*2000000)=2,2919662401371197582064134076398e+6771 [+risas] [+risas] [+risas]

5,50306803266317964950353942621e+265 <<< 4,015524852720233816377636290185e+6781

Así que sin que sirva de precedente le doy la razón a jiXo [poraki] . Conseguir una depuración/optimización de codigo semejante es poco menos que utópico; pero se puede intentar.
si, se que es utopico e imposible, pero... ¿y lo que nos vamos a reir? XD

hombre, al final es sacar 2 factores primos que al multiplicarse sean el numero dado. y yo lo estoy haciendo mas que nada por ver la potencia de cell y por aprender, pero si de camino suena la flauta, eso que me encuentro...
tonces no sale rentable...
f5inet escribió:si, se que es utopico e imposible, pero... ¿y lo que nos vamos a reir? XD

hombre, al final es sacar 2 factores primos que al multiplicarse sean el numero dado. y yo lo estoy haciendo mas que nada por ver la potencia de cell y por aprender, pero si de camino suena la flauta, eso que me encuentro...


Ahora bien... lo he estado pensando...

Imagínate que la clave resulta ser 000000000000000000000000000000000004 (p.ej)

¿Cuántos cálculos habría que hacer? Pocos. Lo mio solo son estimaciones, por lo que te animo a seguir trabajando. Puede sonar la flauta.

(Y ya sabes, si mejoras el codigo y lo adaptas a Windows, un servidor ayudaría)
ya que has hecho algunos calculos, te doy los mios para que los cruces con los tuyos:
mi algoritmo totalmente optimizado, necesitaria hacer un total de 3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2) 'loops' a la funcion factorize.

el algortimo actual, sin optimizar, hace 750.000 loops por segundo en una PS3. espero conseguir un incremento minimo de x20 al pasarlo a una SPU. espero poder usar los 6 SPUs en paralelo, puesto que el algoritmo es altamente paralelizable y vectorizable. una PS3 espero que pueda entregar 750.000*20*6 loops/seg, adicionalmente, espero conseguir una aceleracion en el PPE de x6 al usar altivec, asi que añadele 750.000*6 usando uno de los hilos del PPE, dejando el otro hilo de ejecucion del PPE en plan mayordomo para mantener alimentados los SPE y el PPE

ya tienes datos de ejecucion reales, a ver si puedes calcularme cuanto tiempo seria necesario con 1 y con 1000 PS3...
TitoT está baneado por "faltas de respeto, troleos y flames continuos"
Mirar no se de que coño estais hablando, no entiendo ni papa, pero que coño adelante con ello y si no sale me voy este verano a japon y le meto dos sopapos al Japo de turno pa que me lo escriba en un papel...

Es coña, jeje, adelante chicos, aunque no valga mas que para saber que podeis intentarlo...y sobretodo para aprender.
Me parece un proyecto muy interesante (a la par que imposible, pero bueno...), me intersa bastante el algoritmo y su aplicacion sobre la PS3 (mas que el intento de romper RSA-2048).

Tengo el C un poco oxidado [360º] pero mirando el codigo me parece que no esta del todo optimizado en su vertiente numerica (que es lo realmente me interesa)...

Seria mucho pedir un pseudocodigo :) ?¿


Salu2
f5inet escribió:ya que has hecho algunos calculos, te doy los mios para que los cruces con los tuyos:
mi algoritmo totalmente optimizado, necesitaria hacer un total de 3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2) 'loops' a la funcion factorize.

el algortimo actual, sin optimizar, hace 750.000 loops por segundo en una PS3. espero conseguir un incremento minimo de x20 al pasarlo a una SPU. espero poder usar los 6 SPUs en paralelo, puesto que el algoritmo es altamente paralelizable y vectorizable. una PS3 espero que pueda entregar 750.000*20*6 loops/seg, adicionalmente, espero conseguir una aceleracion en el PPE de x6 al usar altivec, asi que añadele 750.000*6 usando uno de los hilos del PPE, dejando el otro hilo de ejecucion del PPE en plan mayordomo para mantener alimentados los SPE y el PPE

ya tienes datos de ejecucion reales, a ver si puedes calcularme cuanto tiempo seria necesario con 1 y con 1000 PS3...


Venga pues:

Hemos de ponernos en lo peor---> con lo cual el objetivo estaría en 2048^2048

3*10^(2048^2048)= Lo siento, pero la calculadora de WXP no da para tanto [+risas] Va enserio, podéis comprobarlo. Pero vamos sería algo así: 3e+4,015524852720233816377636290185e+6781

que es un zurullo incompreensible, así que me voy a descargar una calculadora como Dios manda y ahora edito...

EDITO: Por el momento ni una sola calculadora es capaz de hacer esa operación...

EDITO2: Sigo sin poder... este es el problema:

GetD overflow, continuing...

Floating multiply overflow, continuing...
wabo escribió:
f5inet escribió:ya que has hecho algunos calculos, te doy los mios para que los cruces con los tuyos:
mi algoritmo totalmente optimizado, necesitaria hacer un total de 3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2) 'loops' a la funcion factorize.

el algortimo actual, sin optimizar, hace 750.000 loops por segundo en una PS3. espero conseguir un incremento minimo de x20 al pasarlo a una SPU. espero poder usar los 6 SPUs en paralelo, puesto que el algoritmo es altamente paralelizable y vectorizable. una PS3 espero que pueda entregar 750.000*20*6 loops/seg, adicionalmente, espero conseguir una aceleracion en el PPE de x6 al usar altivec, asi que añadele 750.000*6 usando uno de los hilos del PPE, dejando el otro hilo de ejecucion del PPE en plan mayordomo para mantener alimentados los SPE y el PPE

ya tienes datos de ejecucion reales, a ver si puedes calcularme cuanto tiempo seria necesario con 1 y con 1000 PS3...


Venga pues:

Hemos de ponernos en lo peor---> con lo cual el objetivo estaría en 2048^2048

3*10^(2048^2048)= Lo siento, pero la calculadora de WXP no da para tanto [+risas] Va enserio, podéis comprobarlo. Pero vamos sería algo así: 3e+4,015524852720233816377636290185e+6781

que es un zurullo incompreensible, así que me voy a descargar una calculadora como Dios manda y ahora edito...

EDITO: Por el momento ni una sola calculadora es capaz de hacer esa operación...


Seguro que estas haciendo bien el calculo?

Igualmente: Quieres que te pase el archivo con tu calculo?

Salu2
Weno pos eso adelante con el proyecto y contar con mi ps3 mi ordena el de mi padre el de mi hermano y el de todos mis amigos jajajaja...
No se de programación aunque me gustaria saber pero bueno almenos colaboro con lo que puedo... saludos ;)
mellon escribió:
wabo escribió:
f5inet escribió:ya que has hecho algunos calculos, te doy los mios para que los cruces con los tuyos:
mi algoritmo totalmente optimizado, necesitaria hacer un total de 3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2) 'loops' a la funcion factorize.

el algortimo actual, sin optimizar, hace 750.000 loops por segundo en una PS3. espero conseguir un incremento minimo de x20 al pasarlo a una SPU. espero poder usar los 6 SPUs en paralelo, puesto que el algoritmo es altamente paralelizable y vectorizable. una PS3 espero que pueda entregar 750.000*20*6 loops/seg, adicionalmente, espero conseguir una aceleracion en el PPE de x6 al usar altivec, asi que añadele 750.000*6 usando uno de los hilos del PPE, dejando el otro hilo de ejecucion del PPE en plan mayordomo para mantener alimentados los SPE y el PPE

ya tienes datos de ejecucion reales, a ver si puedes calcularme cuanto tiempo seria necesario con 1 y con 1000 PS3...


Venga pues:

Hemos de ponernos en lo peor---> con lo cual el objetivo estaría en 2048^2048

3*10^(2048^2048)= Lo siento, pero la calculadora de WXP no da para tanto [+risas] Va enserio, podéis comprobarlo. Pero vamos sería algo así: 3e+4,015524852720233816377636290185e+6781

que es un zurullo incompreensible, así que me voy a descargar una calculadora como Dios manda y ahora edito...

EDITO: Por el momento ni una sola calculadora es capaz de hacer esa operación...


Seguro que estas haciendo bien el calculo?

Igualmente: Quieres que te pase el archivo con tu calculo?

Salu2


Creo que si :-?

Sería (para 1 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(750000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(750000*20*6)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(750000*20*36)= Óptimo (si lo he entendido bien creo que es así)

En dias (para 1 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(64800000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(7776000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(46656000000000)= Óptimo (si lo he entendido bien creo que es así)

Ya dirás que te sale.

EDITO:

En dias (para 1000 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(64800000000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(7776000000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(46656000000000000)= Óptimo (si lo he entendido bien creo que es así)

En dias (para 1000000 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(64800000000000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(7776000000000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(46656000000000000000)= Óptimo (si lo he entendido bien creo que es así)

En dias (para 2000000 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(129600000000000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(15552000000000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(93312000000000000000)= Óptimo (si lo he entendido bien creo que es así)
pero eso seria en caso de que saliese la clave en la ultima pasada, imaginaos que aparece en la 5ª o la 6ª pasada como han puesto mas arriba, el tiempo se reduce bastante [looco] [looco] [looco] [looco]
wabo escribió:Ahora bien... lo he estado pensando...

Imagínate que la clave resulta ser 000000000000000000000000000000000004 (p.ej)

¿Cuántos cálculos habría que hacer? Pocos. Lo mio solo son estimaciones, por lo que te animo a seguir trabajando. Puede sonar la flauta.

(Y ya sabes, si mejoras el codigo y lo adaptas a Windows, un servidor ayudaría)


Maylot escribió:pero eso seria en caso de que saliese la clave en la ultima pasada, imaginaos que aparece en la 5ª o la 6ª pasada como han puesto mas arriba, el tiempo se reduce bastante [looco] [looco] [looco] [looco]



pero lo mas logico digo yo que es que hayan elegido la clave mas dificil no? o sea la que se mas larga de descifrar, vamos que si yo quiero proteger un archivo y tengo un maximo de 4 caracteres para elegir la contraseña, porque voy a usar el 0002 y que tarden nada en sacarla, elegiria el 9999 y tardarian bastante mas, pues los programas para sacar la clave van probando uno a uno los numeros, no?

si se lleva adelante me apunto

animo!
wabo escribió:
mellon escribió:
wabo escribió:Venga pues:

Hemos de ponernos en lo peor---> con lo cual el objetivo estaría en 2048^2048

3*10^(2048^2048)= Lo siento, pero la calculadora de WXP no da para tanto [+risas] Va enserio, podéis comprobarlo. Pero vamos sería algo así: 3e+4,015524852720233816377636290185e+6781

que es un zurullo incompreensible, así que me voy a descargar una calculadora como Dios manda y ahora edito...

EDITO: Por el momento ni una sola calculadora es capaz de hacer esa operación...


Seguro que estas haciendo bien el calculo?

Igualmente: Quieres que te pase el archivo con tu calculo?

Salu2


Creo que si :-?

Sería (para 1 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(750000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(750000*20*6)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(750000*20*36)= Óptimo (si lo he entendido bien creo que es así)

En dias (para 1 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(64800000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(7776000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(46656000000000)= Óptimo (si lo he entendido bien creo que es así)

Ya dirás que te sale.

EDITO:

En dias (para 1000 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(64800000000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(7776000000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(46656000000000000)= Óptimo (si lo he entendido bien creo que es así)

En dias (para 1000000 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(64800000000000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(7776000000000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(46656000000000000000)= Óptimo (si lo he entendido bien creo que es así)

En dias (para 2000000 PS3):
(3*10^(2,0077624263601169081888181450925e+6781))/(129600000000000000)= Actualmente.
(3*10^(2,0077624263601169081888181450925e+6781))/(15552000000000000000)= Optimista.
(3*10^(2,0077624263601169081888181450925e+6781))/(93312000000000000000)= Óptimo (si lo he entendido bien creo que es así)


No discuto tus calculos ni los del autor pero segun lo que ha puesto f5inet (que tampoco se de donde lo saca y por lo tanto si es correcto).

un total de 3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2) 'loops' a la funcion factorize.


Por lo que quedaria para un cifrado RSA-2048 en exactamente 607 digitos.

3*10^(607/2) = 3*10^(304) 'loops' (y apartir de aqui calcular)

Segundo, no me acabo de aclarar con el codigo en C, pero diria que al algoritmo le faltaria alguna que otra optimizacion (numericamente hablando) por eso pido un pequeño esquema en pseudocode del autor (si no es mucho pedir)...

Pero respecto a los calculos: 1 loop al inicio de la busqueda (suponiendo que se empieze de 0) no gasta los mismo ciclos de reloj que un loop al final. Ya que los numeros a probar son sumamente grande en torno a 10^100 por lo que no se si los calculos que haceis son correctos.

pero lo mas logico digo yo que es que hayan elegido la clave mas dificil no? o sea la que se mas larga de descifrar, vamos que si yo quiero proteger un archivo y tengo un maximo de 4 caracteres para elegir la contraseña, porque voy a usar el 0002 y que tarden nada en sacarla, elegiria el 9999 y tardarian bastante mas, pues los programas para sacar la clave van probando uno a uno los numeros, no?

si se lleva adelante me apunto

animo!


Las cosas no funcionan asi, esto no es la contraseña de un usuario de WinXP ni mucho menos.


PD= ¿Se dispone de la clave publica de Sony? Y del número RSA?
mellon escribió:
Las cosas no funcionan asi, esto no es la contraseña de un usuario de WinXP ni mucho menos.

PD= ¿Se dispone de la clave publica de Sony? Y del número RSA?


bueno y podrias explicarme como funcionan entonces? tengo curiosidad
David13_13 escribió:
mellon escribió:
Las cosas no funcionan asi, esto no es la contraseña de un usuario de WinXP ni mucho menos.

PD= ¿Se dispone de la clave publica de Sony? Y del número RSA?


bueno y podrias explicarme como funcionan entonces? tengo curiosidad


A lo que se refiere es que no es algo que ponga el tipico friki-arreglatodo-informatico de la empresa, sino que ese calculo estará muy bien estudiado y seguramente no encontrarás ningún sentido al codigo, piensa que es un numero de 607 cifras, intenta poner algo con sentido XDDDD.

Respecto a lo de que los calculos creo que hay que tener bastante en cuenta que el algoritmo está en C, y que por lo tanto un loop no puedes asociarlo a velocidad por segundo.

Me explico, en C una multiplicacion no es una sola instruccion, por lo que necesitas varios tiempos de reloj para ello, por lo que los calculos que se han deducido creo que no serían totalmente correctos.

Otra cosa es que el algoritmo estubiera en ASM directamente, donde cada instrucción si tiene un tiempo asociado.

Un saludo
David13_13 escribió:
mellon escribió:
Las cosas no funcionan asi, esto no es la contraseña de un usuario de WinXP ni mucho menos.

PD= ¿Se dispone de la clave publica de Sony? Y del número RSA?


bueno y podrias explicarme como funcionan entonces? tengo curiosidad


La Seguridad del cifrado reside en que dado un numero muy grande (en este caso concreto 607 cifras) se necesita un tiempo de computacion extremadamente largo para determinar los factores de dicho numero, que en un cifrado RSA son siempre 2 numeros (obviamente primos) de un longitud muy grande.

Sabiendo los factores de dicho numero es muy facil romper el cifrado y asi por ejemplo poder leer la particion de Sony del disco duro de la PS3 (que la verdad no se si usa RSA para el cifrado (quiza AES), pero como ejemplo vale).


Salu2
wabo escribió:
f5inet escribió:ya que has hecho algunos calculos, te doy los mios para que los cruces con los tuyos:
mi algoritmo totalmente optimizado, necesitaria hacer un total de 3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2) 'loops' a la funcion factorize.

el algortimo actual, sin optimizar, hace 750.000 loops por segundo en una PS3. espero conseguir un incremento minimo de x20 al pasarlo a una SPU. espero poder usar los 6 SPUs en paralelo, puesto que el algoritmo es altamente paralelizable y vectorizable. una PS3 espero que pueda entregar 750.000*20*6 loops/seg, adicionalmente, espero conseguir una aceleracion en el PPE de x6 al usar altivec, asi que añadele 750.000*6 usando uno de los hilos del PPE, dejando el otro hilo de ejecucion del PPE en plan mayordomo para mantener alimentados los SPE y el PPE

ya tienes datos de ejecucion reales, a ver si puedes calcularme cuanto tiempo seria necesario con 1 y con 1000 PS3...


Venga pues:

Hemos de ponernos en lo peor---> con lo cual el objetivo estaría en 2048^2048

3*10^(2048^2048)= Lo siento, pero la calculadora de WXP no da para tanto [+risas] Va enserio, podéis comprobarlo. Pero vamos sería algo así: 3e+4,015524852720233816377636290185e+6781

que es un zurullo incompreensible, así que me voy a descargar una calculadora como Dios manda y ahora edito...

EDITO: Por el momento ni una sola calculadora es capaz de hacer esa operación...

EDITO2: Sigo sin poder... este es el problema:

GetD overflow, continuing...

Floating multiply overflow, continuing...


3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2)=3*10^300, o sea, un 3, seguido de 300 ceros 'loops'

optimista para 1 PS3=750000*6*20=90.000.000 loops/segundo, vamos a redondear y vamos a decir que una PS3 calcula 100Mloops/segundo, en un dia calcularia 100*3600*24=aproximadamente 9*10^12 loops. en un año calcularia 10^13 (vamos a dejarlo en 10^13 loops para abreviar) * 365= 3*10^15 loops.

si, aun queda lejisimos de 3*10^300 y necesitariamos varios millones de años para sacarlo...

pero oye, me gusta el reto, lo voy a intentar de todas formas...
o todas las ps3 existentes xD
y cuando vas a empezar??
f5inet escribió:
wabo escribió:
f5inet escribió:ya que has hecho algunos calculos, te doy los mios para que los cruces con los tuyos:
mi algoritmo totalmente optimizado, necesitaria hacer un total de 3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2) 'loops' a la funcion factorize.

el algortimo actual, sin optimizar, hace 750.000 loops por segundo en una PS3. espero conseguir un incremento minimo de x20 al pasarlo a una SPU. espero poder usar los 6 SPUs en paralelo, puesto que el algoritmo es altamente paralelizable y vectorizable. una PS3 espero que pueda entregar 750.000*20*6 loops/seg, adicionalmente, espero conseguir una aceleracion en el PPE de x6 al usar altivec, asi que añadele 750.000*6 usando uno de los hilos del PPE, dejando el otro hilo de ejecucion del PPE en plan mayordomo para mantener alimentados los SPE y el PPE

ya tienes datos de ejecucion reales, a ver si puedes calcularme cuanto tiempo seria necesario con 1 y con 1000 PS3...


Venga pues:

Hemos de ponernos en lo peor---> con lo cual el objetivo estaría en 2048^2048

3*10^(2048^2048)= Lo siento, pero la calculadora de WXP no da para tanto [+risas] Va enserio, podéis comprobarlo. Pero vamos sería algo así: 3e+4,015524852720233816377636290185e+6781

que es un zurullo incompreensible, así que me voy a descargar una calculadora como Dios manda y ahora edito...

EDITO: Por el momento ni una sola calculadora es capaz de hacer esa operación...

EDITO2: Sigo sin poder... este es el problema:

GetD overflow, continuing...

Floating multiply overflow, continuing...


3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2)=3*10^300, o sea, un 3, seguido de 300 ceros 'loops'

optimista para 1 PS3=750000*6*20=90.000.000 loops/segundo, vamos a redondear y vamos a decir que una PS3 calcula 100Mloops/segundo, en un dia calcularia 100*3600*24=aproximadamente 9*10^12 loops. en un año calcularia 10^13 (vamos a dejarlo en 10^13 loops para abreviar) * 365= 3*10^15 loops.

si, aun queda lejisimos de 3*10^300 y necesitariamos varios millones de años para sacarlo...

pero oye, me gusta el reto, lo voy a intentar de todas formas...


Oye, te importria poner un pequeño pseudocode de lo que hace el algoritmo?¿ Es que mi C esta un poco oxidado y en ciertas partes me pierdo.

Me gustaria comentarte un par de cosas, pero no estoy seguro de entender el algoritmo completamente.


Salu2
f5inet escribió:3*10^(<numero de digitos del producto buscado, en caso de 2^2048 son 600 digitos>/2)=3*10^300, o sea, un 3, seguido de 300 ceros 'loops'

optimista para 1 PS3=750000*6*20=90.000.000 loops/segundo, vamos a redondear y vamos a decir que una PS3 calcula 100Mloops/segundo, en un dia calcularia 100*3600*24=aproximadamente 9*10^12 loops. en un año calcularia 10^13 (vamos a dejarlo en 10^13 loops para abreviar) * 365= 3*10^15 loops.

si, aun queda lejisimos de 3*10^300 y necesitariamos varios millones de años para sacarlo...

pero oye, me gusta el reto, lo voy a intentar de todas formas...

Je,je... Me había colado pero bien al interpretar lo que me decías.

Bueno, a ver si te levanta el ánimo:

1 PS3= 90000000 loops/segundo
100 PS3= 9000000000 loops/segundo
100000 PS3= 9000000000000 loops/segundo
500000 PS3= 45000000000000 loops/segundo --> en un dia: 3888000000000000000 loops (3,888*10^18) -->en un año 1,419*10^21 loops

A partir de aquí la cosa no aumenta de forma espectacular:
Nº consolas Loops 1er año
1000000 2,83824E+21
1500000 4,25736E+21
2000000 5,67648E+21
2500000 7,0956E+21
3000000 8,51472E+21
3500000 9,93384E+21
4000000 1,1353E+22
4500000 1,27721E+22
5000000 1,41912E+22
5500000 1,56103E+22
6000000 1,70294E+22
6500000 1,84486E+22
7000000 1,98677E+22
7500000 2,12868E+22
8000000 2,27059E+22
8500000 2,4125E+22
9000000 2,55442E+22
9500000 2,69633E+22
10000000 2,83824E+22

Y lo que es peor, cada vez se "ralentiza" más (obvio, al incrementarse exponencialmente las posibilidades):
93500000 2,65375E+23

Ahora veamos que pasa si partiendo de una base de 500000 cada año se añaden 200000:

Nº consolas Nº Años Loops/año/solas Loops acumulados
500000 1 1,41912E+21 1,41912E+21
700000 2 3,97354E+21 5,39266E+21
900000 3 7,66325E+21 1,30559E+22
1100000 4 1,24883E+22 2,55442E+22
1300000 5 1,84486E+22 4,39927E+22

Aunque consiguieses duplicar la velocidad...

Optimizado x2
2,83824E+21
1,07853E+22
2,61118E+22
5,10883E+22
8,79854E+22


El problema base (obviando dificultades técnicas), es que mientras nosotros aumentamos la "velocidad" de forma lineal, añadiendo más PS3, el problema se nos pone más complicado geométricamente.

Y me da que esto no tiene facil solución... [snif]
107 respuestas
Archivado
1, 2, 3
Volver a Scene