Lecture 17: Encryption #2 - Public Key Systems

Addendum: Avoiding Exponentiation

One of the biggest problems (for beginners) in implementing the RSA algorithm is that of exponentiation -- raising large numbers to the power of other large numbers. In general, this is very difficult without a special-purpose "BigNum" library. However, for our "demonstration" examples we can actually use a very clever algorithm to avoid hitting "integer overflow", and still demonstrate that the numbers are correct. Here's the pseudocode for how we calculate C, the ciphertext, from P, the plaintext using the secret key K_p, defined as n concatenated with E.

C := 1
begin for i := 1 to E do
    C := MOD( C * P, n )
end

To decrypt, simply replace E with D and P with C in the above algorithm. Exercise: implement this in your favourite programming language, and prove it works...

The tutorial for this lecture is Tutorial #17.
La Trobe Uni Logo

[Previous Lecture] [Lecture Index] [Next Lecture]

previous | start