PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

格讲莘
5 years ago
Views:

完善保密加密计算复杂性香农 (Claude Elwood Shannon,1916 年 4 月 30 日 -2001

1 完善保密加密计算复杂性香农 (Claude Elwood Shannon,1916 年 4 月 30 日年 2 月 26 日 ), 美国数学家电子工程师和密码学家, 被誉为信息论的创始人裴士辉 QQ:

2 完善保密加密 2

3 离散的随机变量定义一个离散的随机变量, 比方说 X, 由有限集合 X 和定义在 X 上的概率分布组成我们用 Pr[X=x] 表示随机变量 X 取 x 时的概率如果随机变量是固定的, 我们有时缩写成 Pr[x] 对任意的 x X 0 Pr[ x] 1, 并且 x X Pr[ x] 1, 有 Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 3

4 事件的概率假设我们有定义在集合 X 上随机变量 X,E X X 在子集 E 上的取值的概率可由下式计算 : Pr[ x E] Pr[ x] 子集 E 通常称为事件 x E Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 4

5 例假设随机抛一对骰子我们可以用一个随机变量 Z 来刻画这个过程这个随机变量定义在集合 Z {1, 2,3, 4,5,6} {1, 2,3, 4,5,6} 上, 并且对于任意的 (, i j) Z,Pr[( i, j)] 1/ 36 考虑两个骰子的和每一可能的和都定义了一个事件, 给出两个骰子的和为 4 对应的事件表示和对应的概率 Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 5

6 联合概率和条件概率定义假设 X 和 Y 是分别定义在有限集合 X 和 Y 上的随机变量联合概率 Pr[ x, y ] 是 X 取 x 并且 Y 取 y 的概率条件概率 Pr[ x y ] 表示 Y 取 y 时 X 取 x 的概率如果对任意的 x X 和 y Y, 都有 Pr[ x, y] Pr[ x]pr[ y], 则称随机变量 X 和 Y 是统计独立的 Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 6

7 Bayes 定理定理 (Bayes 定理 ) 如果 Pr[ y] 0, 那么 Pr[ x]pr[ y x] Pr[ x y] Pr[ y] Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 7

8 例假设 {,} ab 满足 Pr[ a] 1/ 4,Pr[ b] 3 / 4 设 { K1, K3, K3} 满足 Pr[ K ] 1/ 2, Pr[ K ] Pr[ K ] 1/ 4 设 {1,2,3,4}, 加密函数定义为 e ( a ) 1, e K 1 K 1 ( b) 2, ek 2 ( a) 2, ek 2 ( b) 3, e ( a ) 3, e K 3 K 3 ( b) 4 这个密码体制可以有如下加密矩阵表示 : K K K a b 计算的概率分布 2 计算给定密文后, 明文空间的条件概率分布 8

9 完善保密性定义一个密码体制具有完善保密性, 如果对于任意的 x 和 y, 都有 Pr[ x y] Pr[ x] 也就是说, 给定密文 y, 明文 x 的后验概率等于明文 x 的先验概率 Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 9

10 香农定理定理假定密码体制 (,,,, ) 满足该密码体制是完善保密的, 当且仅当每个密钥被使用的概率是 1/, 并且对于任意的 x 和 y, 存在唯一的密钥 K 使得 ek ( x) y Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 10

11 定义一次一密一次一密密码体制假设 n 1是正整数, ( 2) n 对于 K ( 2) n, 定义 ek ( x ) 为 K 和 x 的模 2 的向量和 ( 或者说是两个比特串的异或 ) 因此, 如果 x ( x1, x2,..., x n ) 并且 K ( K1, K2,..., K n ), 则 ek( x) ( x1 k1, x2 k2,..., xn kn)mod 2 解密和加密是一样的如果 y ( y1, y2,..., y n ), 则 d ( y) ( y k, y k,..., y k )mod K n n 2 Douglas R. Stinson,Cryptography Theory and Practice(Third Edition) 11

12 计算复杂性 12

13 计算复杂性计算复杂性理论 (Computational complexity theory) 是理论计算机科学和数学的一个分支, 它致力于将可计算问题根据它们本身的复杂性进行分类, 同时探讨这些分类之间的关系计算复杂性理论所研究的资源中最常见的是时间和空间对二者的度量分别是时间复杂性和空间复杂性维基百科 13

14 时间复杂性如果一个问题的规模是 n, 解这一问题的某一算法所需要的时间为 T(n), 它是 n 的某一函数 T(n) 称为这一算法的时间复杂性常用大 O 表示法表示时间复杂性维基百科 14

15 算法的时间复杂度 sum=0; 1 for(i=1;i<=n;i++) 2 for(j=1;j<=n;j++) 3 sum++; 4 15

16 算法的时间复杂度 i=1; 1 while (i<=n) i=i*2; 2 16

17 算法的时间复杂度 for(i=0;i<n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) x=x+2; 1 } } 17

18 Name Running time (T(n)) Examples constant time O(1) 10 logarithmic time O(log n) log n, log(n 2 ) fractional power O(n c ) where 0 < c < 1 n 1/2, n 2/3 linear time O(n) n linearithmic time O(n log n) n log n, log n! quadratic time O(n 2 ) n 2 polynomial time 2 O(log n) = poly(n) n, n log n, n 10 sub-exponential time(first) sub-exponential time(second) factorial time O( ) for allε >0 2 o(n) 1 2 n 2 n 3 O(n!) n! 2 log n log log n exponential time 2 poly(n) 2 n, 2 n2 18

19 P(Polynomial) 问题复杂性类可以在多项式时间解决的决定性问题 NP 问题 (nondeterministic polynomial time) 可以在多项式时间验证答案的决定性问题 NP 完全问题 (NP-Complete) 一个决定性问题 C 若是为 NPC, 则代表它对 NP 是完备的, 这表示 : 1. 它是一个 NP 问题, 且 2. 其他属于 NP 的问题都可归约成它 NP-hard 问题一个问题是 NP-hard 问题当且仅当存在一个 NP 完全问题可以归约成它维基百科 19

20 复杂性类维基百科 20

21 第一个 NP 完全问题逻辑电路问题是指的这样一个问题 : 给定一个逻辑电路, 问是否存在一种输入使输出为 True 一个逻辑电路由若干个输入, 一个输出, 若干逻辑门和线组成维基百科 21

22 背包问题背包问题 (Knapsack problem): 给定一组物品, 每种物品都有自己的重量和价格, 在限定的总重量内, 我们如何选择, 才能使得物品的总价格最高维基百科 22

23 1. 形成精确的定义 2. 精确的假设依赖现代密码学的基本准则 3. 严格的安全证明若给定假设 X 是正确的, 根据给定的定义, 构造方案 Y 是安全的 Jonathan Katz and Yehuda Lindell,Introduction to Modern Cryptography 23

24 针对蛮力攻击对称密钥的长度密钥长度安全性评估位短期 : 需要几个小时或几天破解位长期 : 在量子计算出现之前, 需要几十年才能破解 256 位长期 : 即使使用量子计算机运行目前已知的量子算法, 也需要几十年才能破解 Christof Paar,Jan Pelzl. Understanding Cryptography. 24

25 现代公钥密码的基本假设假设如下问题没有多项式时间的破解算法 : 1. 大整数的因式分解问题 2. 离散对数问题 3. 椭圆曲线离散对数问题 25

26 量子计算量子计算思想的提出 Richard Feynman 1982 量子图灵机模型 David Deutsch 1985 Shor 算法 (Peter Shor 1994) 多项式时间分解大数质因子 26

27 对抗量子计算的困难问题 Multivariate Quadratic Polynomials( 多元二次多项式 ) p ( x,, x ) x x x 1 1 n 1, j, k j k 1, j j 1 1 j k n j 1 p ( x,, x ) x x x i 1 n i, j, k j k i, j j i 1 j k n j 1 p ( x,, x ) x x x m 1 n m, j, k j k m, j j m 1 j k n j 1 n n n ir. Bart Preneel,Multivariate Quadratic Polynomials in Public Key Cryptography 27

RSA 图为 RSA 公开密钥算法的发明人, 从左到右 Ron Rivest, Adi Shamir, Leonard Adleman. 照片摄于 1978 年裴士辉 QQ:

RSA 图为 RSA 公开密钥算法的发明人, 从左到右 Ron Rivest, Adi Shamir, Leonard Adleman. 照片摄于 1978 年裴士辉 QQ:168159305 RSA 的数论基础质数 ( 素数 ) (prime number) 一个大于 1 的自然数, 除了 1 和它本身以外不再有其他的因数, 那么这个数为素数 ; 否则称为合数最小的质数是目前为止, 人们未找到一个公式可求出所有质数