Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

EDIT: I've been confusing this the whole time. What I've been wanting to say this whole time is addition modulo $2^{32}$ not addition modulo 32 as the question originally said. Thanks for pointing that.


I can't find any information on this and I really want to know. We discussed in class number theory and after making some proofs on division algorithms we made some modular arithmetic. It is my understanding that the definition of addition modulo $2^{32}$ is: $a +_n b = (a + b) \bmod (n)$.

So if I were to have for example 27 added to 8 modulo 32, I would have something like $(27 + 8) \bmod (32) = (35) \bmod (32) = 3$.

Is this right? Is this the same hashing algorithms talk about when mentioning addition modulo $2^{32}$? Why can't I find this anywhere?

Why isn't there a Wikipedia article with details on the addition modulo $2^{32}$ that is talked about on cryptography?

I ask if this is the same hashing algorithms talk about because in my understanding, this answer here says that in Java addition modulo $2^{32}$ is the same as simply writing "+", but I don't think a simple sum can possibly be the same. I'm totally lost.

share|improve this question
    
Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Feb 21 at 17:29
up vote 3 down vote accepted

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 longor 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, shortor 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.