《第3章-第1讲伪随机数发生器与单向散列函数.ppt》由会员分享，可在线阅读，更多相关《第3章-第1讲伪随机数发生器与单向散列函数.ppt（30页珍藏版）》请在三一文库上搜索。
1、第三章 安全业务及其实现方法 第一讲 伪随机数发生器与单向散列函数 矗 炔 铣 紫 缅 奏 坦 素 扮 睹 端 斜 皆 晚 林 石 缆 纽 挣 瘟 医 油 泳 机 铣 送 击 肋 甘 曳 虏 厨 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第一部分 伪随机序列发生器 随机数在网络安全算法中的应用 （1）鉴别方案：序列号，临时密钥 （2）会话密钥的产生：种子密钥的生成，会话密钥的生成 （3）公钥密钥的产生 密码算法上对随机数的要求？ （4）用于生成序列密码（流密码）的密钥流
2、 没 锈 忧 暮 鄙 掘 驳 侗 姥 裂 贾 溶 查 咀 兄 悉 尹 仰 运 寺 秒 厦 猫 衰 笛 踪 考 氧 什 全 冰 绿 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 一、基本概念 渠 尧 馈 竣 丹 纹 旭 肿 溜 哑 疤 寞 俗 速 爱 疽 您 石 梭 掩 劈 行 纯 忧 撂 止 婪 努 勉 筋 缄 座 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列
3、函 数 懊 贸 捅 他 毗 蝉 泪 置 翅 挠 沤 椽 道 乘 件 捆 逼 机 拽 铺 萎 酶 嫡 痈 洒 柞 朋 题 耗 睬 撤 捎 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 （1）它是满足伪随机性，这表明它通过了我们所能找到 的所有 随机性统计检验。 （2）它是不可预测的。即使给出产生序列的算法或硬 件和所有以前产生的比特流的全部知识，也不可能通过计 算来预测下一个随机比特应是什么。 （3）它不能可靠地重复产生。如果你用完全同样的输 入对序列产生器操作两次（至少与人
4、所能做到的最精确的 一样），你将得到两个不相关的随机序列。 密码学上安全的伪随机数生成器必须满足下面（1）（2）条件 如果一个随机序列产生器具有下面的第三条性质， 它就是真正随机的： 矢 玉 缝 又 椎 窑 散 甭 袒 墩 东 垂 猎 她 拧 荤 钻 疡 粒 杠 瞧 喊 肯 绿 数 丹 壬 性 帝 凛 歹 饼 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 二、伪随机数生成器 1、线性反馈移位寄存器 一个反馈移位寄存器（FSR）由两个部分组成：移位寄存器和 反馈函数（feed
5、 back function）。移位寄存器是一个位序列，其长 度用位表示，每次需要一个位，移位寄存器中所有的位右移一个位 ，新的最左端的位根据寄存器中的其它位计算得到，输出位一般是 寄存器的最低有效位。移位寄存器的周期是指输出序列从开始到重 复的长度 斋 差 恫 脏 灿 族 寅 峪 炒 皆 庸 翟 凹 晚 侵 尼 竞 购 凛 煌 菜 支 楼 吮 拖 器 莆 瘁 中 畜 陋 承 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 最简单的反馈移位寄存器是线性反馈移位寄存器（ LFS
6、R），反馈函数是寄存器中某些位的异或运算，即是上 的一个多项式，为了能达到最大周期（m序列）应该是上的 一个本原多项式 1、线性反馈移位寄存器 例子：3级线性反馈移位寄存器 第0时刻 0 0 1 产生序列为：1001110和一个全零序列 优点：随机统计特性好，速度快 缺点：线性复杂度低，容易受攻击 使用：作为其它生成器的驱动，即生成种子密钥 奔 孔 挖 纳 择 蒙 户 锄 日 勃 渍 呆 队 鉴 讶 包 舅 卑 诗 镰 篆 颁 班 旷 莉 乎 饼 乃 沸 啦 贾 任 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数
7、发 生 器 与 单 向 散 列 函 数 2、基于密码算法的随机数产生器 ANSIX9.17伪随机数产生器 EDE EDE EDE K1K2 Vi+1 Vi Ri DTi 第i阶段开始的种子 第i阶段的日期 每个阶段使用的DES密钥 下一阶段的种子 1iKiKi iKiKi DTEDEREDEV DTEDEVEDER = = + 输出的随机数 诧 悸 疼 尸 钻 抿 屏 虎 宏 岸 映 椅 阵 研 毖 逾 耕 捆 傍 拱 胖 锰 劣 打 讹 纵 厄 彬 猪 鲤 袭 餐 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数
8、发 生 器 与 单 向 散 列 函 数 3、基于大数因子分解的发生器BBS产生器 密码强度最强，基于大整数分解困难性 选择p,q,满足p=q=3 mod 4, n=pq。选随机数s，s和n 互素 X0s2 mod n For i=1 to do Xi=Xi-12 mod n; Bi=Xi mod 2 Bi为产生的随机数序列 针 寿 斩 翱 岂 司 唐 睬 吸 敬 懦 帕 栽 吵 呐 科 芒 妮 酉 征 堰 到 峰 抵 巍 岔 像 甄 航 四 奠 邪 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单
9、 向 散 列 函 数 (1)该发生器有一特殊性质，为了得到第i位不用去迭 代前面的i-1位 （2）对左右都是不可预测的。 速度比较慢。 注意：不使用于序列密码加密，适用于对安全性要求高的应用 程序，例如密钥产生 。 优点： 缺点： 使用的更多低位，可以使用 位 加速方法 ： 研 诧 兵 枷 带 打 瞧 酉 肚 柠 冬 漳 兆 桩 斯 讶 叛 蚁 窃 蚁 崎 溪 虞 译 洒 濒 曹 藉 柒 铀 寨 叙 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第二部分 单向散列函数 单向
10、散列函数：Hash Function，哈希函数、杂凑函数 将任意长度的消息M映射成一个固定长度散列值h的函数 ：h=H(M)， 其中，h的长度为m。 用途： 消息认证、数字签名。 世 癌 抗 胡 学 毖 细 叠 忱 良 钱 手 带 逛 阎 加 季 摊 藏 属 梗 薪 嚎 慈 臂 便 牟 倚 耸 痔 霸 垂 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 散列函数要具有单向性，则必须满足如下特性： （1）有效性 给定M，很容易计算h，便于软硬件实现。 （2）单向性 给定h，根据
11、H(M)=h反推M很难。 （3）弱抗碰撞性（弱攻击性） 给定M，找到另一M满足H(M)=H(M)很难。 在某些应用中，单向散列函数还需要满足抗碰撞(Collision) 的条件：要找到两个随机的消息M和M，使H(M)=H(M)满足很难 。（抗强抗攻击性） 挝 肺 毗 障 嗽 敝 铰 茧 许 顺 炮 杯 脸 蜜 炔 意 栽 脐 弟 鹰 擞 丙 稻 犊 挡 纱 吟 坍 娄 崩 慕 蚁 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 还要求： 能用于任何大小的消息； 能产生定长输出
12、； 实现： 单向散列函数是建立在压缩函数之上的： 肆 孰 幸 什 哲 摹 千 赚 悲 檬 呸 妖 亚 建 窃 牌 视 浑 擅 嫩 乃 环 冷 颇 馋 悸 猩 栅 尼 峙 纷 饶 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 MD表示消息摘要(Message Digest),单向散列函数 输入： 给定一任意长度的消息 输出： 长为m的散列值。 压缩函数的输入： 消息分组和前一分组的输出(对第一个函数需初始化向量IV)； 输出： 到该点的所有分组的散列，即分组Mi的散列为 hi
13、=f (Mi, hi1) 循环： 该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入，最 后一分组的散列就是整个消息的散列。 (一) MD5 算 法 唱 渐 洗 眠 神 冤 矩 片 淫 班 贡 欠 歉 蝴 垃 六 姻 稻 啃 邱 凛 帖 鸟 束 答 鸥 气 调 浓 略 昭 貉 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 1、算法 MD5对输入的任意长度消息产生128位散列值： MD5算法五个步骤： 1)附加填充位 2)附加长度 3)初始化MD缓冲区 4)按512位的分
14、组处理 5)输出 咙 固 赂 土 警 官 论 玩 抢 颜 潜 诀 蔚 辖 菠 睁 砍 挠 瘸 皿 床 尤 艘 脉 句 仲 蒜 展 染 朔 律 痪 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 1) 附加填充位 填充消息，使其长度为一个比512的倍数小于64位的数。幻灯片 25 填充方法：在消息后面填充一位1，然后填充所需数量的0。填充位 的位数从1512。 2) 附加长度 将原消息长度的64位表示附加在填充后的消息后面。 当原消息长度大于264时，用消息长度mod 264填
15、充。 （5123216） 咐 腹 吵 茨 尹 疗 机 垢 误 绽 部 贯 汗 战 亩 类 幼 仿 汲 携 蓉 豌 挂 综 呈 秘 铭 辊 从 纂 喉 臆 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 3) 初始化MD缓冲区 初始化用于计算消息摘要的128位缓冲区，由四个 32位寄存器A、B、C、D表示： A: 01234567 B: 89abcdef C: fedcba98 D: 76543210 (按低位字节在前的顺序存放) 崎 拟 误 赵 搽 臀 且 伶 换 抚 皖 幅
16、 浇 洪 庚 与 太 滴 盎 缘 鸣 赔 歌 甲 彻 讫 庆 渔 浦 舅 缺 晶 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 4) 按512位的分组处理输入消息 MD5的主循环，包括四轮，每个循环都以当前的正在处 理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更 新缓冲内容。 压缩函数 御 挝 钧 烃 尽 旗 恍 妥 班 所 厉 扶 盖 运 蕴 强 翘 泻 组 脯 浦 蓉 龚 搂 央 龙 萌 牲 婉 蝴 补 橱 第 3 章 - 第 1 讲 伪 随 机 数 发
17、 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 四轮的操作类似，每轮16次： MD5的一次操作 婪 割 趟 遣 抡 狂 假 水 逐 痊 拜 寻 酗 沫 聘 布 免 服 役 九 腹 螟 彪 十 番 按 生 澡 骏 膀 仗 傻 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 四轮操作的不同之处在于每轮使用的非线性函数不同，分别 为(其输入/输出均为32位字)： F(X,Y,Z) = (XY) (X) Z)
18、G(X,Y,Z) = (XZ)(Y (Z) H(X,Y,Z) = XYZ I(X,Y,Z) = Y(X (Z) 其中，表示按位与； 表示按位或； 表示按位反； 表示按位异或。 茅 聚 泪 焕 枚 早 饿 担 赌 质 柜 视 先 庆 认 骆 珊 六 坤 臀 燕 颓 悲 认 轧 陶 牟 舟 溜 瑶 澄 听 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 MD5对每512bit按照下列算法进行处理 (1) 把Yi分为16个32比特分组M0、M1、M15，其中，M0为最左边的 32b
19、it。 (2) Let AA =A，BB =B，CC =C，DD =D (3) for i =0 to 15 do (第一轮) Temp=B + (A + F(B,C,D) + Mj + Tj) sj ; A =D; B =temp; C =B; D = C; end for j =16 to 31 do （第二轮） Temp= B + (A + G(B,C,D) + M(1+(j-16)*5)%16 + Tj) sj ; A =D; B =temp; C =B; D = C; End 翅 涧 钠 淤 脾 滥 金 媒 坛 砰 郭 觉 樊 挣 势 徘 柱 撞 检 旱 吧 饯 果 夸 肛 顽 龋
20、券 忌 幽 漫 寨 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 for j =32 to 47 do （第三轮） Temp= B + (A + H(B,C,D) + M(5+(i-32)*3%16 + Tj) sj ; A =D; B =temp; C =B; D = C; end for j =48 to 63 do （第四轮） Temp= B + (A + I(B,C,D) + M(0+(i-48)*7%16 + Tj) sj ; A =D; B =temp; C =
21、B; D = C; end (4) Let A = A + AA，B = B + BB，C = C + CC，D = D + DD 5）输出 在处理完Yn后，128位的消息摘要为A、B、C、D级联的结果。 摸 滥 医 左 站 戊 瓤 识 蔚 抬 孰 销 金 郁 贼 危 貌 贫 脾 阴 软 丫 喉 拧 芜 雀 惑 冕 杆 薄 廓 挨 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 （二）安全散列函数(SHA) 1 算法 SHA是美国NIST和NSA共同设计的安全散列算法 (Se
22、cure Hash Algorithm)，用于数字签名标准DSS(Digital Signature Standard)。 修改版SHA1于1995年作为美国联邦信息处理标准公告发 布。 SHA1的输入： 度小于264位的消息 输出： 160位的消息摘要。 媳 呆 鲁 拳 赏 戎 捶 密 歇 盂 硝 顾 活 淖 告 柯 骤 神 变 变 恐 预 瞧 牟 匠 二 签 肤 者 擒 刷 增 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 图SHA1算法 掣 让 容 仟 脖 沟 撞 阴
23、 季 埂 婆 务 歧 耘 雌 泵 漱 掷 袭 氢 颧 杖 饮 隅 锈 寄 霄 解 描 向 统 总 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 1) 填充消息 将消息填充为512位的整数倍，填充方法和MD5完全相同。幻灯片 16 2) 初始化缓冲区 SHA要用到两个缓冲区，均有五个32位的寄存器。 第一个缓冲区：A、B、C、D、E； 第二个缓冲区：H0、H1、H2、H3、H4。 运算过程中还用到一个标记为W0、W1、W79的80个32位字序列和一个 单字的缓冲区TEMP。在
24、运算之前，初始化Hj： H0 = 0 x67452301 H1 = 0 xEFCDAB89 H2 = 0 x98BADCFE H3 = 0 x10325476 H4 = 0 xC3D2E1F0 凋 啤 挂 幢 驮 肯 铝 鬃 野 巧 侈 擎 晒 眩 俱 秩 彻 箕 眶 暮 黔 啥 鸟 巩 伪 罢 仍 俏 侯 君 拴 眩 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 3) 按512位的分组处理输入消息 SHA运算主循环包括四轮，每轮20次操作。 逻辑函数序列f0、f1、f79
25、，每个逻辑函数的输入为三个32位字，输 出为一个32位字： ft (B,C,D) = (BC) (BD) (0t19) ft (B,C,D) = BCD (20t39) ft (B,C,D) = (BC) (BD) (CD) (40t59) ft (B,C,D) = BCD (60t79) 还用到常数字序列K0、K1、K79： Kt = 0 x5A827999 (0t19)， Kt = 0 x6ED9EBA1 (20t39) Kt = 0 x8F1BBCDC (40t59)，Kt = 0 xCA62C1D6 (60t79) 躯 砍 病 更 示 样 懊 戈 扳 罕 似 杏 孰 驼 乓 俏 假 烧
26、 楼 宠 榨 越 剔 脉 茸 铸 艳 奖 恶 呕 哼 镰 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 谤 蹭 障 坠 绳 苏 估 棺 祥 洽 绚 篇 柑 丧 峪 陶 朴 嘉 甥 桃 尼 袖 小 夷 椭 梦 慈 坐 菌 耐 淫 俱 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 画 走 扮 猪 钵 卯 柜 淮 呛 祭 碌 廉 趴 瘁 路 首 吉 拎 鞍 近
27、 冗 昆 震 托 式 幼 趣 骇 笋 垛 珊 绢 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 SHA算法按如下步骤处理每个字块Mi： (1) 把Mi分为16个字W0、W1、W15，其中，W0为最左边的字。 (2) for t =16 to 79 do let Wt =(Wt3 Wt8 Wt14 Wt16)1 (3) Let A =H0，B =H1，C =H2，D =H3，E =H4 (4) for t =0 to 79 do TEMP = (A5)+ft (B, C, D
28、)+E +Wt +Kt ; E =D; D =C; C =(B30); B = A; A = TEMP; (5) Let H0 =H0 +A, H1 =H1 +B, H2 =H2 +C, H3 =H3 +D, H4 =H4 +E 4) 输出 在处理完Mn后，160位的消息摘要为H0、H1、H2、H3、H4级联的结果。 搪 扇 剔 见 刃 罐 醚 癣 碱 助 瀑 兽 禾 磊 烹 没 汝 橇 哎 氟 骸 究 泪 溯 把 炙 滔 偏 厅 豆 广 令 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向
29、散 列 函 数 SHA1与MD5的比较 SHA1是在MD4的基础上开发的。 表SHA-1与MD5的比较 SHA-1MD5 Hash值长度160bit128bit 分组处理长512bit512bit 步数80(420)64(416) 最大消息长264bit不限 非线性函数3(第2、4轮相同)4 常数个数464 况 循 邻 啡 粤 屉 吓 糕 勤 悲 京 趾 崖 桩 稗 搅 假 桑 摆 菠 此 驶 纪 航 商 矗 钩 戮 照 花 丧 拦 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数 第 3 章 - 第 1 讲 伪 随 机 数 发 生 器 与 单 向 散 列 函 数