This is post of S_L__S from xbox Scene. What you think. Is this viable?
Neo project is dead... it's sad :-(
But the biggest problem is that the MS key is a 2048bits key, and the time to crack it is ... enormous !
With a crypto professor I've discussed about RSA and after weeks we had an idea to break RSA.
We think that there can be a security hole in RSA if the numbers P and Q are closer, and N can be considerate as a square. It reduce the search for cracking.
Let me give you a simple example :
RSA is done by choosing 2 primes numbers P and Q (very close this time)
> P = 61
> Q = 53
We need the number N known as : N = P x Q
> N = 61 x 53 = 3233
To obtain E, the public exponent we have to find a number
that don't have common factor with (P-1)(Q-1)
> (P-1)(Q-1) = (61-1)(53-1) = 60x52 = 3120
> 3120 = 2 x 2 x 2 x 2 x 3 x 5 x 13
> 3120 = 2^4 x 3^1 x 5^1 x 13^1
So I choose :
> E = 11 x 17 = 187
Now I need D, the private exponent where
( E x D ) mod ( ( P - 1 ) x ( Q - 1) ) = 1
> ( 187 x D ) mod ( 3120 ) = 1
And we find
> D = 2803
> 187 x 2803 = 524161
> 3120 x 168 + 1 = 524161
The Public key is : 187|3233
The Private key is : 2803|3233
Encryption of the number  :
69^2803 mod ( 3233 ) = 2586
Decryption of 2586 :
2586^187 mod ( 3233 ) = 69, yeah it works :-)
Now, if i'm a cracker i've only :
N = 3233
E = 187
P is prime
Q is prime
and i now that 69 -> 2568
I can supose that N is a square so P = Q
In that way to find P and Q i use step by step calculs
Sqrt( N ) = Sqrt( 3233 ) = 56.859
So I try to find the primes numbers neer 56,859
but I'm sure that one is > 56.8 (let's say P2)
and the other is < 56.8 (it's Q2)
So i have my list of prime numbers :
1, 2, ..., 37, 41, 43, 47, 53, 59, 61, 67, 71
So i try :
P2 < 56.8 => P2 = 53
Q2 > 56.8 => Q2 = 59
53 x 59 = 3127 < N so i have to increase P2 or Q2
I can't increse P2 (<56.
so I increase Q2
P2 < 56.8 => P2 = 53
Q2 > 56.8 => Q2 = 61
53 x 61 = 3233, FOUND !
I know that this example is very VERY very VERY very simple but it shows another way to crack RSA and a faster way to do it than brute forcing :-)
Unfortunatly I'm too busy to program a client as NEO PROJECT and to program a crack that follow my may, but if anybody has time too it would be great :-)
[ ADD 08 January 2002 ]
Please correct me if i'm wrong.
the Xbox RSA Private key is 2048bits len.
The Key is composed by 2 numbers : D and N, 1024bits len each.
N is a 1024bits number => 2^1024.
With the square method, we can 'only' test every P by a division : N/P is integer ? (a division is a succession of substractions)
And we can decide to compute with P < Sqrt(N) (so Q > Sqrt(N) )
So P is (2^1024)^(1/2) => 2^512.
There are a lot of chance that P may be a big number, maybe > 2^256
So the chalenge may be more... reasonable ;-) , no ?
I think we can do a Central Bot site that delivery several small works for thousand of an assigned member with a login and password. I saw this before for others purpose, but i don't remenber how much bit the RSA was.