密码学的基本概念

《密码学的基本概念》由会员分享，可在线阅读，更多相关《密码学的基本概念（51页珍藏版）》请在金锄头文库上搜索。

1、密码学的基本概念uu1 1 密码学的基本概念密码学的基本概念u2 对称算法和非对称算法对称算法和非对称算法uu3 3 网络加密的方式网络加密的方式u4 密码分析0 处理密码的三种方式u三种考虑角度（1）从明文到密文的变换替换(substitution)置换(transposition)（2）钥匙的数目对称、单钥加密法双钥、公钥加密（3）明文的处理方式分组加密（块加密算法）流方式加密1 加密、解密u消息被称为明文（plain text）。u用某种方法伪装消息以隐藏它的内容的过 程称为加密(encryption, encipher)。u加了密的消息称为密文(cipher text)。u而把密文转变

2、为明文的过程称为解密 (decryption, decipher)。1 密码编码与密码分析u使消息保密的技术和科学叫做密码编码学 (cryptography)。u从事此行的叫密码编码者（cryptographer）。u破译密文的科学和技术叫做密码分析学（ cryptanalysis）。u从事密码分析的专业人员叫做密码分析者（ cryptanalyst）。u密码学包括密码编码学和密码分析学两者。现代 的密码学家通常也是理论数学家。密码体制u通常一个完整密码体制要包括如下五个要素通常一个完 整密码体制要包括如下五个要素通常一个完整密码体制要 包括如下五个要素通常一个完整密码体制要包括如下五个 要素

3、M, C, K, E, D 1 M 是可能明文的有限集称为明文空间 2 C 是可能密文的有限集称为密文空间 3 K 是一切可能密钥构成的有限集称为密钥空间 4 对于密钥空间的任一密钥有一个加密算法和相应的解密算法使 得 ek : M C 和 dk :C M 分别为加密解密函数满足dk (ek (x)= x, 这里xM, kKu一个密码体制要是实际可用的一个密码体制要是实际可用的一个密 码体制要是实际可用的一个密码体制要是实际可用的必须满足如下特 性必须满足如下特性必须满足如下特性必须满足如下特性u1 每一个加密函数ek 和每一个解密函数dk 都能有效地计算u2 破译者取得密文后将不能在有效的时

4、间内破解出密钥k 或明文xu3 一个密码系统是安全的必要条件:穷举密钥搜索将是不可行的 密码算法分类u按发展进程分分:密码的发展经历了古典密码、对称密钥 密码、公开密钥密码的发展阶段u古典密码是基于字符替换的密码，现在已很少使用了， 但是它代表了密码的起源，现在仍在使用的则是对位进行 变换的密码算法，这些算法按密钥管理的方式可以分为两 大类：即对称算法与公开密钥算法；对称算法的加密密钥 和解密密钥相同，这些算法也叫作秘密密钥算法或单密钥 算法u按加密模式分：对称算法又可分为序列密码和分组密码 两大类，序列密码-每次加密一位或一字节的明文也可以 称为流密码，序列密码是手工和机械密码时代的主流；分

5、 组密码将明文分成固定长度的组用同一密钥和算法对每一 块加密，输出也是固定长度的密文1 密码学的其它作用u鉴别 消息的接收者应该能够确认消息的 来源；入侵者不可能伪装成他人。u完整性 消息的接收者应该能够验证在传送 过程中消息没有被修改；入侵者不可能用 假消息代替合法消息。u抗抵赖 发送者事后不可能虚假地否认他 发送的消息。1 加密算法u密码算法也叫密码，是用于加密和解密的数 学函数。通常情况下，有两个相关的函数：一 个用作加密，另一个用作解密。u明文用M（消息），密文用C表示，加密函数 E作用于M得到密文C，用数学表示为： E（M）=C.u相反地，解密函数D作用于C产生M D（C）=M.u先

6、加密后再解密消息，原始的明文将恢复出 来，下面的等式必须成立：D（E（M）=M1 受限制的加密算法u如果算法的保密性是基于保持算法的秘密 ，这种算法称为受限制的算法。u如果有人无意暴露了这个秘密，所有人都 必须改变他们的算法。 1 密钥u现代密码学用密钥解决了这个问题，密 钥用K表示。u密钥K的可能值的范围叫做密钥空间。u加密和解密运算都使用这个密钥，加/解 密函数现在变成：EK1（M）=C DK2（C）=M DK2（EK1（M）=MEK（M）=C DK（C）=M DK（EK（M）=M2 对称算法和非对称算法u对称算法 加密密钥能够从解密密钥中推 算出来，反过来也成立。u公开密钥算法 公开密钥

7、算法用作加密的密 钥不同于用作解密的密钥，而且解密密钥 不能根据加密密钥计算出来。2 对称密码的特点u对称加密算法的特点算法强度足够安全性依赖于密钥，不是算法速度快2 对称加密算法的基本模 型 u加密: E: (X,k) Y, Y = E(x,k)XYkEYXkDu解密: D: (Y,k) X, x = D(y,k)2 非对称密码系统的特点2 混合密码体制2 序列密码2 分组密码3 密码通信系统模型-示意 图3 密码通信系统模型-说明3 网络加密的方式3 链路加密3 节点对节点加密3 端对端加密3 网络加密的实现4 密码分析与攻击4 对密码系统的攻击4 密码分析u密码分析学是在不知道密钥的情况

8、下。恢 复出明文的科学。u对密码进行分析的尝试称为攻击。u密码分析的一个基本假设：密码分析者已 有密码算法及其实现的全部详细资料。在 实际的密码分析中并不总是有这些详细信 息的应该如此假设。如果其他人不能 破译算法，即便了解算法如何工作也是徒 然，如果连算法的知识都没有，那就肯定 不可能破译它。密码分析的基本假设u对密码进行分析的尝试称为攻击。荷兰人 A.Kerckhoffs最早在19世纪阐明密码分析的一个 基本假设，这个假设就是秘密必须全寓于密钥中 。Kerckhoffs假设密码分析者已有密码算法及其 实现的全部详细资料（当然，可以假设中央情报 局(CIA)不会把密码算法告诉摩萨德(Moss

9、ad)（ 译注：以色列的情报组织），但Mossad也许会 通过什么方法推出来）。u在实际的密码分析中并不总是有这些详细信息的 应该如此假设。如果其他人不能破译算法， 即便了解算法如何工作也是徒然，如果连算法的 知识都没有，那就肯定不可能破译它。密码算法的安全性Lars Knudsen把破译算法分为不同的类别，安全性的递减顺序为：u1全部破译。密码分析者找出密钥K，这样: DK（C）=P。u2全盘推导。密码分析者找到一个代替算法A，在不知道密钥K的 情况下，等价于: DK（C）=P。u3实例（或局部）推导。密码分析者从截获的密文中找出明文。u4信息推导。密码分析者获得一些有关密钥或明文的信息。这

10、些 信息可能是密钥的几个比特、有关明文格式的信息等等。u如果不论密码分析者有多少密文，都没有足够的信息恢复出明文， 那么这个算法就是无条件保密的，事实上，只有一次一密乱码本，才 是不可破的（给出无限多的资源仍然不可破）。所有其它的密码系统 在唯密文攻击中都是可破的，只要简单地一个接一个地去试每种可能 的密钥，并且检查所得明文是否有意义，这种方法叫做蛮力攻击 u密码学更关心在计算上不可破译的密码系统。如果一个算法用（现 在或将来）可得到的资源都不能破译，这个算法则被认为在计算上是 安全的（有时叫做强的）。准确地说， “可用资源”就是公开数据的 分析整理密码攻击的复杂性u可以用不同方式衡量攻击方法

11、的复杂性 ：u1数据复杂性。用作攻击输入所需的数据量。u2处理复杂性。完成攻击所需要的时间，这个经常叫做工作因素u3存储需求。进行攻击所需要的存储量。u作为一个法则，攻击的复杂性取这三个因数的最小化，有些攻击包 括这三种复杂性的折中：存储需求越大，攻击可能越快。u复杂性用数量级来表示。如果算法的处理复杂性是2128，那么破译 这个算法也需要2128次运算；假设有足够的计算速度去完成每秒钟一 百万次运算，并且用100万个并行处理器完成这个任务，那么仍需花 费1019年以上才能找出密钥，那是宇宙年龄的10亿倍。u当攻击的复杂性是常数时，就只取决于计算能力了。u许多密码分析攻击用并行处理机是非常理想

12、的：这个任务可分成亿 万个子任务，且处理之间不需相互作用。u一种算法在现有技术条件下不可破译就简单地宣称该算法是安全的 ，这非常冒险。好的密码系统应设计成能抵御未来许多年后计算能力 的发展。4（1）唯密文攻击u密码分析者有一些消息的密文这些消息都用同一加密算法加密密码分析者的任务是恢复尽可能多的明文或者最好是能推算出加密消息的密钥来已知：C1=EK（P1），C2=EK（P2）， ，推导出：P1，P2，4（2）已知明文攻击u密码分析者不仅可得到一些消息的密文， 而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加 密的密钥或导出一个算法，此算法可以对用同 一密钥加密的任何新的消息进行解

13、密。已知：P1，C1=Ek（P1），P2，C2=Ek（P2 ），Pi，Ci=Ek（Pi）推导出：密钥k，或从Ci+1= Ek（Pi+1）推出 Pi+1的算法。4（3）选择明文攻击u分析者不仅可得到一些消息的密文和相应的 明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能 选择特定的明文块去加密，那些块可能产生更多关 于密钥的信息，分析者的任务是推出用来加密消息 的密钥或导出一个算法，此算法可以对用同一密钥 加密的任何新的消息进行解密。4（4）选择密文攻击u密码分析者能选择不同的被加密的密文， 并可得到对应的解密的明文，例如密码分 析者存取一个防窜改的自动解密盒，密码

14、分析者的任务是推出密钥。 已知：C1，P1=Dk（C1），C2，P2=Dk（C2 ），Ci，Pi=Dk（Ci）， 推导出： k。4（5）软磨硬泡攻击u密码分析者威胁、勒索，或者折磨某人 ，直到他给出密钥为止。行贿有时称为购 买密钥攻击。这些是非常有效的攻击，并 且经常是破译算法的最好途径。4 穷举攻击4 分析破译4 分析破译的条件4 猜测破译4 攻破密码系统的标准4 要公开加密算法吗 u最好的算法是那些已经公开的，并经过 世界上最好的密码分析家们多年的攻击， 但还是不能破译的算法。u 美国国家安全局对外保持他们的算法的 秘密，但他们有很好的密码分析家在内部 工作，他们互相讨论他们的算法，通过执

15、 著的审查发现他们工作中的弱点。4 要公开加密算法吗 u密码分析者不是总能知道算法的。例如在 二战中美国人破译日本人的外交密码 紫密（PURPLE）794就是例子，而且美 国人一直在做这种事。如果算法用于商业 安全程序中，那么拆开这个程序，把算法 恢复出来只是时间和金钱问题。如果算法 用于军队的通讯系统中，购买（或窃取） 这种设备，进行逆向工程恢复算法也只是 简单的时间和金钱的问题。4 加密算法的有效性uUnconditionally secure，绝对安全？永不可破，是理想情况，理论上不可破， 密钥空间无限，在已知密文条件下，方程无解 。但是我们可以考虑：破解的代价超过了加密信息本身的价值破

16、解的时间超过了加密信息本身的有效期uComputationally secure，满足上述两个条件4 直觉：什么是一个好的加 密算法u假设密码(password)k是固定的u明文和密文是一个映射关系：单射，即Ek(x1) != Ek(x2) if x1 != x2u通常情况是：明文非常有序u好的密码条件下，我们期望得到什么样的 密文随机性u如何理解随机性静态：特殊的点动态：小的扰动带来的变化不可知4 考虑设计一个加密算法u打破明文本身的规律性随机性(可望不可及)非线性(一定要)统计意义上的规律u多次迭代迭代是否会增加变换的复杂性是否存在通用的框架，用于迭代u复杂性带来密码分析的困难和不可知性实践的检验和考验4 已有密码算法的讨论u经典密码算法替换技术置换技术u现代密码算法DES其他密码算法uAES密码算