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);
}
ROOTSECURITY 