Modular Arithmetic

Before we look at the code in the RSA program example, let's first understand a bit more about modular arithmetic. Modular arithmetic is used in many cryptographic systems, including RSA, DSA, and SSL. The algebraic structure that is used is referred to as Z _n , which is the set of nonnegative integers modulo n. Z _n consists of the set {0, 1, 2, , n “ 1} along with operators defined for addition and multiplication. Note that Z _n is integer arithmetic on a finite circle, not an infinite number line. Z _n is sometimes referred to as clock arithmetic, since a twelve hour clock implies Z ₁₂ arithmetic.

For example, Z ₁₂ would be the set of numbers from 0 to 11, with addition defined much like regular addition, but any result over 11 (the modulus minus one) is wrapped around starting back at zero. So, in Z ₁₂ , 1 + 0 = 1, 1 + 1 = 2, and 3 + 5 = 8. However, when an addition would normally go beyond 11, then the modular wraparound takes effect. For example, 10 + 5 = 3, not 15. Regular arithmetic would have 10 + 5 = 15, but 15 is greater than 11, so in modular arithmetic, with a modulus of 12, 10 + 5 is actually 15 “ 12, which is 3. As another example, 5 + 7 would produce 0 rather than 12, since 12 “ 12 = 0. The idea behind modular arithmetic is that given a value for a modulus, you will never have to deal with any quantities equal to or greater than the modulus. In powerful and peculiar ways, this trick provides extraordinary advantages when dealing with the implementation of asymmetric cryptographic algorithms. Of course, in algorithms such as RSA, you never work with a tiny modulus like 12, but, rather, you work with a much more computationally significant modulus.