一种新的混沌随机数生成器实现方案_图文


计算机技术 ● 信息安全

一种新的混沌随机数生成器实现方案

胡 涛, 郭 立, 黄 昊, 刘 军 (中 国 科 学 技 术 大 学 电 子 科 学 与 技 术 系 , 安 徽 合 肥 230027)
摘 要 : 提 出 了 一 种 基 于 时 钟 相 位 抖 动 的 混 沌 随 机 数 产 生 器 , 并 在 Xilinx FPGA 开 发 板 上 实 现 并 进 行 了 测 试 。测 试 结 果 表 明 , 最 高 输 出 速 率 达 8Mbps , 实 现 了 设 计 要 求 。硬 件 结 构 简 单 , 并 且 该 RNG 的 输 入 源 不 受 电 路 噪 声 源 的 影 响 , 易 于 今 后 的 IC 实 现 。
关键词: 混沌随机数产生器 真随机数 随机性测试

随 着 计 算 机 网 络 、Internet 和 无 线 设 备 等 数 字 通 信 技 术的广泛应用, 数据加密越来越成为人们关注的焦点。 很多加密系统的安全性直接依赖于产生的密钥的不可 预测性以及非相关性。然而要产生一个理想的密钥, 仅 仅由人来输入一个密码是无法达到要求的。因为那样 会有太强的主观性。要生成非主观的密钥, 目前常用 的 方 法 是 伪 随 机 数 产 生 器 PRNG ( Pseudorandom Number Generator ) 。但 再 好 的 PRNG 只 要 其 中 一 个 状 态 因 为 某 种 原 因 泄 漏 , 就 极 有 可 能 导 致 整 个 PRNG 的 产 生 机 制 被 破 解 , 从 而 使 得“ 伪 随 机 ”变 成“ 不 随 机 ”。因 此 人 们 开 始 研 究 真 随 机 数 生 成 器 。有 些 随 机 数 产 生 器 是 基 于 一 个 模 糊 的类随机源的, 如键盘的延迟, 电脑的系统时钟状态等。 这些随机数产生器的安全性总是受这种模糊的类随机 源 的 影 响 。于 是 采 用 自 然 界 中 的 真 随 机 量 产 生 密 钥 便 成 为 一 个 新 的 课 题 。例 如 电 路 中 的 热 噪 声 或 者 放 射 源 的 衰 变 等 都 是 真 随 机 量 。 在 SoC(System on Chip)广 泛 应 用 的 今 天 , 如 何 设 计 一 个 基 于 IC 的 RNG 就 成 为 安 全 通 信 应 用 的 急 切 需 要 。随 机 噪 声 源 ( 如 热 噪 声 和 发 射 噪 声 ) 存 在 于 IC 中 却 总 是 被 人 为 地 屏 蔽 掉 了 。因 此 , 利 用 电 路 噪 声 放 大 的 商 用 RNG 设 计 需 要 专 门 的 外 部 组 件 和 特 殊 硬 件 来 与 那 些 需 要 屏 蔽 噪 声 的 组 件 隔 开 。 在 IC 设 计 中 , 对 数 模混合信号的处理经验表明, 底层噪声和电源噪声电平 总是高于随机噪声源电平。所以一个不被干扰的白噪声 源 在 一 个 基 于 IC 的 数 字 加 解 密 系 统 的 RNG 中 是 不 可 能

被使用的, 必须考虑如何利用抗干扰的随机源来实现随 机数生成器。
本 文 提 出 一 种 新 的 混 沌 RNG 的 实 现 方 案 , 更 易 于 用 硬 件 即 IC 实 现 。首 先 讨 论 其 原 理 和 模 型 及 其 实 验 , 并 对 其 进 行 随 机 性 测 试 ; 然 后 讨 论 它 的 FPGA 实 现 方 案 。 1 模型及实验 1.1 随机数生成器的定义
定义 1 一个理想的随机数生成器是一个生成等概 率 符 号 的 离 散 无 记 忆 信 息 源 (DMIS), RNG 是 一 个 有 着 正 熵 的 离 散 信 息 源 [1]。
但 是 , 现 实 中 的 RNG 都 是 产 生 非 均 匀 概 率 符 号 的 离 散 有 记 忆 信 息 源 。 因 此 采 用 有 偏 差 的 RNG 来 区 别 于 定 义 1 中 理 想 的 RNG。 一 个 有 偏 差 的 RNG 性 能 的 好 坏 可 通 过 它 的 冗 余 度 ! =log2Q- h 来 衡 量 , 其 中 Q 和 h 分 别 是 离 散 符 号 集 的 基 数 和 相 关 信 源 的 熵 。 一 个 理 想 RNG 的 冗 余 度 应 该 等 于 0 , 而 一 个 有 偏 差 的 RNG 的 冗 余 度 则 标 志 这 个 RNG 跟 理 想 RNG 的 差 距 。例 如 一 个 冗 余 度 为 ! 的 RNG 产 生 长 度 为 N 位 的 密 钥 , 则 攻 击 方 平 均 要 尝 试 2(1- !)N 个 密 钥 才 能 找 到 正 确 的 密 钥 , 因 此 密 钥 的 有 效 长 度 可 以 被 定 义 为 Ne=(1- !)N。 1.2 混沌随机数生成器模型
混沌理论作为非线性动态系统的分支, 近年来受到 越 来 越 多 的 关 注 。它 使 得 一 个 低 维 动 态 系 统 也 可 以 拥 有 复 杂 的 、不 可 预 料 的 行 为 , 使 复 杂 的 方 程 不 再 是 生 成 随

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

(接 上 页)

hiding.IBM SYSTEMS JOURNAL.1996 ; 35(3&4)

参考文献

4 Ciloglu T, Utku Karaaslan S.An improved all- pass water-

1 A N Lemma , J Aprea , W Oomen et al.A temporal domain

marking scheme for speech and audio.In : IEEE International

audio watermarking technique.IEEE Trans.Signal Processing,

Conference on Volume 2 , Aug 2000

2003 ; 51(4): 1088~1097

5 Darko Kirovski , Henrique S.Malvar.Spread- Spectrum Water-

2 Brain C J Moore.An introduction to the psychology of hear-

marking of Audio Signals.IEEE Trans.Signal Processing,

ing, 4th edition.New York : Academic , Feb , 1997

2003 ; 51(4): 1020~1033

3 W Bender , D Gruhl , N Morimoto et al.Techniques for data

( 收 稿 日 期 : 2006 - 02 - 08 )

《电子技术应用》2006 年第 6 期

本 刊 邮 箱 :e ta @ncs e . com . cn

51

计算机技术 ● 信息安全

机 数 序 列 的 必 要 条 件 [1]。

混沌系统可以用基于下列迭代关系式描述的

Bernouli 移 位 映 射 [2]:

Xn=[2(Xn- 1+e(n))]mod 1.0

(1)

式 中 , e(n)表 示 一 个 高 斯 噪 声 信 号 。这 个 迭 代 式 表 明

由(1)式 产 生 的 序 列 是 极 为 平 滑 和 均 一 分 布 的 [3]。 另 外 ,

与 混 沌 相 关 的 轨 迹 发 散 包 含 了 噪 声 , (1)式 产 生 的 序 列 在

一定范围内是不可预测的, 从而使系统能被当作一个真

随 机 比 特 源 。 离 散 时 间 混 沌 法 不 受 其 他 噪 声 源 影 响[3]。

在 电 路 上 实 现 Bernouli 移 位 映 射 的 关 键 在 于 实 现 一

个 抗 干 扰 的 高 斯 噪 声 信 号 。传 统 的 混 沌 随 机 数 生 成 器 是

用一个伪随机数生成器产生一个伪高斯噪声信号来实

现 (1)中 的 e(n)[2], 如 图 1 所 示 , 这 在 一 定 程 度 上 降 低 了

混沌随机数生成器的安全性和真随机性。

产 生 最 后 的 输 出 x(n), x(n)被 反 馈 到 寄 存 器 中 进 行 下 次 操作。 1.3 实验结果及讨论
根 据 前 面 的 定 义 1 来 检 测 本 文 中 提 出 的 混 沌 RNG 的 性 能 , 用 它 生 成 不 同 长 度 的 8bit 随 机 数 序 列 , 计 算 其 冗 余 度 , 并 与 参 考 文 献 [2] 中 的 传 统 混 沌 RNG 方 案 做 对 比, 如图 4 所示, 点线表示本文提出的方案, 实线表示的 是 文 献 [2]中 的 方 案 。 通 过 对 比 可 以 很 明 显 地 看 出 改 进 后 的 混 沌 RNG 性 能 优 于 采 用 伪 随 机 高 斯 噪 声 的 传 统 混 沌 RNG 方 案 。

典 型 的 振 荡 器 采 样 法 [5]是 利 用 时 钟 的 相 位 噪 声 (理 论 上 是 MOSFET 热 噪 声 的 副 产 品 )产 生 随 机 数 。 通 过 一 个由较慢时钟信号控制的 D 触发器对一个高速时钟进 行采样, 高速时钟的相位抖动导致具体采样值的不确定 性, 如图 2 所示, 理论上每次采样都会产生一个随机比 特 。 典 型 采 样 后 的 抖 动 电 平 是 符 合 高 斯 分 布 的 [4], 而 且 这 种 抖 动 不 会 受 到 电 路 中 其 他 噪 声 的 干 扰 [5]。 另 外 , 振 荡器采样法的随机性可以通过仔细挑选快的和慢的时 钟 频 率 比 来 人 为 增 强 。采 样 时 发 生 的 非 线 性 偏 移 现 象 使 得这种振荡器采样技术比目前的确定性噪声更健壮。

仅 仅 由 冗 余 度 来 衡 量 一 个 RNG 是 不 够 的 。 为 了 了 解 本 文 提 出 的 混 沌 RNG 输 出 序 列 的 随 机 性 是 否 实 现 了 “ 随 机 ”, 我 们 根 据 美 国 国 家 标 准 及 技 术 研 究 所 (NIST) 的 要 求 [6] 对 本 文 的 混 沌 RNG 方 案 产 生 的 随 机 数 序 列 的 随 机 性 进 行 一 系 列 测 试 。 测 试 所 用 数 据 为 慢 速 时 钟 =8kHz, 高 速 时 钟 =100MHz, 输 出 精 度 为 8bit 的 输 出 值 , 测 试 长 度 为 3 000 000 个 8 位 随 机 数 的 序 列 , 表 1 为 测 试 结 果 。

表 1 测试结果及对比

测试

最低测 试通过 允许值

最 高 测 参考文献[2] 本 文 方 法 试 通 过 中方法 的 测 试 允 许 值 测试平均值 平 均 值

基于上述原理, 提出用振荡器采样输出作为一个高 斯 噪 声 信 号 e(n)实 现 (1)式 。 结 合 两 种 随 机 数 生 成 器 方 案实现混沌随机数生成器, 系统原理框图如图 3 所示。
其 中 S/H (Shift/Hold ) 为 一 个 移 位 保 持 电 路 , 用 来 实

单比特测试 扑克测试
最长步长测试 步长为 1 统计测试 步长为 2 统计测试 步长为 3 统计测试 步长为 4 统计测试 步长为 5 统计测试 步长为 6+统计测试
普遍性测试 1 阶相关度测试 2 阶相关度测试 3 阶相关度测试 4 阶相关度测试

9 655 10 346

1 . 03 57 . 4



33

2 267 2 733

1 079 1 421

502

748

223

402

90

223

90

223

7 . 138 7 . 229

- 0 . 015 8 0 . 015 8

- 0 . 015 8 0 . 015 8

- 0 . 015 8 0 . 015 8

- 0 . 015 8 0 . 015 8

9 996 16 . 17
13 2 484 1 246 627 312 161 157 7 . 178 - 0 . 005 9 - 0 . 003 4 0 . 001 8 0 . 003 7

10 002 14 . 92
15 2 503 1 250 626 314 153 158 7 . 153 0 . 002 7 - 0 . 001 9 - 0 . 000 4 0 . 002 1

现 2 (x(n - 1)+e (n))。 低 速 时 钟 控 制 D 触 发 器 、寄 存 器 和

经 过 以 上 一 系 列 的 随 机 性 测 试 , RNG 表 现 良 好 , 在

S/H 。 寄 存 器 中 残 余 信 号 作 为 初 始 输 入 信 号 , 然 后 与 振 置 信 水 平 为 95% 的 情 况 下 通 过 了 全 部 测 试 , 没 有 表 现 出

荡 器 采 样 输 出 信 号 进 行 模 2 加 操 作 ( 异 或 ) , 再 通 过 S/H 非 随 机 性 , 并 且 在 信 源 相 关 度 的 测 试 (correlation order test)

52 欢迎网上投稿 www.aetnet.cn www.aetnet.com.cn 《电子技术应用》2006 年第 6 期

计算机技术 ● 信息安全

中 性 能 超 过 了 参 考 文 献 [2]中 的 混 沌 RNG 方 案 。 这 项 测 试 是 测 试 一 个 随 机 数 序 列 的 相 邻 随 机 数 的 相 关 度 。一 个 理 想 RNG 的 前 后 随 机 数 相 关 度 应 该 为 0 。 由 表 1 中 数 据 可 知 , 本 文 的 混 沌 RNG 测 试 结 果 更 接 近 于 理 想 RNG。 因此可以认为, 就目前已知的测试随机数的随机性的测 试 结 果 表 明 , 本 文 介 绍 的 混 沌 RNG 生 成 的 随 机 数 序 列 是比较好的。
光谱测试可以直观地显示出随机数序列与其自身 的 相 关 情 况 。通 过 图 5 可 以 更 直 观 地 看 到 一 个 相 关 度 低 的 RNG 与 一 个 伪 RNG( 用 10 位 线 性 反 馈 移 位 寄 存 器 来 做 例 子 ) 的 对 比 。相 关 度 为 0 的 理 想 RNG 应 该 均 匀 分 布 在整个二维空间内, 线性反馈移位寄存器的测试结果 (图 b)就 反 映 出 了 它 的 高 相 关 度 , 而 本 文 提 出 的 混 沌 RNG 方案 的测 试结 果(图 a) 则 显示 了其不 可预 测 性 与 无 规 则 性分布。
2 硬件实现 本 文 采 用 Xilinx 公 司 的 XUPV2P30 开 发 板 实 现 这 个
混 沌 RNG, 这 块 开 发 板 上 自 带 两 个 独 立 的 (不 同 相 位 )时 钟 源 , 二 者 都 可 以 输 出 8k ~100MHz 的 不 同 频 率 的 时 钟 。 选 择 慢 速 时 钟 信 号 频 率 范 围 为 8k ~1MHz, 高 速 时 钟 信 号 频 率 为 100MHz, 输 出 精 度 为 8bit 。 其 逻 辑 使 用 资 源 情 况 如表 2 所示。
从表 2 可以看到, 在硬件上以极低的逻辑资源使用 (18 个 Slices 约 合 1800 + 门 )实 现 了 本 文 提 出 的 混 沌 RNG 方 案 , 对 比 参 考 文 献 [2] 中 的 方 案 ( 3000 + 门 ) , 该 电 路 得

表 2 本文混沌 RNG 的逻辑资源使用情况

逻辑资源 时钟数 Slices 数
通过随机性测试的最低频率 通过随机性测试的最高频率
最高输出速率 最低输出速率

使用 2 18
8kHz 1MHz 8Mbps 64kbps

到 大 大 简 化 , 而 参 考 文 献 [2]中 的 伪 高 斯 噪 声 生 成 器 占 用 了 很 大 的 硬 件 资 源 。该 方 案 的 最 高 输 出 速 率 受 到 了 板 载 最 高 时 钟 频 率 的 限 制 。如 果 本 文 的 混 沌 RNG 用 IC 方 案 实现, 则可以进一步减小所需要的硬件资源并进一步提 高输出速率。
本文提出的方案通过了一系列高要求的随机性测 试 , 其 逻 辑 资 源 的 占 用 远 小 于 传 统 的 混 沌 RNG 方 案 , 最 高 输 出 速 率 可 达 8Mbps 。因 而 这 种 RNG 方 案 可 以 用 于 对 安全性和性能需求日益增长的加密系统中。 参考文献 1 Stojanovski T, Kocarev L.Chaos- based random number gen-
erators- part I.IEEE Transactions on Circuits and Systems , 2001 ; (3): 281~288 2 Petrie C S, Connelly J A.A noise- based IC random number generator for applications in cryptography.IEEE Trans.Circuits Syst , 2000 ; 47(5): 615~621 3 Chua L O, Yao Y, Yang Q.Generating randomness from chaos and constructing chaos with desired randomness.Int J Circuit Theory Appl , 1990 ; 18 : 215~240 4 Paul S.Little known characteristics of phase noise.Applica- tions Note AN- 741 , Analog Devices , www.analog.com 5 Petrie C S, Connelly J A.Modeling and simulation of oscilla- tor- based random number generators.In : Proc.ISCAS′96 , vol. 4 , May 1996 : 324~327 6 National Institute of Standards and Technology, Kanata , ONT, Canada.Security requirements for cryptographic modules.FIPS PUB 140- 2 , Dec 2002
( 收 稿 日 期 : 2006 - 01 - 15 )

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

( 上 接 第 48 页 )

学 院 学 报 , 2001 ; 19 (2 ): 23 ~27

感 度 系 数 作 为 确 定 噪 声 点 的 依 据 , 根 据 窗 口 内 噪 声 点 的 3 Piva A, Barni M, Bartolini F et al.DCT- based watermark re-

个数, 自适应地选择合适的滤波窗口, 并在滤波时采用 了 改 进 的 加 权 平 均 来 计 算 均 值 。这 种 方 法 在 保 护 细 节 与 去噪能力之间做了较好的折衷, 比标准均值滤波和标准 中值滤波具有更好的滤波能力。 参考文献 1 Liu J P, Yu Y L.A flexible method for image noise removal[J].
Joural of South China University Technology, 2000 ; 28(2): 60 ~63

covering without resorting to the uncorrupted original image. In : Proceedings of 4th IEEE international conference on image processing ICIP′97.Santa Barbara , CA, USAL: ICIP , 1997 4 Zhong W.Image watermarking using legendre array[J].Journal of China Institute of Communications , 2001 ; 22(1): 1~6 5 张 严.基于高阶累积量的谐波信号参考估计问题研究.吉 林 工 业 大 学 硕 士 学 位 论 文 , 1998
( 收 稿 日 期 : 2006 - 01 - 19 )

2 祝 宇 鸿 .一 种 改 进 的 数 字 图 像 中 值 滤 波 算 法 [J]. 长 春 邮 电

《电子技术应用》2006 年第 6 期

本 刊 邮 箱 :e ta @ncs e . com . cn

53


相关文档

一种基于混沌原理的真随机数发生器
混沌随机数发生器的设计
一种新型均匀分布混沌伪随机数发生器
一种新的基于时空混沌的伪随机数发生器
基于混沌的高速真随机数发生器的设计与实现
混沌随机数发生器的设计_王云峰
VC3050大随机数生成器算法的研究与实现2
一种基于双混沌系统的伪随机数发生器
一种基于FPGA的高斯随机数生成器的设计与实现
混沌与随机数
电脑版