- Edited
I've been recently working on one of the most interesting topics in my field and one of my favorite as well:
Cryptography and Information Security...
I - Introduction
Cryptography is probably the most important aspect of communications security and is becoming increasingly important as a basic building block for computer security.
By far the most important automated tool for network and communications security is encryption. Two forms of encryption are in common use:
1- Conventional, or symmetric encryption.
2- Public-key, or asymmetric encryption.
The RSA algorithm was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978. The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-key encryption.
II - Description of the Algorithm
Note: (I used images to show operators, powers, and other mathematical terms that cannot be expressed here)
Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C:
Both sender and receiver must know the value of n. The sender knows the value of e, and only the receiver knows the value of d. Thus, this is a public-key encryption algorithm.
The ingredients of the RSA are the following:
The private key consists of {d, n} and the public key consists of {e, n}. Suppose that user A has published its public key and that user B wishes to send the message M to A. Then B calculates C = M^e mod n and transmits C.
On receipt of this ciphertext, user A decrypts by calculating M = C^d mod n.
The resulting keys are public key PU = {7,187} and private key PR = {23,187}. The example shows the use of these keys for a plaintext input of M = 88. For encryption, we need to calculate C = 88^7 mod 187. This can be done by exploiting the properties of Modular Arithmetic.
III - The Security of RSA
Four possible approaches to attacking the RSA algorithm are as follows:
1- Brute force: This involves trying all possible private keys.
2- Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of two primes.
3- Timing attacks: These depend on the running time of the decryption algorithm.
4- Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm.
The defense against the brute-force approach is the same for RSA as for other cryptosystems, namely, use a large key space. Thus, the larger the number of bits in d, the better.
However, because the calculations involved, both in key generation and in encryption/decryption, are complex, the larger the size of the key, the slower the system will run.
We can identify three approaches to attacking RSA mathematically:
1- Factor n into its two prime factors. This enables calculation of f(n) = (p - 1) x (q - 1), which, in turn, enables determination of d e^-1 (mod f(n)).
2- Determine f(n) directly, without first determining p and q. Again, this enables determination of d e1 (mod f(n)).
3- Determine d directly, without first determining f(n).
Most discussions of the cryptanalysis of RSA have focused on the task of factoring n into its two prime factors. Determining f(n) given n is equivalent to factoring n.
With presently known algorithms, determining d given e and n appears to be at least as time-consuming as the factoring problem. Hence, we can use factoring performance as a benchmark against which to evaluate the security of RSA.
For a large n with large prime factors, factoring is a hard problem, but not as hard as it appears...
IV - The Attack on RSA
There are 3 known algorithms to attack RSA by factorizing N into 2 prime numbers,
1- Quadratic Sieve (April 1991)
2- General Number Field Sieve (April 1996)
3- Lattice Sieve (April 2003)
V - The Code
What follows is a C# code i wrote today to factorize N into 2 prime numbers.
Here's the function:
for example, if N = 654643387, P and Q are equal to 25583 and 25589. (calculated instantly)
Larger values takes some time to compute the 2 prime numbers P and Q.
Note that for better security in the RSA, P and Q should be selected carefully. To avoid values of n that may be factored more easily, P and Q should differ in length by only few digits and should be on a close order of magnitude. The Closer to the Square root of N, the harder to guess P and Q.
For example, if P = 11, which is a prime, it takes less than a fraction of a second to guess Q, since we'll be checking values of P starting from 0 till the Square Root of N.
-------------
This is it for today, I hope you'll like this post as much as i do. I tried to explain all keywords by adding references to Wkikipedia.
I'd also appreciate any comments on this post.
Cheers'
Cryptography and Information Security...
I - Introduction
Cryptography is probably the most important aspect of communications security and is becoming increasingly important as a basic building block for computer security.
By far the most important automated tool for network and communications security is encryption. Two forms of encryption are in common use:
1- Conventional, or symmetric encryption.
2- Public-key, or asymmetric encryption.
The RSA algorithm was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978. The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-key encryption.
II - Description of the Algorithm
Note: (I used images to show operators, powers, and other mathematical terms that cannot be expressed here)
Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C:
Both sender and receiver must know the value of n. The sender knows the value of e, and only the receiver knows the value of d. Thus, this is a public-key encryption algorithm.
The ingredients of the RSA are the following:
The private key consists of {d, n} and the public key consists of {e, n}. Suppose that user A has published its public key and that user B wishes to send the message M to A. Then B calculates C = M^e mod n and transmits C.
On receipt of this ciphertext, user A decrypts by calculating M = C^d mod n.
The resulting keys are public key PU = {7,187} and private key PR = {23,187}. The example shows the use of these keys for a plaintext input of M = 88. For encryption, we need to calculate C = 88^7 mod 187. This can be done by exploiting the properties of Modular Arithmetic.
III - The Security of RSA
Four possible approaches to attacking the RSA algorithm are as follows:
1- Brute force: This involves trying all possible private keys.
2- Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of two primes.
3- Timing attacks: These depend on the running time of the decryption algorithm.
4- Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm.
The defense against the brute-force approach is the same for RSA as for other cryptosystems, namely, use a large key space. Thus, the larger the number of bits in d, the better.
However, because the calculations involved, both in key generation and in encryption/decryption, are complex, the larger the size of the key, the slower the system will run.
We can identify three approaches to attacking RSA mathematically:
1- Factor n into its two prime factors. This enables calculation of f(n) = (p - 1) x (q - 1), which, in turn, enables determination of d e^-1 (mod f(n)).
2- Determine f(n) directly, without first determining p and q. Again, this enables determination of d e1 (mod f(n)).
3- Determine d directly, without first determining f(n).
Most discussions of the cryptanalysis of RSA have focused on the task of factoring n into its two prime factors. Determining f(n) given n is equivalent to factoring n.
With presently known algorithms, determining d given e and n appears to be at least as time-consuming as the factoring problem. Hence, we can use factoring performance as a benchmark against which to evaluate the security of RSA.
For a large n with large prime factors, factoring is a hard problem, but not as hard as it appears...
IV - The Attack on RSA
There are 3 known algorithms to attack RSA by factorizing N into 2 prime numbers,
1- Quadratic Sieve (April 1991)
2- General Number Field Sieve (April 1996)
3- Lattice Sieve (April 2003)
V - The Code
What follows is a C# code i wrote today to factorize N into 2 prime numbers.
long n = _N; // Get the value of N
long sqrtOfN = (long)Math.Sqrt(n); // Find the Square root of N.
long p = 0;
long q = 0;
// Loop through all values untill reaching the Square Root (There's no need to continue beyond this number)
for (p = 2; p <= sqrtOfN; p++)
{
// Check For Primality of P.
if (_CheckIfPrime(p) == true)
{
// If P is prime, calculate q = N / P. If Q must be a prime number too.
q = n / p;
// Check For Primality of Q.
if (_CheckIfPrime(q) == true)
{
if (q * p == n)
{
// Display Results...
MessageBox.Show(p.ToString() + "\n" + q.ToString());
break;
}
}
}
}Here's the function:
public bool _CheckIfPrime(long number)
{
bool isPrimeNumberFound = true;
// Get Square root of number and iterate, start from 2 (cannot start from 0 or 1).
int checking = (int)Math.Sqrt((double)(number));
// perform iteration from 2 all the way to the value of "checking".
for (int j = 2; j <= checking; j++)
{
// If remainder = 0 ==> current number is not a prime number...
if (number % j == 0)
{
isPrimeNumberFound = false;
break;
}
}
return isPrimeNumberFound;
}for example, if N = 654643387, P and Q are equal to 25583 and 25589. (calculated instantly)
Larger values takes some time to compute the 2 prime numbers P and Q.
Note that for better security in the RSA, P and Q should be selected carefully. To avoid values of n that may be factored more easily, P and Q should differ in length by only few digits and should be on a close order of magnitude. The Closer to the Square root of N, the harder to guess P and Q.
For example, if P = 11, which is a prime, it takes less than a fraction of a second to guess Q, since we'll be checking values of P starting from 0 till the Square Root of N.
-------------
This is it for today, I hope you'll like this post as much as i do. I tried to explain all keywords by adding references to Wkikipedia.
I'd also appreciate any comments on this post.
Cheers'
