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?
1
-
$\begingroup$ 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... $\endgroup$– ponchoSep 4, 2021 at 3:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Technically, the Blum Blum Shub number is based on a ring with nontrivial ideals, hence it is not a finite field... $\endgroup$– ponchoSep 4, 2021 at 3:28
$\begingroup$
$\endgroup$
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:
- 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))$$
- 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/
- You can also take multiple LFSRs and apply a nonlinear function to their output. Similar comments as in 2 above apply.
