One of the most critical mathematical concepts cryptographers need to learn is modulo arithmetic. This is an operation where we divide two integers together and throw away everything in the result but the integer remainder.
For example, 15 % 6 is read as “fifteen modulo six.” The result is calculated as:
At first glance, this doesn’t seem very useful. Let’s unpack what exactly a modulo operation gives us.
Clock functions
Imagine a clock on the wall. It has every integer represented from 1 to 12. You can never have a 22 or a 15.3 or anything outside of the set [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. Clocks make telling time relatively easy.
We could all use military time and talk about the hour as an absolute counter from midnight. In some situations this is useful as it disambiguates AM versus PM. It also makes math a bit easier – 4 hours after 11 is 15.
But most of us learned a 12-hour clock and need a better way to work in that system. In fact, a typical clock is a counting system with a modulus of 12.
If you want to know what time it will be four hours after 11, you use modulo arithmetic:
The modulo operation is considered a “clock function.” It limits the potential outputs of the function to a specific, finite range. If your operation will exceed that range, everything loops back to the beginning again. Just like the hands of a clock moving from 12 back to 1.
Why do we care?
When we work with cryptographic operations, we work with very large numbers. For asymmetric encryption as leverage exponentiation, meaning we take a large number and raise it to the power of another large number. The result … is far larger than would actually be useful.
So we leverage modulo arithmetic to keep our values within reasonable bounds.
This helps keep our cryptographic keys reasonable, but also any encrypted payloads small. The security of any encryption algorithm is based partly on the bounds within which it operates. It’s also based on the complexity of the math involved, a topic we’ll cover more later.
Mostly, though, an algorithm’s security is based on its utility. If encryption were incredibly costly either in terms of speed or the size of encrypted data, no one would use it to begin with.