[Cryptography] Exotic Operations in Primitive Construction

[Sid Spry]

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
also wanted to ask about other hard to generalize operations.

Reversing the representation of a number seems like a good one. I'm going
to speak to more replies, but I'm trying to figure out what I meant to ask.

Cheers.