aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--openssl.c108
1 files changed, 105 insertions, 3 deletions
diff --git a/openssl.c b/openssl.c
index 5c46d9c..bea15c3 100644
--- a/openssl.c
+++ b/openssl.c
@@ -3790,10 +3790,112 @@ static int rand_ready(lua_State *L) {
} /* rand_ready() */
+static unsigned long long rand_llu(lua_State *L) {
+ unsigned long long llu;
+
+ if (!RAND_bytes((void *)&llu, sizeof llu))
+ throwssl(L, "rand.uniform");
+
+ return llu;
+} /* rand_llu() */
+
+/*
+ * The following algorithm for rand_uniform() is taken from OpenBSD's
+ * arc4random_uniform, written by Otto Moerbeek, with subsequent
+ * simplification by Jorden Verwer. Otto's source code comment reads
+ *
+ * Uniformity is achieved by generating new random numbers until the one
+ * returned is outside the range [0, 2**32 % upper_bound). This guarantees
+ * the selected random number will be inside [2**32 % upper_bound, 2**32)
+ * which maps back to [0, upper_bound) after reduction modulo upper_bound.
+ *
+ * --
+ * A more bit-efficient approach by the eminent statistician Herman Rubin
+ * can be found in this sci.crypt Usenet post.
+ *
+ * From: hrubin@odds.stat.purdue.edu (Herman Rubin)
+ * Newsgroups: sci.crypt
+ * Subject: Re: Generating a random number between 0 and N-1
+ * Date: 14 Nov 2002 11:20:37 -0500
+ * Organization: Purdue University Statistics Department
+ * Lines: 40
+ * Message-ID: <ar0igl$1ak2@odds.stat.purdue.edu>
+ * References: <yO%y9.19646$RO1.373975@weber.videotron.net> <3DCD8D75.40408@nospam.com>
+ * NNTP-Posting-Host: odds.stat.purdue.edu
+ * X-Trace: mozo.cc.purdue.edu 1037290837 9316 128.210.141.13 (14 Nov 2002 16:20:37 GMT)
+ * X-Complaints-To: ne...@news.purdue.edu
+ * NNTP-Posting-Date: Thu, 14 Nov 2002 16:20:37 +0000 (UTC)
+ * Xref: archiver1.google.com sci.crypt:78935
+ *
+ * In article <3DCD8D7...@nospam.com>,
+ * Michael Amling <nos...@nospam.com> wrote:
+ * >Carlos Moreno wrote:
+ *
+ * I have already posted on this, but a repeat might be
+ * in order.
+ *
+ * If one can trust random bits, the most bitwise efficient
+ * manner to get a single random integer between 0 and N-1
+ * can be obtained as follows; the code can be made more
+ * computationally efficient. I believe it is easier to
+ * understand with gotos. I am assuming N>1.
+ *
+ * i = 0; j = 1;
+ *
+ * loop: j=2*j; i=2*i+RANBIT;
+ * if (j < N) goto loop;
+ * if (i >= N) {
+ * i = i - N;
+ * j = j - N;
+ * goto loop:}
+ * else return (i);
+ *
+ * The algorithm works because at each stage i is uniform
+ * between 0 and j-1.
+ *
+ * Another possibility is to generate k bits, where 2^k >= N.
+ * If 2^k = c*N + remainder, generate the appropriate value
+ * if a k-bit random number is less than c*N.
+ *
+ * For N = 17 (numbers just larger than powers of 2 are "bad"),
+ * the amount of information is about 4.09 bits, the best
+ * algorithm to generate one random number takes about 5.765
+ * bits, taking k = 5 uses 9.412 bits, taking k = 6 or 7 uses
+ * 7.529 bits. These are averages, but the tails are not bad.
+ *
+ * (https://groups.google.com/forum/message/raw?msg=sci.crypt/DMslf6tSrD8/rv9rk6oP3r4J)
+ */
+static int rand_uniform(lua_State *L) {
+ if (lua_isnoneornil(L, 1)) {
+ unsigned long long r = rand_llu(L);
+
+ lua_pushnumber(L, r);
+
+ return 1;
+ } else {
+ unsigned long long N = luaL_checknumber(L, 1);
+ unsigned long long r, m;
+
+ luaL_argcheck(L, N > 1, 1, lua_pushfstring(L, "[0, %d): interval is empty", (int)N));
+
+ m = -N % N;
+
+ do {
+ r = rand_llu(L);
+ } while (r < m);
+
+ lua_pushnumber(L, (r % N));
+
+ return 1;
+ }
+} /* rand_uniform() */
+
+
static const luaL_Reg rand_globals[] = {
- { "bytes", &rand_bytes },
- { "ready", &rand_ready },
- { NULL, NULL },
+ { "bytes", &rand_bytes },
+ { "ready", &rand_ready },
+ { "uniform", &rand_uniform },
+ { NULL, NULL },
};
int luaopen__openssl_rand(lua_State *L) {