Wheel factorization: Efficient?

[3.14159]

Retina: This uses Brent’s XORGEN ("a generalisation of Marsaglia's 'xorshift' random number generators") to simulate a uniform random distribution on the integers from 0 to n-1. I'm sure 3.14159 doesn't intend to use these for crypto.

*Picard facepalm* crypto depends on the inability to factor an integer.

It's as easy as adding the nextprime function to the random function, so it only generates prime numbers.

Examples: 148503599607675376327643096073847383532506324974398790977303580131975018496624075455825241101722900334753749994785762348854940183930011820566563438507 and 457585737543888599372885355510412842773181811746998283312123375548268116173690774280889442060057690415388596166818087804386186378332943916905105585384387.

[retina]

Originally Posted by 3.14159

*Picard facepalm* crypto depends on the inability to factor an integer.

It also depends upon the inability to predict the input numbers. If the "random" numbers are not so random after all then you compromise your security.

[CRGreathouse]

Edit: retina beat me to it. My point about breaking RNGs is the same as retina's point about prediction.

Originally Posted by 3.14159

*Picard facepalm* crypto depends on the inability to factor an integer.

It's as easy as adding the nextprime function to the random function, so it only generates prime numbers.

Examples: 148503599607675376327643096073847383532506324974398790977303580131975018496624075455825241101722900334753749994785762348854940183930011820566563438507 and 457585737543888599372885355510412842773181811746998283312123375548268116173690774280889442060057690415388596166818087804386186378332943916905105585384387.

Of course you don't want to use a standard random number generator for crypto, lest the attacker break your RNG rather than your encryption. And you want semiprimes, not primes.

I have a very basic Pari function rp(b) that generates random b-bit primes. At the moment it's implemented using nextprime(), but this is actually not the best method; preferable (for b > 2) is to generate random odd numbers in the range and test for (pseudo)primality, selecting a new random number if the number is composite. This avoids certain biases in the selection.

[3.14159]

It also depends upon the inability to predict the input numbers. If the "random" numbers are not so random after all then you compromise your security.

How would they be "predictable"? How does one suddenly become a crystal ball?

Of course you don't want to use a standard random number generator for crypto, lest the attacker break your RNG rather than your encryption. And you want semiprimes, not primes.

You misread my post. I meant: 148503599607675376327643096073847383532506324974398790977303580131975018496624075455825241101722900334753749994785762348854940183930011820566563438507 * 457585737543888599372885355510412842773181811746998283312123375548268116173690774280889442060057690415388596166818087804386186378332943916905105585384387.

And, the risk of an attacker actually succeeding is minimal, as most people are idiots when it comes to computers. (Unfortunately, that set of people includes me.)

I have a very basic Pari function rp(b) that generates random b-bit primes. At the moment it's implemented using nextprime(), but this is actually not the best method; preferable (for b > 2) is to generate random odd numbers in the range and test for (pseudo)primality, selecting a new random number if the number is composite. This avoids certain biases in the selection.

If the method for generation of random odd numbers is the same as that for primes, isn't there no improvement in how "random" the output is?

[CRGreathouse]

Originally Posted by 3.14159

How would they be "predictable"? How does one suddenly become a crystal ball?

See, e.g., the following:
http://www.computerworld.com/s/artic...ows_encryption
http://www.ibm.com/developerworks/li.../index.html#h4
http://www.ngssoftware.com/research/...Randomness.pdf

For a general overview, see
http://en.wikipedia.org/wiki/Cryptog...mber_generator

[CRGreathouse]

Originally Posted by 3.14159

If the method for generation of random odd numbers is the same as that for primes, isn't there no improvement in how "random" the output is?

No. Consider the interval 101 to 200. The method I outlined generates each prime in that range with probability 1/21 = 4.7...%. By contrast, your method gives 2% probability to 101 and 14% probability to 113.

[3.14159]

Originally Posted by CRGreathouse

See, e.g., the following:
http://www.computerworld.com/s/artic...ows_encryption
http://www.ibm.com/developerworks/li.../index.html#h4
http://www.ngssoftware.com/research/...Randomness.pdf

For a general overview, see
http://en.wikipedia.org/wiki/Cryptog...mber_generator

In that case, how has RSA not been entirely compromised in general?

[CRGreathouse]

Originally Posted by 3.14159

In that case, how has RSA not been entirely compromised in general?

By using CSPRNGs and RNGs instead of normal PRNGs.

[3.14159]

@CRG: You stated that any regular random integer generator is vulnerable to someone knowing how it works and is able to know what it will generate ahead of time.

Some sites claim randomness from other sources: Random.org claims atmospheric noise as the source of its random integer generator. I decided to perform a few tests. Now; here are the output numbers from random.org vs. those from PARI's random(n) function.

From random.org: (Range 1k to 2k)
1854
1003
1826
1083
1789
1050
1977
1480
1549
1137
1357
1745
1701
1680
1584

PARI's random(n):
1154
1775
1617
1654
1096
1423
1174
1231
1832
1295
1145
1338
1269
1442
1981
1576

There wasn't much of a difference there, but after a few more tests, I saw that PARI's generator was biased to the numbers closer to 2k.
There were rarely any numbers beginning in "10", "11", or "12"

[CRGreathouse]

Originally Posted by 3.14159

@CRG: You stated that any regular random integer generator is vulnerable to someone knowing how it works and is able to know what it will generate ahead of time.

Something like that. I don't claim that it's impossible that a PRNG would be cryptographically secure by accident, but it's pretty unlikely. Their characteristics are very different.

Originally Posted by 3.14159

There wasn't much of a difference there, but after a few more tests, I saw that PARI's generator was biased to the numbers closer to 2k.
There were rarely any numbers beginning in "10", "11", or "12"

I doubt this is more than an anomaly:

sum(n=1,1e6,1000+random(1000)<1300)
%1 = 300219

which is well within the expected range N(300000, 1000).

There shouldn't be any massive defects of that sort. However there are smaller defects that could allow an attacker to reconstruct the internal state of the PRNG and therefore guess future outcomes.

[CRGreathouse]

Originally Posted by 3.14159

Some sites claim randomness from other sources: Random.org claims atmospheric noise as the source of its random integer generator.

That's an RNG, not a PRNG. (That site actually calls them TRNGs, a synonym for RNGs.)