Desiderata of a "hypothetical" PL extension
in [Cryptography]
|
Prev: Keys Made Easier
Next: Popular Cryptography Magazine
From: Mok-Kong Shen on 26 Jun 2010 09:02 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. I could tentatively think of the following concerning unsigned long int: 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.) Thanks. M. K. Shen
From: Maaartin on 26 Jun 2010 10:09 On Jun 26, 3:02 pm, 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. I could tentatively > think of the following concerning unsigned long int: You need no real language extensions, just functions and a compiler which translates them efficiently. > Carry-over of addition. ??? > Double-length result of multiplication. You can write int64 f(int32 x, int32 y) {return (int64) x * y;} and hope the compiler generates the appropriate machine code. > Division with a double-length dividend. The same. > Circular shift. You can write int32 f(int32 x, int32 distance) {return (x<<distance) | (x>>(32- distance));} and hope again (this actually happens with gcc). > m-th bit (and m1-th - m2-th bit range) operations. This is not very useful. > Parity. Getting only one bit result can't be very useful. > Reversal of bit order. This would be funny, but I'm unaware of a CPU doing this. There's a reversed carry chain addition implemented by many DSPs, which would be surely useful in crypto. > Bit count. (Of the last I have only heard its having been used > in crypto in the past but not how.) http://en.wikipedia.org/wiki/CLMUL_instruction_set Because of the huge amount of necessary analysis work, modern crypto uses only operations available on all architectures, concentrating on the cheapest ones. There's hardly anything my CPU couldn't do much faster than my HD feeds the data, but there are a lot of tiny devices which could profit from better algorithms.
From: Mok-Kong Shen on 26 Jun 2010 10:36 Maaartin wrote: > Mok-Kong Shen 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. I could tentatively >> think of the following concerning unsigned long int: > > You need no real language extensions, just functions and a compiler > which translates them efficiently. But it is desirable to have coding efficiency (i.e. writing less). >> Carry-over of addition. > ??? Useful e.g. for coding multiple-length multiplicatons. >> Double-length result of multiplication. > You can write > int64 f(int32 x, int32 y) {return (int64) x * y;} > and hope the compiler generates the appropriate machine code. If one can declare int64 'normally', which is apparently what is assumed above, than the double-length would be an 'int 128'. > >> Division with a double-length dividend. > The same. > >> Circular shift. > You can write > int32 f(int32 x, int32 distance) {return (x<<distance) | (x>>(32- > distance));} > and hope again (this actually happens with gcc). But I want to simply write x>>>c. > >> m-th bit (and m1-th - m2-th bit range) operations. > This is not very useful. I think that simply way of writing set bit and mask operations may be convenient. M. K. Shen
From: pomerado on 26 Jun 2010 16:36 On Jun 26, 7:09 am, Maaartin <grajc...(a)seznam.cz> wrote: > On Jun 26, 3:02 pm, 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. I could tentatively > > think of the following concerning unsigned long int: > > You need no real language extensions, just functions and a compiler > which translates them efficiently. > > > Carry-over of addition. > > ??? > > > Double-length result of multiplication. > > You can write > int64 f(int32 x, int32 y) {return (int64) x * y;} > and hope the compiler generates the appropriate machine code. > > > Division with a double-length dividend. > > The same. > > > Circular shift. > > You can write > int32 f(int32 x, int32 distance) {return (x<<distance) | (x>>(32- > distance));} > and hope again (this actually happens with gcc). > > > m-th bit (and m1-th - m2-th bit range) operations. > > This is not very useful. > > > Parity. > > Getting only one bit result can't be very useful. > > > Reversal of bit order. > > This would be funny, but I'm unaware of a CPU doing this. There's a > reversed carry chain addition implemented by many DSPs, which would be > surely useful in crypto. > > > Bit count. (Of the last I have only heard its having been used > > in crypto in the past but not how.) > > http://en.wikipedia.org/wiki/CLMUL_instruction_set > > Because of the huge amount of necessary analysis work, modern crypto > uses only operations available on all architectures, concentrating on > the cheapest ones. There's hardly anything my CPU couldn't do much > faster than my HD feeds the data, but there are a lot of tiny devices > which could profit from better algorithms. "Hope" shouldn't enter into it.
From: Mok-Kong Shen on 26 Jun 2010 17:07
Maaartin wrote: > Mok-Kong Shen wrote: >> Parity. > Getting only one bit result can't be very useful. A computation I could imagine is transformation of a vector of 32 bit elements (a word) by multiplying it with a non-singular 32*32 bit matrix (represented as 32 words) in Z_2. One could 'and' a row vector of the matrix with the given vector and then take the parity to get one element of the result vector. M. K. Shen |