02 密码技术基础

02 密码技术概要,主要内容,密码学的发展历史 密码体制 散列函数 消息认证 数字签名 身份认证和密钥管理,密码简史,最早可追溯到4000年前：字母、字符的掉换 大约前400年：开始使用加密棒 两次世界大战促进了密码的长足发展 1949年Shannon发表论文“保密通信的信息理论” 密码研究成为学术研究 1976年W.Diffie和M.E.Hellman发表论文“密码学的新方向”：公钥思想提出 21世纪，各种新领域的密码学研究得到了广泛的开展,密码体制,Kerchhoff原理,一个密码系统唯一应该保密的只有密钥。不公开的算法意味着可能更多的弱点。 军事部门和政府应用中核心密码对外部不公开加密算法，在内部还是公开的。,密码体制的分类,根据密钥的使用方式不同，可分为： 对称密码：用于加密数据的密钥和用于解密的密钥相同，或者两者之间存在着某种明确的数学关系。 非对称密码（公钥密码）：用于加密的密钥和解密的密钥不同，而且从加密密钥很无法推导出将解密密钥。,对称密码体制,古典密码主要的设计原理是：代换和置换 现代密码中，大多数优秀算法的主要组成部分仍然是代换和置换的组合 对称密码有两种不同的实现方式： 分组密码：先把明文划分成许多分组，每个明文分组被当成一个整体来产生一个等长的密文分组。 序列密码：每次加密数据流中的一位或一个字节。,分组密码,分组密码体制是目前商业领域中比较重要而流行的加密体制，广泛应用与数据的保密传输、加密存储等应用场合。 典型的分组密码有：DES、AES,计算安全与理论安全,理论安全：不管破译者截获多少密文并加以分析，其结果和直接猜明文没有区别；理论上任何算法（一次一密除外，但它不实用）都是可破译的 计算安全：如果破译所需的计算能力和时间是现实所不能实现的，则称该密码体制是安全的，或称为计算上安全的；破译一密码所需要的计算时间和计算能力的总和，即破译算法的时间复杂度和空间复杂度，称为工作因子。,序列密码,序列密码也称流密码。 “一次一密”在理论上是不可攻破的。序列密码则由“一次一密”密码启发而来。 序列密码的关键是产生密钥流的算法，该算法必须能够产生可变长的、随机的、不可预测的密钥流。 实际应用中密钥留不可能真正随机。 典型的序列密码是RC4。,其他对称加密算法,在不同的安全系统中，还存在其他对称加密算法： IDEA-国际数据加密标准 CLIPPER Blowfish Twofish CAST-128 GOST,非对称加密原理,公钥和私钥不是简单的不同，公钥和私钥一一对应，但由公钥导出私钥很困难！,非对称密码,常见的公钥密码算法： RSA DH ECC ElGamal 公钥密码算法基于数学函数而不是基于代换和置换,单向陷门函数 满足下列条件的函数f称为单向陷门函数 (1)给定x，计算y=f(x)是容易的； (2)给定y, 计算x使y=f(x)是困难的。(所谓计算x=f-1(Y)困难是指计算上相当复杂，已无实际意义。) (3)存在，已知 时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。 只满足前两条的称为单向函数 公钥密码体制相当于单向陷门函数族,RSA,基本情况 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的（见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126) 该算法的数学基础是初等数论中的Euler（欧拉)定理，并建立在大整数因子的困难性之上。 欧拉定理（Euler）：若整数a与整数n互素，则a(n)1(mod n) ak(n)1a(mod n) aeda(mod n) (ae ) da(mod n),算法描述：假设明文空间P密文空间C=Zn. (a) 密钥的生成: 选择p,q，p,q为互异素数，计算n=p*q, (n)=(p-1)(q-1), 选择整数e使得(n),e)=1,1e (n), 计算d,使d=e-1(mod (n),公钥Pk=e,n;私钥Sk=d,p,q (b)加密 (用e,n):明文：Mn 密文：C=Me(mod n). (c)解密 (用d,p,q)：密文：Cn 明文：M=Cd(mod n),注：1*, 加密和解密时一对逆运算。 M=Cd（mod n)= Med（mod n)=M 2*, 对于0Mn时，若(M,n) 1，则M为p或q的整数倍，假设M=cp，由(cp,q)=1 有 M (q) 1(mod q) M (q) (p) 1(mod q) 有M (q) (p) = 1+kq 对其两边同乘M=cp有 有M (q) (p) 1=M+kcpq=M+kcn于是 有M (q) (p) 1 M(mod n),DH公钥加密,混合加密系统： 公钥机制传输密钥 对称机制加密数据 “DH公钥加密”“DH密钥交换”“对称加密” DH密钥交换：通信双方可安全可靠的共享密钥。相当于公钥，比公钥似乎更好！,DH交换：当Alice和Bob要进行保密通信时，他们可以按如下步骤来做： (1)Alice送取大的随机数x，并计算X=gx(mod P) (2)Bob选取大的随机数x，并计算X = gx (mod P) (3)Alice将X传送给Bob；Bob将X 传送给Alice。 (4)Alice计算K=(X )X(mod P);Bob计算K （X) X (mod P),易见，K=K =g xx (mod P)。 由(4)知，Alice和Bob已获得了相同的秘密值K,ECC,椭圆曲线密码算法ECC基于在有限域的椭圆曲线上定义加法和乘法形成椭圆群，在此椭圆群上离散对数的求解将更加困难。ECC的优点在于用少得多的比特大小取得和RSA相等的安全性。 ECC由于密钥短，速度快，可以用于智能卡等存储和运算能力有限的设备上。国际上对ECC的兴趣越来越大，其应用越来越广泛。,非对称密码应用方式,3 密码认证,HASH函数 消息认证 数字签名 身份认证 PKI,HASH函数,Hash函数,完整性校验；数字指纹技术；计算指纹容易，反之很困难，不同信息指纹相同的概率极小。Hash是一种直接产生认证码的方法 Hash函数: h=H(x), 要求: 可作用于任何尺寸数据且均产生定长输出 H(x)能够快速计算 单向性: 给定h，找到x使h=H(x)在计算上不可行 Weak Collision Resistence(WCR): 给定x，找到yx使H(x)=H(y)在计算上不可行 Strong Collision Resistence(SCR): 找到yx使H(x)=H(y)在计算上不可行 MD5，SHA1,消息认证,消息认证概念： 消息认证问题的背景与消息加密方案的背景很相似，通信双方也在一个不安全信道上传送消息，如互联网（internet），但现在的第三者不仅可能截取消息进行分析，而且可能伪造或篡改发送的消息，称为入侵者。通信双方希望交换消息而拒绝接受入侵者欺骗的协议。,三种方式 Message encryption：用整个消息的密文作为认证标识 接收方必须能够识别错误 MAC：一个公开函数，加上一个密钥产生一个固定长度的值作为认证标识 Hash function：一个公开函数将任意长度的消息映射到一个固定长度的散列值，作为认证标识,数字签名,消息认证可以保护双方之间的数据交换不被第三方侵犯，但它并不保证双方自身的相互欺骗。 即虽然保证了信息的完整性，但无法保证信息的抗否认性 数字签名利用公钥密码体制进行，其安全性取决于密码体制的安全性,数字签名,基于RSA的签名方案 令MS=Zn,选择p,q，p,q为互异素数，计算n=p*q, (n)=(p-1)(q-1), 选择整数e使得(n),e)=1,1e (n), 计算d,使d=e-1(mod (n),公开Pk=e,n; Sk=d,p,q保密 对k=(n,p,q,e,d)，定义 Sigk (x)= xe (modn),x Zn Verk (x,y)=T y= xd (modn), x,y Zn,PKI,概念：Public Key Infrastructure是一个用公钥概念与技术来实施和提供安全服务的具有普适性的安全基础设施 解决问题： 公钥技术如何提供数字签名功能 公钥技术如何实现不可否认服务 公钥和身份如何建立联系：为什么要相信这是某个人的公钥 公钥如何管理 方案：引入证书和权威中心实现,核心功能： 证书管理：创建、签发、废除 证书认证： 加密、签名服务：,4 密钥管理,密钥分配 密钥管理原则 秘密共享 Clipper芯片的密钥管理,密钥分配,对于通信方A和B来说，密钥分配可以用以下几种方法完成： (1) 一个密钥由A选定，然后物理地传递给B。 (2) 一个第三方可以选定密钥，然后物理地传递给A和B。 (3)如果A和B在不久以前使用过一个密钥，一方可以使用旧密钥加密新密钥并传输给另一方。 (4)如果A和B每人都有一个到第三方C的加密连接，C就可以用加密连接把密钥传递给A和B。,密钥管理原则,密钥应足够长 密钥应安全保存和传送 密钥应尽量在随机 密钥生命周期与保护对象的敏感程度相关 密钥应该备份或交由可信第三方保护，以防万一 密钥生命周期后应该销毁,秘密共享,在用电子方式来存储重要档案中，对不同的加密解密密钥以一个主密钥（Master Key）来加以保护，并交给单独一个系统管理员保管，操作上存在许多弊端。 将主密钥复制多份，交给多位系统管理员保管。 将主密钥打造成n份不同的子密钥（Shadow），交给n位系统管理员保管，一人一份，当所有管理员到齐后才能推导出主密钥。 秘密共享在实用密码学领域内是一个非常重要的工具，在理论密码学领域内也是研究成果非常丰富的。,Clipper芯片的密钥管理,用会话密钥加密,用单位密钥加密,消息,消息,Clipper芯片序 列号数据库,1、序列号与单位密钥对应 2、消息中包含序列号信息 3、从而可以获得会话密钥 和信息本身,5 密码攻击,密码分析 中间人攻击 字典攻击 重放攻击 旁路攻击,密码分析,密码分析： 仅密文攻击：密文片段 已知明文攻击：若干明文密文对 选择明文攻击：任意明文密文对 选择密文攻击：任意密文明文对,6 小结,公钥理论和应用 认证基本方法和应用 密钥管理相关概念,思考题 试述公钥密码算法和单向限门函数的关系。 公钥密码算法两种基本的应用方式是什么？ DH交换在什么应用环境下解决了安全通信中的什么问题？ 什么是数字签名，数字签名和MAC、HASH有什么异同？ 试设计一个非对称密码体制应用的场景。,