Breaking RSA: Totient indirect factorization

rsa_logo.gif

Este texto tenta expor um algoritmo o qual permite a fatorização do RSA Modulus Totien e assim

quebrar a RSA.

RSA algorithm
————-

O algoritmo RSA é gereado da seguinte forma:

1) m = p*q -> RSA modulus
2) t = (p-1)*(q-1) -> totien(m)

3) (e*d) mod t = 1 mod t

4) a^e mod m = b
5) b^d mod m = a

e = public key
d = private key

Força do RSA
————

A Equação (3) mostra que é possivel recuperar a chave privada “d” sabendo-se a chave publica “e” e o totien “t”.

sequencia “a^n mod m”
——————–

Para saber sobre o totien nós temos que examinar a sequencia “a^n mod m”, um exemplo é “2^n mod 11” (n de 1 à 11)
com o totien 10:

2, 4, 8, 5, 10, 9, 7, 3, 6,*1, 2

Em “n=10” nós temos um “1” porque “a^totien(m) mod m” é sempre 1 (Teorema de Euler).

A sequencia “3^n mod 11” tem o mesmo totien 10:

3, 9, 5, 4,*1, 3, 9, 5, 4,*1, 3

mas nós temos dois “1”, “n=5” y “n=10” (totien), e neste caso deve-se observar a natureza cíclica de “a^n mod m”
porque sempre teremos a mesma lista de números antes de cada “1”.

Equação “a^n mod m = 1”
————————

A Natureza cíclica da sequência “a^n mod m” nos leva à nossa primeira tabela verdade:

1) – O Valor exponencial da solução “a^n mod m” será sempre o valor divisor do Totien.

A sequência “3^n mod 11” tem como solução “5” e “10”, e eles são divisores do valor do totien (totien(11) = 10).

3, 9, 5, 4,*1, 3, 9, 5, 4,*1, 3

Maximizando as soluções de “a^n mod m = 1”
——————————————-

O Segundo valor de nossa tabela verdade é:

2) – Se “x” é um divisor de totien, então “a^x^n mod m = 1” irá multiplicar a solução
“a^n mod m = 1” por “x”.

Ex.: A sequência “2^n mod 11” tem um “1”

2, 4, 8, 5, 10, 9, 7, 3, 6,*1, 2

“2^5^n=32^n”, “32^n mod 11” produz cinco “1”:

10,*1, 10,*1, 10,*1, 10,*1, 10,*1, 10

O limite de “a^n mod m = 1”
———————

O terceiro valor da tabela verdade:

3) Se x ainda não é um divisor de totien então “a^x^n mod m = 1” terá as mesmas soluções que “a^n mod m = 1”
porém com os valores permutados.

Ex.: A sequência “2^n mod 11” tem um “1”

2, 4, 8, 5, 10, 9, 7, 3, 6,*1, 2

“2^2^n= 4^n”, “4^n mod 11” tem dois “1”

4, 5, 9, 3,*1, 4, 5, 9, 3,*1, 4

“4^2^n= 16^n”, “16^n mod 11” ainda terá dois “1” mas veja que os valores estão permutados.

5, 3, 4, 9,*1, 5, 3, 4, 9,*1, 5

Finalizando a Sequência
————————

Nosso ultimo axioma é:

4) Se “a” contém todos os divisores de totien, então “a^n mod m” sempre terá que ser “1”.

Ex.: “2^2^5^n= 1024^n mod 11

*1,*1,*1,*1,*1,*1,*1,*1,*1,*1,*1

Teorema de Euler
—————–

Esta tabela verdade é a consequencia do valor da tabela 3 mas eu não utilizei ela no algoritmo.

5) Se “n” e tão grande quanto o maior número dos totiens condicentes o divisor será:

a^((n-1)(t*(t+1)/2)) mod m = 1 mod m (t = totien(m))

Algoritmo
———

– Repita “a = a^n mod m” com n de 2 até m, salvando todos os resultados em uma tabela até a == 1 (Tabela 4).

– Examine a tabela do final para o começo printando “n” se o número de “1” for divisível por “n” (Tabela 1,2,3),

Impacto
——

Vendors de PKI devem modificar o gerador de algorítmos do modulos para que discartem totiens com baixos valores.
Os certificados atuais podem ser fatorizados em menor tempo do que o esperado e comprometer a segurança do algoritmo

Creditos
——–

Alex Bassas serramia
Barcelon (SPAIN)

Exemplo de Implementação
—————————-

#ifdef WIN32
#include <windows.h>
#include <io.h>
#else
typedef long long ULONG64;
#define TRUE (-1)
#define FALSE (0)
#endif
#include <stdio.h>
#include <time.h>

ULONG64 getrand (void) {
ULONG64 n,num;

for (n=0;n<8;n++) {
num = (num << 8) | (rand()%256);
}
return (num);
}

ULONG64 expmod (ULONG64 x,ULONG64 n,ULONG64 m) {
ULONG64 r = 1;

while (n) {
if (n&1) {
r = (r*x)%m;
n = n – 1;
}
x = (x*x)%m;
n = n / 2;
}
return (r);
}

int isprime (ULONG64 p) {
ULONG64 k,a;

for (k=0;k<8;k++) {
a = getrand() % p;
if (expmod(a,p-1,p) != 1) {
return (FALSE);
}
}
return (TRUE);
}

ULONG64 value (ULONG64 bits) {
ULONG64 n;

n = 1 << bits;
return (n);
}

ULONG64 getprime (ULONG64 bits,ULONG64 mbits) {
ULONG64 num,m;

m = value(mbits);
do {
num = getrand();
if (bits < 64) {
num %= value(bits);
}
}
while ((num<m) || (num<=1) || !isprime(num)); return (num); }

struct s_reg {
ULONG64 base;
ULONG64 exp;
ULONG64 res;
};

int num_reg (FILE *f) {
int l;

fseek (f,0,SEEK_END);
l = ftell(f);
return (l/sizeof(struct s_reg));
}

int go_reg (FILE *f,int num) {
fseek(f,num*sizeof(struct s_reg),SEEK_SET); return (TRUE); }

int read_reg (FILE *f,int num,struct s_reg *r) { if (go_reg(f,num)) {
fread (r,sizeof(struct s_reg),1,f);
}
return (TRUE);
}

int write_reg (FILE *f,int num,struct s_reg *r) { if (go_reg(f,num)) {
fwrite (r,sizeof(struct s_reg),1,f);
}
return (TRUE);
}

void delete_table (char *name) {
FILE *f;

f = fopen (name,”wb”);
if (f != NULL) {
fclose(f);
}
}

void expand_table (char *name,ULONG64 m) { FILE *f; int l; struct s_reg r;

f = fopen (name,”a+b”);
if (f != NULL) {
l = num_reg (f);
if (!l) {
r.base = 2;
r.exp = 2;
r.res = expmod (r.base,r.exp,m);
write_reg (f,0,&r);
l = 1;
}
read_reg (f,l-1,&r);
while (r.res != 1) {
r.base = r.res;
r.exp++;
r.res = expmod (r.base,r.exp,m);
write_reg (f,l++,&r);
}
fclose (f);
}
}

void reverse_table (char *name,ULONG64 m) { FILE *f; struct s_reg a,b; int l,n;
ULONG64 r,e;

f = fopen (name,”rb”);
if (f != NULL) {
l = num_reg (f);
e = 1;
for (n=l-1;n>=0;n–) {
read_reg (f,n,&a);
read_reg (f,n+1,&b);
r = expmod (a.base,e,m);
if (r != 1) {
printf (“reverse\texp = %I64i\r\n”,a.exp);
e *= a.exp;
}
}
fclose (f);
}
}

#define TABLE “test.dat”
#define P_BITS 32

int main (int argc,char *argv[],char *envp[]) {
ULONG64 p,q,m,t;

srand((unsigned)time(NULL));
p = getprime(P_BITS/2,0);
printf (“p = %I64i\r\n”,p);
q = getprime(P_BITS/2,0);
printf (“q = %I64i\r\n”,q);
m = p*q;
printf (“m = %I64i\r\n”,m);
t = (p-1)*(q-1);
printf (“t = %I64i\r\n”,t);
delete_table (TABLE);
expand_table (TABLE,m);
reverse_table (TABLE,m);
return (0);
}

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s