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: 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
