Score:0

PRNG based on GF?

tf flag
Tom

Are there any pseudo random number generator based on Galois fields? The source of the AES randomness lies in the GF, so GF should be capable of generating random bits.

Why are there no such generators?

poncho avatar
my flag
Well, AND gates do multiplication in $GF(2)$, while XOR gates do addition. All circuits can be built out of these primitives, hence any logic expressible as a circuit (including a PRNG) can be viewed as being based in that finite field...
Score:1
si flag

There are several generators that use finite fields. Blum Blum Shub uses one directly, but is very slow. AES-CTR-DRBG is a CSPRNG that uses AES-128 in CTR mode, thereby indirectly using a finite field. It's fast enough for practical use, particularly with the hardware accelerated AES instructions many modern processors have.

poncho avatar
my flag
Technically, the Blum Blum Shub number is based on a ring with nontrivial ideals, hence it is not a finite field...
Score:1
sa flag

I don't understand what you mean by The source of AES randomness lies in the G(alois) F(ield).

A field is an algebraic structure, it has no randomness. You can think of classical information theoretic randomness, which is a property of a probabilistic source. The source is used to generate a seed, and the seed can be taken to be an element of the field, with an update mapping based on the algebraic structure of the field.

Even if you wanted to think in terms of Kolmogorov complexity as a measure of "randomness" and took a binary extension Galois field and thought of its individual elements as bitstrings, some of those elements will have short descriptions, some not, but the field is just a passive structure.

In addition to the nice examples in the other answer of generators making use of finite fields, the following also use finite fields:

  1. Maximum length sequences ($m-$sequences) use LFSRs with connection polynomial a primitive polynomial $f(x)$ of degree $n$ over $GF(2)$ and the clocking of the state corresponds to multiplying by a primitive element in the extension field $$GF(2^n)=GF(2)/(f(x))$$
  2. You can take an $m-$sequence which is vulnerable to the Berlekamp Massey attack and apply a nonlinear boolean function to some of the state bits. The properties needed (nonlinearity, resilience, algebraic immunity, etc) for such a filtering function to lead to a more secure output sequence are proved by using Galois fields. See for example the answer to this question for some of these properties: https://crypto.stackexchange.com/questions/34946/how-are-boolean-functions-used-in-cryptography/
  3. You can also take multiple LFSRs and apply a nonlinear function to their output. Similar comments as in 2 above apply.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.