# [Cryptography] Exotic Operations in Primitive Construction

Sid Spry sid at aeam.us
Fri Oct 2 21:38:54 EDT 2020

```On Fri, Oct 2, 2020, at 4:08 AM, Dave Horsfall wrote:
> On Wed, 30 Sep 2020, Peter Gutmann wrote:
>
> > If you're referring to an implementation in C, it's not even that any
> > more, any compiler from the last 15-20 years has a rotate recogniser and
> > will translate 'x << y | x >> ( wordsize - y )' into a single rotate
> > instruction.
>
> As another followup (and I'm not trying to turn this into a C forum), but
> can anyone think of a way to flip an n-bit word around i.e. LSB becomes
> MSB etc?
>

Generally as follows. For simplicity's sake I've removed the container
type you need to store an arbitrary sized number. You should see the
size of the type as a potential parameter.

uint16_t reverse(uint16_t v) {
uint16_t r = 0;
for (int i = 0; i < 16; i++) {
r |= (((1 << i) & v) >> i) << (15 - i);
}
return r;
}

> Assume that "n" is not necessarily a power of 2, just for generality; the
> best that I can think of is a 1-bit wide stack.
>

To know the best way to do this efficiently you'd have to know why you are
doing it. You could generalize the algorithm above in a way compatible with
how GNU's BigNum library works, but you could potentially store the
information you are representing with the bits as something else entirely.

> After much reading, it seems that most (if not all) crypto systems assume
> that powers of 2 are somehow magical, because of today's computers.
>
> Well, I've used a 12-bit box (PDP-8) and 60-bit (CDC), so I was
> wondering...
>

This is exactly why I asked the question. I had begun to wonder if rotation
was an operation that could be analyzed in an algebraic way, especially
for other digit systems. Perhaps I should have asked that explicitly, but I