Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

i want to generate random number for example from [1..100]. The algorithm which would generates random number should work similarly like a "Linear congruential generator", like this:

$X_{n+1}≡(aX_n + c)\ (mod\ m)$

Where:
$c$ - increment should be something like 98979817
$a$ - should be used for security and should be great number
$X_n$ - initial number

However, I can't use this formula because my $m\ (mod m)$ is 100 so it's $m < c$ and $m < a$. While it should be $m > c$ and $m > a$.

Maybe there is something similar which is more secure than this?

share|improve this question
1  
If something can't be simply twisted to work, one has to look for alternatives. I suppose that a sufficiently good scheme that can be adapted for use in your applications could be RC4, see Wiki. –  Mok-Kong Shen Feb 4 '13 at 14:23
    
Beware that RC4 has some significant flaws. Careless operation might be vulnerable. See en.wikipedia.org/wiki/RC4#Security –  drxzcl Feb 6 '13 at 15:24

2 Answers 2

up vote 7 down vote accepted

Any Pseudo Random Number Generator using a Linear Congruential Generator, and no cryptography, is going to be unsafe, or at the very least unsatisfactory, per the criteria in our FAQ. Likely, a skilled adversary would be able to predict future output from some amount of past output with moderate work; at best, that won't happen, but there will be no sound argument that it is not possible. There are many more or less difficult to read papers making that point. A recent question, another there, further illustrate this. If the more secure requirement is to be taken any seriously, it is best to forget the LCG entirely, and use cryptography.

There should be three steps in a secure "Random Number Generator depending on a key" producing an output sequence uniformly distributed on the integers in $[1…100]$:

  1. Stretching of the initial key. The purpose is to make brute force search of the key infeasible, or at least costly. That is superfluous if the key is already both wide enough (say 120 bit or more; 256 is aplenty) and chosen uniformly at random; in almost any other case, including when a human is expected to remember (or worse choose) the key, a deliberately slow transformation of that input is highly recommended. In many cases (notably: the combination of multiple users and use of password), the initial key should be salted while stretched. The standard building block for these functions is a Password-Based Key Derivation Function. A common one is PBKDF2; Bcrypt is much safer; the current state of the art is Scrypt.

  2. A Cryptographically Secure Pseudo Random Number Generator, or equivalently the Keystream Generator of a secure Stream Cipher. We'll feed it the (possibly stretched) key (in the input named seed or key), and then it will output on demand practically any number of random-looking bits that we may want. The design of that cryptographic primitive strives to make that output computationally indistinguishable from random by an adversary not knowing the seed. There are a plethora of CSPRNG and Stream Ciphers to choose among, and the best choice depends on context. If it must be fast on any modern CPU, Salsa20 comes to mind.

  3. Post-conditioning to obtain outputs uniformly distributed on the desired output interval $[u…v]$, here $[1…100]$. One simple suitable technique (slightly wasteful, but that does not matter since the CSPRNG is likely fast) is to:

    • Find the lowest integer $w$ such that $2^w\ge v-u+1$; here that is $w=7$, since $128\ge100$.
    • Obtain $w$ bits using the CSPRNG, forming an integer $r$ in range $[0…2^w-1]$, until $r<v-u+1$ (otherwise, discard $r$ and repeat this step).
    • Output $u+r$, and proceed to the previous step as needed to obtain more output.

If being simple and based on a LCG is important, and being secure is pointless as long as the output is good enough to pass some simple statistical test, the following procedure builds a LCG and post-condition its output (I assume the range $[u…v]$ has width no more than about $2^{16}$).

  1. Choose $m=2^{64}$ (or a convenient higher power of $2$), $a=3141592621$, $c=1$ (this conforms to more detailed advice in TAOCP Volume 2, section 3.6; except that I kept $a$ unchanged, rather than taking the risk to scale it with $m$); the C or C++ type unsigned long long, if available, is suitable for implicit reduction modulo some appropriate implementation-dependent $m$.
  2. Find $w$ from the interval $[u…v]$ as above (here $w=7$ for $[1…100]$).
  3. Set $X$ to the key truncated to the bit width of $m$ (Repeat: security is out of scope! But still, it does not harm to feed other key bits in $c$, as long as it is forced to be odd).
  4. Set $X$ to $a⋅X+c\bmod m$; in C that's X = a*X+c;.
  5. Form $r$ in range $[0…2^w-1]$ from the $w$ high bits of $X$; in C that's r = X>>(W-w); where W is the bit width of the unsigned integer type chosen for X, and $m=2^{\mathtt W}$.
  6. If $r\ge v-u+1$, proceed to step 4.
  7. Output $u+r$, and proceed to step 4 as needed to obtain more output.
share|improve this answer

For your purposes the following should be adequately secure: Choose $m$ as large as is convenient for the data type you're using. Choose a random odd $a$ and whatever $c$ you like. The sequence of successive X values will look random. To get your random number in the range 1 to 100 inclusive, calculate $1+(X_n \mod 100)$

share|improve this answer
    
This technique generates numbers that are appreciably biased. Independently of that, it is not secure in a cryptographic sense: the state (and thus all forthcoming and previous output) can be recovered with little effort from a small list of consecutive outputs. –  fgrieu Feb 4 '13 at 20:02
2  
There's worse: if $m$ is even (as implied by $m$ as large as is convenient, which points to a power of 2), then the low bit of what's generated is constant (for even $c$) or toggling between 0 and 1 (for odd $c$). Fact is: both choice of parameters of the LCG, and how its output is reduced to range [1..100], are deeply flawed. –  fgrieu Feb 4 '13 at 22:32
    
@fgrieu What you say is true. I forgot the lower bit would toggle and should have insisted on an odd $m$. However the level of my answer was appropriate for the question. We both know that any simple scheme based on a linear congruential generator is flawed and therefore "Streetboy" is not looking for something secure but needs instead to be told that he doesn't need to set m to 100 just because he needs numbers in that range. Now give me some upvotes! –  Barack Obama Feb 5 '13 at 11:27
    
Odd $m$ is not enough: for a post-conditioning of such a LCG using $\bmod 100$, it is necessary (not necessarily sufficient) that $\gcd(m,100)=1$; with $m=2^{2^k}-1$ and $k>1$ (a nice fit for odd and as large as is convenient for the data type), that's not the case, and the rightmost digit of the output in base 5 will follow a cyclic pattern of length 5 (or be constant); that will be discernible to the naked eye in base 10. Also the question asks something more secure; to me that's antagonist with not looking for something secure. –  fgrieu Feb 5 '13 at 17:03
    
@fgrieu You're quite right. Although I'm sure it's more fun to pick holes in other people's answers than it is to craft your own, now you've already expended all this effort, why don't you craft a "proper" answer and see whether it gets accepted eh? –  Barack Obama Feb 5 '13 at 17:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.