Cryptography Reference
In-Depth Information
compare different public-key cryptosystems. A complicating factor is that keys in
public-key cryptosystems are:
• first specified in terms of 'numbers';
• then converted into binary strings for implementation.
As a result, unlike in symmetric cryptosystems, the actual length in bits of a private
key will vary, since a smaller 'number' will involve fewer bits when it is converted
into binary. Thus we tend to regard the 'length' of a private key as the maximum
length that the private key could possibly be.
In order to determine the (maximum) length of a private key we have to
consider the specifics of the public-key cryptosystem. For example, in RSA the
decryption key
d
is a number modulo
n
. This means that the decryption key can
be any number less than
n
. Hence the maximum number of bits that we need to
represent an RSA private key is the smallest number
k
such that:
2
k
≥
n
.
This might sound a bit complicated since, given the modulus
n
, we would appear
to have to perform some calculation before we can determine the length in
bits of an RSA private key. However, the good news is that key length is of
sufficient importance that we tend to approach this issue the other way around.
In other words, public-key cryptosystems tend to be referred to directly in
terms of their maximum private key lengths. When someone refers to
1024-
bit RSA
, they mean that the modulus
n
is 1024 bits long when written in
binary and thus that the maximum private key length is also 1024 bits. This
means that the actual modulus
n
, when considered as a 'number', is much
(much) bigger than 1024. More precisely, the modulus
n
will be a number in the
range:
2
1023
2
1024
≤
<
,
n
since these are the numbers that have 1024 bits when written in binary.
COMPARING SECURITY OF PUBLIC-KEY CRYPTOSYSTEMS
Comparing the security of two different public-key cryptosystems, especially if
they are based on different computationally hard problems, is a task best left to the
experts. It is not usually easy to come up with direct comparisons of their relative
security. As we further discuss in Section 10.2, this issue is further complicated
by the fact that assessment tends to be subjective and the relative security may
change over time, for example, if progress is made on solving one hard problem
but not another.
Security comparisons tend to be expressed in terms of the key length. In other
words, for a given perceived level of security, the required key length to achieve
this security level for each public-key cryptosystem is determined. A common
benchmark for the 'perceived level' of security is to use the difficulty of exhaustive
key searches for given symmetric key lengths. For example, a perceived level of
