Prev: Keys Made Easier
Next: Popular Cryptography Magazine
From: Globemaker on 27 Jun 2010 06:15
On Jun 26, 9:02 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> I like to learn what basic operators or functions (values) would be
> deemed desirable/convenient for a "hypothetical" extension of a general
> purpose programming language like C (eventually with corresponding
> extension in common hardware instruction set for achieving execution
> efficiency) for potential crypto-related coding.

The modular multiplication of 2048 bit numbers is a function that
microprocessor designers have considered adding to their silicon
chips. This function has quietly been added to a few microprocessors
so RSA can be done quickly.
http://eprint.iacr.org/2004/198.pdf
Montgomery and Quisquater enhancements are recommended, so they
"perform squaring about twice faster than general multiplications or
modular reductions.".
From: Bryan on 27 Jun 2010 21:14
Maaartin wrote:
> Mok-Kong Shen wrote:
> > Circular shift.
>
> You can write
>
> int32 f(int32 x, int32 distance)
> {return (x<<distance) | (x>>(32-distance));}

Well, that might not be so good. First, you definitely want to use an
unsiged integer type.

Second, C's required integer types guarantee a minimum bit width, but
not a maximum, so you should mask the result to 32 bits. A good
compiler will optimize away the mask if the actual width is 32 bits.
C99 implementations may (but are not required to) define uint32_t in
stdint.h, and if defined it is an unsigned integer of exactly 32 bits,
so in that case there is no need to mask.

Finally, there's the gotcha of what happens if we call f() with a
distance of 0 or 32 . One of the shifts would get a right operand of
32, which is probably the width of the left operand. From ISO/IEC
9899:1999 section 6.5.7 "Bitwise shift operators", paragraph 3:

If the value of the right operand is negative or is greater than
or equal to
the width of the promoted left operand, the behavior is undefined.

So at the very least f() needs a comment saying that the distance
parameter must be from 1 to 31 inclusive.

Also, in C99 we'd probably want to declare f() "inline", and in older
C we might want to write it as a macro.


--
--Bryan Olson
From: Maaartin on 28 Jun 2010 01:44
On Jun 28, 3:14 am, Bryan <bryanjugglercryptograp...(a)yahoo.com> wrote:
> Maaartin wrote:
> > Mok-Kong Shen wrote:
> > > Circular shift.
>
> > You can write
>
> > int32 f(int32 x, int32 distance)
> > {return (x<<distance) | (x>>(32-distance));}
>
> Well, that might not be so good. First, you definitely want to use an
> unsiged integer type.
>
> Second, C's required integer types guarantee a minimum bit width, but
> not a maximum, so you should mask the result to 32 bits. A good
> compiler will optimize away the mask if the actual width is 32 bits.
> C99 implementations may (but are not required to) define uint32_t in
> stdint.h, and if defined it is an unsigned integer of exactly 32 bits,
> so in that case there is no need to mask.
>
> Finally, there's the gotcha of what happens if we call f() with a
> distance of 0 or 32 . One of the shifts would get a right operand of
> 32, which is probably the width of the left operand. From ISO/IEC
> 9899:1999 section 6.5.7 "Bitwise shift operators", paragraph 3:
>
>     If the value of the right operand is negative or is greater than
> or equal to
>     the width of the promoted left operand, the behavior is undefined..
>
> So at the very least f() needs a comment saying that the distance
> parameter must be from 1 to 31 inclusive.

Agreed with everything, except for the comment, which I consider
useless. I'd either write it in a way which works always, or call it
rotateLeftIfDistanceBetween1And31; otherwise there will be a problem
some day somewhere.

It's quite fascinating what has been done in C in the name of the
speed. Literally dozens of partially defined build-in types,
operations doing what you want just sometimes. One need to be very
careful when doing anything and I shouldn't have been so sloppy when
posting this.

> Also, in C99 we'd probably want to declare f() "inline", and in older
> C we might want to write it as a macro.
From: Mok-Kong Shen on 29 Jun 2010 03:26
Mok-Kong Shen wrote:
[snip]
> Carry-over of addition. Double-length result of multiplication.
> Division with a double-length dividend. Circular shift. m-th bit
> (and m1-th - m2-th bit range) operations. Parity. Reversal of bit
> order. Bit count. (Of the last I have only heard its having been used
> in crypto in the past but not how.)

There was a rumour that bit count (population count) was first included
in the instruction set of some hardware due to demands from agencies.
IMHO it could be useful in investigating avalanche.

M. K. Shen

First  |  Prev  | 
Pages: 1 2
Prev: Keys Made Easier
Next: Popular Cryptography Magazine