Re: Two ideas for random number generation
At 10:18 AM 4/25/02 -0700, Tim May wrote: On Thursday, April 25, 2002, at 07:45 AM, Major Variola (ret) wrote: Predictability gets much worse if one of the walls of a pool-table is curved, then the uncertainty in a perfectly-round ball's momentum is magnified after reflection, compared to a pool-table of 3 or more flat walls. Yes, of course. There are many sources of divergence, and curved walls certainly add divergence. But, as you acknowledge, the curvature of the spherical balls is a source. In fact, the radius of curvature of a ball is much smaller than that of curved side walls, so of course they are huge sources of divergence. Yep. I misremembered the model. The importance of curved walls is only in abstract-billiards with point-balls. Otherwise, analytically, you get into fixed sequences with flat walls. Pong-like games can demonstrate this. Its all about, as you said, the effect of divergence on initial uncertainty. And it's important for people not to think that the curved walls or curved balls are important to the phenomenon: if all surfaces were nominally flat (say, to a sixteenth wavelength, about the best a telescope mirror is ground to), the divergences would _still_ occur. Tiny alternations in temperature would affect dimensions, friction, speeds, and hence would alter arrival times. At some point, objects in one history would bounce and in another history would miss...the changes at this point are _huge_. These are unavoidable *empirical* sources of uncertainty; the above gedankenbilliards divergence addresses *analytic* magnification of uncertainty. (I actually did a project at Intel which exploited this. I devised a scheme whereby known good microprocessors would be imaged by an electron microcope, state by state (using beam blanking to only illuminate the chip during a specific state), and then would be digitally subtracted or otherwise compared to the internal states of chips having some speed problem, or some voltage problem, or just plain failing. By examining the time evolution of divergent states, especially by running the history backwards, we could pinpoint the first divergence, the first state where voltage levels differed noticeably. This was usually a place where a design needed to be tweaked, or where a marginality was present, or a flaw, etc. This machine, the Dynamic Fault Imager, was used to get speeds up on the 80286 and later processors.) Much more finesse than your 'cutting the crap out of packaging materials' trick... BTW, someone was speculating about history healing itself (this is my term for it, a familiar trope in SF). A look at the billiard ball model will show how this cannot conceivably happen: as soon as one ball misses another, all of the later trajectories are radically different. If this is not immediately clear, spend several minutes drawing pictures. Time-machine inventor reports that his stepping on a butterfly in Brazil averted a Chinese cyclone... If the writer was talking about conserved quantities (I think he mentioned vapors in an elevator, for example), this is not at all what we are talking about. Yes, the total energy of the billiard balls will remain roughly the same in both histories, though divergences will occur even in total energy, just more slowly. Yes, the earth's overall climate is not dramatically affected by butterflies. To track one (odor) molecule's position into the future, you'd need exponentially more information (about the other molecules it interacts with) the farther you want to predict in time. ... Jim Bell was just doing physics-of-computation experiments in IRS offices..
Re: Two ideas for random number generation
Jim Choate [EMAIL PROTECTED] wrote: But that changes the game in the middle of play, the sequence of digits in pi is fixed, not random. You can't get a random number from a constant. Otherwise it wouldn't be a constant. PRNG output is fixed/repeatable too - that is a properly you *want* from a PRNG. any subset of the digits of pi is as close to RNG output as you would need to satisfy any entropy tests - unless you *knew* you had derived it from pi you couldn't distinguish it from a true random string of the same size. You can't stop them from using their tables. Slow them down, not stop them. You can't use that huge a seed, hardware limitations. They can match you. *shrug* given that adding a bit to the seed doubles the quantity of data they would have to cache in their tables, it can quickly become unworkable; the single-digit-of-pi formula is too slow to form a good stream cypher, but is otherwise ok; if you aren't constrained to matching a real world sequence (pi in this case) but are happy with *any* non-repeating but deterministic stream, you can probably find something much faster.
Re: Two ideas for random number generation
On Wed, 24 Apr 2002, David Howe wrote: Jim Choate [EMAIL PROTECTED] wrote: But that changes the game in the middle of play, the sequence of digits in pi is fixed, not random. You can't get a random number from a constant. Otherwise it wouldn't be a constant. PRNG output is fixed/repeatable too - that is a properly you *want* from a PRNG. No it isn't. You -want- a RNG but you can't have one. Nobody -wants- a PRNG, they -settle- for it. What one wants is a bit sequence which is -random-. There are many definitions of random, but they boil down to -unpredictable- outside of chance with respect to predicting individual bit results as well as sequences of bits (they are not the same statistically speaking, re probability distributions). Ideally what one would want is a situation where each bit has a 50/50 chance of being in either state and there are -no- inter-bit dependencies. That implies no modulo (though it doesn't prevent clustering which can fool you if you don't test your sub-strings well enough - re Gamblers Ruin). Which raises an interesting aspect for me, what happens if you put a PRNG into a 'Garden of Eden' state? any subset of the digits of pi is as close to RNG output as you would need to satisfy any entropy tests - unless you *knew* you had derived it from pi you couldn't distinguish it from a true random string of the same size. Satisfying an -entropy test- is -not- equivalent to -being- a RNG. It only says that within a particular error margin you're -close enogh-. You can't stop them from using their tables. Slow them down, not stop them. You can't use that huge a seed, hardware limitations. They can match you. *shrug* given that adding a bit to the seed doubles the quantity of data they would have to cache in their tables, it can quickly become unworkable; Really? The offset into the sequence is a fixed width and the result is alaways a single character. Where do you add a bit? the single-digit-of-pi formula is too slow to form a good stream cypher, but is otherwise ok; Maybe for you, I sure as hell wouldn't use it either as a key or as a seed into a known hashing/whiting algorithm. Let me ask you a more pointy question. Are you selecting some offset and then taking the sequence of digits from pi, or are you selecting the digits out of order? In either of these cases it isn't the sequence of pi that is providing the randomness (which is apparently the claim) but rather the selection process; which is both undescribed at this point -and- simply moves the argument from one area to another - this -proving- nothing. -- The law is applied philosophy and a philosphical system is only as valid as its first principles. James Patrick Kelly - Wildlife [EMAIL PROTECTED] www.ssz.com [EMAIL PROTECTED] www.open-forge.org
Re: Two ideas for random number generation
Sampo Syreeni [EMAIL PROTECTED] wrote: Aren't there dedicated avalanche diodes available with low breakdown voltages, precisely for this reason? I think they're used in applications where zeners could be, except for higher breakdown current. Sure. I was thinking of an IC design, in which case you're a lot more likely to be able to make a bipolar than you are to have essentially 5V zeners. [mention of reliability issues] Shouldn't be a problem, if you limit the breakdown current. If you're after entropy, you'd likely want to use a constant current source anyway. To first order, yes, but at least a couple of the processes I've worked with warn against even controlled emitter-base breakdown. Of course, I suppose they're assuming you want to use the transistor some other way, too... -- Riad Wahby [EMAIL PROTECTED] MIT VI-2/A 2002
Re: Two ideas for random number generation
On Tue, 23 Apr 2002 [EMAIL PROTECTED] wrote: -- Jim Choate wrote: If you can't develop a RNG in software (ie you'd be in a state of sin), what makes you think you can do it using -only- digital gates in hardware? You can't. James A. Donald: Classic Choatian physics. Of course you can. Jim Choate: Not if you use -only- digital gates and derived functions (eg flip flop or a shift register) One can build a true random generator using a two resistors, a capacitor, three unbuffered inverters and a shift register. A second shift register and an XOR gate will serve to quite adequately whiten the output. Yeah, the shit for brains will probably tell you that resistors and capacitors aren't digital gates. In which case you can just use a bunch of flip-flop that feed back to themselves at different rates, so you get different streams of 1's and 0's, and xor'em all together. Inefficient as compared to using analog components, but it would work if the timing between them is different enough and you only get data from them sporadically. Lots of whitening to do afterwards of course...
Re: Two ideas for random number generation
On 24 Apr 2002 at 17:41, David Howe wrote: Maybe for you, I sure as hell wouldn't use it either as a key or as a seed into a known hashing/whiting algorithm. its probably a better (if much slower) stream cypher than most currently in use; I can't think of any that have larger than a 256 internal state, and that implies a 2^256 step cycle at best; for pi to be worse, it would have to have less than 2^256 digits. This is putting sillines on top of silliness. It's true that in principle that the decimal expansion of pi has an infinite number of digits, but any practical implementation of a PRNG based on pi would still have to have a finite number of accessable states. That is, to get the infinite cycle, you'd have to have some method of generating a uniform random integer 0 to infinity for the initial state, and you'd need an infinite amount of memory to store the current internal state. Neither of which is acheivable ion practice. Conversely, a PRNG whose cycle is only 2^256 bits long will never repeat itself during the lifetime of the device, or the lifetime of the universe for that matter. George
Re: Re: Re: Two ideas for random number generation
-- Joseph Ashwood Because with a pRNG we can sometimes prove very important things, while with a RNG we can prove very little (we can't even prove that entropy actually exists, let alone that we can collect it). James A. Donald: Don't be silly. Of course we know that entropy exists, and we can collect it. If a RNG runs off Johnson noise, then the ability to predict its output would imply the ability to violate the second law of thermodynamics. If it runs off shot noise, then the ability to predict its output would disprove quantum mechanics. Joseph Ashwood Actually there are models that fit the universe that are entirely deterministic. These models are entirely incoherent, and I would summarize them as God knows. And if these models allowed us to predict the outcome of a true RNG, they would not fit the universe. James A. Donald: And if ofne is implementing a PRNG in software, it is trivial to have lots of internal state (asymptotically approaching one-time pad properties). Joseph Ashwood The problem is not having that much internal state, but what do you do with it? Currently the best options on that front involve using block ciphers in various modes, but this has a rather small state, RC4 has 1684 bits of state, which should prove sufficient to defeat guessing. And RC4 is far from a good RNG of any type, it's distinguishable from random fairly easily, and unless it's used very carefully it's weak. If one were to try to guess all 1684 bits it would be exceedingly difficult, but to start with, it's only a permutation so the space is much smaller, in addition the state itself has more attacks available Wrong. 1684 bits of entropy. Count them. The state is a permutation 256, which requires 2048 bits to describe (256 *8) but contains 1684 bits of entropy, not 1684 bits. 2048 bit description, but because it is a permutation, 1684 bits actual entropy. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG MjdAfFTXXtA7qo/FzKsFLPFEYgVQ8bY2lfseYhYX 4P9O7sqp2z5todA8tcLMmb8wQiZ9lLBz/la5zhU+f
RE: Two ideas for random number generation
On Tue, 23 Apr 2002, Trei, Peter wrote: Exactly what is the Choatian definition of a PRNG which requires it to repeat, anyway? Wrong question, the -right- questions is... What is -random-? It means unpredictable, this means unrepeatable. If it repeats then it -must- be predictable; that means it ain't -random-. A PRNG isn't unpredictable, only taking such a long time that by the time the repeat gets there you don't care. The length of that sequence is called the modulus of the generator. -ALL- PRNG's will repeat, if they didn't they wouldn't be -pseudo-. -- The law is applied philosophy and a philosphical system is only as valid as its first principles. James Patrick Kelly - Wildlife [EMAIL PROTECTED] www.ssz.com [EMAIL PROTECTED] www.open-forge.org
Re: Two ideas for random number generation
On Sunday, April 21, 2002, at 09:53 PM, Joseph Ashwood wrote: - Original Message - From: [EMAIL PROTECTED] To: Tim May [EMAIL PROTECTED]; Eugen Leitl [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Sunday, April 21, 2002 1:33 PM Subject: Re: Two ideas for random number generation Why would one want to implement a PRNG in silicon, when one can easily implement a real RNG in silicon? Because with a pRNG we can sometimes prove very important things, while with a RNG we can prove very little (we can't even prove that entropy actually exists, let alone that we can collect it). Not to be pedantic, but we cannot _really_ prove that entropy is being collected from a PRNG, either. In fact, there really _is_ no entropy from a PRNG: the bits are deterministic from the PRNG, meaning they actually have no uncertainty, no entropy. To the person who selected the program and the seed, _he_ certainly sees no randomness, no entropy. Relativity. Usual Kolmogorov/Chaitin stuff here. Operationally, when faced with a purported source of random numbers, naive calculations of entropy are often made. This is true for the output of a Johnson noise diode, or a radioactive decay circuit, or the RAND Corporation's Table of One Million Random Digits. But all of the calculated (measured) entropy numbers collapse to zero or some small number if and when someone figures out that he knows how to predict the nth digit. The usual arguments I hear about why PRNGs are better is that they a) can give reproducible sequences for testing software (often much more useful than physically-derived numbers would be, for obvious statistical reasons), b) in some sense there is more assurance that a BBS generator, for example, has not been manipulated. If I wanted a good PGRNG (Pretty Good RNG) I'd favor one that mixes a physical source, mixes entropy extracted from user actions (keystroke intervals, mouse movements, over a lot of days), and distills it all some more with a BBS. (The meta-solution for good numbers is then to mix different kinds of RNGs, to take a BBS output and XOR it with a Lava Lamp sequence, to seed a PRNG with mouse strokes, etc. As with ciphers, composition of many functors tends to help, unless one of the stages has bad properties, e.g., avalanche conditions. (Blowfish (3DES (Bassomatic (foo))) will be at least as strong as (Blowfish (foo)), all other things being equal.) --Tim May You don't expect governments to obey the law because of some higher moral development. You expect them to obey the law because they know that if they don't, those who aren't shot will be hanged. - -Michael Shirley
Re: Re: Two ideas for random number generation
- Original Message - From: [EMAIL PROTECTED] To: Tim May [EMAIL PROTECTED]; Eugen Leitl [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Sunday, April 21, 2002 1:33 PM Subject: CDR: Re: Two ideas for random number generation Why would one want to implement a PRNG in silicon, when one can easily implement a real RNG in silicon? Because with a pRNG we can sometimes prove very important things, while with a RNG we can prove very little (we can't even prove that entropy actually exists, let alone that we can collect it). And if one is implementing a PRNG in software, it is trivial to have lots of internal state (asymptotically approaching one-time pad properties). The problem is not having that much internal state, but what do you do with it? Currently the best options on that front involve using block ciphers in various modes, but this has a rather small state, but again we can quite often prove things about the construct. Joe
Re: Two ideas for random number generation
On Mon, 22 Apr 2002, Tim May wrote: What real-life examples can you name where Gbit rates of random digits are actually needed? Multimedia streams, routers. If I want to secure a near-future 10 GBit Ethernet stream with a symmetric cypher for the duration of a few years (periodic rekeying from a RNG might help?) I need both lots of internal state (the PRNG can't help leaking information about its state in the cypher stream, though the rate of leakage is the function of smarts of the attacker) and a high data rate. In any case, if someone wants Gbits per second of random numbers, it'll cost 'em, as it should. Not something I think we need to worry much about. Maybe, but it's neat trying to see how the constraints of 2d and 3d layout of cells, signal TOF and fanout issues influence PRNG design if lots of state bits and a high data rate are involved. It is not very useful right now, agreed.
Re: Two ideas for random number generation
On Sun, 21 Apr 2002 [EMAIL PROTECTED] wrote: Why would one want to implement a PRNG in silicon, when one can easily implement a real RNG in silicon? Both applications are orthogonal. PRNG != entropy. And if one is implementing a PRNG in software, it is trivial to have lots of internal state (asymptotically approaching one-time pad properties). Yes, but software is too slow to be able to handle GBit data rates. It's inefficient use of CPU silicon real estate.
Re: Re: Two ideas for random number generation
- Original Message - From: Eugen Leitl [EMAIL PROTECTED] On Mon, 22 Apr 2002, Tim May wrote: What real-life examples can you name where Gbit rates of random digits are actually needed? Multimedia streams, routers. If I want to secure a near-future 10 GBit Ethernet stream with a symmetric cypher for the duration of a few years (periodic rekeying from a RNG might help?) I need both lots of internal state (the PRNG can't help leaking information about its state in the cypher stream, though the rate of leakage is the function of smarts of the attacker) and a high data rate. Actually that's not necessarily the case. Let's use your example of a Multimedia stream server that is filling a 10GBit/s connection. Right now the current minimum seems to be 56kbit/s. So that means that if every available connection is taken in the same second, the server would only need a rate of 2.2 million bits/sec from it's RNG to build a 128-bit key for each. A good design for this though has the client doing most of the random number choosing, where the only purpose of the server random number is to prevent the client of biasing the result, so 128-bits is more than sufficient. So 2.2 Mbit/sec seems to be the peak for that. Finding situations where a decent design will yield a need for an RNG to run about 1 Gbit/sec is extremely difficult. With poor designs it's actually rather easy, take a RNG that is poor enough (or a situation where that is a basic assumption) that it has to be distilled to 1 billionth it's size, obviously to support that multimedia stream server would require 2.2 million Gigabits per second (approximately). In any case, if someone wants Gbits per second of random numbers, it'll cost 'em, as it should. Not something I think we need to worry much about. Maybe, but it's neat trying to see how the constraints of 2d and 3d layout of cells, signal TOF and fanout issues influence PRNG design if lots of state bits and a high data rate are involved. It is not very useful right now, agreed. I think it would be a good process to go through to develop a design for one, or at least a basic outline for how it could be done, but the basic idea that comes to mind looks a lot like /dev/random, but run in parallel collecting from several sources including a custom hardware pool similar to the Intel RNG. Joe
Re: Re: Two ideas for random number generation: Q for Eugene
- Original Message - From: gfgs pedo [EMAIL PROTECTED] Oh surely you can do better than that - making it hard to guess the seed is also clearly a desirable property (and one that the square root rng does not have). U can choose any arbitrary seed(greater than 100 bits as he (i forgot who) mentioned earlier.Then subject it to the Rabin-Miller test. Since the seed value is a very large number,it would be impossible to determine the actual value.The chances the intruder find the correct seed or the prime number hence generated is practically verly low. You act like the only possible way to figure it out is to guess the initial seed. The truth is that the number used leaves a substantial amount of residue in it's square root, and there are various rules that can be applied to square roots as well. Since with high likelihood you will have a lot of small factors but few large ones, it's a reasonable beginning to simply store the roots of the first many primes, this gives you a strong network to work from when looking for those leftover signatures. With decent likelihood the first 2^32 primes would be sufficient for this when you choose 100 bit numbers, and this attack will be much faster than brute force. So while you have defeated brute force (no surprise there, brute force is easy to defeat) you haven't developed a strong enough generation sequence to really get much of anywhere. Of course, finding the square root of a 100 digit number to a precision of hundreds of decimal places is a lot of computational effort for no good reason. Yes the effort is going to be large but why no good reason? Because it's a broken pRNG, that is extremely expensive to run. If you want a fast pRNG you look to ciphers in CTR mode, or stream ciphers, if you want one that's provably good you go to BBS (which is probably faster than your algorithm anyway). So there's no good reason to implement such an algorithm. BTW, the original poster seemed to be under the delusion that a number had to be prime in order for its square to be irrational, but every integer that is not a perfect square has an irrational square root (if A and B are mutually prime, A^2/B^2 can't be simplified). Nope ,I'm under no such delusion :) Just the delusion that your algorithm was good. Joe
Re: Two ideas for random number generation: Q for Eugene
At 11:22 AM 4/21/02 +0200, Eugen Leitl wrote: I disagree here somewhat. Cryptography ttbomk doesn't have means of construction of provably strong PRNGs, especially scalable ones, and with lots of internal state (asymptotically approaching one-time pad properties), and those which can be mapped to silicon real estate efficiently both in time (few gate delays, GBps data rates) and in space (the silicon real estate consumed for each bit of PRNG state). What is a provably strong PRNG? Strong against what? If I'm supposed to know this, and have forgotten it, a pointer will suffice. I know what the attacks are for a crypto-strong plain-ole-analog-based-RNG. Its quite easy to generate apparently-random (ie, PRNGs) from block ciphers being fed, say, integers, or their own output, etc. These can be made small and fast in hardware. Large families of these can be constructed e.g. by varying bits e.g., in Blowfish's S-tables, etc.
Re: Two ideas for random number generation
-- Tim May: As a meta-point, the world is not in short supply of lots of good RNGs, ranging from Johnson noise detectors to very strong Blum-Blum-Shub generators. The interesting stuff in crypto lies in other places. Eugen Leitl I disagree here somewhat. Cryptography ttbomk doesn't have means of construction of provably strong PRNGs, especially scalable ones, and with lots of internal state (asymptotically approaching one-time pad properties), and those which can be mapped to silicon real estate efficiently both in time (few gate delays, GBps data rates) and in space (the silicon real estate consumed for each bit of PRNG state). Why would one want to implement a PRNG in silicon, when one can easily implement a real RNG in silicon? And if one is implementing a PRNG in software, it is trivial to have lots of internal state (asymptotically approaching one-time pad properties). --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG zpSkoZyEIznFD4uNK6xfnsbGREchDTx3PKS53GZp 4n1eG5pY8G+sWam6uh16xNeCGWMWn5a5IiBmurVoA
Re: Two ideas for random number generation: Q for Eugene
[EMAIL PROTECTED] wrote: On 21 Apr 2002 at 10:00, Major Variola (ret) wrote: At 11:22 AM 4/21/02 +0200, Eugen Leitl wrote: I disagree here somewhat. Cryptography ttbomk doesn't have means of construction of provably strong PRNGs, especially scalable ones, and with lots of internal state (asymptotically approaching one-time pad properties), and those which can be mapped to silicon real estate efficiently both in time (few gate delays, GBps data rates) and in space (the silicon real estate consumed for each bit of PRNG state). What is a provably strong PRNG? Strong against what? If I'm supposed to know this, and have forgotten it, a pointer will suffice. I know what the attacks are for a crypto-strong plain-ole-analog-based-RNG. Its quite easy to generate apparently-random (ie, PRNGs) from block ciphers being fed, say, integers, or their own output, etc. These can be made small and fast in hardware. Large families of these can be constructed e.g. by varying bits e.g., in Blowfish's S-tables, etc. Yes. If you know what PRNG somebody is using and you know the seed you know the output. Seems to me the best a PRNG could hope to get is a situation where, looking at a long stream of output, there's no way of predicting the future output that's more efficient than guessing the initial seed. I don't think achieving that is all that hard in practice. Oh surely you can do better than that - making it hard to guess the seed is also clearly a desirable property (and one that the square root rng does not have). Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff
Two ideas for random number generation
hi, Here are two ideas which came up in my mind. Since I have done a few diagrams for illustration and thought that it will not be a good idea as attachment,I have put the ideas at the following url http://www.ircsuper.net/~neo/ I sincerely appreciate ur comments.Thank u for ur time. Regards Data. __ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
Re: Two ideas for random number generation
For the start, before deeper analysis, it would be a good idea to run Diehard on the output, just to check for the obvious problems. = end (of original message) Y-a*h*o-o (yes, they scan for this) spam follows: Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
