What is modular arithmetic?
I was looking into RSA, an asymmetric cryptosystem. The RSA algorithm relies on “modular exponentiation”. But what is modular exponentiation, and what are the properties of modular exponentiation that make it useful for cryptography?
Let’s start with exponentiation. You likely saw exponentiation in school. 37, or “3 to the power 7”, is 3 multiplied by itself 7 times, 3×3×3×3×3×3×3, or 2187. Modular exponentiation is the same operation, modulo some natural number.
You might have seen modular arithmetic in school.
You’ve certainly worked with modular addition when telling the time.
Modular arithmetic is arithmetic where the numbers “wrap around”.
In normal addition, 3+11 is 14,
but on a 12-hour clock-face, 3+11 is 2. (3am + 11 hours = 2pm.)
Computers often use modular arithmetic, with a power-two modulus.
Addition over unsigned char values does arithmetic modulo 256.
For example, what is 156+240 in unsigned chars?
140. 156+240 = 396. 396 hours around a 256-hour clock reaches 140.
There are modular versions of all the normal operations,
such as addition, subtraction, multiplication, and exponentiation.
What is 3×5 on the clock-face?
3. Compute 3×5 = 15,
then count 15 hours around the clock-face from noon.
In traditional notation, we write 3×7 ≡ 3 (mod 12). This relation a ≡ b (mod n) can be defined in terms of normal equality: a = b+kn. For example, 38 = 17 + 3×7, so we can say 38 ≡ 17 (mod 7), taking k = 3. Notice we can also say 38 ≡ 17 (mod 3), taking k = 7. What k shows that 15:00 is 3pm, i.e. that 15 ≡ 3 (mod 12)? k=1. 15 hours around the clock goes once around, then three hours more.
Addition is iterated stepping, multiplication is iterated addition, and exponentiation is iterated multiplication. All this is true in normal arithmetic and in modular arithmetic. We can define these naïvely in C:
#include <stdio.h>
#include <stdint.h>
typedef unsigned int uint;
uint mod_incr(uint x, uint n) { return (x+1 == n) ? 0 : x+1; }
uint mod_add(uint a, uint b, uint n) { uint x = a; while (b--) x = mod_incr(x,n); return x; }
uint mod_mul(uint a, uint b, uint n) { uint x = 0; while (b--) x = mod_add(x,a,n); return x; }
uint mod_exp(uint b, uint e, uint n) { uint x = 1; while (e--) x = mod_mul(x,b,n); return x; }
int main(void) {
printf("3 + 11 = %u (mod 12)\n", mod_add(3, 11, 12));
printf("3 * 7 = %u (mod 12)\n", mod_mul(3, 7, 12));
printf("11 ^ 8 = %u (mod 12)\n", mod_exp(11, 8, 12));
return 0;
}$ clang main.c
$ ./a.out
3 + 11 = 2 (mod 12)
3 * 7 = 9 (mod 12)
11 ^ 8 = 1 (mod 12)Every time the number is operated on (incremented),
the above algorithm checks whether the number has wrapped around,
and if so, resets it to zero.
But there’s another way to compute a modular expression:
compute it in ordinary arithmetic,
then apply the “modulo” at the end.
In C, we can redefine our functions using the % (remainder) operator.
(This is equivalent as long as the numbers are non-negative.)
uint mod_incr(uint x, uint n) { return (x+1) % n; }
uint mod_add(uint a, uint b, uint n) { return (a+b) % n; }
uint mod_mul(uint a, uint b, uint n) { return (a*b) % n; }
uint mod_exp(uint b, uint e, uint n) { uint x = 1; while (e--) x *= b; return x % n; }In normal arithmetic over the integers, each of these operations has an inverse. Subtraction is the inverse of addition, because (a + b ) - b = a. The inverse of multiplication is division, because (a×b) / b = a (unless b is zero!). And exponentiation has as its inverse the “nth root”: b√(a b) = a. There are inverses in modular arithmetic, too, but they don’t work how you might expect!
Say you’re at noon, then go forward 3 hours. How do you undo this operation? How do you undo “going 3 hours around the clock-face”? One answer is “by going back 3 hours”. But another answer is “by going forward until you loop back to the original time”. So in clock arithmetic, the inverse of +3 is +9 (adding 3 then adding 9 leaves you in the same place). In general, for modulus n, the inverse of +b is +(n-b).
How about the inverse of multiplication and exponentiation? This gets closer to the territory of the RSA algorithm, and I’ll cover them in future posts.
This page copyright James Fisher 2017. Content is not associated with my employer.
TigYog
Kickabout