《信息系统安全.chapter03》由会员分享，可在线阅读，更多相关《信息系统安全.chapter03（43页珍藏版）》请在金锄头文库上搜索。
1、信 息 系 统 安 全第三讲 公钥密码张焕国武汉大学计算机学院目 录1、信息系统安全的基本概念 2、密码学(1) 3、密码学(2) 4、操作系统安全(1) 5、操作系统安全(2) 6、数据库安全(1) 7、数据库安全(2) 8、可信计算(1) 9、可信计算(2)一、公开密钥密码的概念1、传统密码的缺点：密钥分配困难；网络密钥量大 ：(1/2)n(n-1)不易实现数字签名。 2、公钥密码的基本思想：把密钥一分为二：Ke为加密钥，Kd为解密钥；由Ke在计算上不能推出Kd;将Ke公开，也不损害Kd的安全，于是可将其公开。北京武汉K KK K3、公钥密码的理论模型： 定义： 设y=f(X),如果已知x
2、求y容易，而已知y 求x很难，则称f(X),为单向函数。进一步，若已 知某陷门信息，从y求x容易，不知陷门信息， 则从y求x很难，则称f(X)为单向陷门函数。 公钥密码的理论模型是单向陷门函数. 理论上尚不能证明单向函数一定存在。4、工程上认为单向性足够即可： 大合数的因子分解问题； 离散对数问题。一、公开密钥密码的概念一、公开密钥密码的概念5、公钥密码的基本条件：设E为解密算法，D为解密算法，Ke为公开加密钥，Kd 为保密的解密钥： 可逆性： D（E（M， Ke ）， Kd ）M ； 基本条 件如果满足 ，则可确保秘密性； 由公开的Ke 在计算上不能计算出保密的Kd ； 安全条 件 E和D都
3、高效； 实用条 件 满足以上3个条件，可构成一个公钥密码体制(可保密)。 如果E （ D （M， Kd ）， Ke ）M，则可确保真实性； 如果D（E（M， Ke ）， Kd ） E (D(M， Kd )，Ke)M，则 可同时确秘密性和保真实性；一、公开密钥密码的概念一、公开密钥密码的概念6、算法复杂性理论： 问题：计算机求解的对象； 问题的规模：求解问题所需输入的二进制位数n。 算法复杂度：a. 用一个算法求解一个规模为n的问题，若对任意的n和所有长为n 的输入，最多需f(n)步可将问题求解，则称算法复杂度为f(n) 。b.算法复杂度分为时间复杂度和空间复杂度，通常考虑时间复杂 度。C.显然
4、：算法复杂度是求解某问题的最难特例所需的计算时间；问题复杂度是求解该问题的最佳算法的算法复杂度。d.算法复杂度强调f(n)随n的变化速度。e.算法复杂度f(n)=O(g(n)的充要条件是，存在一个常数c和n0使当 n0n 时， f(n)c g(n)。例： f(n)=17n+10，因为当n10时，就有17n+1018n ，选c=18,g(n)=n ,n0=10,就得到f(n)O（n）. 一、公开密钥密码的概念一、公开密钥密码的概念算法复杂度：f、典型的复杂度：多项式复杂度：常数复杂度O（1）线性复杂度O（n）平方复杂度O（n2）O（n的多项式）指数复杂度：O（cn），c为常数 阶乘复杂度：O（n
5、!） 复杂度增大复杂度增大一、公开密钥密码的概念一、公开密钥密码的概念问题复杂度分类a.P类问题：在确定型图灵机上，用多项式时间可求解 的问题类。通俗地说： P类问题是计算机易处理的。b、NP类问题：在非确定型图灵机上，用多项式时间可 求解的问题类。通俗地说： NP类问题是计算机难处理的。C、NPC问题：NP类问题中最难的问题子类。 利用NPC问题可以构造单向陷门函数。背包问题是NPC问题，但背包密码却是可破的。一、公开密钥密码的概念一、公开密钥密码的概念二、公钥密码的基本工作方式1、管理与组织 要有一个管理机构：对用户是可信赖的；制定政策； 统一技术；用户注册；密钥产生；公钥库管理； 每个用
6、户两个密钥：公开的加密钥Ke，保密的解密钥 Kd； 建立共享的公开钥数据库 PKDB:用户ID 公开钥 A KeA B KeB2、确保数据秘密性A B 通信协议：A方 B方 A查PKDB，查到B的KeB; 接收密文C；加密：CE（M， KeB ）； 用自己的KdB解密： 发C 给B； MD（C， KdB ） 安全分析： 因为只有B才有KdB，而且由KeB推不出KdB ，所以只有B才能解密得 到明文M，所以可确保数据的秘密性； 因为任何人都可查到B的KeB，故任何人冒充A发假消息，不能确保 数据真实性。M二、公钥密码的基本工作方式3、确保数据真实性A B通信协议：A方 B方 用自己的KdA解密：
7、 接收密文S；SD（M， KdA ） 查PKDB，查到B的KeA; 发S 给B ； 加密：ME（S， KeA ） 安全分析： 因为只有A才有KdA，而且由KeA推不出KdA ，只有A才能产生S，任何人 不能冒充，所以可确保数据的真实性； 因为任何人都可查到A的KeA，故任何人都可获得明文，所以不能确 保数据秘密性。M二、公钥密码的基本工作方式4、同时确保确保数据真实性A B 通信协议：A方 B方 用自己的KdA解密： 接收密文C；SD（M， KdA ） 用自己的KdB解密： 查PKDB，查到B的KeB; SD（C， KdB） 加密： CE（S， KeB） 查PKDB，查到A的KeA 发C给B
8、； 加密：ME（S， KeA ） 安全分析：因为综合了前两个协议，只有A才能产生S，只有B才能得到M ，所以可同时确保数据的秘密性和真实性；M二、公钥密码的基本工作方式三、计算困难问题及相应密码1、大合数的因子分解小合数的因子分解是容易的，然 而大合数的因子分解却是十分困难的 。关于大合数的因子分解的时间复杂 度下限目前尚没有一般的结果，迄今 为止的各种因子分解算法提示人们这 一时间下限将不低于 O(EXP(lnNlnlnN)1/2)。根据这一结论， 只要合数足够大，进行因子分解是相 当困难的。1、大合数的因子分解l2005年人们利用数域筛法分解了一个十进制 200位的大合数(665位的RSA
9、) 。这是目前世 界大合数因子分解的世界纪录。l为了RSA密码的安全，目前建议：对于一般 应用可选1024位的大合数，对于重要应用应 选2048位的大合数。如国际可信计算组织 TCG的标准：根密钥2048位，加密和认证密 钥1024位。l基于大合数因子分解困难性，构建了RSA密 码类。 三、计算困难问题及相应密码2、有限域上的离散对数问题l设p为素数，为模p的本原元。 以为底的模p的指数运算为YX mod p，1Xp-1 。 以为底的模p的对数运算为 XlogY mod p ，1Xp-1 。从X计算Y是容易的，至多需要2log2p次乘法运算。可 是从Y计算X就困难得多，利用目前最好的算法，对于
10、 小心选择的p将至少需用p 1/2次以上的运算，只要p足够 大，求解离散对数问题是相当困难的。 基于离散对数问题可构造公开密钥密码；a) ELGamal密码；b) Diffie和Hellman的密钥分配协议；三、计算困难问题及相应密码3、 椭圆曲线离散对数问题 设p是大于3的素数，且4a3+27b2 0 mod p ，称曲线y2 =x3 +ax+b ，a,bGF(p) 为GF（p）上的椭圆曲线。 称曲线y2+xy=x3 +ax+b， a,bGF(2m) 为GF（2m）上的椭圆曲线。 椭圆曲线的解为一个二元组，将此二元组描画到 椭圆曲线上便为一个点，于是又称其为解点。三、计算困难问题及相应密码3
11、、椭圆曲线离散对数问题 椭圆曲线的全体解点，再加上一个无穷远点O ，构成加法交换群。 设E为椭圆曲线的解点群，G是E中的n阶元素， n为素数，则集合E1=0,G,2 G,3 G,( n 1) G。是E的循环子群，并称是由G生成的群。 设d1，n，若已知n和G，计算P=nG是容易 的，但已知P和G求n ，是求解椭圆曲线上的离 散对数问题，这是困难的。 基于椭圆曲线上的离散对数问题可构建公钥密 码，称为椭圆曲线密码。三、计算困难问题及相应密码4、椭圆曲线密码简评 椭圆曲线密码、RSA、EIGamal密码是目前最实 用的公钥密码。 椭圆曲线密码的安全在于：ECDLP尚没有亚指 数算法。因子分解和FP
12、DLP有亚指数算法。 普遍认为，160位长的椭圆曲线密码的安全性 相当于1024位的RSA密码。这是因为椭圆曲线 密码的基本运算比RSA密码的基本运算复杂的 多。 在硬件实现中电路的规模小，省电。因此椭圆 曲线密码特别适于在航空、航天、卫星及智能 卡中应用。三、计算困难问题及相应密码一、密钥协商l利用密码的首要问题是使收发双方共享密钥，称为密 钥分配或密钥协商。lDiffie-Hellman密钥协商协议是基于离散对数问题复杂 性的密钥分配协议。 系统选用一个大素数p和GF（p）的一个本原元。 用户A产生一个随机数x，2xp-2，计算MA=x mod p ，并把MA传给用户B。 用户B也产生一个
13、随机数y，2yp-2，计算MB=y mod p ，并把MB传给用户A。 A计算KA（MB）x mod p yx mod p，B计算KB （MA）y mod p yx mod p，显然KAKB。取Ks KAKB ，于是用户A和用户B共享了会话密钥Ks 。四、公钥密码的应用二、数字签名l数字签名就是数字形式的签名。 1、签名技术的基本特性：签名者事后不能抵赖；其他人不能伪造签名；签名容易公开验证。 l传统的以书面文件为基础的事务处理中采用书面签名；如手签、手印、印章等。l近代的以计算机文件为基础的事务处理中采用数字签名 ；l中国、美国、俄罗斯等国都颁布了自己的数字签名标准 。l我国、法国和其他一些国家地区颁布了数字签名法。 四、公钥密码的应用2、数字签名主要研究解决以下问题： A如何在数据M上签名？ B如何验证A的签名的真伪？ A如何鉴别人伪造自己的签名？- B如何阻止A签名后又抵赖？ 3、数字签名系统的构成 一个数字签名系统要包括两个方面的处理： 施加签名设施加签名的算法为SIG，产生签名的密钥为K ，被签名的数据为M，产生的签名信息为S，则 有 SIG (M，K)S 。 四、公钥密码的应用验证签名设验证签名的算法为VER ，用VER 对签名S进 行验证，可鉴别S的真假。真，当SSIG (M，K)；假，当
