密码学

内容提纲 密码学概述 密码学相关知识 古典加密技术 对称密码体制 非对称密码体制 密钥的管理 散列函数与数字签名

密码学概述 一个加 密系统 采用 的基本 工作 方式称 为 密码体 制，密 码体 制的基 本要 素是密 码 算法和 密钥， 其中 密码算 法是 一些公 式 、法则 或程序 ，而 密钥是 密码 算法中 的 可变参 数。 密码算 法分为 加密 和解密 算法 ，前者 是 将明文 变换成 密文 ，后者 是将 密文变 换 成明文 ；密钥 相应 地也分 为加 密密钥 和 解密密 钥。

一个加 密系 统数学 符号 描述如 下： S= ｛ P ， C ， K ， E ， D ｝ 其中 P 是明文 空间， C 是密文 空间， K 是密 钥空 间， E 是加密 算法 ， D 是解密 算法， 当给 定密钥 k∈K 时， 加、 解密算 法分 别记作 Ek 和 D k ，并有 ： C=Ek(P) P=Dk(C)=Dk(Ek(P)), 或记为

Dk=Ek–1 且 Ek=Dk–1

现代密 码学的 一个 基本原 则是 一切秘 密应寓 于密钥 之中 ，即在 设计 加密系 统时， 总是假 定密 码算法 是公 开的， 真正需 要保密 的是 密钥。

加密通信的模型

加密密钥

解密密钥 密文

明文

加密算法

解密算法

密码学 相关 知识 专有名 词 •明文 pla in text – 原始信息 •密文 cip he rtex t – 加密后的信息 •加密 cip he r – 将明文转换成密文的算法 •密钥 ke y – 只有传送者和接受者才知道的加密 用资料 •加密 enc ip her (e nc ry pt) – 将明文转换为 密文 •解密 dec ip her (d ec ry pt) – 将密文破解为 明文 •密码学 cr ypt ogr ap hy – 研究加密的原理与方 法 •密码破 解 cr yp ta nal ysi s (c ode bre ak in g) – 在不知道密钥的情況下，研究破解密文的原理与 方法 •密码技 术 cr yp to log y – 整合密码与密码破解

密码破 解的方 式 唯密文 –只知 道演 算方法 与密 文，利用统 计方法 来求出 明 文

已知明 文 –籍由 已知 的或推 测的 明文－ 密文 组合来 破解

选择文 1. 自选 明文 –籍由 自选 的明文 与对 应的密 文来 破解

2. 自选 密文 –籍由 自选 的密文 与对 应的明 文来 破解

暴力搜 寻法 •理论上 可以 尝试所 有的 密钥 •最基本 的破 解法，所需 成本与 密钥 大小成 正比 •前提： 可以 看懂或 辨识 明文

古典加 密技 术 凯撒 加密法 •我们所 知道的 最早 的加密 法 •由凯撒 所发展 出来 的 •最早运 用于军 事 •将每个 字母用 后面 的第三 个字 母来 替代 •范例 :

meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB

•可将转 换方式定义 如下

:

a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

•指定 一个 数字给每 个字 母 a b c d e f g h i j k

l

m

0 1 2 3 4 5 6 7 8 9 10 11 12 n

o

p

q

r

s

t

u

v

w

x

y

Z

13 14 15 16 17 18 19 20 21 22 23 24 25

•则可将凯 撒加 密法定 义如 下

:

C = E(p) = (p + k) mod (26) p = D(C) = (C – k) mod (26)

凯撒 加密法 的破 解方式 •只有 26 种加 密方式 –A 对应 到 A,B,…Z •采用暴 力搜 寻法 •给定密 文后 ，只需 测试 所有可 能的 位移 距离（ 26 种） •当明文 出现 时能辨 析出 来 •例如， 破解 密文 “ GCUA VQ DTGCM”

凯撒 法得 出的 26 种加 密方式

Monoalphabetic 加密 法 •不只是 单纯 对字母 移位 •可以任 意的 弄乱字 母 •每个明 文字 母都会 随机的 对应 到另 一个 密文字 母 •应此， 密钥 的长度 就是 26 位字母 明文 : abcdefghijklmnopqrstuvwxyz Key: DKVQFIBJWPESCXHTMYAUOLRGZN 明文 : ifwewishtoreplaceletters 密文 : WIRFRWAJUHYFTSDVFSFUUFYA

Monoalphabetic 加密法的安全性 •现在共有 •26 ！＝ 26×25×24…×2×1= 4 x 1026 钥匙 •有这么多把钥匙，应该算是安全 了！！！？？？

语言的特性 与密码破 解的关系 •人类的语言是充满赘词的 •例如 “ th lrd s m shphrd shll nt wnt” •字母的使用频率并不等 •在英文中， e 的使用次数最高 •其次是 T,R,N,I,O,A,S •其它字母很少用 •如 Z,J,K,Q,X •单字母、双字母已经三字母的出现 频率已经有现成的统计表格

英文字 母的出 现频 率

应用在 密码破解 上 •关键概 念 - monoalphabetic 取代加 密法 并不 会改 变字母 间相 对出现 的频 率 •阿拉 伯科学 家在 九世 纪时就 发现了 这种 破解法 •计算 密文的 字母 出现 的频率 •将结 果与已 知的 频率 数值互 相比较 •如果 针对 Cae sa r 加密法 的统计 图形找寻波 峰与 波谷 –波峰波峰在 A-E -I 三字母 , NO 双字母 , RS T 三字母 –波谷出现在 : JK , X-Z •如果 是针对 mono al pha bet ic 加密法 ，就必 须 逐一辨 识每个字母 –常用的 双字母 与三字 元统计 表格可 以帮助我 们来破解

破解范例 •给定密文 : UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

•

计算 字母 出现频 率

•

猜测 P 与 Z 就是 e 与 t

•

猜测 ZW 就是 th ，而 ZWP 就是 the

•

在边试 边改 的情况 下，最后可 得 : it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong in moscow

Playfair 加密法 •根据一 个关键 字来 产生一 个 5X5 阶的字 母矩阵 •将关键 字的字 母填 入矩阵 中 ( 删除 重复字 母 ) •将剩余 字母填 入矩 阵中 •例如，使用 关键字 MONARCHY MONAR CHYBD EFGIK LPQST UVWXZ

加密与解密 •每次加 密明 文中的 两个 字母 : 1. 如果这两 个字母 一样 ，则在其间 插入 ‘ X’ ，例如 “ ba llo on ” 变成 “ ba l x lo on ” 2. 如果 这两个 字母落在 矩阵 中的同一 列， 则 用它们右边 的字 母来取 代它 们 ( 把第 一个 字元 当成是 最后一个 字母的右边字元 ) 。例 如 “ ar” 变成 “ RM ” 3. 如果 这两个 字母落在矩 阵中的同一 行， 则 用它 们下方 的字 元来取代它们 ( 把第一 个 字母当 成是最 后一个字母的下方 字母 ) 。例 如 “ mu” 变成 “ CM ” 4. 在其他 的情况下， 每个字母都换成与 它自 己同一列 ，但 是与另一个字母同一行 的那 个 字母。例 如， “ hs ” 变成 “ BP” ，“ ea” 变成 “ IM ” 或是 “ JM” ( 由加

Playfair 加密法的安全 性 •比 monoalphabetic 安全 许多 •因为有 26 x 26 = 676 那么多 字母 •表格中 需要 676 个项目才 足以 分析 (monoalphabetic 的表格 只需 要 26 个项目 ) •相对的 产生 更多的 密文 •已经广 泛地 使用许 多年 ( 例如 ，第一次世 界大 战时 ，美军与英 军都 使用此 法 ) •在给定 几百 个字母 的密文 的情 况下 ，词法 仍可 破解 •应为其 中仍 存有明 文的结 构

古典的 加密方 法除 了上面 介绍 的三种 ，还 有很多 ，下面 列举 了一些 具有 代表性 的古 典加密 方法 Polyalphabetic 加密法 Vigenère 加密法 Autokey 加密法 One-Time Pad 加密法 旋转 机加 密法 … 等等

对称密 码体制

对称密 码体制 又称 为秘密 密钥 密码体 制（或 单密钥 密码 体制／ 隐蔽 密钥密 码体 制 ），即 加密密 钥和 解密密 钥相 同或一 个可 由 另一个 导出。

分组 密码 体制 这是根 据密码 算法 对明文 信息 的加 密方 式进 行分类 的方 法。如 果密 文仅与 给定 的密 码算 法和密 钥有 关，与 被处 理的明 文数 据段 在整 个明文 （或 密文） 中所 处的位 置无 关， 则称 为分组 密码 体制。 分组 密码体 制就 是将 明文 分成固 定长 度的组 ，如 64bit 一组 ，用 同一 密钥和 算法 对每一 组加 密，输 出也 是固 定长 度的密 文。 序列 密码 体制 如果密 文不仅 与给 定的密 码算 法和 密钥有关 ，同时 也是被 处理 的明文 数据 段在 整个明文 （或密 文）中 所处 的位置 的函 数， 则称为序 列密码 体制 。

确定型密码体制 如果一个 加密 过程可 以描 述为： 当 明文和 密钥 确定后 ，密 文的形 式也 就惟一 地 确定， 则称 为确定 型密 码体制 。前 面提到 的 加密方 法中 ，多数 属于 这一类 。 概率密码体制 如果一 个加 密过程 可以 描述为 ：当 明文 和密钥 确定 后，密 文的 形式仍 是不 确定的 ， 最后产 生出 来的密 文通 过客观 随机 因素从 一 个密文 集合 中选出 ，则 称为概 率密 码体制 。

美国 数据加 密标 准（ DES ） 1 ． DES 算法

DES 属于分组 加密 算法。 在这 个加密 系统中 ，其每 次加 密或解 密的 分组大 小是 64 位，所 以 DES 没有密 文扩充 的问 题。

DES 的描述 • DES 利用 56 比特 串长 度的密 钥 K 来加密长 度 为 64 位的明 文，得 到长 度为 64 位的密 文 输入 64 比特明 文数 据 初始置换 IP 在密 钥控制 下 16 轮迭代 交换左 右 32 比特 初始 逆置 换 IP-1 输出 64 比特密 文数 据 DES 算法框 图

DES 的安全性 （ 1 ）弱 密钥（ Weak Key ） 所谓的弱 密钥 是指在 所有 可 能的密 钥中 ，有某 几个 特别的 密钥 会 降低 DES 的安全 性，所 以使 用者一 定 要避免 使用 这几个 弱密 钥。 （ 2 ）半 弱密钥 （ Semi-weak Key ） 除了上述 的弱 密钥之 外， 还 有另外 一种 被称为 半弱 密钥的 初始 密 钥。半 弱密 钥所产 生的 子密钥 只有 两 种可能 ，每 一种可 能的 子密钥 刚好 各 出现 8 次。

Triple-DES 的四种模型 • DES-EEE3 ：三个不同密钥，顺序使用三次加 密算法 • DES-EDE3 ：三个不同密钥，依次使用加密 解密 - 加密算法 • DES-EEE2 ： K1=K3 ，同上 • DES-EDE2 ： K1=K3 ，同上

国际数据加密算法（ IDEA ） 国际 数据加 密算 法 （ International Data Encryption Algorithm ， IDEA ）是由 瑞士 联邦理 工 学院 Xuejia Lai 和 James Massey 的在 1990 年提出 的。 IDEA 是最近几 年提 出 的用来 替代 DES 的许多 算法 中的一 种 ，是一 个对 称分组 密码 算法。

设计原理 IDEA 是一 种使用 128 位密钥 以 64 位分 组为单 位加 密数据 的分 组密码 算 法。 与此相 对照 ， DES 使用 56 位密 钥以 64 位的 分组为 单位 进行加 密。 IDEA 的设计 目标可 以归 结为与 密码 强 度和 使用的 方便 性两方 面有 关，其 中 密码 强度包 括分 组长度 、密 钥长度 、 混淆 （ Confusion ）和扩 散 （ Diffusion ）； 使用的 方便 性指方 便 硬件 和软件 实现 。通过 由超 大规模 集 成电 路（ VLSI ）进行 的硬件 实现 的 设计 目标是 取得 高速度 ，而 软件实 现 则有 灵活和 低价 的优点 。

IDEA 加密方法

IDEA 加密 方法包 括 8 轮的 重复 运算， 加上最 后的 输出变 换运 算 （ Transformation ）。 64 位的 明文分 组在 每 一轮中 都是 被分成 4 份，每 份 16 位为一单 元来处 理。 每一轮 中有 6 个不同 的子密 钥参 与作用 。

高级加密标准（ Advanced Encryption Standard ） AES 的基本要 求是 该算法 是对 称密码 体制 ，也即 秘密密 钥算 法；算 法应 为分组 密码 算法 ，分组 长度是 128bit ，密钥 长度为 128 ， 192 和 256bit ；比三 重 DES 快， 至少和 三重 DES 一 样安全 。 “Rijndael 数据加 密算 法”为 新世 纪的美 国 高级加 密标准 推荐 算法。 Rijndael 算法 是由比 利时 的两个 学者 Joan Daemen 和 Vincent Rijmen 提出 的。该 算法 的原 形是 Square 算法， 它的设 计策 略是宽 轨迹 策略

设计基本原理

该算 法的设 计目 标有以 下 3 点：

① 能抗击 所有 的已知 攻击 ； ② 在广大 范围 平台上 的快 速和代 码简 洁； ③ 设计简 单。

非对称密码体制 非对称 密码 体制又 称为 公开密 钥密 码 体制， 即加 密密钥 公开 ，解密 密钥 不 公开， 从一 个推导 出另 一个是 不可 行 的。

非对称 密码体 制的原 理 公开 密钥 加密过 程重 要步骤 如下 。 （ 1 ）网络 中的每 个端 系统都 产生 一对 用于它 将接 收的 报文 进行加 密和 解密的 密钥 。 （ 2 ）每个 系统都 通过 把自己 的加 密密 钥放进 一个 登记 本或 者文件 来公 布它， 这就 是公开 密钥 。另一 个则 是私 有的。 （ 3 ）如果 A 想给 B 发送一 个报 文， A 就是 B 的公 开密 钥加 密这个 报文 。 （ 4 ） B 收到这 个报 文后就 用他 的保 密密钥 解密报 文。 其他 所有收 到这 个报文 的人 都无法 解密 ，因为 只有 B 才有 B 的私有 密钥 。

为了区 分开这 两个 机制， 一般 将常规 加密 中 使用的 密钥称 为秘 密密钥 （ Secret Key ） ，公开 密钥加 密中 使用的 两个 密钥则 称为 公 开密钥 （ Public Key ）和私 有密钥 （ Private Key ）。在 任何 时候私 有密 钥 都是保 密的， 把它 称为私 有密 钥而不 是秘 密 密钥， 以免同 常规 加密中 的秘 密密钥 相混 淆 。

RS A 算法 RSA 是一种分组密码，其理论基础是一种特 殊的可逆模幂运算，其安全性基于分解大整 数的困难性； RSA 既可用于加密，又可用于数字签名，已 得到广泛采用； RSA 已被许多标准化组织 ( 如 ISO 、 ITU 、 IETF 和 SWIFT 等 ) 接纳；

DSA • 数字签名算法，是 Elgamal 签名机制的一 种变形，变美国 NIST 作为 DSS （数字签 名标准）于 1994 年 5 月 19 日被颁布，专 用于签名 / 验证。

RSA 与 DSA 比较 • RSA 既可用于加密 , 也可用于签名 ; • DSA 只能用于签名 , 不能用于加密 ; • RSA 算法产生签名比 DSA 慢，但验证签名 比 DSA 快 ;

密钥的管理 密钥的 管理综 合了 密钥的 设置 、产生 、分 配、存 储、进 入、 使用、 备份 、保护 和销 毁等 一系列 过程。 其中 密钥分 配是 最棘手 的问 题。

1 ．密钥设置协议 2 ．密钥分配 目前， 典型的 自动 密钥分 配 途径 有两类 ：集 中式分 配方 案和分 布 式分 配方案 。 所谓 集中式 分配 是指利 用网 络中的 “ 密钥 管理中 心” 来集中 管理 系统中 的 密钥 ，“密 钥管 理中心 ”接 受系统 中 用户 的请求 ，为 用户提 供安 全分配 密 钥的 服务。 分布 式分配 方案 取决于 它们 自己的 协

3 ．密钥保护 4 ．密钥产生及进入 5 ．密钥的保存 密钥整 体保存 的最 简单方 法是 将其记 忆在 脑子中 。 密钥分 散保存 的目 的是为 了降 低由于 某个 人或保 密装置 的问 题而导 致密 钥泄漏 的危 险。 6 ．密钥的使用、备份和销毁 密钥的 保存机 制重 点在于 安全 问题， 但也 有可靠 问题， 因此 密钥的 备份 机制也 是需 要的 。

密钥的 分配 密钥 的分 配技术 解决 的是在 网络环 境中需 要进 行安全 通信 的端实 体之间 建立共 享的 对称密 钥问 题。 1 ．对称密码体制的密钥分配 对于 通信 方 A 和 B 来说， 密钥分 配可以 用以 下的多 种方 法完成 。

（ 1 ）一个 密钥可 以由 A 选定，然 后物 理地传 递给 B 。 （ 2 ）一个 第三方 可以 选定密 钥，然 后物理地传 递给 A 和 B。 （ 3 ）如果 A 和 B 在不久 以前使 用过 一个密 钥， 一方 可 以使 用旧 密钥加 密新 密钥并 传输 给另一 方。 （ 4 ） 如 果 A 和 B 每人都 有一 个和三 方 C 的加密连 线 ， C 就可以加 密连 线把密 钥传递 给 A 和 B 。

在这个 方案中 ，一 个密钥 分配 中心（ Key Distribution Center ， KDC ）负责按 照需 要 分配密 钥给各 对用 户（主 机、 进程和 应用 ）。 每个用 户必须 与 KDC 共享一 个惟一 的密 钥 ，以便 进行密 钥分 配。 每一 个端 系统或 用户 都与 KDC 共 享惟一 的主密 钥， 当然， 这些 主密钥 要以 某 种方式 进行分 配。

散列函数与数字签名 散列函 数 1． 对任 意长度 的明 文 m ，经 由散列 函数 h 可产生固 定 长度的 散列值 ，下 面用 h(m) 表 示产生 的散列 值。 使用在 数字 签名上 的散列 函数 必须满 足下 面的条 件。

（ 1 ）散列函 数必 须对任 意长 度的明 文产 生固定 长度 的 散列函数 值。

（ 2 ）对任 意的 明文 m ，散列 函数值 h(m) 可通 过软 件 或硬件很 容易 地产生 。 （ 3 ）对任 意的 h(m) 值 x ，要找 到一个 明文 m 与之对 应，即 x=h(m) ，在计 算上是 不可 行的。 （ 4 ）对一 个明 文 m1 ，要找到 另一 个不同 的明 文 m2 ， 而且具有 相同 的散列 函数值 h(m1)= h(m2) ，在 计算 上 是不可行 的。 （ 5 ）要找 到任 意一对 不同 的明 文（ m1 ， m2 ），而 且 具有相同 的散 列函数 值 h(m1)= h(m2) ，在 计算 上是不 可行的。

散列函数 的特 点 • 密钥尺寸至少为 散列结果的 • 对不同报文很难 有不同的报 这与不同的人有 不同的指纹 • 强单向杂凑与弱 单向杂凑－ 性 Collision-free)

长度 文摘要， 很类似 （无碰撞

报文 摘要 报文摘要 （ Message Digests ）是单向 的 散列 函数 ，它以 变长 的信息 为输 入，把 其压 缩成 一个 定长 的值输 出。 若输入 的信 息被改 变了 ，则 输出 的定 长值（ 摘要 ）也会 相应 改变。

MD5 MD5 是利用 MD5 散列函数计 算报文鉴别 码值 MD5 以 512 位分组来处 理输入的信 息，每 一分组又被划分 为 16 个 32 位子分组， 经过一系列的处 理后，算法 的输出由四 个 32 位分组组 成，最后 级联后生成一 个 128 位散列值

安全 散列 函数（ SHA ） 美国国家 标准 局（ NIST ）为 配合 数字签名 算 法（ DSA ），在 1993 年对外 公布 为安全 散列 函数 ，在 设计 的方 法上也 是依 据 MD4 方法。 SHA 对任 意长 度明文 的预 处理和 MD5 的过程 是一 样的 ，即 预处理 完后 的明文 长度 是 512 位的整数 倍。 SHA 的输出 是 160 位，分 别存储 于 5 个 32 位的 记录 单 元中 。这 5 个记录 单元 的初始 值分 别用 16 进位制 表示 ，如 下所 示。 A=67452301 B=EFCDAB89 C=98BADCFE D=10325476 E=C3D2E1F0

（ 1 ）安全 性 SHA 所产 生的 摘要较 MD5 多了 32 位。若两 种 散列 函数 在结构 上没 有任何 问题 的话， SHA 比 MD5 更安全 。 （ 2 ）速度 两种方法 都是 主要考 虑以 32 位处理 器为 基础的 系统结 构。但 SHA 的运算 步骤较 MD5 多了 16 个步骤 。而且 SHA 记录单元 的长 度较 MD 5 多了 32 位 。因此 若是以 硬件 来实现 SHA ，其速度 大约 较 MD5 慢了 25 ％。 （ 3 ）简易 性 两种 方法 都是相当 的简单， 在实现 上不 需 要很复 杂的 程序或 是大 量的 存储空 间。 然而从 总体 上来讲 ， SH A 对每一 步的操 作描 述较 MD 5 简单。

谢谢