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.

This article is my oldest. It is 1471 words long, and it’s got 0 comments for now.