RSA Encryption Algorithm, Factorisation Issues
Joe Wilkinson
Prime numbers
Prime numbers are whole numbers that always give a remainder when divided
by every number less than themselves (other than 1). The first prime numbers
are 2, 3, 5, 7, 11, 13, 17, 19 etc. The Prime numbers used in RSA encryption
are much bigger and may have up to 18 digits. The product of these prime
numbers, n, together with one of another pair of numbers (e
and d) that are calculated from them is given away as a Public key
(e,n). The Private key (d,n) includes the second number d
which can be calculated from can be calculated from the Public key, but
only if n can be factorised. The security of RSA Encryption depends
on the difficulty of factorisation of n and the calculation of the
Private Key (d,n).
Security
RSA uses 128 bit encryption, so n in binary may be 128 bits long,
i.e. as big as 2^128.
2^10 is roughly 1000, so 2^128 could be bigger than 1000^12 or 10^36,
or 1,000,000,000,000,000,000,000,000,000,000,000,000
To use RSA encryption two prime numbers are chosen and multiplied to
give a product in this range. To break RSA encryption requires this number
to be factorised, and RSA security relies upon this being too slow or expensive
to do before access to the data is no longer useful.
How Slow?
In the range of 18 digit numbers, i.e. between 1 and 10^18, there are of
the order of 10^17 primes. To check a given value n against one
of these might (optimistically) take 1 cycle of a 1GHz, 64 bit processor.
To check all 10^17 would take 10^17/10^9 = 100,000,000 seconds, or about
3 years. Of course someone might get lucky, but most times would be likely
to take half of the 3 year maximum. And processors will have to be much
faster before it can be done in seconds.
How costly?
An alternative strategy might be to work out the factorisations in advance.
This would involve storing every product-of-two-primes, around 10^34 values,
each with two factors 10^17 in size. This is approximately 10^34 sets of
4, 64 bit numbers (this is 4*8bytes*10^34, =32*10^34 bytes).
This would be 10^25 32GByte disks, costing £10^27, and
a huge amount of volume and power. Unless a much cheaper, compact form
of storage comes along, the task is hopeless.