March 11th, 2013, 06:46 PM

NonMath Chaos/RNG
To begin, let us assume that we have a set of numbers  all unique, but mixed.
i = {4,8,1,3,9,6,2,0,5,7}
We can sort these n items in (on average) < 2n cycles.
Code:
for (t = 0; t < n_items; t++)
swap(i[t], i[(int)i[t]]);
In other words, swap the "value" of a given element with it's position. Or rather, 'an integer will tell you exactly where it belongs in the set'. A set of integers will selfsort, in a way. When we have more than one element the same value, the elements will deadlock, where a value in 'some position' will stay the same in that position because it swaps with another version of itself  almost akin to Quantum Entanglement. What I found amazing was that we can actually use this selfsorting property of integers to create chaotic dynamical systems!
Odd as it may be, if you apply this principle in not less than 4 dimensions, i.e. 4 sets interacting with one another, you can create a chaotic dynamical system. Random begets more random. For example:
Code:
a = {4,8,1,3,9,6,2,0,5,7}
b = {2,5,3,6,8,9,3,1,7,0}
c = {4,2,9,3,9,1,7,3,1,9}
d = {6,5,8,3,4,0,1,2,7,7}
for (t = 0; t < 10; t++) {
swap(a[t], a[(int)b[t]]);
swap(b[t], b[(int)c[t]]);
swap(c[t], c[(int)d[t]]);
swap(d[t], d[(int)a[t]]);
}
Produces:
a = 1093872465
b = 8931530627
c = 3413972991
d = 5167874302
This dynamic will continue with unknown and generally unknowable periods for each possible randomized initialization. Using four or more dimensions, we disallow the numbers to selforganize along any single dimension, which creates a complex chaotic dynamical system. We have built and implemented an RNG based on this principle and the results are very promising!
March 12th, 2013, 03:11 AM

You need to choose your seed conditions carefully.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void swap (int *x, int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
void print ( int *a, int *b, int *c, int *d, size_t len ) {
for ( size_t i = 0 ; i < len ; i++ ) {
printf("%d",a[i]);
}
printf(" ");
for ( size_t i = 0 ; i < len ; i++ ) {
printf("%d",b[i]);
}
printf(" ");
for ( size_t i = 0 ; i < len ; i++ ) {
printf("%d",c[i]);
}
printf(" ");
for ( size_t i = 0 ; i < len ; i++ ) {
printf("%d",d[i]);
}
printf("\n");
}
int compareArrays ( int ref[][4], int a[], int b[], int c[], int d[] ) {
return memcmp(ref[0],a,sizeof(ref[0])) == 0 &&
memcmp(ref[1],b,sizeof(ref[0])) == 0 &&
memcmp(ref[2],c,sizeof(ref[0])) == 0 &&
memcmp(ref[3],d,sizeof(ref[0])) == 0 ;
}
int main()
{
int a[] = {0,1,2,3};
int b[] = {1,2,3,0};
int c[] = {2,3,0,1};
int d[] = {3,0,1,2}; // cyclelen = 244793
// int d[] = {3,2,1,0}; // cyclelen = 489586
// int d[] = {0,1,3,2}; // cyclelen = 530095
// int d[] = {0,3,2,1}; // cyclelen = 30100
int ref[4][4];
size_t len = sizeof(a)/sizeof(*a);
for ( size_t t = 0; t < len; t++) {
ref[0][t] = a[t];
ref[1][t] = b[t];
ref[2][t] = c[t];
ref[3][t] = d[t];
}
int cyclelen = 0;
size_t t = 0;
for ( ; ; ) {
swap(&a[t], &a[b[t]]);
swap(&b[t], &b[c[t]]);
swap(&c[t], &c[d[t]]);
swap(&d[t], &d[a[t]]);
print(a,b,c,d,len);
cyclelen++;
if ( compareArrays(ref,a,b,c,d) ) break;
t++; if ( t == len ) t = 0;
}
printf("Cycle Length=%d\n", cyclelen );
return 0;
}
One is exceedingly short (and those are my only attempts), and none are anywhere near the 16! (I think) theoretical permutations of 16 symbols.
It may be that you can pick any 4 sets of 8 permuted numbers (in your example), and not find a repeating sequence in a reasonable amount of time on any hardware you have access to.
But can you be sure that any start condition will always produce a substantial fraction (ideally all) possible permutations, as opposed to an unknown tiny fraction of all possible permutations?
March 12th, 2013, 08:00 AM

Originally Posted by salem
You need to choose your seed conditions carefully.
Sure.... you wouldn't select a seed that for example, has all the same digits. The periods for each possible seed are generally ( likely ) unknowable until you actually run them out.
One is exceedingly short (and those are my only attempts), and none are anywhere near the 16! (I think) theoretical permutations of 16 symbols.
When you ran them, the one you found exceedingly short, were all four sets returned to their original state?
It may be that you can pick any 4 sets of 8 permuted numbers (in your example), and not find a repeating sequence in a reasonable amount of time on any hardware you have access to.
But can you be sure that any start condition will always produce a substantial fraction (ideally all) possible permutations, as opposed to an unknown tiny fraction of all possible permutations?
Not at all... The periods for each initialization cannot be known until it is run out. However, the RNG we have designed based on this method takes 4 sets, each containing 256 randomly initiated values. We return only the first element from each set xord with the second element from sequential sets.
March 12th, 2013, 08:07 AM

One is exceedingly short (and those are my only attempts), and none are anywhere near the 16! (I think) theoretical permutations of 16 symbols.
What if for example you try d[] = {1,1,0,2}; ?
March 12th, 2013, 04:40 PM

> When you ran them, the one you found exceedingly short, were all four sets returned to their original state?
Yes, the cycle time is the number of iterations that it took to return to the initial state.
I draw two particular conclusions from running just 4 experiments.
1. That unexpectedly 'short' sequences are common rather than rare.
2. That much shorter sequences also exist.
> What if for example you try d[] = {1,1,0,2}; ?
You've got the code I posted, why don't you try it?
> To begin, let us assume that we have a set of numbers  all unique, but mixed.
Mmm, OK.
But what happened here in your original post?
b = {2,5,3,6,8,9,3,1,7,0}
c = {4,2,9,3,9,1,7,3,1,9}
d = {6,5,8,3,4,0,1,2,7,7}
> Not at all... The periods for each initialization cannot be known until it is run out.
That's a rather bold statement  where is your proof?
I'm talking about mathematical proof, not some conjecture based on a couple of hours of machine runtime from a few randomly selected test cases that were observed not to repeat (in the time allotted).
March 12th, 2013, 08:19 PM

Firstly, I really only meant unique & mixed to be applied to the sorting algorithm for demonstration purposes ( which I never finished explaining in the post and for that I apologize ) and not necessarily the RNG, which is why I had multiple elements of the same digit in the sets for the RNG section.
Secondly, I don't have a mathematical proof ( which is probably obvious ), and never meant the statement absolutely. Obviously, some initialization's are easily determinable, i.e. all 0's or 1's etc. and there may be some formula to calculate the cycle length.
There are a few interesting, but probably insignificant things I noticed on the output of cycles of your seeds.
244793 is precisely half of 489586
244793 has the following factors: 1,61,4013,244793
4013 and 61 are prime.
530095 has the following factors: 1,5,106019,530095
5 and 106019 are prime.
It would be interesting to play around with this a bit more.
March 13th, 2013, 02:41 AM

Originally Posted by salem
You've got the code I posted, why don't you try it?
After playing around and thinking about it a bit with a different implementation, I am not sure where you are getting your numbers from....
16! ? There aren't that many possible permutations.
Assuming repetition were allowed, there can only be at most 4^16 possible permutations. But repetition isn't allowed because we only have 4 of each digit as per unique/mixed sets. Meaning, we cannot have a = {0,0,0,0} and b = {0,1,2,3} at the same time. Since this is the case, we have a different calculation. Each set has 4! possible initialization's.
There are at most, n! / (nr)! = 255,024 permutations in this given scenario, where n is the number of possible initialization's per set ( 24 ). Your algorithm does not seem to be working correctly. The numbers I came up with were 244793, which again is precisely 1/2 the 489,586 you got on one run and 7525 which is precisely 1/4 the 30100 you got on another. So your algorithm is not stopping when it should.
Since these two numbers were prevalent throughout, there obviously IS a way to calculate the period for each init, so I recant that statement. But again, although this is the framework around which the RNG is built, there's a slight bit more to it.
March 13th, 2013, 05:07 AM

@nsagames:
I noticed the expression "RNG". There is not, and cannot be, an algorithm for the generation of random numbers. Algorithmically computed sequences that "seem random" are pseudorandom number generators, or PRNGs. Probably you already know this, but it is a VERY important distinction  and literally thousands of wouldbe crypto inventors fall into the trap of not recognizing its power.
It's not difficult to see that a PRNG, especially for cryptography, must show statistical uniformity when sufficiently large samples of output are analyzed: for example, all possible digits must be equally likely; all pairs of successive digits must be equally likely; there must be no correlation between a digit and the 13th digit after it; and so on and so on.
But meeting the statistical tests is relatively easy, and far from sufficient. For a PRNG to be useful for strong cryptography, it must possess this critical property:
For a given generator (that is, an algorithm and its "seed" value), knowledge of the history (sequence of generated digits) must not give any clue to the next digit. For example, if you knew the last billion digits that came out of a perfect PRNG, you would have no better chance of predicting the next digit than random chance (for a decimal PRNG, the probability that your prediction is correct would be 0.1).
This property is extremely tricky: it isn't enough to say, "I know the last thousand digits and I can't predict what the next one will be," because I might not understand the mathematical properties of the generator well enough to make the prediction. I must be able to make a convincing argument that NOBODY can do an analysis that would enable prediction.
For a good bad example, consider the LFSR, which is statistically perfect (uniformity of outputs), but tragically (from a crypto viewpoint) predictable. A 44bit LFSR has a sufficiently long period (length of sequence before it completely repeats itself) that one period would completely fill a 2terabyte hard drive. But ANY sequence of 88 bits in a row is sufficient to predict all the others! Oops.
So, if you think you've found a new PRNG, and that it might be useful for cryptography, the very hard challenge is to determine how far mathematical analysis could be applied to the algorithm!
______________________________________
If anyone is interested, there is a generator out there (with the lyrical name Blum Blum Shub) that has an interesting security case. The most efficient known attack against Blum Blum Shub (that is, for guessing the next output) is identical to the most efficient known attack against properly used RSA  that is, the attacker must factor the product of two very large randomly chosen primes. So the extent that nbit RSA is too costly to break, so (based on present knowledge of the best attacks) is Blum Blum Shub.
March 13th, 2013, 12:00 PM

Originally Posted by mah$us
@nsagames:
Probably you already know this, but it is a VERY important distinction  and literally thousands of wouldbe crypto inventors fall into the trap of not recognizing its power.
Indeed. I guess I always assume this and would argue a few things on this point. Primarily, given the requirements that a TRNG would need to have, it simply isn't possible. Even quantum. It is the very nature of computing. The hardware itself is designed to perform specific tasks. This means the hardware is limiting the scope of the input it can work with and further limiting and controlling the output it produces by means of voltage regulation, path restriction etc. Even quantum cannot achieve this because it too follows the same conditionals.
So let me ask you this:
Let us assume a hardware TRNG could exist. Let us then assume universal state A which transitions to universal state B which is immediately adjacent to universal state A. Given a "replay" of universal state A will it always transition to universal state B if all universal conditions are identical?
If so, then doesn't this negate the existence of a TRNG since the output is predictable given a known universal state ( including all conditions  momentum, position, energy etc. ) of all universal "elements"?
It's not difficult to see that a PRNG, especially for cryptography, must show statistical uniformity when sufficiently large samples of output are analyzed: for example, all possible digits must be equally likely; all pairs of successive digits must be equally likely; there must be no correlation between a digit and the 13th digit after it; and so on and so on.
Of course, there is always the inverse  make every input plain text output 0.
But meeting the statistical tests is relatively easy, and far from sufficient. For a PRNG to be useful for strong cryptography, it must possess this critical property:
For a given generator (that is, an algorithm and its "seed" value), knowledge of the history (sequence of generated digits) must not give any clue to the next digit. For example, if you knew the last billion digits that came out of a perfect PRNG, you would have no better chance of predicting the next digit than random chance (for a decimal PRNG, the probability that your prediction is correct would be 0.1).
This property is extremely tricky: it isn't enough to say, "I know the last thousand digits and I can't predict what the next one will be," because I might not understand the mathematical properties of the generator well enough to make the prediction. I must be able to make a convincing argument that NOBODY can do an analysis that would enable prediction.
Certainly. I am well aware of the requirements of an RNG to be suitable for cryptographic use.
March 14th, 2013, 04:58 AM

Concerning Hardware RNGs
I'm sure I didn't follow very well the reasoning posted above, about hardware RNGs.
The most important point I'd like to make, is that randomness is a definite (though rather baffling) mathematical property. Hardware RNGs have certainly been observed to suffer from imperfect randomness, and it is much more difficult than one might at first expect to eliminate statistical bias from such a device.
One important difference between PRNGs and hardware RNGs is that the hardware systems are NOT computational in the algorithmic sense of a PRNG. Unless it is very badly broken indeed, a hardware RNG will never produce periodic output (or any other gross pattern), and predictions of its next digits can never be computable in the sense that PRNGs must be computable.
Instead, the defects of hardware RNGs generally show in the form of statistical bias (for example, 0bits are microscopically more frequent than 1bits, the bit sequence 101 is more frequent than 011, etc. etc.)
So, we can make an interesting comparison of the two approaches.
Statistical Properties: PRNGs can exhibit statistical uniformity indistinguishable from an ideal RNG, provided that the sample is smaller than the period! Hardware RNGs can be "tweaked" to improve statistical uniformity, but are necessarily imperfect.
Predictability: PRNGs are (by definition) ALWAYS computable; that is, there exists a computation (namely, the PRNG itself) that perfectly predicts future outputs. We can hope for a cryptographic PRNG, that if the internal state (a function of the seed data) is concealed, that reconstruction of the PRNG is too expensive to be practical: but it is ALWAYS mathematically possible. Hardware RNGs (excluding those that are massively defective) are NEVER computable, but are subject to a limited degree of prediction based on their imperfect statistical uniformity.
What I'm suggesting here, is that all real RNGs differ from an ideal RNG. Their imperfections are of different kinds. For example, suppose that a hardware RNG has sufficient bias that its bit sequences are (speaking crudely) about 10% predictable (this would be a really lousy RNG). If such a device were used to generate a 128bit number for cryptographic use, an attacker's bruteforce search space would be reduced from about 2^127 (on average) to about 2^114. Now, 2^114 is still a gigantic search space that is likely to remain beyond reach for a long time.
In contrast, suppose that an attacker discovers a previously unsuspected algebraic property of a PRNG. Depending on the attacker's access to previous outputs of the PRNG, the bruteforce search space could collapse to as small as 2^0. [Note that even if the attacker can't perfectly see previous outputs, in practical situations there could be information leakage that enables at least partial knowledge of previous outputs, possibly leading to a reduction of the search space.]
_____________________________________________________________________
As to whether a hardware generator can exhibit "true randomness", I offer two questions.
(1) Suppose that a hardware RNG contains a Geiger counter (in essence), and measures the time between nuclear decay events, and that these timesbetween exhibit a distribution that can be determined from a large number of samples. If some postcomputation is done to compensate for ("flatten out") this distribution curve ... is there any power on heaven or earth that could use knowledge of, say, the last 1,000,000,000 outputs to predict the next output better than by pure chance?
(2) As to the thought experiment of resetting the universe to a previous state and rerunning the hardware RNG ... how could that correspond to any realizable weakness, if the universe is governed by the Second Law of Thermodynamics?
March 14th, 2013, 07:20 AM

What I mean is, bits aren't really bits. They are metaphysical representations of a finite hardware state  physical switches, which regulate and control the flow of electrons through a confined tunnel or path. The electrons flowing through a machine are not allowed to go where they want. They go where they must, as per machine design. No hardware RNG can for example, on a "whim" suddenly decide that the electrons shall not pass through a particular junction to throw a particular switch such that when it *should* have produced 101, produces 000 instead. Not unless it is subject to some sort of trauma!
Point is, while a hardware RNG might take input from external source to produce unpredictable output, if the exact make up of all inputs is known once it has been "sensed" or "measured", then the output can be predicted before it is even produced by the hardware as per the design of the hardware which is the very purpose of electronics and there components. Even a quantum computer is subject to this restriction  hardware is required to produce the signal, hardware that is designed to control and restrict that signal to within a particular range of operation. Of course, sometimes things do happen outside the bounds of its particular operation  we call these errors.
Likewise, a PRNG on a mathematically predictable framework will exhibit the exact same properties as a hardware RNG given "sensed" or "measured" input from external sources and proper coding and design. Remove the unpredictable sensory input and substitute a constant and you will quickly realize that a mathematical framework for a PRNG on a generalized hardware system is precisely analogous to the IC design of a hardware RNG. In other words, it's not the hardware itself which is producing the unpredictable output, it is the already unpredictable input which produces the unpredictable output.
March 14th, 2013, 02:16 PM

Pssst  don't tell Intel and you can make a fortune compromising all those naive people blindly trusting hardware RNG's.
March 14th, 2013, 05:05 PM

I never suggested they are in any way compromised due to the fact they are predictable machines given such knowledge of input. I'm merely suggesting that it's not the machine that produces the unpredictable output, rather, the unpredictability is already inherent in the input. I'm also suggesting that a mathematically predictable PRNG on a generalized closed loop system can achieve the same unpredictable results given the same unpredictable input from an outside source.
Is it really that hard to understand?
March 15th, 2013, 02:52 AM

Originally Posted by nsagames1234
Is it really that hard to understand?
It's not clear to me, what motivated you to describe in this forum an algorithm that exhibits seemingly chaotic behavior. If you are interested in reading some perspectives and ideas that might not have occurred to you as yet, it's my pleasure to respond.
To interpret someone else's differing view as a failure to understand, risks missing out on an opportunity to learn something.
________________________________________________
I'll try one time more:
Once a PRNG is seeded, its operation is fully deterministic. Reinitialized with the same seed, it will generate precisely the same sequence of outputs, no matter how many times the experiment is tried. It is absolutely deterministic, and its outputs can be perfectly predicted given knowledge of its internal state at any single preceding stage of its sequence.
In a hardware RNG based on, for example, radioactive decay (yes, this has been done) or more typically, thermal motion of electrons. No one knows any method to predict how many nanoseconds will elapse until the next unstable nucleus decays, or what all of the individual electron energy states will be one nanosecond after the last observation. Assuming that the generator is reasonably designed to avoid extreme bias, it is nondeterministic. It is physically impossible to reset it to a previous state so as to generate the same sequence of outputs as any earlier run. Even the absolute maximum knowledge of its internal state, that is accessible to human observation, would not enable prediction of any future outputs  except to the extent that imperfectly corrected statistical bias would enable us to say "the probability of a 0bit is 0.5001 and the probability of a 1bit is 0.4999".
A hardware RNG can be tampered with by physical intervention, so as to deliberately bias its outputs. But barring such tampering, it cannot be "hacked" in a way that allows output prediction its bias errors.
A software PRNG can be "hacked"  with enough analysis of a sufficient sample of outputs, its internal state can be deduced completely, enabling prediction of all future outputs.
________________________________________________
I humbly suggest, that on the strength of the foregoing, the properties  and especially for cryptography, the security characteristics  of PRNGs and hardware RNGs are fundamentally different. One is absolutely predictable, the other inherently unpredictable.
In particular, the security case for a PRNG must convincingly demonstrate that the mathematical analytic methods and computing power available today (and in the reasonably foreseeable future) make the reverseengineering of the PRNG's internal state too costly to be practical.
To the reader who sees here any errors of fact, or logic  kindly post, and we'll investigate more deeply.
March 15th, 2013, 04:04 AM

Originally Posted by mah$us
To interpret someone else's differing view as a failure to understand, risks missing out on an opportunity to learn something.
That statement was aimed at Salem. You have been more than gracious enough to post real arguments. For not making that distinction, I apologize.
I fully understand what you are saying. I get it. My arguments here go a bit beyond "what's in the box" and "what is humanly accessible". They are more on the order of  "what is the box 'made of'" and "If I were the master of the universe".
Physically, outside of the unpredictable input, a hardware RNG suffers precisely the same determinism  because ' it has to '. The difference is, a software PRNG generally takes a single initialization seed which makes output beyond the scope of a single number predictable, whereas, a hardware RNG takes input from an already unpredictable source which makes output beyond the scope of a single number unpredictable. It is this distinction alone that separates the two.
As a comparison, imagine that a software PRNG were wired to an RF receiver which is tuned to pick up atmospheric noise and which is programmed to reseed the PRNG after a single number was generated. This would make the software PRNG identical to a hardware RNG, no?
This is my point. There is not a bit of difference in the fundamental logic gates and processes between a hardware RNG and a software PRNG. They are precisely analogous. The difference only lies within the seeding of each implementation of that logic.
If a PRNG does not reseed after every number with an unpredictable source, then by definition, the PRNG is predictable. Absolutely. Since a hardware RNG reseeds with an unpredictable source, then by definition the hardware RNG is unpredictable. No argument there. If a PRNG reseeds with an unpredictable source, then by definition the PRNG is unpredictable.
If a PRNG, given a reseed from an unpredictable source of input/entropy is precisely equivalent to a hardware RNG then we need to ask ourselves three things: What exactly qualifies as an unpredictable source of input/entropy? How do we link that to our implementation? How much entropy is really necessary to make that implementation truly unpredictable?