Re: Generating a large sequence of unique, random numbers

From: Benjamin Goldberg (ben.goldberg_at_hotpop.com)
Date: 05/28/03 

Date: Tue, 27 May 2003 22:41:19 -0400

Ulrich Eckhardt wrote:
>
> (f'up set)
>
> Hi everybody!
>
> One note up front, I'm not sure this really is the right place to ask
> but I'm a bit lost as to where I should ...
>
> The problem:
> Generate n unique codes of length l so that they are non-predictable.
[snip]
> My first approach was to use brute force: create codes, ignoring
> duplicate ones, but that approach requires large amounts of memory,
> entropy and later complicates storing and finding the state
> (used/unused) in a database.

Actually, it would be faster to simply create an array of numbers
0..n-1, and then shuffle this array, rather than generating items one at
a time and checking that they haven't already been used.

Of course, the later complications (storing all this data) still remain.

> My second approach was to simply take the numbers from 0 to n-1 and
> use some encrypting or hashing algorithm on them to produce the
> requested codes, but already there my knowledge ends. I have no idea
> whatsoever which algorithm to use or how to start in general.

This may be easier...

Here's one method:

Find the smallest M, such that M >= N, M = X*X, and X is an integer.

Generate four functions, F1, F2, F3, F4, which are random functions from
0..X-1 to 0..X-1. They need not be permutations (some outputs may
appear more than once, and not all outputs need appear). Since X is
significantly smaller than M, it wouldn't require huge amounts of
storage for F1..F4.

Take your counter, C (in the range 0..M-1), and turn it into two
integers, L and R, such that C = L+R*X. Then you encrypt them, using a
Luby-Rackoff construct, using F1..F4, producing L' and R'. Then
construct C'=L'+R'*X.

If C' >= N, discard it, advance the counter, and repeat.

Here's another method: Mail the author of the Hasty Pudding Cipher, and
ask him for the source of his algorithm. Use that to encrypt the
counter directly. 

-- 
$a=24;split//,240513;s/\B/ => /for@@=qw(ac ab bc ba cb ca
);{push(@b,$a),($a-=6)^=1 for 2..$a/6x--$|;print "$@[$a%6
]\n";((6<=($a-=6))?$a+=$_[$a%6]-$a%6:($a=pop @b))&&redo;}

Relevant Pages

  • Re: What is exponent?
    ... For simple description of RSA algorithm ... I also have the receiver's certificate (public key only). ... Use RSA to encrypt the session key ...
    (microsoft.public.dotnet.security)
  • Algorithm for license codes
    ... I know that posting here the details of a new algorithm would irk most of us, but this is the only place I know where I can ask for a reliable advice. ... I'm studying the feasibility of an algorithm based on public key cryptography that is suited for generating strong license codes for product activation. ... The public key part are the polynomials, the private part are an equivalent representation of the polynomials such that it's easy, given Y, to compute the reverse X = F^-1. ...
    (sci.crypt)
  • Re: A Revolutionary Breakthrough in Data Compression!
    ... What I have got is a minor improvement of the classic Huffman ... This is usually addressed by modifying the algorithm to arrange the ... even require rearrangement of the codes: ...
    (comp.compression)
  • Re: Use my your own HashAlgorithm Class
    ... Rather than use the EncryptValue / DecryptValue methods (which RSACryptoServiceProvider doesn't support), ... the Encrypt and Decrypt methods. ... >> doesn't know about your new algorithm. ... But CAPI doesn't work with OIDs directly, ...
    (microsoft.public.dotnet.security)
  • RE: Password encryption
    ... I'm not looking to encrypt a password. ... Because we usually don't need to use symmetric algorithm to ... we just store the hash of the ... Microsoft Online Community Support ...
    (microsoft.public.dotnet.framework)