# RSA: Attacking the cryptosystem

## Introduction :

```
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, [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.