2
$\begingroup$
  1. what does ROTL stand for? I know it does left shifting but what about the acronym?
  2. When we do a left shift, do we take the leftmost bit and add it at the end, by making the second bit the first, and the third the second... and the first the last ? OR, we remove the first bit, and add a 0 at the end? left shifts have been used in DES key generation and SHA-1 algos.
$\endgroup$
7
$\begingroup$

In computer science, and implementation of crypto, ROTL stands for ROTate Left. ROTL is also noted ROL, or RLNC for Rotate Left No Carry.

"Rotate left through carry" by Cburnett - Licensed under CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0/) via Wikimedia Commons

On a $w$-bit word with bits numbered from $0$, bit number $j$ of the input of ROTL with a shift count of $n$ goes to bit $j+n\bmod w$ of the result; $n=1$ unless otherwise specified (and is the only value available on some hardware).

The venerable VAX has a ROTL instruction. The recent ST40 also. Most modern CPUs have it under some name, sometime (e.g. ARM) indirectly, by doing a right shift with count $-n\bmod w$. Your millage may vary according to CPU brand regarding the state of the Carry bit after ROTL or equivalent (same as bit $0$ of the result, unchanged..), with additional twist depending on if the shift count modulo $w$ is $0$ or not.

From the comfort of the C or C++ language, the result of ROTL of a $w$-bit unsigned value $x$ by $n$ bit(s) with $0<n<w$ (and sometime other $n$) is x<<n | x>>(w-n), and some compilers even manage to recognize that idiom and use the built-in CPU instruction when there is one (typically for $w$ some power of two from $2^3$ to $2^6$) and the alignment of planets is favorable appropriate options and surrounding conditions are met, typically including $w$ and $n$ being constants; on some others, there's a compiler intrinsic, with names like __i64_rotl, __lrotl, __rotl, _rotl16,_rotl8, etc..

Rotation by a constant is very common in cryptographic primitives, typically in combination with addition $\pmod{2^w}$ and bitwise operators such as exclusive-OR, in order to speed-up diffusion, and create it in the first place for diffusion of left bits to right bits. Examples include hashes like SHA-1 and SHA-256 (which heavily use $w=32$-bit rotations) and SHA-512 ($64$-bit rotations); and some ciphers like Serpent, Salsa-20.
A different use occurs in DES, where rotation of two $w=28$-bit registers is used in the key schedule; there, the intent is to vary which bit gets fed to the S-Box inputs.
Some ciphers, notably RC5, use rotation by a data-dependent count, which has some virtues (and implementation drawbacks, including abyssal slowness on some low-end CPUs, and making attack by data-dependent timing at least conceivable).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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