______________________________________________________________________________________________
RSA: Attacking the cryptosystem [pt. 1]
Written by The Death, February 8th 2001
(I can be found on the BoxNetwork's IRC server under ThyDeath)
______________________________________________________________________________________________
Table of Content
1.0..............................................................Introduction
1.1..................................Basic Math & Functions Used In This
Part
1.2................................................Basic Statements Used Here
1.3............................................................Trial Division
1.4..................................The Idea Behind The Described Algorithms
1.5........................................................Fermat's Factoring
1.6.............................................................Pollard's P-1
1.7....................................................Initial Segment Attack
______________________________________________________________________________________________
>>> 1.0 Introduction <<<
The RSA cryptosystem is the most widely-used Asymmetric Cryptosystem. In this
tutorial I will explain some vulnerabilities of this Cryptosystem, for people to learn from and
protect themself or attack others.
I will not explain the Cryptosystem itself, As it is described in many pages in
the Internet. Furthermore, i will expect you to know the Cryptosystem yourself.
If you have any questions you can find your answers at the sci.crypt newsgroup,
or you can ask me on the IRC or Email (thedeadh@netvision.net.il)
This part is dealing with one aspect: Finding the factors of the modulus. next
parts will deal other aspects of attacking this Cryptosystem.
The Death
>>> 1.1 Basic Math & Functions Used In This Part <<<
* Length(N) returns N's number of digits
* The ^ symbol will be used here for Exponent.
* M is the Modulus of the key.
* P & Q are the two primes, which their product is M
* [R] Denotes the greatest integer not exceeding R. Example: [4] = 4, [4.6] = 4,
[-2.1] = -3.
* The GCD(a,b) function returns the Greatest Common Divisor of a & b.
Example: GCD(100, 30) = 10, GCD(7,17) = 1.
* Euler's Phi(N) Function returnf the greatest B that comply: B =< N,
GCD(B,N) = 1
>>> 1.2 Basic Statements Used Here <<<
* X^2 - Y^2 = (X+Y)(X-Y)
Proof:
(X+Y)(X-Y) = X^2 - XY + XY - Y^2 = X^2 - Y^2
* M is odd, unless P or Q = 2
Proof:
M = PQ. P & Q are primes, Therefore are not divisible by 2 unless they are
2.
The product of two primes is divisible only by these primes.
* Fermat's factoring theorem: Every odd number can be written as the difference
of two squares,
X^2 - Y^2 (X,Y : Natural).
Proof: WTF?! I Don't care what the proof is! Go dig him up and ask him if you wish!
* Conclusions from the Phi function:
* If P is a prime, then phi(P^K) = (P^(K-1))*(P-1)
* If GCD(A,B) = 1 Then Phi(A*B) = Phi(A)*Phi(B)
(Note: Fermat was a jackass guy who enjoyed solving mathematical sentences, then
ask his friends to solve them themself, just to annoy them)
>>> 1.3 Trial Division <<<
This is the lesser algorithm there is for attacking the RSA cryptosystem. I put
it here because hmmm.... hmmmmm..... I am not sure. Maybe i inhaled too much CO2 from the Coke
bottle. Anyways, It is simple:
1) Assign X = 2
2) Is X a divisor of M ?
* Yes - You found the P factor! Q is M/X, and now you cracked the modulus!
* No - Assign X with the next prime and do this step again
This algorithm is very slow when dealing high numbers. I still can't recall why
did i put it here.
>>> 1.4 The Idea Behind The Described Algorithms <<<
The next algorithms are called specific factorization algorithms. They can
theoreticlly factor every modulus, but work best on a key with primes that weren't chosen properly.
Each of them has a short description of the element it attacks, and how to avoid
it.
>>> 1.5 Fermat's Factoring <<<
This attack is based on Fermat's Factoring Theorem (No shit...).
If X^2 - Y^2 = M, then X^2 - M = Y^2.
M is known, so we will brute-force X to find a pair X & Y that comply being
Integers.
The algorithm is as follows:
1) Assign X with [SquareRoot(M)]
2) Is SquareRoot(X^2 - M) = [SquareRoot(X^2 - M)] ?
* No - Increase X by 1 and do this step again
* Yes - Proceed to step 3
3) Assign Y with SquareRoot(X^2 - M)
4) The factorisation of M is (X+Y)(X-Y), meaning P = X-Y and Q = X+Y
This algorithm is very effective against keys with modulus produced from two
close primes. The bigger ((sqrt(P) - sqrt(Q))^2)/2 is, the greater is the number of steps
needed for Fermat's factoring attack to find P and Q.
>>> 1.6 Pollard's P-1 <<<
The algorithm is as follows:
1) Choose a number A that comply 1 < A < M
2) Choose a number K
3) Is GCD(A,M) = 1 ?
* Yes - You found a factor, GCD(A,M)
* No - Proceed to step 4
4) Assign L = A^K mod M
5) Assign D = GCD(L-1, M)
6) Is D a factor of M ?
* Yes - You found a factor, D. P = D, Q = M/D.
* No - Change K and/or A and return to step 3
This algorithm is effective on M such that P or Q has small prime factors.
>>> 1.7 Initial Segment Attack <<<
There is no exact algorithm, but this what i got: (M#3, M#1... will be used to
reffer to the
# digit of M. Say M = 72342, then M#1 = 2, M#5 = 7...)
1) Assign A = 2
2) Assign T with the minimum number of 0s to check the segment
3) Is M#A, M#(A+1)...M#(A+T) = 0 ?
* Yes - Proceed to step 4
* No - If A < Length(M) Then increase A by 1 and return to step 2, else
exit
4) Assign B with the segment from M#A to M#1 (Initial segment starting from M#A)
5) Is GCD(B,M) > 1 ?
* Yes - You found a factor! P = GCD(B,M), Q = M/P
* No - If A < Length(M) Then increase A by 1 and return to step 2, else
exit
This algorithm is effective if Length(P) < Length(Q) by much, and Q has alot
of 0s in it.
______________________________________________________________________________________________
That is all for now. I will add this part other algorithms as I find & learn
them. Expect preceeding parts to come!
The Death
______________________________________________________________________________________________