下载文档原格式
1绪论《现代密码学》第一讲课程信息课程名称：现代密码学(必修课，考试) 共16周任课教师：杨义先郑世慧时间/地点：周二上午10:10 -12:00 教3楼417学生：2008211317 2008211318 2008211319 2008211320考核方式：平时+期中考试30%-40%期末考试60%-70%作业：前一周作业，下一周上课前交齐作业题目、作业提交及相关课程信息见“网络教学””精品课程“网站/buxdmmx请先注册，然后进行相关操作参考书目⏹现代密码学教程，谷利泽等，北邮出版社，2009⏹现代密码学基础，章照止，北邮出版社，2004⏹现代密码学，杨波，清华大学出版社，2004参考书目⏹密码学原理与实践,(加)Douglas R.Stinson著，冯登国译，电子工业出版社, 2003.⏹密码编码学与网络安全——原理与实践,(美) Stallings,W.著，孟庆树等译,电子工业出版社,2006.⏹应用密码学－协议、算法与C源程序，Burce等，机械工业出版社，2002.⏹现代密码学理论与实践，Wenbo Mao著，王继林译，电子工业出版社，2004.⏹应用密码学手册, Alfred Menezes著，胡磊译，电子工业出版社，2005⏹密码学基础，O.Goldreich著，杨义先等译，人民邮电出版社，2003.⏹高级加密标准（AES)算法—Rijndael的设计，John Daemen,Vincent Rijndael著；谷大武等译，清华大学出版社，2003.注意事项⏹《现代密码学》是信息安全专业重要的专业基础课，理论性强，难度大，请大家用功学习。
⏹北邮《现代密码学》是国家级精品课程，希望师生共同努力，将该门课程建设得更好！⏹欢迎学有余力的同学参与信息安全中心的相关课题研究！本讲主要内容⏹密码学的目的⏹密码学的历史⏹现代密码学的分类⏹《现代密码学》课程讲授主要内容密码学的目的中国古代的保密例1：汉代泥封古时的官、私文书和书信往来大都写在竹简或木牍上，这些简牍书信，在传递过程中需要保密就得封缄起来。
1
复杂性理论
《现代密码学》第三讲
上讲内容回顾
Shannon通信保密系统 熵和无条件保密
分组密码的设计思想
本章主要内容
问题的定义及分类
算法复杂度定义及分类 P问题和NP问题
规约思想与NPC类
密码算法的计算安全性
1 设A=(a 1,a 2,…,a n )是由n 个不同的正整数构成的n 元组，S 是另一已知的正整数. A 称为背包向量，S 称为背包容积. 求A
中元素集合A’，使.2 设背包向量A=(1,2,5,10,20,50,100), 背包容积为177，求向量，使得.'i
i a A a S ∈=∑7{0,1}X ∈71
177i i i x a ==∑
3 已知整数N，问N是否是一个素数？
4 试问77是否是素数？
5 试问79是否是素数？
6 已知整数N，求N的素分解式.
7 已知整数177，求其素分解式.
问题：描述参量陈述解答应当满足的性质（称为询问）.
参量为具体数值时，称为问题的一个实例. 判定问题：回答只有Yes或No.
计算问题：从其可行解集合中搜索出最优解.
7
算法复杂度的定义
例设x 是小于100的某个整数，问x 是否是素数？
解答一：取2～的所有整数，依次试除x ，若存在某个整数可以整除x ，则程序停止，输出x 为合数，否则输出x 为素数.
最坏试除次数：存储空间：0
解答二：预先将所有小于100的素数存储在寄存器中；然后将X 与存储器中的元素比较，若存在某个素数等于x ，则程序停止，输出x 为素数，否则输出x 为合数.
最坏比较次数: 100/ln 100, 存储空间: 100/ln 100
x ⎢⎥⎣⎦x ⎢⎥⎣⎦
8
算法复杂度的定义
时间（计算）复杂性：考虑算法的主要操作步骤，计算执行中所需的总操作次数. 空间复杂性：执行过程中所需存储器的单元数目.
数据复杂性：信息资源.
计算模型----确定性图灵机（有限带符号集合，有限状态集，转换函数）（读写头，读写带）.
算法复杂度的定义
不同的编程语言，不同的编译器导致执行一次操作的时间各不相同，为了方便不同算法比较，通常假定所有计算机执行相同的一次基本操作所需时间相同，而把算法中基本操作执行的最大次数作为执行时间.
基本操作数量
运行时间=
机器速度
10算法复杂度的定义
定义
假设一个算法的计算复杂度为O(n t )，其
中t 为常数，n 为输入问题的长度，则称这算法的复杂度是多项式的。
具有多项式时间复杂度的算法为多项式时间算法.
函数g(n )=O(n t )表示存在常数c>0和n 0>=0，对一切n > n 0均有|g(n )|<=c|n t | 成立，也就是说，当n 足够大时，g(n )存在上界.定义非多项式时间算法：算法的计算复杂性写不成O(P(n ))形式，其中P(n )表示n 的多项式函数.
算法复杂度的定义
例设x是小于100的某个整数，问x是否是素数？
解法1是否是多项式时间算法？
解法2是否是多项式时间算法？
12
P问题和NP问题
定义(P 问题)如果一个判定问题存在解它的多项式时间的算法，则称该问题属于P 类. 定义(NP 问题) 如果一个判定问题不存在解它的多项式时间的算法，且对于一个解答可以在多项式时间验证其是否正确，则称该问题属于NP 类.
公开问题：P ≠NP ？
它是Clay 研究所的七个百万美元大奖问题之一
二次函数、三次函数、2x函数的示意图
例. 设问题输入长度为n，在一个每秒钟运行百万次
的计算机上的运行时间如下:
10305060
T(n)=n20.0001s0.0009s0.0025s0.0036s
T(n)=2n0.001s17.9月35.7年366世纪
14
当问题输入长度足够大，分析密码体制的算法的复杂度较大，可能的计算能力下，在保密的期间内可以保证算法不被攻破，这就是密码体制的计算安全性思想。
注：分析方法是无穷无尽的，类似于解决问题的算法，目前不存在非多项式时间的分析方法，将来可能存在，即算法将来可能不堪一击. 如差分分析出现。
16
密码系统设计：
合法用户——易（多项式）攻击者——难（非多项式）注：计算模型----图灵机
量子计算机出现导致分解因子问题容易，从而RSA 等密码系统不再安全，缘由是计算模型不同.非多项式时间问题多项式问题
17
定义判定问题，. 若存在的解法
S1，那么通过调用S1（作为子程序），可以在多项式时间内解问题，则称可多项式规约至“∝”
定义若判定问题∈NP ，对每个判定问题∈NP ，都有∝，则称属于NPC 类，或称为NP 完全的.
1π2π
1π2π1
π2π2π1πππ′π′π′π
主要知识点小结
算法的复杂度定义及分类 密码算法的计算复杂度
20作业
1 求冒泡排序法的计算复杂度, 该算法是否为多项式的？
2 超递增背包问题：
设A=(a
1,a 2,…,a n )是由n 个不同的正整数构
成的n 元组，且，S 是另一已知的正整数。
求A 的子集A’，使.
(1) 给出该问题的求解算法；(2) 求算法的计算复杂度.
11
2,,j j i i a a j n
−=>=∑L
'
i i a A a S ∈=∑
21THE END
！。
