In cryptography, addition modulo $n$ (where $n$ is a positive integer, maybe $n=32$ as in the original question, or $n=2^{32}$ as in the revised question) is usually understood as the application from $\mathbb Z\times \mathbb Z$ to $\mathbb Z$, $(a,b)\mapsto c$ with $c$ such that $0\le c<n$ and $(a+b-c)$ is a multiple of $n$. That's also a common sense in math, although there the result could rather be in $\mathbb Z/n\mathbb Z$ (recall $\mathbb Z$ is the set of signed integers, whereas $\mathbb Z/n\mathbb Z$ is the set of equivalence classes of the relation: equal modulo $n$).
We may write $(a+b)\bmod n=c$ using \bmod
in $\TeX$. This implie $a+b\equiv c\pmod n$ using \pmod
in $\TeX$, but only the former restrict $c$ to be in range $[0\dots n-1]$.
When the modulus $n$ is the $k$-th power of $2$ ($n=2^k$), addition modulo $n$ is also called $k$-bit addition. Thus, addition modulo $32$ is the same as $5$-bit addition, and addition modulo $2^{32}$ is the same as $32$-bit addition.
Often, in cryptography, we assimilate numbers to bitstrings, and the output $c$ of the operator is not a number, but rather a bitstring representing $c$ in base $2$ (over exactly $\lceil \log_2n\rceil$ bits and most significant bit first unless otherwise stated).
Thus the result of addition modulo $32$ of $27$ and $8$ is the integer $3$, or the bitstring 00011
, depending on context. And the result of addition modulo $2^{32}$ of $2000000000$ (0x77359400
) and $3000000000$ (0xB2D05E00
) is $705032704$ (0x2A05F200
) or the bitsring 00101010000001011111001000000000
, because $5000000000-705032704=2^{32}$.
Sometime the inputs $a$ or $b$ of the operator are restricted to be non-negative, or/and less than $n$, or/and bitstrings, perhaps of fixed or limited size. Sometime the output range for $c$ is $-n/2\le c<n/2$ rather than $0\le c<n$ (e.g. for implementation of 32-bit addition in contexts lacking unsigned 32-bit type, see below). YMMV.
There is a Wikipedia entry on modular arithmetic which is a better introduction to that subject, but lacks the specialization to crypto and discussion on bitstrings.
The following discussion is exclusively about Java (except for restrictions of the language in some Java Cards, which may not support type long
or even int
), and thus somewhat off-topic here, but well.
When working with variables of type long
(also int
, short
, byte
) (a+b)&0xffffffffL
is the sum of a
and b
modulo $2^{32}$ in the cryptographic sense, and of type long
. That &0xffffffffL
technique works for operators + - * & | ^ ~
(but not % /
). It can be extended to any modulus $n=2^k$ with $0\le k\le63$ by adjusting the constant, which is $n-1$. Further, when $0\le k\le31$ we can remove the L
, and if both a
and b
are of type int
, short
or byte
, the result will be of type int
.
The definition of operators + - * & | ^ ~
(but not % /
) operating on int
variables is such that you can get along with assuming these operators work modulo $2^{32}$ as defined in cryptography, except that numbers in range $[2^{31}\dots 2^{32}-1]$ are represented as a negative int
in Java. This makes code clearer, simpler, faster, and (for arrays) conserves memory. That technique is used because, before Java 7, there was no unsigned type in Java.
For n
of type int
in range $[1\dots2^{31}-1]$ and operands a
and b
of type int
in range $[0\dots2^{30}-1]$, (a+b)%n
is the sum of a
and b
modulo n
in the cryptographic sense, and of type int
. This does not hold for the full range of input operands for two independent reasons:
- when the left operand of operator
%
is negative and not a multiple of the right operand, the result is negative;
(a+b)
is defined to be the integer $c$ with $-2^{31}\le c<2^{31}$ and $c\equiv a+b\pmod{2^{32}}$, from which it follows that sometime $(\mathtt{(a+b)\%n})\not\equiv (a+b)\pmod n$ (though that second issue can not occur when $n$ is a power of two, including for $n=32$).
Notice that, except for educative/testing purposes, it is seldom a good idea to implement a cryptographic primitive in Java: in production, one should use more efficient primitives called from Java.