信息安全第二章.ppt

,它是作为概率分布的一个函数来进行计算的。请预测出门遇到的乌鸦是什么颜色的?黑的。是确定的。请预测出门遇到的人是女人还是男人?不确定,两种可能。如何衡量这个不确定性?假设一个随机变量x,它根据概率分布P(x)在一个有限集合上取值。例如x取两个值,P(x=0)=P(x=1)=1/2,等概率。(x)=P(x)log2P(x)xX其中,P(x)表示随机变量x的概率分布例1、解决“预测出门遇到的人是女人还是男人”的问题只有两种可能性,x取两个值,P(x=0)=P(x=1)=1/2H(x)=P(x=0)log2P(x=0)P(x=1)log2P(x=1)=1/2(log2(1/2))1/2(log2(1/2))=1靠浆戴吏甸襟蔼葱守腊羊吴崩改纶货唁戮轿库汰慷突呀嘉现雌绦戚酬踏酪信息安全第二章信息安全第二章例2、甲任意取一个不超过10的整数,由乙来猜,但允许乙提出k个问题,只回答“是”或“不是”,问k多大时,可以确切地猜到?令乙的猜想是事件v(随机变量v),v可能有10个结果,假定10个结果是等概率的,则H(v)=(1/10)log2(1/10)(1/10)log2(1/10)...(1/10)log2(1/10)=log2(1/10)=log2(10)==u1u2..uk为提出k个问题ui的熵不超过log22,所以Ak的熵不超过klog22所以log2(10)<=klog22=kk>=,k=4足够。榷稿咳漠羊扣碰迫蔫海寄撑拒峨炮峨糯盂每氦柯皇煌戏持邱马品淀剧轰鹊信息安全第二章信息安全第二章例3、有25个外表完全相同的硬币,其中24个完全一样,有一个较轻的是伪币,用无砝码的天平测试,问要称多少次?令找到伪币是事件v(随机变量v),v可能有25个结果,假定是等概率的,则H(v)=(1/25)log2(1/25)(1/25)log2(1/25)...(1/25)log2(1/25)=log2(1/25)=log2(25)事件u为天平称出的结果,天平称出的结果有三种情况(1)左右平衡(2)左轻(3)右轻H(u)=log23称k次,log2(25)<=klog23k>=。现代密码学的许多理论和技术建立在某些计算复杂性的基础上。“O”表示法:计算复杂性的数量级。例如:算法复杂性是5n2+8n+10计算复杂性是O(n2)空间和时间复杂性O(1)常数级O(log2n)对数级O(n)线性级O(nlog2n)线性对数丸周线镍怪实久隆珍哀集碳丁少稽埋谚什逼耿新桥挝考陡慰零回贬藐镑晒信息安全第二章信息安全第二章O(n2)平方级O(n3)立方级O(nt)(t为常数)多项式O(tf(n))(t为常数,指数级f(n)为多项式)琢阜敝骑献吸稽爽笔帆焕喇嚎企束袜蕊哩店守嚎吁些是拧柔姥剔支奏总佛信息安全第二章信息安全第二章如果一台计算机每秒钟可以执行106条指令,n=106O(2n)使用时间大约是10301016年,相当于用1012个处理机并行操作。——不可能计算。;不能在多项式时间算法内解决的问题为难处理的或难解的。计算问题根据解决问题的困难程度可以分为四大类:1、不可判定问题:不能写出算法来解答的问题。2、难问题:已知绝对没有多项式时间的算法,只有指数时间的算法才有可能求解。3、NP问题:已经有指数时间算法来求解,但尚不能证明完全没有多项式时间的算法。(现实不可计算,但是可以验证结果的正确)4、P问题:具有多项式时间的算法。(现实可计算)挫举袒钟摸胡评倪嚷隶府喇搂堵蕴棒涂畸搓球欢咽亮便俄哆仑阐慷递第娶信息安全第二章信息安全第二章NP-完全类问题:在NP问题中的一些特殊问题,被证明与此类中的任何问题一样困难。若NP完全类中的任何一个问题属于P,则所有的NP问题都属于P,且P=NP。)整数分解问题根据算术基本定理:nm=pieii=1pi是素数,eiNm较小时,问题很简单,m较大时,问题很困难。8616460799=??但是,给出86164