Cryptography Reference
In-Depth Information
security defined by a symmetric key length of 128 bits means that solving the
underlying hard problem for the given public-key cryptosystem is believed to be
as hard as conducting an exhaustive key search for a 128-bit symmetric key.
EXHAUSTIVE KEY SEARCHES FOR PRIVATE KEYS
Note that we almost never consider the concept of an exhaustive search for the
private key of a public-key cryptosystem. This is because:
1. An 'uninformed' exhaustive search of all possible private keys is normally
impossible because the key lengths involved are so much larger than for
symmetric cryptosystems. A complete exhaustive search for a 1024-bit RSA
private key will involve trying 2
1024
keys, which is clearly an impossible task,
keeping in mind that searching for a 128-bit symmetric key is regarded as
infeasible for the foreseeable future!
2. An 'informed' exhaustive key search would consist of only trying private keys
that have the necessary mathematical properties. For example, not all 1024-
bit numbers are possible values of
d
for RSA. To perform such a search we
need a means of determining which keys are valid candidates for private keys.
The catch is that finding that means of determining candidates tends to be
related to solving the underlying hard problem. In the case of RSA, in order to
determine whether a number is a candidate for
d
we first need to know the
factorisation of
n
.
3. Most importantly, an exhaustive private key search is generally not the
most efficient method of attacking a public-key cryptosystem. The equivalent
'benchmark' attack on a public-key cryptosystem is the best-known attack on
the underlying hard problem (factoring, in the case of RSA).
As a result it tends to bemore appropriate to focus on trying to solve the underlying
hard problem rather than attempting an exhaustive search for the private key of a
public-key cryptosystem.
RELATIVE KEY LENGTHS
Table 5.2 shows the estimated equivalence between key lengths for RSA
(represented by the bit length of the modulus
n
), ElGamal (represented by the bit
length of the group size
p
) and elliptic-curve-based ElGamal variants (represented
by the bit length of the underlying elliptic curve group), based on one example of
expert opinion. It also indicates the bit length of a symmetric key for which an
exhaustive key search provides the perceived level of security.
Note that the values in Table 5.2 represent respected guidance at a particular
moment in time. It would be prudent to check the latest opinions and information
on such equivalences.
One interesting issue to note about the key lengths in Table 5.2 is that it is
believed that we get equivalent security for the same key length in both RSA
and basic ElGamal. For example, the equivalent security for an RSA modulus of
1776 bits requires an ElGamal modulus
p
of the same length. However, crucially,
