Cryptography Reference
In-Depth Information
In fact, the bulk of this chapter simply examines how to perform arithmetic on
arbitrarily large numbers. Once that's out of the way, the actual process of public
key cryptography is surprisingly simple.
Understanding the Theory Behind the RSA
Algorithm
The theory behind RSA public-key cryptosystems is actually very simple. The
core is modulus arithmetic; that is, operations modulo a number. For example,
you're most likely familiar with C's mod operator %; (
x
% 2) returns 0 if
x
is even
and 1 if
x
is odd. RSA public-key cryptography relies on this property of a fi nite
number set. If you keep incrementing, eventually you end up back where you
started, just like the odometer of a car. Specifi cally, RSA relies on three numbers
e
,
d
, and
n
such that (m
e
)
d
% n=m — here
m
is the message to be encrypted and
converted to a number.
Not all numbers work this way; in fact, fi nding three numbers
e
,
d
, and
n
that
satisfy this property is complex, and forms the core of the RSA specifi cation. After
you've found them, though, using them to encrypt is fairly straightforward. The
number
d
is called the
private key
, and you should never share it with anybody.
e
and
n
together make up the
public key
, and you can make them available to
anybody who cares to send you an encoded message. When the sender is ready
to send you something that should remain private, he fi rst converts the message
into a number
m
and then computes m
e
% n and sends you the result
c
. When
you receive it, you then compute c
d
% n and, by the property stated above, you
get back the original message
m
.
Pay special attention to the nomenclature here. Most people, when fi rst intro-
duced to the RSA algorithm, fi nd it confusing and “backward” that encryption
is done with the
public
key and decryption with the
private
key. However, if
you think about it, it makes sense: The public key is the one that's shared with
anybody, anywhere, and thus you can use it to encrypt messages. You don't
care how many people can see your public key because it can only be used to
encrypt messages that you alone can read. It's the decryption that must be done
privately, thus the term
private key
.
The security of the system relies on the fact that even if an attacker has access to
e
and
n
— which he does because they're public — it's computationally infeasible
for him to compute
d
. For this to be true,
d
and
n
have to be enormous — at least
512 bit numbers (which is on the order of 10
154
) — but most public key crypto-
systems use even larger numbers. 1,024- or even 2,048-bit numbers are common.
As you can imagine, computing anything to the power of a 2,048-bit number
is bound to be more than a bit computationally expensive. Most common com-
puters these days are 32-bit architectures, meaning that they can only perform
Search WWH ::
Custom Search