|
Science Forum Index » Cryptography Forum » Questions about Galois Fields with 2^n
Page 1 of 2 Goto page 1, 2 Next
|
| Author |
Message |
| Stefan Seiffarth |
 Posted: Thu Jan 01, 2004 4:17 pm |
|
|
|
Guest
|
In GF(2^n) addition is the operation "xor"
Multiplication with x is "shl" and division through x is "shr".
I wonder if "and","or","rol","ror" also have similar "meanings" in GF(2^n) ?
I think I've read somewhere that "rol" is squaring and "ror" is squareroot,
but I can't verify that.
I would be glad if anyone could help me with that, also what would be the
irreducible polynome for GF(2^n) like GF(2^32) or GF(2^16) for something
like rol/ror (if it has any meaning at all for GF) ? (for example if i do an
operation like __asm{rol eax,3})
Regards
Stefan |
|
|
| Back to top |
|
| Gregory G Rose |
| Posted: Thu Jan 01, 2004 5:43 pm |
|
|
|
Guest
|
In article <bt22pt$e1l$02$1@news.t-online.com>,
Stefan Seiffarth <seiffart@in.tum.de> wrote:
Quote: In GF(2^n) addition is the operation "xor"
Multiplication with x is "shl" and division through x is "shr".
No, it's a bit more complicated than that. In the
standard representation , you represent the field
element modulo a degree-n polynomial P. Then
multiplication of "w" by "x" is:
if (w & (1 << (n-1))
w = (w << 1) ^ P;
else
w = w << 1;
Quote: I wonder if "and","or","rol","ror" also have similar "meanings" in GF(2^n) ?
I think I've read somewhere that "rol" is squaring and "ror" is squareroot,
but I can't verify that.
That's using a different representation of the
field (normal basis). You won't reconcile the two
operations; they can't happen at the same time.
Quote: I would be glad if anyone could help me with that, also what would be the
irreducible polynome for GF(2^n) like GF(2^32) or GF(2^16) for something
like rol/ror (if it has any meaning at all for GF) ? (for example if i do an
operation like __asm{rol eax,3})
No point giving you irreducible polynomials until
you know somewhat more. Schneier has a table of
them though.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au |
|
|
| Back to top |
|
| Gregory G Rose |
| Posted: Thu Jan 01, 2004 5:43 pm |
|
|
|
Guest
|
In article <bt22pt$e1l$02$1@news.t-online.com>,
Stefan Seiffarth <seiffart@in.tum.de> wrote:
Quote: In GF(2^n) addition is the operation "xor"
Multiplication with x is "shl" and division through x is "shr".
No, it's a bit more complicated than that. In the
standard representation , you represent the field
element modulo a degree-n polynomial P. Then
multiplication of "w" by "x" is:
if (w & (1 << (n-1))
w = (w << 1) ^ P;
else
w = w << 1;
Quote: I wonder if "and","or","rol","ror" also have similar "meanings" in GF(2^n) ?
I think I've read somewhere that "rol" is squaring and "ror" is squareroot,
but I can't verify that.
That's using a different representation of the
field (normal basis). You won't reconcile the two
operations; they can't happen at the same time.
Quote: I would be glad if anyone could help me with that, also what would be the
irreducible polynome for GF(2^n) like GF(2^32) or GF(2^16) for something
like rol/ror (if it has any meaning at all for GF) ? (for example if i do an
operation like __asm{rol eax,3})
No point giving you irreducible polynomials until
you know somewhat more. Schneier has a table of
them though.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au |
|
|
| Back to top |
|
| Roger Schlafly |
| Posted: Thu Jan 01, 2004 8:33 pm |
|
|
|
Guest
|
"Gregory G Rose" <ggr@qualcomm.com> wrote
Quote: No point giving you irreducible polynomials until
you know somewhat more. Schneier has a table of
them though.
Be sure to check the errata, or try another source. |
|
|
| Back to top |
|
| Roger Schlafly |
| Posted: Thu Jan 01, 2004 8:33 pm |
|
|
|
Guest
|
"Gregory G Rose" <ggr@qualcomm.com> wrote
Quote: No point giving you irreducible polynomials until
you know somewhat more. Schneier has a table of
them though.
Be sure to check the errata, or try another source. |
|
|
| Back to top |
|
| Stefan Seiffarth |
| Posted: Thu Jan 01, 2004 9:11 pm |
|
|
|
Guest
|
Thanks for your answers, I guess Greg was right and I mixed up the different
representations of GF(2)[x].
Stefan |
|
|
| Back to top |
|
| Stefan Seiffarth |
| Posted: Thu Jan 01, 2004 9:11 pm |
|
|
|
Guest
|
Thanks for your answers, I guess Greg was right and I mixed up the different
representations of GF(2)[x].
Stefan |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Thu Jan 01, 2004 9:22 pm |
|
|
|
Guest
|
"Stefan Seiffarth" <seiffart@in.tum.de> wrote in message
news:bt2k1c$ogj$01$1@news.t-online.com...
Quote: Thanks for your answers, I guess Greg was right and I mixed up the
different
representations of GF(2)[x].
You could argue it's a rotation not a shift for multiplication. For
example, multiplication by x in GF(2^4)[x]/(x^4+x^3+1) is
y_0 = x_3
y_1 = x_0 + x_3
y_2 = x_1
y_3 = x_2 + x_3
[if I got that right] where + is the XOR gate.
So really you just rotate the bits and XOR the msb against the "taps"
Tom |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Thu Jan 01, 2004 9:22 pm |
|
|
|
Guest
|
"Stefan Seiffarth" <seiffart@in.tum.de> wrote in message
news:bt2k1c$ogj$01$1@news.t-online.com...
Quote: Thanks for your answers, I guess Greg was right and I mixed up the
different
representations of GF(2)[x].
You could argue it's a rotation not a shift for multiplication. For
example, multiplication by x in GF(2^4)[x]/(x^4+x^3+1) is
y_0 = x_3
y_1 = x_0 + x_3
y_2 = x_1
y_3 = x_2 + x_3
[if I got that right] where + is the XOR gate.
So really you just rotate the bits and XOR the msb against the "taps"
Tom |
|
|
| Back to top |
|
| Marcel Martin |
| Posted: Thu Jan 01, 2004 9:54 pm |
|
|
|
Guest
|
Tom St Denis a écrit :
Quote:
"Stefan Seiffarth" <seiffart@in.tum.de> wrote in message
news:bt2k1c$ogj$01$1@news.t-online.com...
Thanks for your answers, I guess Greg was right and I mixed up the
different
representations of GF(2)[x].
You could argue it's a rotation not a shift for multiplication. For
example, multiplication by x in GF(2^4)[x]/(x^4+x^3+1) is
y_0 = x_3
y_1 = x_0 + x_3
y_2 = x_1
y_3 = x_2 + x_3
[if I got that right] where + is the XOR gate.
With a standard basis the result is
y_0 = x_3
y_1 = x_0
y_2 = x_1
y_3 = x_2 + x_3
This is not a rotation, this is a shift followed by a reduction, i.e.,
x_3 x^4 + x_2 x^3 + x_1 x^2 + x_0 x + 0
xor x_3 x^4 + x_3 x^3 + x_3
-----------------------------------------
x_2 x_1 x_0 x_3
+ x_3
mm
--
http://www.ellipsa.net/
mm@ellipsa.no.sp.am.net ( suppress no.sp.am. ) |
|
|
| Back to top |
|
| Marcel Martin |
| Posted: Thu Jan 01, 2004 9:54 pm |
|
|
|
Guest
|
Tom St Denis a écrit :
Quote:
"Stefan Seiffarth" <seiffart@in.tum.de> wrote in message
news:bt2k1c$ogj$01$1@news.t-online.com...
Thanks for your answers, I guess Greg was right and I mixed up the
different
representations of GF(2)[x].
You could argue it's a rotation not a shift for multiplication. For
example, multiplication by x in GF(2^4)[x]/(x^4+x^3+1) is
y_0 = x_3
y_1 = x_0 + x_3
y_2 = x_1
y_3 = x_2 + x_3
[if I got that right] where + is the XOR gate.
With a standard basis the result is
y_0 = x_3
y_1 = x_0
y_2 = x_1
y_3 = x_2 + x_3
This is not a rotation, this is a shift followed by a reduction, i.e.,
x_3 x^4 + x_2 x^3 + x_1 x^2 + x_0 x + 0
xor x_3 x^4 + x_3 x^3 + x_3
-----------------------------------------
x_2 x_1 x_0 x_3
+ x_3
mm
--
http://www.ellipsa.net/
mm@ellipsa.no.sp.am.net ( suppress no.sp.am. ) |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Thu Jan 01, 2004 10:07 pm |
|
|
|
Guest
|
"Marcel Martin" <mm@ellipsa.no.sp.am.net> wrote in message
news:3FF4DD4D.1A99B568@ellipsa.no.sp.am.net...
Quote: Tom St Denis a écrit :
"Stefan Seiffarth" <seiffart@in.tum.de> wrote in message
news:bt2k1c$ogj$01$1@news.t-online.com...
Thanks for your answers, I guess Greg was right and I mixed up the
different
representations of GF(2)[x].
You could argue it's a rotation not a shift for multiplication. For
example, multiplication by x in GF(2^4)[x]/(x^4+x^3+1) is
y_0 = x_3
y_1 = x_0 + x_3
y_2 = x_1
y_3 = x_2 + x_3
[if I got that right] where + is the XOR gate.
With a standard basis the result is
y_0 = x_3
y_1 = x_0
y_2 = x_1
y_3 = x_2 + x_3
This is not a rotation, this is a shift followed by a reduction, i.e.,
[oops yeah, my y_1 was wrong]
You say reduction I say rotate and xor the MSB into several taps. So do the
people who design this in hardware ;-)
Tom |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Thu Jan 01, 2004 10:07 pm |
|
|
|
Guest
|
"Marcel Martin" <mm@ellipsa.no.sp.am.net> wrote in message
news:3FF4DD4D.1A99B568@ellipsa.no.sp.am.net...
Quote: Tom St Denis a écrit :
"Stefan Seiffarth" <seiffart@in.tum.de> wrote in message
news:bt2k1c$ogj$01$1@news.t-online.com...
Thanks for your answers, I guess Greg was right and I mixed up the
different
representations of GF(2)[x].
You could argue it's a rotation not a shift for multiplication. For
example, multiplication by x in GF(2^4)[x]/(x^4+x^3+1) is
y_0 = x_3
y_1 = x_0 + x_3
y_2 = x_1
y_3 = x_2 + x_3
[if I got that right] where + is the XOR gate.
With a standard basis the result is
y_0 = x_3
y_1 = x_0
y_2 = x_1
y_3 = x_2 + x_3
This is not a rotation, this is a shift followed by a reduction, i.e.,
[oops yeah, my y_1 was wrong]
You say reduction I say rotate and xor the MSB into several taps. So do the
people who design this in hardware ;-)
Tom |
|
|
| Back to top |
|
| Stefan Seiffarth |
| Posted: Fri Jan 02, 2004 10:01 am |
|
|
|
Guest
|
The reason I asked was a code snippet from an university assignment:
__int16 var1;
__int16 var2;
var1 = ror16(var1, 1) ^ (~var1)&0x08000;
if( var1 & 0x08000 ) var1 ^= var2;
ror16 is rotate right on a Word.
This code snippet gets looped 32 times (and is repeated several times with
slightly different variables)
As far as I could follow you this might be a division on GF(2)[x], but I
guess I'm getting confused with
polynomial basis (the one I know) and normal basis (for hardware
implementations).
I would be glad if someone could enlighten me if this code snippet is
anything "meaningful" in GF(2)[x]
If it is "normal basis" are there any algorithms to convert normal basis
representation to polynomial basis ?
Regards
Stefan |
|
|
| Back to top |
|
| Stefan Seiffarth |
| Posted: Fri Jan 02, 2004 10:01 am |
|
|
|
Guest
|
The reason I asked was a code snippet from an university assignment:
__int16 var1;
__int16 var2;
var1 = ror16(var1, 1) ^ (~var1)&0x08000;
if( var1 & 0x08000 ) var1 ^= var2;
ror16 is rotate right on a Word.
This code snippet gets looped 32 times (and is repeated several times with
slightly different variables)
As far as I could follow you this might be a division on GF(2)[x], but I
guess I'm getting confused with
polynomial basis (the one I know) and normal basis (for hardware
implementations).
I would be glad if someone could enlighten me if this code snippet is
anything "meaningful" in GF(2)[x]
If it is "normal basis" are there any algorithms to convert normal basis
representation to polynomial basis ?
Regards
Stefan |
|
|
| Back to top |
|
| |
