Because encryption with RSA requires little more than computing ab 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
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 ...