湘教版高中数学选修4-6初等数论初步公匙密码.ppt

公匙密码 公匙密码 1 公匙密码 Public Key 公匙密码也被称为”非对称“密码， 或“双匙”密码 公匙密码体系是近代密码学的产物， 由英国政府通信总局(GCHQ(类似于NSA))的密码学者在20世纪60年代末和民间学者在70年代初分别独立提出 政府开始没有足够重视， 直至民间学者公开研究成果， 最终导致密码学的革命 公匙密码体制比对称匙密码相对少很多 基于特殊的数学结构 对称匙密码则可以有很多新思路 公匙密码 2 公匙密码 Public Key 两个密匙 发送者用接收者的公匙进行加密 接收者用自己的私匙来解密 基于单向陷门函数(trap door, one way function) 从一个方向容易计算 从反方向很难计算 运用“陷门”创建密匙 例如: 给定 p 和 q, 积 N=p*q 很容易计算；但给定积 N, 很难找到因子 p 和 q 公匙密码 3 公匙密码学 加密 假设我们用Bob的公匙对信息M加密 解密 只有通过Bob的私匙才能解密得到信息M Bob还可以使用私匙对信息进行签名 任何人可以通过公匙解密这个信息 只要私匙拥有者能进行签名 如同手工签名 公匙密码 4 背包密码(Knapsack)最早提出的公匙密码体制 公匙密码 5 背包(Knapsack)密码 给定一组n个重量W0,W1,...,Wn-1和一个总重量S,能否找到一组系数ai  {0,1}满足 S = a0W0+a1W1 +...+ an-1Wn-1 (也称其为“子集-和”问题) 实例 重量(62,93,26,52,166,48,91,141) 问题：找到系数满足S=302 答案: 62+26+166+48=302 此处系数为 已证明一般knapsack问题是NP-完全问题(非常难解) 公匙密码 6 背包(Knapsack)问题 一般背包问题(GK)很难解决 但超递增背包问题(super-increasing knapsack) (SIK)很容易解决 SIK要求重量递增排列且每个重量比前面所有重量和还大 实例 重量(2,3,7,14,30,57,120,251) 问题: 找出子集满足和=186 从大到小逐步推算… 答案: 120+57+7+2=186 系数为(1,0,1,0,0,1,1,0) 公匙密码 7 背包密码系统 创建一个超级递增背包(SIK) 将超级背包转换成“普通” 背包(GK) 公匙: 普通背包问题 私匙: 超级递增背包加转换因子 很容易用普通背包(GK)加密 很容易用私匙解密(将密文转换成SIK) 在没有私匙的情况下, 必须解决普通背包问题?(非常困难) 公匙密码 8 背包密码系统实例 假设(2,3,7,14,30,57,120,251)是超级递增背包 选择m = 41、n = 491。这里m, n互素并且n大于背包各元素之和 则普通背包产生方式： 2 * 41 mod 491 = 82 3 * 41 mod 491 = 123 7 * 41 mod 491 = 287 14* 41 mod 491 = 83 30 * 41 mod 491 = 248 57 * 41 mod 491 = 373 120 * 41 mod 491 = 10 251 * 41 mod 491 = 471 普通背包: (82,123,287,83,248,373,10,471) 公匙密码 9 背包密码系统实例 私匙: (2,3,7,14,30,57,120,251) 及12 （m1 mod n 称为m的模逆） m1 mod n = 411 mod 491 = 12 （491+1=492/12=41） 公匙: (82,123,287,83,248,373,10,471), n=491 实例: 加密明文 82 + 83 + 373 + 10 = 548（密文） 解密, (548 · 12)mod491 = 6576%491=193 6576=491*13+193 用私匙(2,3,7,14,30,57,120,251)解193 得到明(2+14+57+120=193) 公匙密码 10 背包密码系统实例分析 如果没有私匙[(2,3,7,14,30,57,120,251),12] 攻击者必须找到公匙(82,123,287,83,248,373,10,471)里的某个子集满足元素之和为491 变成了普通背包问题，非常难解 将超递增背包通过模运算转换为普通背包就是陷门，没有私匙的情况下将很难解密 公匙密码 11 背包密码系统分析 陷门: 通过模运算将超级超递增背包转换为一般递增背包 单向: 一般背包容易用来加密，难解密; 超递增则容易解密 这种背包密码系统是不安全的 在198