Mastering Algorithms with C

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 ...