Why do algebraic proofs apply to cryptography?

Question

How do we know that the number theoretic and algebraic results used in cryptography provide a perfect model for the behavior of integers as implemented in computers? Does there exist a bijection between the purely mathematical integers and the two’s complement integers, and are subsets of the two’s complement integers under the modulus operator isomorphic to the corresponding (mathematical) integers mod n?

If so, are these conditions sufficient for all cryptographic proofs relying on algebra and number theory?

Answer 1

Integer operations as implemented on computers are isomorphic to a theoretical definition of integers. Otherwise operations would not give the correct results.

Given the terminology in your question, I suspect that when you think of integer operations on a computer, you're thinking of operations on machine words. Cryptography uses numbers that don't fit in machine words: any cryptography code that works on integers (i.e. generally speaking asymmetric cryptography) must include a bignum library (or rely on a third-party one).

Two's complement is a way to represent negative integers. It's irrelevant to cryptography because cryptography pretty much never uses negative integers: only nonnegative integers ($\mathbb{N}$, or integers modulo $n$ which are stored using their representative in the range $[0,n-1]$.

You can find a formal proof of the equivalence between Peano arithmetic and arithmetic on binary representations in many places, for example in the BitNat module of Coq.

Implementing integer operations is a non-problem as far as getting the correct result, but it does have an impact on security. If the implementation is not careful, side channels such as timing and memory access patterns may leak confidential data that compromises the security of a protocol that would be secure if the adversary could not find out any information about the intermediate values.

Answer 2

We know that the number theoretic model of integers do NOT always provide a perfect or even practically suitable model for the behavior of integers as implemented in computers. Applied cryptography must take into account

• Possible overflow of a machine word (rarely larger than 64-bit, which is much smaller than used in asymmetric cryptography). That's the relatively easy part, and taken care by "bignum" libraries (built into some languages).
• Implementation errors that creep (example), often for specific compilers and hardware, rare and obscure:

  This error occurs when the DIV/DIVW instruction is interrupted and a second interrupt is generated during the execution of the IRET instruction of the first ISR.

• Data-dependent timing dependencies: bignum libraries and sometime hardware or/and compiler tend to take variable time depending on the number of machine words used and values manipulated, which can lead to key or plaintext leak. A foundational paper is Paul C. Kocher Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems (in proceedings of Crypto 1996). This is dealt with special implementations of bignum libraries tailored to either operate in constant-time, or make it hard to gather exploitable information from their residual timing variation. An important special case is comparison (memcmp library function, sometime even the equality operator ==) which is a common and easy target for timing attack.
• Other side channels like power consumption. A foundational paper is Paul C. Kocher, Joshua Jaffe, Benjamin Jun Differential Power Analysis (in proceedings of Crypto 1999).
• Faults: attacker can often force the implementation to make errors (with a laser on the IC of a Smart Card..) and deduce information from the incorrect results obtained. A foundational example is the so-called Bellcore attack: Dan Boneh, Richard A. DeMillo, and Richard J. Lipton On the importance of checking cryptographic protocols for faults (in Journal of Cryptology, 2001, originally in proceedings of Eurocrypt 1997). Here is a (dated) introduction to the practicalities.

---

On a theoretical standpoint ignoring the above issues, there is exact correspondence (isomorphism) between integers modulo $2^k$ and $k$-bit computer words for the usual unsigned binary arithmetic. Mathematical two-operand operators $+$, $-$, $\cdot$ (multiplication), $/$ (understood here as quotient of Euclidean division), and $\bmod$ (remainder of Euclidean division) precisely correspond to +, -, *, / and % in the C language (and hardware instructions when available) for variables of any unsigned type, with the possible exception of the behavior of division and remainder with value zero of the right operand (which is forbidden in math, but leads to undefined behavior or exception in computer arithmetic).

For signed integers in $k$-bit 2-complement, a similar correspondence applies for addition, subtraction, and multiplication when implementation ignores overflow (as common). Integers in range $[0,2^{k-1})$ are represented as in unsigned binary arithmetic, integers $x\in[-2^{k-1},0)$ have the machine representation that $x+2^k$ has in unsigned binary arithmetic. The representative of the residue class modulo $2^k$ lies in the interval $[-2^{k-1},2^{k-1})$ rather than $[0,2^k)$. There is no clear correspondence for quotient and remainder ( (-1)%2 may be -1 or 1 ).