北京大学网络信息安全课件-消息验证与数字签名.ppt

回顾上次课的内容 分组密码的操作模式 实用中数据格式的多样性 安全的工作模式 分组密码的分析方法 现代常规分组加密算法 Triple DES RC5、RC6 AES …… 加密的位置： 链路方式和端到端的方式 讨论议题 随机数的产生 密钥分配 公钥密码算法 Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC 随机数（Random number） 随机数用途，重要的角色，例如 认证过程中，避免重放攻击 会话密钥 RSA公钥算法 随机数的基本特点 随机性 均匀分布，有大量的测试方案 独立性，难以测试，只能测试足够独立 不可预测性 Random number generation 真正的随机数难以产生 伪随机数 线性同余法 Xn+1 = (aXn+c) mod m m 模数 m0 231 a 乘数 0?am a=75=16807 c 增量 0 ?cm X0 种子 0 ? X0m 线性同余伪随机数缺乏不可预测性 基于密码的随机数产生 循环加密 DES输出反馈方式 ANSI X.917 伪随机数产生器 Blum Blum Shub(BBS)产生器 循环加密 DES输出反馈模型 BBS伪随机数产生器 (1)首先选择两个大素数p,q p?q ?3(mod4) (2)选择s与n互素 通过了“下一位”测试(next-bit test) 不存在多项式时间的算法使得在已知前k位的情况下预测出第k+1位的概率大于0.5 BBS的安全性同样基于分解n的难度 密钥分配（Key Distribution） 必威体育官网网址通信双方需共享密钥 共享密钥要经常更换 A选择密钥并手工传递给B 第三方C选择密钥分别手工传递给A,B 用A,B原有共享密钥传送新密钥 与A,B分别有共享密钥的第三方C传送新密钥给A和/或B N个用户集需要N(N-1)/2个共享密钥 密钥分发中心(Key Distribution Center) Key Distribution Center 每个用户与KDC有共享密钥(Master Key) N个用户,KDC只需分发N个Master Key 两个用户间通信用会话密钥(Session Key) 用户必须信任KDC KDC能解密用户间通信的内容 起源 公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, 见 Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126 公开密钥密码的重要特性 加密与解密由不同的密钥完成 加密: X?Y: Y = EKU(X) 解密: Y?X: X = DKR(Y) = DKR(EKU(X)) 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的) X = DKR(EKU(X)) = EKU(DKR(X)) 基于公开密钥的加密过程 基于公开密钥的鉴别过程 基本思想和要求 涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文 公钥算法的条件： 产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的顺序可交换 陷门单向函数 单向陷门函数是满足下列条件的函数f： (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使x=fk-1(y)是不可行的。 (3)存在k，已知k 时,对给定的任何y，若相应的x存在，则计算x使fk-1(x)是容易的。 Euler数 Euler数?(n)定义为小于n且与n互素的正整数个数 p是素数,?(p)=p-1 若n的因子分解为n=?Piai, ai0,Pi互不相同,则 ?