首页
社区
课程
招聘
[原创]计算机生成真随机数原理及实践
2014-7-19 02:43 18976

[原创]计算机生成真随机数原理及实践

2014-7-19 02:43
18976
收藏
点赞1
打赏
分享
最新回复 (36)
雪    币: 3721
活跃值: (3216)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
chuxue 2014-7-26 19:26
26
0
我只知道计算机上电时候的第一条指令
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 2014-7-30 11:25
27
0
“随机”并不是一个绝对的概念,可以检验一个串的随机性程度,但不管什么程度,都不能说这个串就是随机数。
也不是说真随机数就是随机性好,伪随机数就是随机性差,这里的真假其实是指产生随机的源头,通常“真随机”是由确定的物理随机源产生,例如芯片运算中的电流干扰;而“伪随机”通常是由确定的数值(种子)产生,是通过计算模拟产生。一般经验其实是:真随机的随机性不如伪随机。
随机数发生器通常的做法是:用真随机(物理随机源)产生种子,用伪随机(密码计算,例如DES,SHA1)产生需要的随机数。
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
sjdkx 2014-7-30 12:32
28
0
  基本同意上述说法。随机程度现在还没有统一的标准,如果有方法计算数组的熵也就可以度量随机性了。如果一个数组成员基本符合均匀分布那随机性应该就不错了。
  上面说的随机数组生成方法,虽然种子是真随机数,但生成的数组仍然是伪随机序列,其缺陷是内在的,少量应用或许没什么问题,大量应用能显现出其缺陷而影响你的目的,尤其是伪随机序列交叉应用时,道理很简单因为伪随机序列源于同样的生成机制,如果这样的数据在计算中相遇的时候容易出问题。
  除了上面说的随机数组生成方法,随机数组是可以随意建造的,例如物理方法:你手里有一万个带顺序编号的同样的纸片,并且纸片有正反两面,抛撒下来你就有了一万位二进制数......。数学方法就更随意了,构造成员均匀分布的原始数组,用随机排序去打乱它们的秩序吧,一遍不行就多遍,最终得到分布均匀的随机序列。
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 2014-7-30 13:25
29
0
NIST早就有随机数检测标准,国密现在也有了随机数检测标准。
随机数检测标准比你想象的严格的多,除了熵和卡方分布之外,还包括很多检测手段,例如:压缩性、线性秩相关性等,一般生成的随机数,要达到这个标准中规定的显著性水平,并不是一件容易事。
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
sjdkx 2014-7-30 13:42
30
0
  可悲的是那十几项标准还是不能判断随机数组是不是真随机数组。主要是对伪随机数组的内部关联性不能判断出来。
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 2014-7-30 14:50
31
0
公布了算法,就能判断内部关联性。

任何软硬件,都可以设计后门,这不是密码技术能解决的问题,而是监管问题。
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
sjdkx 2014-7-30 22:04
32
0
 如果这样可能做出的随机数组更好些,选取两个长周期性能优良的随机函数A和B,用真随机数做A的种子生成第一个随机数,用这个随机数做B的种子生成第二个随机数并作为A的种子,余此类推生成随机数组。这样数据内部的分布就比较复杂了,既不像A序列也不像B序列。
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 2014-7-31 10:36
33
0
把A、B看做一个整体不就行了。事实上,目前的hash算法和对称算法,都是由很多轮运算组成,这里的每一轮运算,就相当于你说的A、B函数。
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
sjdkx 2014-7-31 13:44
34
0
  差多了,各轮运算方法类似只是参数不同而已,两个随机函数可以差得很多这里没有可比性。上面只是举例实际上可以用更多的随机函数,在各序列中上蹿下跳根本无法分析。想当然看问题是不行的,把地球看成一粒微尘,里面的复杂性也不会变化。
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 2014-7-31 14:20
35
0
“上蹿下跳”是否就“无法分析”需要实际检验。

目前世界上好的伪随机数生成算法屈指可数,你如果有好的算法,不妨使用NIST的随机性测试软件测试一下。如果各项都达标,可以让学术界鉴定。
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 2014-7-31 14:31
36
0
我可以给你一个最简单的检测随机性的方法:你用你的算法生成一个100M以上的文件,然后使用RAR或zip压缩一下,如果压缩后的文件和原文件几乎一样大,那么大致可以认为你过了随机性检测的某一项检测。
雪    币: 10014
活跃值: (2012)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
sjdkx 2014-7-31 15:50
37
0
http://bbs.cisps.org/viewtopic.php?f=104&t=33556&sid=99c8a1a3e3647e5038295b7aada93ca5
再好的随机函数也只能生成伪随机序列。所以好不到哪里去。但你可以改造它们,打乱其内部规律,参见
http://bbs.pediy.com/showthread.php?t=190453
介绍的方法
游客
登录 | 注册 方可回帖
返回