RFC：符合clc标准的伪随机数生成器 [英] RFC: clc-compliant pseudo-random number generator
问题描述
在这里经常出现的一个问题是伪随机数生成器的质量很差，这些伪随机数生成器提供了许多实际的b
实现。因此，我们必须使用rand（）返回的高位而不是
低位来推荐
之类的东西，避免使用rand（）对于任何想要
相当随机的数字，如果你想要超过
大约不使用rand（）。 UINT_MAX完全不同的序列，依此类推。
所以我写了一些使用RC4的PRNG代码，种子高达256
字节。这里是。我相信它符合clc标准。评论
这个和其他任何东西都是受欢迎的。
--------------------- -------------------------------------------------
/ *
* prng.c - 便携式，符合ISO C90和C99标准的高质量
*基于所谓的伪随机数发生器RC4
*密码。此PRNG应适用于大多数通用
*用途。不建议用于加密或财务
*目的。不是线程安全的。
* /
/ *
*版权所有（c）2004 Ben Pfaff< bl * @ cs.stanford.edu> ;.
*保留所有权利。
*
*以源代码和二进制形式重新分发和使用，或者<如果满足
*以下条件，则允许不加修改
*：
*
* 1。源代码的再分发必须保留上述
*版权声明，此条件列表以及以下
*免责声明。
*
* 2.二进制形式的再分发必须在文档和/中复制上述
*版权声明，此条件列表以及以下
*免责声明或其他材料
*随分发提供。
*
* 3.作者和贡献者的姓名可能不是用于
*认可或推广源自该软件的产品，不含
*特定prio r书面许可。
*
*本软件由作者和贡献者提供`AS
*是''''和任何明示或暗示的担保，包括但不限于b $ b * *适用于适销性的暗示担保和
*适用于特定用途的担保不予承认。在任何情况下
*对作者或贡献者均不对任何直接负责，
*间接，偶然，特殊，惩戒或后续
*损害（包括但不限于，采购* b $ b *替代商品或服务;损失使用，数据或利润;
*或业务中断）但不会引起以及任何理由
*责任，无论是合同，严格责任还是侵权
*（包括疏忽或其他）以任何方式产生
*使用本软件，即使已被告知可能性
*此类损害。
*
* /
#include" prng.h"
#include< assert.h>
#include< float.h> ;
#include< limits.h>
#include< math.h>
#include< time.h>
/ *基于RC4的伪随机状态。 * /
静态unsigned char s [256];
static int s_i，s_j;
/ *非零如果PRNG有被播种了。 * /
static int seded;
/ *如果可能，请利用内联。 * /
#if __STDC_VERSION__> = 199901L
#define INLINE inline
#else
#define INLINE
#endif
/ *交换字节。 * /
静态INLINE void
swap_byte（unsigned char * a，unsigned char * b）
{
unsigned char t = * a;
* a = * b;
* b = t;
}
/ *如果KEY非空并且SIZE非零，则根据BUF中的SIZE字节为
伪随机数生成器播种。
At大多数BUF的前256字节都被使用。如果KEY为null
指针并且SIZE为零，则根据当前时间播种伪随机数
生成器。
如果用户在任何prng_get
函数之前未调用此函数，则会自动调用该函数以获取基于时间的
种子。 * /
void
prng_seed（const void * key_，size_t size）
{
const unsigned char * key = key_;
size_t key_idx;
int i，j;
断言（（关键！= NULL&& ; size> 0）||（key == NULL&& size == 0））;
if（key == NULL）
{
静态时间_t t;
t =（t == 0）？ time（NULL）：t + 1;
key =（void *）& t;
size = sizeof t;
}
for（i = 0; i< 256; i ++）
s [i] = i;
for（key_idx = 0，i = j = 0; i <256; i ++）
{
j =（j + s [i] + key [key_idx]）& 255;
swap_byte（s + i，s + j）;
if（++ key_idx> = size）
key_idx = 0 ;
}
s_i = s_j = 0;
种子= 1;
}
/ *返回[0,255]范围内的伪随机整数。 * /
unsigned char
prng_get_octet（无效）
{
if（！seeded）
prng_seed（NULL，0）;
s_i =（s_i + 1）& 255;
s_j =（s_j + s [s_i]）& 255;
swap_byte（s + s_i，s + s_j）;
返回s [（s [s_i] + s [s_j]）& 255];
}
/ *返回[0，UCHAR_MAX]范围内的伪随机整数。 * /
unsigned char
prng_get_byte（void）
{
if（UCHAR_MAX == 255）
{
/ * 8位字节的正常情况。 * /
返回prng_get_octet（）;
}
其他
{
/ *处理超大字节。 * /
unsigned byte = prng_get_octet（）;
unsigned done = 255;
while（（unsigned char）done！= UCHAR_MAX）
{
byte =（byte<< 8）| prng_get_octet（）;
done =（完成<< 8）| 255;
}
返回字节;
}
}
/ *用SIZE伪随机字节填充BUF。 * /
void
prng_get_bytes（void * buf_，size_t size）
{
unsigned char * buf;
for（buf = buf_; size--> 0; buf ++）
* buf = prng_get_byte（）;
} $ / $
/ *返回[0，
ULONG_MAX]范围内的伪随机无符号long。 * /
unsigned long
prng_get_ulong（无效）
{
unsigned long ulng = prng_get_octet（）;
unsigned long done = 255;
while（done！= ULONG_MAX）
{
ulng =（ulng<< 8）| prng_get_octet（）;
done =（完成<< 8）| 255;
}
返回ulng;
}
/ *返回在[0，LONG_MAX]范围内的伪随机长度。 * /
长
prng_get_long（无效）
{
for（;;）
{
unsigned ulng = prng_get_ulong（）;
if（ulng< = LONG_MAX）
返回ulng;
}
}
/ *返回[0，
UINT_MAX]范围内的伪随机无符号整数]。 * /
未签名
prng_get_uint（无效）
{
unsigned uint = prng_get_octet（）;
unsigned done = 255;
while（done！= UINT_MAX）
{
uint =（uint << 8）| prng_get_octet（）;
done =（完成<< 8）| 255;
}
返回uint;
}
/ *返回一个伪随机int，范围为[0，INT_MAX]。 * /
int
prng_get_int（无效）
{
for（;;）
{
unsigned uint = prng_get_uint（）;
if（uint< = INT_MAX）
return uint;
}
}
/ *返回统一
分布中的伪随机浮点数范围[0,1）。 * /
双倍
prng_get_double（无效）
{
for（;;）
{
unsigned long ulng = prng_get_ulong（）;
if（ulng！= ULONG_MAX）
return（double）ulng / ULONG_MAX ;
}
}
/ *从
$ b返回一个伪随机浮点数$ b分布，平均值为0，标准差为1.（乘以所需标准偏差的结果为
，然后加上
所需的平均值。）* /
double
prng_get_double_normal（void）
{
/ * Knuth，_The Computer of Computer Programming_，Vol。 2,3.4.1C，
算法P. * /
静态双倍next_normal = DBL_MAX;
double this_normal;
if（next_normal！= DBL_MAX）
{
this_normal = next_normal;
next_normal = DBL_MAX;
}
else
{
double v1，v2，s;
do
{
double u1 = prng_get_double（）;
double u2 = prng_get_double（）;
v1 = 2.0 * u1 - 1.0;
v2 = 2.0 * u2 - 1.0;
s = v1 * v1 + v2 * v2;
}
while（s> = 1）;
this_normal = v1 * sqrt（-2。* log（s）/ s）;
next_normal = v2 * sqrt（-2。* log（s）/ s）;
}
返回this_normal;
}
-------------------------------------- --------------------------------
#ifndef PRNG_H_INCLUDED
#define PRNG_H_INCLUDED
#include< stddef.h>
void prng_seed（const v oid *，size_t）;
unsigned char prng_get_octet（void）;
unsigned char prng_get_byte（void）;
void prng_get_bytes（void *， size_t）;
unsigned long prng_get_ulong（void）;
long prng_get_long（void）;
unsigned prng_get_uint（void）;
int prng_get_int（void）;
double prng_get_double（void）;
double prng_get_double_normal（void）;
#endif / * prng.h * /
--------------------------------- -------------------------------------
-
只有一件事会让他们不再讨厌你。
那就是你做得很好，他们不能忽视你。
我告诉他们你是最好的。现在你该死的好了。
- 奥森斯科特卡，_Ender'的游戏_
One issue that comes up fairly often around here is the poor
quality of the pseudo-random number generators supplied with many
C implementations. As a result, we have to recommend things like
using the high-order bits returned by rand() instead of the
low-order bits, avoiding using rand() for anything that wants
decently random numbers, not using rand() if you want more than
approx. UINT_MAX total different sequences, and so on.
So I wrote some PRNG code that uses RC4, with a seed of up to 256
bytes. Here it is. I believe it is clc-compliant. Comments on
this and anything else are welcome.
----------------------------------------------------------------------
/*
* prng.c - Portable, ISO C90 and C99 compliant high-quality
* pseudo-random number generator based on the alleged RC4
* cipher. This PRNG should be suitable for most general-purpose
* uses. Not recommended for cryptographic or financial
* purposes. Not thread-safe.
*/
/*
* Copyright (c) 2004 Ben Pfaff <bl*@cs.stanford.edu>.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the
* following conditions are met:
*
* 1. Redistributions of source code must retain the above
* copyright notice, this list of conditions and the following
* disclaimer.
*
* 2. Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
*
* 3. The author''s and contributors'' names may not be used to
* endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS
* IS'''' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
* FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
* SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
* OF SUCH DAMAGE.
*
*/
#include "prng.h"
#include <assert.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <time.h>
/* RC4-based pseudo-random state. */
static unsigned char s[256];
static int s_i, s_j;
/* Nonzero if PRNG has been seeded. */
static int seeded;
/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L
#define INLINE inline
#else
#define INLINE
#endif
/* Swap bytes. */
static INLINE void
swap_byte (unsigned char *a, unsigned char *b)
{
unsigned char t = *a;
*a = *b;
*b = t;
}
/* If KEY is non-null and SIZE is nonzero, seeds the
pseudo-random number generator based on the SIZE bytes in BUF.
At most the first 256 bytes of BUF are used. If KEY is a null
pointer and SIZE is zero, seeds the pseudo-random number
generator based on the current time.
If this function is not called by the user before any prng_get
function, it is called automatically to obtain a time-based
seed. */
void
prng_seed (const void *key_, size_t size)
{
const unsigned char *key = key_;
size_t key_idx;
int i, j;
assert ((key != NULL && size > 0) || (key == NULL && size == 0));
if (key == NULL)
{
static time_t t;
t = (t == 0) ? time (NULL) : t + 1;
key = (void *) &t;
size = sizeof t;
}
for (i = 0; i < 256; i++)
s[i] = i;
for (key_idx = 0, i = j = 0; i < 256; i++)
{
j = (j + s[i] + key[key_idx]) & 255;
swap_byte (s + i, s + j);
if (++key_idx >= size)
key_idx = 0;
}
s_i = s_j = 0;
seeded = 1;
}
/* Returns a pseudo-random integer in the range [0,255]. */
unsigned char
prng_get_octet (void)
{
if (!seeded)
prng_seed (NULL, 0);
s_i = (s_i + 1) & 255;
s_j = (s_j + s[s_i]) & 255;
swap_byte (s + s_i, s + s_j);
return s[(s[s_i] + s[s_j]) & 255];
}
/* Returns a pseudo-random integer in the range [0,UCHAR_MAX]. */
unsigned char
prng_get_byte (void)
{
if (UCHAR_MAX == 255)
{
/* Normal case for 8-bit bytes. */
return prng_get_octet ();
}
else
{
/* Handle oversize bytes. */
unsigned byte = prng_get_octet ();
unsigned done = 255;
while ((unsigned char) done != UCHAR_MAX)
{
byte = (byte << 8) | prng_get_octet ();
done = (done << 8) | 255;
}
return byte;
}
}
/* Fills BUF with SIZE pseudo-random bytes. */
void
prng_get_bytes (void *buf_, size_t size)
{
unsigned char *buf;
for (buf = buf_; size-- > 0; buf++)
*buf = prng_get_byte ();
}
/* Returns a pseudo-random unsigned long in the range [0,
ULONG_MAX]. */
unsigned long
prng_get_ulong (void)
{
unsigned long ulng = prng_get_octet ();
unsigned long done = 255;
while (done != ULONG_MAX)
{
ulng = (ulng << 8) | prng_get_octet ();
done = (done << 8) | 255;
}
return ulng;
}
/* Returns a pseudo-random long in the range [0, LONG_MAX]. */
long
prng_get_long (void)
{
for (;;)
{
unsigned ulng = prng_get_ulong ();
if (ulng <= LONG_MAX)
return ulng;
}
}
/* Returns a pseudo-random unsigned int in the range [0,
UINT_MAX]. */
unsigned
prng_get_uint (void)
{
unsigned uint = prng_get_octet ();
unsigned done = 255;
while (done != UINT_MAX)
{
uint = (uint << 8) | prng_get_octet ();
done = (done << 8) | 255;
}
return uint;
}
/* Returns a pseudo-random int in the range [0, INT_MAX]. */
int
prng_get_int (void)
{
for (;;)
{
unsigned uint = prng_get_uint ();
if (uint <= INT_MAX)
return uint;
}
}
/* Returns a pseudo-random floating-point number from the uniform
distribution with range [0,1). */
double
prng_get_double (void)
{
for (;;)
{
unsigned long ulng = prng_get_ulong ();
if (ulng != ULONG_MAX)
return (double) ulng / ULONG_MAX;
}
}
/* Returns a pseudo-random floating-point number from the
distribution with mean 0 and standard deviation 1. (Multiply
the result by the desired standard deviation, then add the
desired mean.) */
double
prng_get_double_normal (void)
{
/* Knuth, _The Art of Computer Programming_, Vol. 2, 3.4.1C,
Algorithm P. */
static double next_normal = DBL_MAX;
double this_normal;
if (next_normal != DBL_MAX)
{
this_normal = next_normal;
next_normal = DBL_MAX;
}
else
{
double v1, v2, s;
do
{
double u1 = prng_get_double ();
double u2 = prng_get_double ();
v1 = 2.0 * u1 - 1.0;
v2 = 2.0 * u2 - 1.0;
s = v1 * v1 + v2 * v2;
}
while (s >= 1);
this_normal = v1 * sqrt (-2. * log (s) / s);
next_normal = v2 * sqrt (-2. * log (s) / s);
}
return this_normal;
}
----------------------------------------------------------------------
#ifndef PRNG_H_INCLUDED
#define PRNG_H_INCLUDED
#include <stddef.h>
void prng_seed (const void *, size_t);
unsigned char prng_get_octet (void);
unsigned char prng_get_byte (void);
void prng_get_bytes (void *, size_t);
unsigned long prng_get_ulong (void);
long prng_get_long (void);
unsigned prng_get_uint (void);
int prng_get_int (void);
double prng_get_double (void);
double prng_get_double_normal (void);
#endif /* prng.h */
----------------------------------------------------------------------
--
"There''s only one thing that will make them stop hating you.
And that''s being so good at what you do that they can''t ignore you.
I told them you were the best. Now you damn well better be."
--Orson Scott Card, _Ender''s Game_
推荐答案
Ben Pfaff写道：
Ben Pfaff wrote:
这里经常出现的一个问题是随着许多实现提供的伪随机数生成器的质量差。因此，我们必须使用rand（）返回的高位而不是
低位来推荐
之类的东西，避免对任何想要的东西使用rand（）
相当随机的数字，如果你想要超过
大约不使用rand（）。 UINT_MAX完全不同的序列，依此类推。
所以我写了一些使用RC4的PRNG代码，种子最多256个字节。这里是。我相信它符合clc标准。欢迎点评这个和其他任何内容。
One issue that comes up fairly often around here is the poor
quality of the pseudo-random number generators supplied with many
C implementations. As a result, we have to recommend things like
using the high-order bits returned by rand() instead of the
low-order bits, avoiding using rand() for anything that wants
decently random numbers, not using rand() if you want more than
approx. UINT_MAX total different sequences, and so on.
So I wrote some PRNG code that uses RC4, with a seed of up to 256
bytes. Here it is. I believe it is clc-compliant. Comments on
this and anything else are welcome.
Niiice。
问：你打算发表吗？这个更方便的地方，比如
sourceforge或freshmeat？
问：您实际测试了哪些平台？
问：是否有潜伏在某处的测试应用程序可以发布？
/ J
Niiice.
Q: Are you going to publish this somewhere more accessible, like
sourceforge or freshmeat?
Q: What platforms have you actually tested this on?
Q: Is there a test application lurking somewhere that you can publish?
/J
Ben Pfaff < bl*@cs.stanford.edu>在消息中写道
news：87 ************ @ pfaff.stanford.edu ...
"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@pfaff.stanford.edu...
一个经常出现的问题这里是伪随机数生成器的质量很差，随着许多实现而提供。因此，我们必须使用rand（）返回的高位而不是
低位来推荐
之类的东西，避免对任何想要的东西使用rand（）
相当随机的数字，如果你想要超过
大约不使用rand（）。 UINT_MAX完全不同的序列，依此类推。
所以我写了一些使用RC4的PRNG代码，种子最多256个字节。这里是。我相信它符合clc标准。评论
这个和其他任何东西都是受欢迎的。
One issue that comes up fairly often around here is the poor
quality of the pseudo-random number generators supplied with many
C implementations. As a result, we have to recommend things like
using the high-order bits returned by rand() instead of the
low-order bits, avoiding using rand() for anything that wants
decently random numbers, not using rand() if you want more than
approx. UINT_MAX total different sequences, and so on.
So I wrote some PRNG code that uses RC4, with a seed of up to 256
bytes. Here it is. I believe it is clc-compliant. Comments on
this and anything else are welcome.
两个评论：
- 因为你使用RC4，如果你真的想要加密
安全，你需要在初始化时丢弃密钥流的某些部分
时间。关于你需要丢弃多少的估计会有所不同 - 我已经看到了估计256到2048字节的b $ b。
- 我相信为rand（）定义的行为是，如果没有播种它被称为
，它就好像用户做了srand（1）。你没有;相反，
你根据时间种下它。
-
poncho
Two comments:
- Since you are using RC4, if you really want to be cryptographically
secure, you''ll need to discard some part of the keystream at initialization
time. Estimates as to how much you need to discard varies somewhat -- I''ve
seen estimates of 256 - 2048 bytes.
- I believe that the defined behavior for rand() is that if it is called
without seeding, it acts as if the user did srand(1). You don''t; instead,
you seed it based on time.
--
poncho
Johan Lindh< jo *** @ linkdata.getridofthis.se>写道：
Johan Lindh <jo***@linkdata.getridofthis.se> writes:
Ben Pfaff写道：
Ben Pfaff wrote:
这里经常出现的一个问题是伪随机数生成器的质量差提供了许多实现。因此，我们必须使用rand（）返回的高位而不是
低位来推荐
之类的东西，避免对任何想要的东西使用rand（）
相当随机的数字，如果你想要超过
大约不使用rand（）。 UINT_MAX完全不同的序列，等等。
所以我写了一些使用RC4的PRNG代码，种子最多256个字节。这里是。我相信它符合clc标准。评论
这个和其他任何东西都是受欢迎的。
Niiice。
问：你是否会在更容易发布的地方发布这个，比如
sourceforge或freshmeat？
One issue that comes up fairly often around here is the poor
quality of the pseudo-random number generators supplied with many
C implementations. As a result, we have to recommend things like
using the high-order bits returned by rand() instead of the
low-order bits, avoiding using rand() for anything that wants
decently random numbers, not using rand() if you want more than
approx. UINT_MAX total different sequences, and so on.
So I wrote some PRNG code that uses RC4, with a seed of up to 256
bytes. Here it is. I believe it is clc-compliant. Comments on
this and anything else are welcome.
Niiice.
Q: Are you going to publish this somewhere more accessible, like
sourceforge or freshmeat?
我将把它放在我的网页benpfaff.org/writings/clc
我很满意。
问：您实际测试了哪些平台？
仅限GNU / Linux i386。
问：是否有潜伏在某处的测试应用程序可以发布？
I will put it up on my webpage at benpfaff.org/writings/clc when
I am satisfied with it.
Q: What platforms have you actually tested this on?
GNU/Linux i386 only.
Q: Is there a test application lurking somewhere that you can publish?
还没有 - 我只是粗略地测试了它。我还没有决定在发布之前应该接收多少测试，或者
应该打包什么样的测试程序。
欢迎提出建议。
-
只是另一位C黑客。
Not yet--I have only tested it in a cursory fashion. I have not
yet decided how much testing it should receive before release, or
what sort of test routine it should be packaged with.
Suggestions are welcome.
--
Just another C hacker.
这篇关于RFC：符合clc标准的伪随机数生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
