Take the 2-minute tour ×
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.

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
    
I think you're confusing with addition modulo $2^{32}$. This is often a source of confusion because the exponent superscript is often lost in copy-pastes, so it often becomes "232" or just "32". –  Thomas Oct 19 '12 at 7:45
    
Oh, I see. I think you are right. It must then differ, but how would it differ. You got some links on info on it? On the addition modulo $2^{32}$ I would appreciate it. –  BTent Oct 19 '12 at 8:02
    
Differ from what? It's the same concept, wrap around once you go beyond the modulus. However, the reason it works in Java (or any other programming language with finite data types, for that matter) is because when you exceed the capacity of the variable, it "wraps around" in exactly the same way, implicitly (because trying to fit too large a number in a small memory location just doesn't work) so you don't need to write it. –  Thomas Oct 19 '12 at 8:11
    
To answer your question, yes, addition modulo $2^{32}$ is exactly the same in cryptography as it is in your number theory class. It just happens to be convenient that the modulo operations are often implicitly assumed throughout cryptography just by saying "this is a 32-bit integer" which means any operation on it is inherently taken modulo $2^{32}$. Is it clearer? –  Thomas Oct 19 '12 at 8:14
    
Oh that. I thought it differed, but didn't know where so I asked. If it is the same then I think I understand. Still, let me try it. Can you please tell me when I'm right? I'm not confident I understood. So, 27 addition 8 modulo $2^{32}$ is simply 35 because $(27 + 8)mod(2^{32}) = (35)mod(2^{32}) = 35$ and that's why in Java I can put 27 + 8 which will yield 35 as result? –  BTent Oct 19 '12 at 8:38

1 Answer 1

up vote 2 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
    
Superb, very detailed explanation of everything. Let me shake your hand. With the clarification from the others and this, my day is made. The Java part was just a side note because I was confusing the modulus number, but thanks too for explaining that in detail. –  BTent Oct 19 '12 at 17:05

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.