在工程中有时候需要用到随机数函数来模拟一些情况,例如加密系统的密钥来源可以用随机数函数获取。
一般来说随机数函数需要有以下性质:
1:随机性,不存在统计学偏差,是完全散乱的数列。
2:不可预测性:不能从过去的的数列推算出下一个出现的数
3:不可重现性:除非数列保存下来,否则不能重新相同的数列(比较难)。
根据以上三个性质,可以将随机数函数分为“弱伪随机数”,“强伪随机数”,“真随机数”。
其中“真随机数”靠软件无法实现,需要借助物理性质,如量子密钥更具量子的偏振等物理状态生成的比特数据即真随机数,而生成随机数的设备称为“随机数生成器”。而“伪随机数”可以依靠软件来实现,该软件一般统称为“伪随机数生成器”。
本章主要围绕伪随机数进行叙述和论证。
伪随机数生成器,其结构为
例如下列以系统时间为种子实现内部初始化的伪随机数生成器,该函数在stdlib.h中提供。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
/*
伪随机数生成(系统调用)
为提高随机性,rand()函数生成的随机数取第一个字节
data[in, out]: 输入时表示待存随机数的缓存空间,输出时表示生成的随机数
len[in]: 需要生成随机数的大小,单位字节
*/
void prng_genrnd_by_system(unsigned char *data, unsigned int len)
{
unsigned int i = 0;
unsigned int j = 0;
/* 随机数函数初始化,以系统时间为种子 */
srand((unsigned int)time(NULL));
for ( i = 0; i < len; i++)
{
j = rand();
memcpy(data + i, &j, 1);
}
}
一个合格的伪随机数生成器需要具备长周期(避免短数列不断重复)和严谨的算法(验证其具备不可预测性),下面我具体列举一些伪随机数生成器的算法:
线性同余法
如C的rand函数和JAVA的java.util.Random类就是使用线性同余法,其为弱伪随机数算法,公式为:
Rn+1 = ( A x Rn + C )modM
例如第一个伪随机数 R0 = ( A x 种子 + C)modM
其中A、C、M为常量,A<M,C<M
第二个伪随机数R1 = ( A x R0 + C)modM
该算法生成的随机数列范围在0~M-1之间,算法的函数实现为
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
/* A、C、M为常量,A<M,C<M */
#define LINEAR_CONGRUENTIAL_METHOD_A (0x87)
#define LINEAR_CONGRUENTIAL_METHOD_C (0x32)
#define LINEAR_CONGRUENTIAL_METHOD_M (0x91)
/*
伪随机数生成(线性同余法)Rn+1 = ( A x Rn + C )modM
为提高随机性,每次产生的随机数取第一个字节
data[in, out]: 输入时表示待存随机数的缓存空间,输出时表示生成的随机数
len[in]: 需要生成随机数的大小,单位字节
*/
void prng_genrnd_by_linear_congruential_method(unsigned char *data, unsigned int len)
{
unsigned int i = 0;
unsigned int a = LINEAR_CONGRUENTIAL_METHOD_A;
unsigned int c = LINEAR_CONGRUENTIAL_METHOD_C;
unsigned int m = LINEAR_CONGRUENTIAL_METHOD_M;
unsigned int r0 = (unsigned int)time(NULL); // 以系统时间为种子
unsigned int r1 = 0;
for ( i = 0; i < len; i++)
{
r1 = (r0*a + c)%m;
memcpy(data + i, &r1, 1);
r0 = r1;
}
}
该算法不具备不可预测性,攻击者只要知晓初始化时A、C、M的值,便可以根据当前随机数列推算出下一个随机数列。
单向散列函数法
单向散列函数在之前的篇章中有提过,利用单向散列函数可以对一组数据生成特定的散列值。
在本章中将利用单向散列函数生成具备不可预测性的强伪随机数生成器。该算法的生成器将之前有进一步优化其结构为:
从随机数生成器结构上我们可以清楚的了解到,该算法利用了单向散列函数的强碰撞性和单向性使得伪随机数生成器拥有不可预知性,使得攻击者即便得到算法和当前随机数也无法推算出下一列随机数值,除非攻击者能获得之前所有的随机数。下面利用SHA-1来实现具体的函数:
#include <stdio.h>
#include <stdlib.h>
#define SHA1_ROTL(a,b) (SHA1_tmp=(a),((SHA1_tmp>>(32-b))&(0x7fffffff>>(31-b)))|(SHA1_tmp<<b))
#define SHA1_F(B,C,D,t) ((t<40)?((t<20)?((B&C)|((~B)&D)):(B^C^D)):((t<60)?((B&C)|(B&D)|(C&D)):(B^C^D)))
long SHA1_tmp;
extern char* StrSHA1(const char* str, long long length, char* sha1){
/*
计算字符串SHA-1
参数说明:
str 字符串指针
length 字符串长度
sha1 用于保存SHA-1的字符串指针
返回值为参数sha1
*/
char *pp, *ppend;
long l, i, K[80], W[80], TEMP, A, B, C, D, E, H0, H1, H2, H3, H4;
H0 = 0x67452301, H1 = 0xEFCDAB89, H2 = 0x98BADCFE, H3 = 0x10325476, H4 = 0xC3D2E1F0;
for (i = 0; i < 20; K[i++] = 0x5A827999);
for (i = 20; i < 40; K[i++] = 0x6ED9EBA1);
for (i = 40; i < 60; K[i++] = 0x8F1BBCDC);
for (i = 60; i < 80; K[i++] = 0xCA62C1D6);
l = length + ((length % 64 > 56) ? (128 - length % 64) : (64 - length % 64));
if (!(pp = (char*)malloc((unsigned long)l))) return 0;
for (i = 0; i < length; pp[i + 3 - 2 * (i % 4)] = str[i], i++);
for (pp[i + 3 - 2 * (i % 4)] = 128,i++; i < l; pp[i + 3 - 2 * (i % 4)] = 0,i++);
*((long*)(pp + l - 4)) = length << 3;
*((long*)(pp + l - 8)) = length >> 29;
for (ppend = pp + l; pp < ppend; pp += 64){
for (i = 0; i < 16; W[i] = ((long*)pp)[i], i++);
for (i = 16; i < 80; W[i] = SHA1_ROTL((W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]), 1), i++);
A = H0, B = H1, C = H2, D = H3, E = H4;
for (i = 0; i < 80; i++){
TEMP = SHA1_ROTL(A, 5) + SHA1_F(B, C, D, i) + E + W[i] + K[i];
E = D, D = C, C = SHA1_ROTL(B, 30), B = A, A = TEMP;
}
H0 += A, H1 += B, H2 += C, H3 += D, H4 += E;
}
free(pp - l);
sprintf(sha1, "%08X%08X%08X%08X%08X", H0, H1, H2, H3, H4);
return sha1;
}
static char *seed_; //种子
static num_=0; //计数器
void Init(char *seed)
{
seed_ = seed;
}
void SHA1_Rand(char *buff ,int bufflen)
{
int i;
char sha1buff[33] = {0};
char str[1024]={0};
while(bufflen/32!=0)
{
bufflen-=32;
sprintf(str, "%s%d", seed_, num_++);
StrSHA1(str, strlen(str), sha1buff);
sprintf(buff, "%s%s", buff, sha1buff);
}
sprintf(str, "%s%d", seed_, num_++);
StrSHA1(str, strlen(str), sha1buff);
strncpy(str, sha1buff, bufflen%32);
}
int main()
{
char *buff = "hello world"; //种子
Init(buff);
char key[65] ={0};
SHA1_Rand(key, 64);
printf("%s\n", key);
}
密码法:
与单向散列法相似,密码法利用加密输出随机数实现随机数的不可预知性,其加密可以采用对称加密AES算法,或者公钥算法其结构为:
密码法的函数实现可以参照单向散列函数,这里不再列写。
此外如果对随机性强度还是不满足,可以了解下ANSI X9.17。一般来说以上三种强伪随机数算法已满足大多数需求。
更多推荐
随机数生成器,基于软件的伪随机数算法
发布评论