# What operations are used in symmetric cryptography and why?

In continuation to Why are bitwise rotations used in cryptography?: what other operations are commonly used in symmetric cryptography? Are there particular operations on numbers that are good for building ciphers? Do common ciphers tend to use the same basic building blocks?

Some similar questions:

-
Two questions, and the first one is too broad. –  Maarten Bodewes Jul 14 '13 at 1:01
@owlstead: Agreed, though I tried to give the first a shot below. –  Reid Jul 14 '13 at 3:01
Let's focus on symmetric crypto. –  Smit Johnth Jul 14 '13 at 3:51
@owlstead Please don't use custom close reason to repeat built-in ones. It's especially confusing because this question is not off-topic, it's obviously about cryptography. It is somewhat too broad, but I've voted against closure and edited the question because I think Reid's answer is worth preserving. –  Gilles Nov 27 '13 at 19:53
@Gilles OK, I'm not particularly interested in closing questions if they are of use to anybody. If anything, I think the stackexchange off-topic thingy is a bit too strict. So if you think the question / answer is useful enough then I'm not against keeping it open. Retracted close, removed comment. –  Maarten Bodewes Nov 27 '13 at 20:03

which else operations are used in cryptography and why?

This question is hopelessly broad, but I'll give the "which" a shot. Ignoring asymmetric constructions like RSA, cryptographic primitives typically stick with operations that are either a single instruction in common architectures or can be implemented cheaply with a combination of a few instructions. Thus, bit rotations, arithmetic addition, logical bitwise operations like AND, OR, and XOR, and so on, are all good candidates for operations. Table lookups are also quite common to speed up implementations.

It's not really the operations themselves that are so important, however. The way you combine them is (obviously) far more important, and hence unless you have a specific question about why a specific operation has so much use, it's not really all that relevant to ask "what operations are used". Instead, study things like how the Merkle–Damgård construction can be used to build a hash function, how a substitution-permutation network can be used to build a block cipher, how HMAC can transform a relatively weak hash function into a good MAC. If you would like more examples, I can provide them.

These are the important building-blocks of primitives, not necessarily the operations underlying them. The operations are obviously important, but don't miss the forest for the trees.

On the other hand, you have the mathematical schemes, for lack of a better term. These use mathematics to achieve some goal, and hence the "operations" in them are virtually limitless. RSA and Diffie-Hellman both use modular exponentation, though in different ways; Shamir's secret sharing scheme relies on the idea that a $n$-degree polynomial can be uniquely identified with $n+1$ points, and so uses polynomial evaluation in a finite field as well as Lagrangian interpolation; the Merkle-Hellman knapsack cryptosystem relies on the subset-sum problem; and it just goes on and on.

There are zero-knowledge proofs, secure multiparty computation schemes, cryptographic voting schemes, fully-homomorphic encryption schemes, functional encryption schemes, identity-based schemes, ... the bounds are limitless. Trying to exhaustively list the operations used here is futile.

My point is that cryptography is a vast field. There are operations aplenty, but far more interesting are the schemes themselves. The operations are just means to an end.

What is the difference between addition modulo 2 (xor) and addition modulo 2 ^ register size (addition with overflow)?

XOR is not just "addition modulo 2"; it's bitwise addition modulo 2, and I dislike this definition. The point of bitwise exclusive-or is that the output of each bit is 1 if and only if the two input bits are different. Hence, it is an exclusive-or: exclusively, one of the bits may be turned on. If both are on, or both are off, the output is 0. This property makes XOR an involution, i.e. a function that is its own inverse. Bitwise-AND and bitwise-OR are not invertible.

Addition modulo 2^{register size} is just what it says on the tin: the addition can overflow or underflow.

-
Also, XOR being an involution makes it very convenient to use in some schemes, for instance in embedded situations it means you don't need to waste space implementing a decryption routine - decryption is exactly (or almost exactly) the same as encryption. Not that relevant today but some elements of DES were in fact designed with this in mind (also, stream ciphers) –  Thomas Jul 14 '13 at 3:30
Both xor and addition with overflow are involutions, what's the difference? –  Smit Johnth Jul 14 '13 at 3:45
"Table lookups are also quite common to speed up implementations." Secure crypto implementations should avoid using table lookups dependent on secret information because it's vulnerable to side-channel atacks. –  orlp Jul 14 '13 at 3:52
@SmitJohnth Addition with overflow isn't an involution. $\left ( x + x \right ) \mod{n} \ne 0$ in general. –  Thomas Jul 14 '13 at 3:59
@Thomas: Another compelling point is that if you XOR a uniformly random bitstring with another bitstring, no matter the distribution, the resultant bitstring will also be uniformly distributed. This is a really nice property, naturally. –  Reid Jul 14 '13 at 6:17