Fast algorithm for pseudo random number generation in Linux user space
-
摘要: 随机数发生器是网络安全应用中的重要组成部分,对于构造加密算法的密钥具有重要作用.Linux操作系统提供了内核级随机数发生器,但因其随机数产生效率较低而不宜将其应用于密钥变换频繁的网络安全应用.给出了一个快速伪随机数生成算法.算法以64 bit硬件高频计数器作为随机数源.算法将计数器的低32 bit放入集合中,然后通过SHA(Security Hash Algorithm)算法对集合进行处理,并采用集合的前16 byte作为随机数输出.采用非参数检验方法检验算法产生的随机数质量,测试结果表明算法产生的随机数具有较高的安全性.同时由于算法运行在用户空间,比Linux的内核级随机数发生器具有较高的随机数生成效率.Abstract: RNGs(random number generators) are important building blocks for algorithms in security applications. They are paramount in construction of encryption keys. For security applications with key exchange in high frequency, the two RNGs provided by Linux kernel are not acceptable because of their low efficiency. An algorithms for fast pseudo random number generation as proposed is implemented in Linux user space. The source of random number is a high-frequency 64 bit counter. The lowest 4 bytes of the counter are added in a pool, then the pool is hashed with SHA(security hash algorithm). The first 16 bytes of the hash are output. This process is repeated until the requested number of random number is achieved. Several statistical tests are employed to investigate the randomness of RNGs. The results show that the quality of random number generated are guaranteed. Due to its running in Linux user space, this algorithm has much higher efficiency than Linux’s two RNGs.
-
Key words:
- random number /
- uniformity /
- randomness /
- statistical independence /
- Linux
-
[1] Linux 2.4内核随机数生成算法源代码 . /usr/src/linux/drivers/char/random.c Source code of Linux 2.4 random number generator ． /usr/src/linux/drivers/char/random.c(in Chinese) [2] FIPS-180-1.Secure hash standard[S]. National Institute of Standards and Technology, US Department of Commerce, 1995 [3] Mungkee D.Cryptographic random number generators . http://www.phrack.org/phrack/59/p59-0x0f.txt [4] Intel.Intel architecture software developer’s manual volume 2:instruction set reference .http://www.intel.com/design/pentiumii/manuals/243191.htm [5] Kaufman C. Internet key exchange (IKE v2) protocol . IETF draft-ietf-ipsec-ikev2-17.txt.Sep,2004 [6] Donald E K.The art of computer programming (2nd Edition),Volume 2/seminumerical algorithms[M]. Beijing:Tsinghua University Press,1980 [7] Juan S.Statistical testing of random number generators .Proceedings of the 22nd National Information Systems Security Conference. http://csrc.nist.gov/nissc/1999/proceeding/papers/p24.pdf [8] 韩于羹.应用数理统计[M].北京:北京航空航天大学出版社,1989 Han Yugeng. Mathematical statistics & applic -
点击查看大图
计量
- 文章访问数: 2759
- HTML全文浏览量: 52
- PDF下载量: 1780
- 被引次数: 0
下载:
