Proposal for a non-periodic CPRNG (WARNING: CROSSPOST!)

S

sebastian

I'd like to present a new variation of the standard Shrinking LFSR Generator (SLG) that, with just a few slight modifications, achieves both non-periodicity and a significantly improved level security. An SLG is of course currently considered impervious to cryptoanalysis except for the case where the characteristic polynomial is known (ie: public). So the first modification proposed is to have the polynomial change somehow over time. In this casewe'll simply increment the polynomial's binary representation whenever theLFSR's internal state has completed a complete cycle (which will be of course some length on [2, (2^N)-1], where N is the degree of the polynomial). The next modification is to dynamically increase the size of the LFSR whenever an overflow of the polynomial's binary representation is imminent. As an arbitrary convention (and better suggestions are certainly welcome here),the internal state of the LFSR is set to the seed and the binary representation of the polynomial is set to seed + 1. That's basically it!

In summary, the new design should demonstrate the following properties:

1) Non-periodicity;
2) Security; Implied by the current consensus that the only weakness of theSLG is the "known polynomial predicament".
3) Memory efficiency; This is implied by the fact that we are merely incrementing the polynomial's binary representation, and that for any given N thenumber of characteristic polynomials with maximal period ((2^N)-1) is T(N)where T is Euler's totient function, so of course the result is a very slow rate of growth indeed. To illustrate the point, if we were to imagine running the generator non-stop for a trillion years on today's computers, the amount of working memory needed would be much less so than what would be required to store the information contained in this very sentence!
4) Low algorithmic complexity; This is of course somewhat of a subjective statement, but just as an example, a very lightly optimized proof-of-conceptprogram written by the author was capable of producing about 3 million output bits per second. A highly optimized version might have produced 2 or 3 times as much, I imagine.
5) Capable of producing "sufficient" randomness; Implied by what research has been done on SLG's as well as the empirical evidence (albeit meager) that has been gathered thus far by the author. Up to this point, the testing Ihave conducted essentially amounts to running the output of the generator through the ENT tool and several file compressors. In the latter case, compression levels consistently amounted to 2% or less for streams up to 3000 bytes and 0% for anything larger, suggesting a high degree of entropy. A fair representation of the type of results obtained from the ENT tool are as follows:

Entropy = 7.999800 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 277.12, and randomly
would exceed this value 16.31 percent of the times.

Arithmetic mean value of data bytes is 127.4699 (127.5 = random).
Monte Carlo value for Pi is 3.146724587 (error 0.16 percent).
Serial correlation coefficient is 0.000509 (totally uncorrelated = 0.0).

6) Bit-width neutrality; There is no need for carefully chosen "magic constants" which depend so delicately on machine word size and other such factors, and the input seed can be any arbitrary value whatsoever, even one whosemagnitude is several thousand bits or what have you.
7) Simplicity; The algorithm is arguably trivial to understand, easy to implement, and overall analysis of the algorithm should invariably prove to bea relatively straight-forward task.

A proof-of-concept implementation of the algorithm written in the C programming language can be found here (http://tinyurl.com/moar-zip). I would sincerely appreciate any comments relating to the algorithm, the source code, or anything else that may be relevant to the discussion here.
 
R

red floyd

I'd like to present a new variation of the standard Shrinking LFSR Generator (SLG) that, with just a few slight modifications, achieves both non-periodicity and a significantly improved level security. An SLG is of course currently considered impervious to cryptoanalysis except for the case where the characteristic polynomial is known (ie: public). So the first modification proposed is to have the polynomial change somehow over time. In this case we'll simply increment the polynomial's binary representation whenever the LFSR's internal state has completed a complete cycle (which will be of course some length on [2, (2^N)-1], where N is the degree of the polynomial). The next modification is to dynamically increase the size of the LFSR whenever an overflow of the polynomial's binary representation is imminent. As an arbitrary convention (and better suggestions are certainly welcome here), the internal state of the LFSR is set to the seed and the binary representation of the
polynomial is set to seed + 1. That's basically it!
[redacted]
A proof-of-concept implementation of the algorithm written in the C programming language can be found here (http://tinyurl.com/moar-zip). I would sincerely appreciate any comments relating to the algorithm, the source code, or anything else that may be relevant to the discussion here.

May I point out that you're off topic here? You might want to try
sci.crypto or comp.lang.c? C and C++ are separate languages, and
Crypto PRNG algorithms are better addressed by cryptographers, not
developers who may or may not have the necessary background.
 
S

Sebastian Garth

May I point out that you're off topic here? You might want to try
sci.crypto or comp.lang.c? C and C++ are separate languages, and
Crypto PRNG algorithms are better addressed by cryptographers, not
developers who may or may not have the necessary background.

Sorry, I forgot to mention that the code was designed to be 100% compatiblewith C++ (now that I think of it, though, I really should have put it in anamespace rather than extern "C"). Anyway, while true that it is still somewhat off-topic for the mere fact that it's primarily formulated as a discussion of cryptographic matters, I nonetheless felt that there may be some C++ programmers out there who may also be interested in such things, and yetwould not likely be exposed to the algorithm had it only appeared in more obscure forums.
 
V

Victor Bazarov

[..] Anyway, while
true that it is still somewhat off-topic for the mere fact that it's
primarily formulated as a discussion of cryptographic matters, I
nonetheless felt that there may be some C++ programmers out there who
may also be interested in such things, and yet would not likely be
exposed to the algorithm had it only appeared in more obscure
forums.

What a load of crap! So, if I have anything to say about *cooking
fish*, and I felt that there "may be some C++ programmers out there who
may also be interested" in *cooking fish*, I should then post it here?
Does it not occur to you that C++ programmers interested in cryptography
already go to cryptography forums?

And, please, if you do intend to cross-post (as your subject indicated),
then *do crosspost*. At least then it would be clear where the
follow-ups should go.

V
 
S

Sebastian Garth

My initial description of the algorithm was admittedly quite vague, so I'm going to go over it again in a little more detail, in hopes that it may clear up any undue confusion.

But first some terminology. "CP" refers to a "characteristic polynomial over the finite field GF(2)". "RN" refers to a "representation of a CP as a binary number". So for example, the CP x^11 + x^9 + x^4 + 1 has an RN counterpart of 10100001000 (ie: 1288 in decimal). "LS" refers to the RN of the LFSR's internal state. "SC" refers to a copy of some previous state of the LS..

So to recap, the entire system basically consists of a CP, an LS, and an SC.. Now here's how the algorithm works. We start with the input seed of arbitrary length and copy it to both the LS and SC. Note that if the seed is zero (which is a forbidden state for our LFSR) then it simply gets incrementedbefore the copy step. We then set our CP to LS + 1. For each cycle of the LFSR we then do the following:
(1) Compare LS with SC. If they are equal, set the boolean flag "SAVE" to "true" and increment the RN of our CP. If the increment overflows, increase the bit-width of the LFSR by one machine word and adjust the LFSR to account for the carry.
(2) "Feed" the LS into CP per standard LFSR operation.
(3) IF "SAVE" is set to "true" copy LS to SC.

So SC serves to detect that our LFSR has produced a maximum length sequencefor that particular CP (remember, much like a counter, an LFSR's CP never produces the same number twice unless it is about to repeat the entire sequence).

Anyway, several of these cycles (at least two) will run during the output-bit-determination step (ie: the "self-shrinking generator").

In conclusion, these very simple modifications yield a mechanism that demonstrates some truly remarkable properties indeed. Namely, an inexhaustible supply of high-quality random bits delivered at reasonably efficient output rates.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top