高中数学选修5-3(密码学算法基础)选修课密码学.ppt

公钥密码体制 背包公钥密码体制 背包体制构造公钥体制的原理 主要内容 一 背包体制 下面以背包问题为例来介绍如何构造公钥密码体制 背包问题 给定一堆物品 重量各不相同 能否将这些物品放入一个背包中 使之等于一个给定的重量 例 这些物品的重量分别为 1 5 6 11 14 20 问能否组成重量分别为22和24的背包 直观上 c表示背包的大小 每个数字ai表示能装到该背包中的物品的大小 问题是选择一些物品 使得它们正好填满这个背包 其中xi为1表示物品在背包中 xi为0表示物品不在背包中 1 背包问题的数学描述给定n个正整数的集合A a1 a2 an 及正整数c 求0 1向量x x1 x2 xn 使得 其中a a1 a2 an 称为背包向量 原则上 只要搜索集合A a1 a2 an 的所有子集并检验其元素之和是否为c 则总可以决定此背包问题是否有解 若有解就一定能够找到 但注意到A的子集个数为 背包问题是NP完全问题 单向函数 由集合A和0 1向量x很容易求得c 但由集合A和c却很难求得0 1向量x 1 背包问题的数学描述 背包密码算法的思想是将消息编码为背包问题的解 明文分组长度等于堆中物品个数 且明文位与0 1向量x相对应 密文是计算得到的和值 例 设背包向量为 A 1 5 6 11 14 20 明文 111001010110100101 密文 1 5 6 205 11 141 11 20 32 30 32 解密时 合法接收者也必须解背包问题 且不同明文有可能加密成同一密文 这不符合公钥密码体制的要求 1 背包问题的数学描述 定义 若对均有则称向量A a1 a2 an 为超递增背包向量 相应的背包问题称为超递增背包问题 2 利用超递增背包构造公钥密码体制 超递增背包问题是易解的 超递增背包中的每一项都大于它之前所有项之和 给定超递增背包向量A a1 a2 an 对任意n比特明文m x1 x2 xn 由a得到密文任何用户收到c后 都可容易地求得m 首先比较c和an 若 则an不在该背包中xn 0 若 则an必在该背包中xn 1 因为所有其它分量的和a1 a2 an 1 an 记c c an 对c 和an 1重复上述过程 当到达a1时 整个过程结束 若变为0 则有唯一解m 否则无解 例 背包A 2 3 6 13 27 52 c 70 该背包的解为 110101 2 利用超递增背包构造公钥密码体制 一般的背包问题是困难问题 而超递增背包问题是易解的 Merkle Hellman公钥密码算法就利用这一性质 保密密钥是一个超递增背包向量A 公开密钥是A经过 置乱 后的一般背包向量 Merkle Hellman公钥密码算法 1 选取一个超递增背包A a1 a2 an 和模M使M a1 a2 an 2 取w使 w M 1 并求满足ww 1modM 1的w 1 3 构造背包向量b b1 b2 bn 且bi waimodM 4 公开密钥 b b1 b2 bn 保密密钥 A a1 a2 an M和w 2 利用超递增背包构造公钥密码体制 5 加密设明文m m1 m2 mn mi 0 1 6 脱密 收到密文c后 计算 s w 1cmodM m1a1 m2a2 mnan 收方由s利用A的超递增特性可求出明文m 由于w是保密的 非法用户不能由c还原m 密文c m1b1 m2b2 mnbn 2 利用超递增背包构造公钥密码体制 例 设M 89 A 2 6 9 19 41 取w 13求w 1 b 对明文m 10101 加密并脱密 解 由Euclid算法可求出w 1 48mod89 则b 26 78 28 69 88 加密 c 26 28 88 142 脱密 计算s cw 1mod89 52 52 41则m5 152 41 119则m3 111 9 2 6则m2 02 2则m1 1 2 利用超递增背包构造公钥密码体制 1 选取一个困难问题P 2 选择困难问题P一个容易子问题PEasy 它应该是多项式时间问题 最好是线性时间问题 3 置乱 问题PEasy使所得问题PS是困难问题 4 公开PS 并描述如何将它用作一个加密变换 将Ps逆回到PEasy的信息作为秘密陷门 5 构造密码系统的细节 使得解密对密码分析者 不得不解PS 和合法接收者 可使用秘密陷门来解PEasy 有本质区别 二 构造公钥密码体制的一般步骤 三 现在流行的公钥密码体制 1 基于大整数因子分解问题 其中最典型的代表是RSA公钥密码 2 基于有限域上离散对数问题 如ElGamal公钥密码 此外 还有Rabin公钥算法 McEliece公钥算法和LUC公钥算法等等 3 基于椭圆曲线群上的离散对数问题 如椭圆曲线公钥密码 一 数学背景介绍公钥密码学中用到的基本数学知识 包括初等数论 有限域 计算复杂性 二 RSA公钥密码介绍RSA算法及其安全性 素性检测 因子分解算法和RSA的实现 三 ElGamal公钥密码讲述ElGamal算法及其安全性分析和实现 离散对数问题的求解 四 本课程概要 五 椭圆曲线公钥密码主要介绍椭圆曲线上的基本运算 椭圆曲线公钥密码算法及其实现 七 公钥密码学的应用介绍公钥基础设施 PKI 六 背包加密算法和其他公钥密码介绍两种背包加密算法并给出其破译算法 Diffie Hellman协议 Rabin公钥算法 McEliece公钥算法和LUC公钥