The RSA cryptosystem is the most widely-used Asymmetric Cryptosystem. In this article, 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 on the Internet. Furthermore, I will expect you to know Cryptosystem yourself.
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.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 returns the greatest B that comply: B =< N, GCD(B,N) = 1
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 P is a prime, then Phi(P) = P-1 * If GCD(A,B) = 1 Then Phi(A*B) = Phi(A)*Phi(B)
Trial Division :
This is the lesser algorithm there is for attacking the RSA cryptosystem. 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.
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.
Fermat's Factoring :
This attack is based on Fermat's Factoring Theorem . 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.
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.
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.
Random Attacks :
These attacks are based some statistic theories which i am not fimilliar with. The basic idea is taking some algorithms (some described in the 1st section) and adding some randomness to them. Additional function used here is Random, which denotes a random number.
Basic Randomness Attack :
This is the simplest attack on this field. Like Trial Devision on the 1st section, this is the most basic algorithms and slow algorithm might be created... 1) Assign A = Random Mod sqrt(N) 2) Is A a divisor of N ? * Yes - Well good for you! * No - Go back to step 1...
Pollard's RHO :
A better algorithm (for some statistical reasons...) 1) Assign X = Random Mod N 2) Assign Y = Random Mod N 3) Is X - Y a divisor of N ? * Yes - Good! * No - You know what to do... This is the most basic idea. It can be improved using a polynomial. Example: 1) Assign X = Random Mod N 2) Assign Y = Random Mod N 3) Set X = (X^2 +1) Mod N 3) Set Y = (Y^2 +1) Mod N 4) Set Y = (Y^2 +1) Mod N Again 5) Set Z = GCD(X-Y, N) 6) Is 1 < Z < N ? * Yes - You found a factor (Z) ! * No - go back to 1...
Real-Life Scenarios :
Here I will show some situations that might occur if the application or person making/using the RSA Cryptosystem is not fully aware of them. Sometimes trivial knowledge of an organization's security architecture might reveal some flaws that can be explotied to crack a key, or find the plaintext of a message.
Known phi(N) :
Take a look at the RSA Cryptosystem's Key-Generation proccess. There is a great part relying on (P-1)(Q-1). The 3rd conclusion of the Phi() function states that Phi(N) is equivalent to (P-1)(Q-1) (Because N = PQ. P,Q = Primes). The fact that Phi(N) is used in the proccess is useful to us if the app saves a log of the proccess, or we can find Phi(N) in any other way. Once Phi(N) is found, we can find P & Q. Here is how: Phi(N) = PQ - (P+Q) +1 = N -P -Q +1 Therefore: Q = N -Phi(N) +1 -P Now, N = PQ. Instead of Q we put the value from the last equation. Therefore: N = P*(N -Phi(N) +1 -P), thus P^2 -P*(N -Phi(N) +1) +N = 0. This is a typical quadratic equation, which you can solve using the quadratic formula. Once solved, P is exposed, Therefore Q is exposed, Therefore key is factored.
Common Modulus :
The next scenario will relay on this basic one: Suppose there is a modulus S which is shared among several people. Each has it's own private/public exponents set, but all based on the same modulus. None of the men know the factors. (This scenerio may occur if a company chooses to issue all of the employees with keys, and for optimization uses a common modulus). If one sends a message to two people sharing the same modulus, and an evesdropper is listening and reading the communication, the evesdropper can get the original message out of the two. * M - The original message * J, K - The two ciphertexts * S - The common modulus * A, B - The public exponents of the two recipents GCD(J,K) = 1, the evesdropper uses the extended euclidian algorithm to find two numbers such that a*x + b*y = 1. Using x and y, the evesdropper computes: M = (J^x)*(K^y) Mod S
Thanks for reading.