Random number generator-Idea 1
hi, With reference to the following url http://www.ietf.org/rfc/rfc1750.txt As in idea 1 what about choosing 2 independent bit file streams. Then as in RFC 1750 6.1.1 A Trivial Mixing Function (page 14), make a 3rd bit file stream such that We xor For i=0 to n bit(i)file3=bit(i)file1 (xor) bit(i) file2 and follow idea 1? Is the problem solved and idea 1 worthy? Regards Data. __ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
Re:Two ideas for random number generators
hi, Using Transition Mappings to De-Skew Randomness Recommendations for Security RFC 1750 An extract from it. Another technique, originally due to von Neumann [VON NEUMANN], is to examine a bit stream as a sequence of non-overlapping pair | pair |probability | | 00 | (0.5 - e)^2 = 0.25 - e + e^2 | | 01 | (0.5 - e)*(0.5 + e) = 0.25 - e^2 | | 10 | (0.5 + e)*(0.5 - e) = 0.25 - e^2 | | 11 | (0.5 + e)^2 = 0.25 + e + e^2 | This technique will completely eliminate any bias but at the expense of taking an indeterminate number of input bits for any particular desired number of output bits. The probability of any particular pair being discarded is 0.5 + 2e^2 so the expected number of input bits to produce X output bits is X/(0.25 - e^2). Eastlake, Crocker Schiller [Page 12] RFC 1750Randomness Recommendations for SecurityDecember 1994 This technique assumes that the bits are from a stream where each bit has the same probability of being a 0 or 1 as any other bit in the stream and that bits are not correlated, i.e., that the bits are identical independent distributions. If alternate bits were from two correlated sources, for example, the above analysis breaks down. The above technique also provides another illustration of how a simple statistical analysis can mislead if one is not always on the lookout for patterns that could be exploited by an adversary. If the algorithm were mis-read slightly so that overlapping successive bits pairs were used instead of non-overlapping pairs, the statistical analysis given is the same; however, instead of provided an unbiased uncorrelated series of random 1's and 0's, it instead produces a totally predictable sequence of exactly alternating 1's and 0's. A few doubts regarding the above. Another technique, originally due to von Neumann [VON NEUMANN], is to examine a bit stream as a sequence of non-overlapping pairs What do they mean by bit stream as a sequence of non-over lapping pairs? Also isn't idea-1 of my earlier post Two idea's for random number generators very similar to this? www.neo.ircsuper.net Wouldn't the problem in idea 1 be solved if I choose a bit stream as a sequence of non-over lapping pairs? If we choose bits that are from a stream where each bit has the same probability of being a 0 or 1 as any other bit in the stream and that bits are not correlated, i.e., that the bits are identical independent distributions. Would n't idea 1 work? Regards Data. __ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/
RE: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
Most hardware solutions that I'm aware of support 1024-bit modular arithmetic. I don't know how easy or hard it is to do 2048-bit ops with 1024-bit primitives, or is there any 2048-bit HW around. = 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/
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.
Hard drive encryption [was: RE: Biometrics helping privacy]
Peter wrote: I have seen hard drives which do sector level encryption, and hook into the bios so that the pw request happens before any system sw runs. This is a good solution (modulo bios hacking)[...] Any such hard drives that I have seen keep the actual encryption key utilized in firmware on the drive, using the password provided during boot merely to authorize the drive to apply the internally stored encryption key, thus making the encryption provided by the drive utterly useless against invasive analysis by an attacker with a modicum of skill in the art. One very promising project underway to get us closer to the goal of transparent universal drive encryption is GEOM, a component scheduled for inclusion in the release of FreeBSD 5.0. (GEOM also will provide a host of other highly desirable mass storage management features in addition to drive encryption). See http://phk.freebsd.dk/geom/ for more information. --Lucky
RE: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
Lucky is to be commended for igniting a neglected aspect of the crypto wars: what happens to cryptosystems over time after they have been invented, tested, criticized, vetted and conditionally trusted, then gradually widely distributed as the best available under practical usage, then compromised by direct attack or undermining from within -- the cycle of all previous cryptosystems. This inevitable vulnerability comes about for the reason Lucky states: sloppiness, laziness, inattention to keeping up with new means of attack, desire to exploit markets based on widespread public and institutional trust, and, not least, succumbing to the stigma of being too paranoid. Attackers of cryptosystems count on this. Inventors of cryptosystems dread gradual decline in their successive implementations, if they continue to care about security and are not enjoying the economic fruits of success and to hell with authentic security, so what if there are a few hundred victims, collateral damage, think big, think Wall Street. Any well-known and trusted cryptosystem should be highly suspect of being compromised, and total reliance upon it is immensely foolhardy. That is why no military grade cryptosystem is wholly trusted by the military in times of war or when war is threatening, which now means all the time. If you are at war with government no government-approved cryptosystem is to be trusted, which means no system in most countries and certainly not in the US. And no commercially successful cryptosystem is to be wholly trusted for its success rests in part on its acceptance by government -- still the prime purchaser of such systems and maker of markets. We will learn someday of currently trusted systems, as we have of those in the past, more or less when they were compromised. More or less reflects that the greatest cryptosystem deceptions of the past 100 years are still classified and will remain so in order to not disturb blind faith in accessible, practical comsec. Without blind faith in comsec, intelligence gathering would be much more difficult for few would transmit their most valuable secrets via trusted systems. And even those who, like Lucky, advocate stronger implementations, remain vulnerable to weaknesses of their correspondents' usage -- who may quote Lucky's transmittal in response, send it to others without Lucky knowing, tamper with his information, violate his trust wittingly or otherwise. One could argue that the increased use of crypto has enhanced intelligence gathering despite government protests widely disseminated to induce trust in the systems, again as with prior deceptions. Too little sustained testing of trusted systems is done in the private realm, and there too little skepticism of widely used systems by enthusiasts and market makers. Here's to Lucky for reminding of the price of success, for pointing to how the crypto wars have gone deeply undercover where they usually are fought without mercy and never with courteous discourse.
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
(P)RNG's and k-distribution
It has been suggested by some that a PRNG can be created that is -not- repeating. There is a property of -all- RNG's that is called k-distribution. For a RNG to -be- a RNG it -must- be infinity-distributed. This means that there are -no- string repititions -ever-. If this can't be guaranteed then the algorithm can be a PRNG (there are other conditionals). A PRNG -by definition- can -not- rule out repititions of some very_large-distribution. Hence, -all- PRNG's must assume - even in principle- some very_large-distribution sequence. So, the statement My PRNG has no modulus is incorrect even in principle. The Art of Computer Programming Volume 2 Seminumerical Algorithms, 3ed D.E. Knuth ISBN 0-201-89684-2 Chapter 3 Random Numbers Section 3.5 What is a Random Sequence? He also has some things to say about Pi and its applicability as a seed in this same section, and the assumptions that people make that are not proven. The representation of of a positive real number n in the radix-b may be regarded as a b-ary sequence; for example, pi corresponds to the 10-ary sequence 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, ... People have conjectured that this sequence is infinity-distributed, but nobody has yet been able to prove it is even 1-distributed. It's worth pointing out that the test of 'randomness' are -all' statistical. They all have a margin of error. There is the a priori recognition of 'window' effect. Which gets to the reference I mentioned in one post about 'Garden of Eden' sequences. These would be sequences that can -never- happen from -any- of the given input states. It is a sequence of states the generator can not make because they are outside the scope of its algorithm (there is usually a data set independency assumed - you can be in -all- combinations of start state). At least as far as I know this could apply to both (P)RNG's. -- 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: Quantum mechanics, England, and Topos Theory
On 23 Apr 2002 at 18:56, Tim May wrote: On Tuesday, April 23, 2002, at 11:18 AM, Ken Brown wrote: Back nearer to on-topic, Tim's explanation why the world could not be predicted even if it were locally (microscopically) predictable sounds spot-on. It's not my idea, obviously. But the fact that I wrote it so quickly, and so glibly (he admits), is because it's so internalized to everything I think. I simply cannot _conceive_ of anyone thinking the Universe, let alone the Multiverse, is predictable in any plausible or operational sense. The sources of divergence (aka chaos, aka combinatorial explosion, aka Big O with a Vengeance) come in from all sides. I can explain why people might think it were. You could imagine that due to feedback mechanisms or statistical averaging, these small uncertainties tend to cancel each other out, provided you're confining your interest to macroscopic observables. For example, when a sheep dies you get more grass for the remaining sheep, which gets you more sheep again, so you can do a reasonable job of predicting sheep population without knowing anything about the fates of individual sheep. Similarly, if i cut a fart in an elevator, there's no telling where an indvidual stink molecule will go, but in not too long they'll be more or less uniformly spread throughout the elevator. I can't see how anyone would believe you would ever be able to predict, say, radio static. But I think 50 years ago most people believed that in principle you could predict the weather arbitrarily far into the future. And there are still people who believe you can predict stock prices based solely on the squiggles. These people are called technical traders by themselves and fools by others. George --Tim May He who fights with monsters might take care lest he thereby become a monster. And if you gaze for long into an abyss, the abyss gazes also into you. -- Nietzsche
