Anyone interested in helping with a new random number generator?

[ad1mt]

...[cut]... this is not dissimilar to what a bigint multiplication does internally, but by splitting it up into individual 32bit multiplications, it does not require bigint.

I like the idea of using bigint arithmetic as part of the initialisation process, precisely because it is more CPU intensive. A small number of bigint operations will not slow down my initialisation by very much.
But in a brute-force attack, where the number of operations would be enormous, the bigint operations will significantly slow it down, which is good thing.

[Thaddy]

...[cut]... not all multipliers are good, and a lot of effort has gone into finding good ones.

In a cryptography setting, this means a reduction in the number of possibilities that have to be tested in a brute-force attack.
In my algorithm, the LCG parameters can be almost any odd number, which helps to make a brute-force attack much more difficult.

This is not true. If the odd number is weak, e.g. a multiplication where the number of divisors other than 1 > 2 the odd number is weak and based on simple math means that when one divider is found, the other divisors can be trivially retrieved. e.g in 27 where 3 can be found by probing, exposing 9 which in turn is 3 * 3. 3 is enough to break it. 9 is also enough to break it etc.
This can be simply found by prime factorization. That is the reason that in cryptography the use of a multiplication of 2 sufficiently large prime numbers is a core technique, where 1, p1, p2 are the only divisors which makes factorization very hard. That is to a certain extend also related to state: the more state is held, the harder it is to break the prng. Most lcg's have not enough state.
I already explained that your lcg does not have enough state in my opinion.
That's why I also said that if you use the same algorithm multiple times, albeit with different parameters, you make the final values likely weaker, not stronger. Your algorithm is merely a a very simple multiplier, addition by a constant and taking the modulo. That is not enough, even if you hold six states.
There is another problem: your over-use of modulo will amplify modulo bias and that is a real problem.
Investigate the theory of modulo bias. A good introduction that is not too mathematically involved is in this post: https://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator

[ad1mt]

There is another problem: your over-use of modulo will amplify modulo bias and that is a real problem.

I think I understand the problem of modulo bias...

A simple example... if a source ranges from 0..15, and you want to change that range to 0..9, then taking a modulo 10 of a random set from the source will give twice as many numbers in the range 0..5 as in the range 6..9 (am I correct? because if not, then my understanding is flawed).

The reason I think my algorithm eliminates bias... is the random nature of my LCG parameters creates multiple biases which "even out" over the six LCG instances.

In my experiments, I found that a "tipping point" is reached around 4 or 5 LCGs, where the combined output becomes good. That is why I chose to have 6.  With only 2 or 3 LCG's, the output can be seriously flawed.

However, if my RNG output was suffering from bias, I would assume Practrand would highlight that... it fails single LCG output even when the parameters known good ones.

[ad1mt]

...[cut]... your lcg does not have enough state in my opinion.

I'm not sure understand the concept of "enough state".
Is an alternative way of describing it as "the number of possible output PRNs before repetition"?

[Nitorami]

Different question

- are you sure your Microdays, or whatever you use to initialise the PRNG, is always a large value, and above approx. 1 shl 50 (depends on password length ) ? Because, when using a smaller qword, I consistently get a seed underflow error.

- I init a T_PRNG_record_rd and call it repeatedly. Injecting a simple writeln command, I see that the the rand_repeat_test is entered repeatedly, but the result is never true, even after 100 million calls. I thought that on a "true" the "modupliers" shall be changed, but it seems they aren't ?

[ad1mt]

I init a T_PRNG_record_rd and call it repeatedly. Injecting a simple writeln command, I see that the the rand_repeat_test is entered repeatedly, but the result is never true, even after 100 million calls.

If I was using a fixed set of LCG parameters, I could pre-calculate the period. But its not possible to do this beause every instance of the PRNG uses a different random set of parameters, and the period will be different every time.
So I call rand_repeat_test for every PRN output, and if repetition is detected, rand_repeat_test returns true.
The LCG seeds are only recalculated when repetition is detected.
Does that answer your question? I might have misunderstood your point here.

[Nitorami]

Yes, and that is how I imagined it works. But then it is unlikely that the parameters change during encryption, so the repeat detection triggered parameters change is not an argument for the strength of the algorithm .

[ad1mt]

- are you sure your Microdays, or whatever you use to initialise the PRNG, is always a large value, and above approx. 1 shl 50 (depends on password length ) ? Because, when using a smaller qword, I consistently get a seed underflow error.

Can I check that you are using the latest version 4.8?
This version has a better algorithm that should make PRNG_seed underflow impossible.

[ad1mt]

Yes, and that is how I imagined it works. But then it is unlikely that the parameters change during encryption, so the repeat detection triggered parameters change is not an argument for the strength of the algorithm .

I'm not sure I understand your point here.
In cryptography the PRN stream is xor'd against the data stream, and a potential weakness occurs when the PRN stream period is significantly shorter than the data stream. In that case, two sections of encrypted data with repeated PRNs can be xor'd against each other, which will cancel out the PRN component leaving just the two data streams xor'd together, which then become much easier to break.
If I can ensure that the PRN stream never repeats, or repeats only at astronomical numbers, then above weakness no longer applies.  Yes, I know the period will not really be infinite, but providing the PRN stream period is not shorter than the data stream length, that weakness disappears.
You would only need to enable the "infinite period" option for data sets that were astronomical in size, or for long running data streams.

[Nitorami]

Version: I used the one from your encryption example in the link. May not be the latest one but I am just travelling and cannot check.

On the repeat detect, that was a misunderstanding. I was under the impression that a frequent modupliers change was an argument for strength, but in fact it is only a safety net. I may have been biased by Melissa's shift algorithm which changes on every call. Anyway, Personally I don't like the idea to add a lot of code , complexity, and probably sacrifice efficiency just to work around the rather small  risk of a small period, introduced by the fixed idea that parametets choice should be as free as possible, to maximize the search space for attackers.

[Thaddy]

In cryptography the PRN stream is xor'd against the data stream,

This is not always true. Some of the strongest algorithms use rol/ror instead of xor. It is just that xor is usually fast.
The major traits from xor and rotation is that they are all reversable and do not loose precision: will not over or underflow on unsigned values.
The major difference is that xor adds entropy, but rotation preserves entropy while adding diffusion.
When designing a prng you have the choice. Both methods are fine if the generated value before the operation is good enough.

[ad1mt]

On the repeat detect, that was a misunderstanding. I was under the impression that a frequent modupliers change was an argument for strength

I think it is an argument for strength in a cryptography setting, because of the weakness when RNG stream period is shorter than the data set.

Personally I don't like the idea to add a lot of code , complexity, and probably sacrifice efficiency just to work around the rather small  risk of a small period, introduced by the fixed idea that parametets choice should be as free as possible, to maximize the search space for attackers.

I agree with you here, which is why I made "infinite period" optional.
I've done many tests of example sets of parameters, where I tried to discover the period by brute-force. I was never able to find what the period was, but it was always very large (gigabytes), and large enough to eliminate the weakness of periods shorter than the dataset.

[ASBzone]

I keep being told that "I should not design my own encryption",

Because designing good encryption is non-trivial...

[Thaddy]

Hea, hear...

[ad1mt]

Because designing good encryption is non-trivial...

1. I like a writing code to solve difficult problems, it's a hobby of mine.
2. I'm not asking/forcing anyone else to use my library.
3. If you know a lot about encryption, please explain what I'm doing wrong.