AOH :: HP Unsorted B
:: TB13427.HTMBreaking RSA: Totient indirect factorization |

Breaking RSA: Totient indirect factorization ============================================ Author: Alex Bassas Serramia (I'm very sorry for my poor english but it's not my first language). Introduction ------------ This document tries to expose an algorithm that allows the RSA modulus' totien factorization and then breaking RSA. RSA algorithm ------------- RSA algorithm is generated the following way: 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 RSA strength ------------ Equation (3) shows that is possible to recover private key "d" knowing public key "e" and totient "t". "a^n mod m" sequence -------------------- To know about totien we have to examine the sequence "a^n mod m", one sample is "2^n mod 11" (n from 1 to 11) with totien 10: 2, 4, 8, 5, 10, 9, 7, 3, 6,*1, 2 At "n=10" we have one "1" because "a^totien(m) mod m" is always one (Euler's theorem). The sequence "3^n mod 11" has the same totien 10: 3, 9, 5, 4,*1, 3, 9, 5, 4,*1, 3 but we have two "1", "n=5" y "n=10" (totien), in this case we can observe the cyclic nature of the "a^n mod m" because we always have the same list of numbers before each "1". "a^n mod m = 1" equation ------------------------ The cyclic nature of the "a^n mod m" sequence take us to the first statement: 1) - The exponent's values of the "a^n mod m = 1" solutions are always totien's divisors. The sequence "3^n mod 11" has "5" and "10" as solutions, they are totien's divisors (totien(11) = 10). 3, 9, 5, 4,*1, 3, 9, 5, 4,*1, 3 Maximazing "a^n mod m = 1" solutions ------------------------------------ The second statement is: 2) - If "x" is a totien's divisor then "a^x^n mod m = 1" will multiply the "a^n mod m = 1" solutions by "x". Ex.: The "2^n mod 11" sequence has one "1" 2, 4, 8, 5, 10, 9, 7, 3, 6,*1, 2 "2^5^n=32^n", "32^n mod 11" produces 5 ones: 10,*1, 10,*1, 10,*1, 10,*1, 10,*1, 10 "a^n mod m = 1" limit --------------------- The third statement is: 3) - If x is not yet a totien's divisor then "a^x^n mod m = 1" will have the same solutions that "a^n mod m = 1" but with the values permuted. Ex.: The "2^n mod 11" sequence has one "1" 2, 4, 8, 5, 10, 9, 7, 3, 6,*1, 2 "2^2^n= 4^n", "4^n mod 11" has two "1" 4, 5, 9, 3,*1, 4, 5, 9, 3,*1, 4 "4^2^n= 16^n", "16^n mod 11" is still having two "1" but with the values permuted. 5, 3, 4, 9,*1, 5, 3, 4, 9,*1, 5 Ending the sequence -------------------- The last statement is: 4) - If "a" contains by power all the totien's divisors then "a^n mod m" will always be "1". Ex.: "2^2^5^n= 1024^n mod 11 *1,*1,*1,*1,*1,*1,*1,*1,*1,*1,*1 Euler's extension ----------------- This statement is a consequence of the statement number 3 but I don't use it in the algorithm. 5) - If "n" is greater than the biggest number of the coincidents totient's divisors then: a^((n-1)(t*(t+1)/2)) mod m = 1 mod m (t = totien(m)) Algorithm --------- - Repeat "a = a^n mod m" with n from 2 to m, saving all the results in a table until a == 1 (Statement 4). - Examine the table from end to begining printing "n" if the number of "ones" is divided by "n" (Statements 1,2,3), Impact ------ PKI vendors must change modulus generator algorithms to discard totients with lower factors. Current certificates can be factorized in lower time than expected and compromised, vendors must review each one separately. Credits -------- Alex Bassas serramia Barcelon (SPAIN) Sample ------ /* (c) Alex Bassas Serramia, Barcelona, SPAIN. */ #ifdef WIN32 #include#include #else typedef long long ULONG64; #define TRUE (-1) #define FALSE (0) #endif #include #include 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 =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); }