## Implementation and Analysis of RSA

Because encryption with RSA requires little more than
computing *a*^{b} mod
*n*, a basic implementation is relatively simple:
all we need is a function to perform modular exponentiation. However,
to make RSA secure, recall that we must use large integers. This
complicates things. Specifically, all arithmetic must be performed
with integers that are twice the size of the keys. (We will see in a
moment that this doubling is required for the modular exponentiation
process.) Thus, if the keys are 200 decimal digits, we need an
abstract datatype that supports integers with at least 400 decimal
digits.

Since support for large-integer arithmetic is not provided in
this book, the RSA implementation presented here must depend on
another library. Several are available. Instead of providing this
support, the datatype `Huge`

has been defined
(see Example 15.1). In a secure implementation we can typedef this to a
large-integer abstract datatype of our choice. The only other
requirement is that we replace each operator in expressions containing
`Huge`

integers with operations defined for
the type. For purposes of illustration in the implementation presented
here, `Huge`

is made a typedef to an unsigned
long integer, an intrinsic type that usually offers 10 decimal digits.
This means that the implementation as it exists in Example 15.4 supports keys up to only 5 decimal digits. Thus, the implementation is functional, but it would not be considered secure without redefining ...