linux-kernel - Re: random.c: LFSR polynomials are not irreducible/primitive

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <5311487.93A5fcTOOn@tauon.chronox.de>
Date:   Tue, 15 Aug 2017 10:45:17 +0200
From:   Stephan Mueller <smueller@...onox.de>
To:     Theodore Ts'o <tytso@....edu>
Cc:     LKML <linux-kernel@...r.kernel.org>, linux-crypto@...r.kernel.org
Subject: Re: random.c: LFSR polynomials are not irreducible/primitive

Am Dienstag, 15. August 2017, 00:21:05 CEST schrieb Theodore Ts'o:

Hi Theodore,

> Have you looked at section 3.1.1 of the above cited paper?
> 
> 	http://eprint.iacr.org/2012/251.pdf

Thanks for the hint, but that does not seem to solve the mystery either.

When I use magma with GF(2^32), I see that all polynomials are neither 
primitive nor irreducible:

F:=GF(4294967296);
F;

P<x>:=PolynomialRing(F);
P;
print "Old polynomials:";

P<x>:=x^128 + x^103 + x^76 + x^51 +x^25 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

P<x>:=x^32 + x^26 + x^20 + x^14 + x^7 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

print "New polynomials:";

P<x>:=x^128 + x^104 + x^76 + x^51 +x^25 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

P<x>:=x^32 + x^26 + x^19 + x^14 + x^7 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);



The output is:

Finite field of size 2^32
Univariate Polynomial Ring in x over GF(2^32)
Old polynomials:
x^128 + x^103 + x^76 + x^51 + x^25 + x + 1
is irreducible:
false
is primitive:
false
x^32 + x^26 + x^20 + x^14 + x^7 + x + 1
is irreducible:
false
is primitive:
false
New polynomials:
x^128 + x^104 + x^76 + x^51 + x^25 + x + 1
is irreducible:
false
is primitive:
false
x^32 + x^26 + x^19 + x^14 + x^7 + x + 1
is irreducible:
false
is primitive:
false


Thus, I am unsure how the referenced document concludes that the new 
polynomials are irreducible over GF(2^32).

Ciao
Stephan