信息安全导论(4-3密码基础-非对称密码).ppt

1,密码基础非对称密码,又称 公钥密码,信息安全导论（模块4密码基础）,2,对称密码体制使用中存在的问题,密钥分配问题：通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现 密钥管理问题：在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目非常大n(n-1)/2,3,对称加密示意图,注意,注意,4,公钥密码体制,1976年，W.Diffie和M.E.Hellman发表了“密码学的新方向”一文，提出了公钥密码学（Public-key cryptography）的思想，在公钥密码体制（Public-key cryptosystem）中加密密钥和解密密钥是不同的，加密密钥可以公开传播而不会危及密码体制的安全性。 通信的一方利用某种数学方法可以产生一个密钥对，一个称为公钥（Public-key)，另外一个称为私钥（Private-key)。该密钥对中的公钥与私钥是不同的，但又是相互对应的，并且由公钥不能推导出对应的私钥。选择某种算法（可以公开）能做到：用公钥加密的数据只有使用与该公钥配对的私钥才能解密。,5,公钥密码体制,公钥密码体制（非对称）包括两个密钥: 公钥：可以被任何人知道，用于加密 私钥：只有消息的接收者知道，用于解密 加密者或其他人不能解密 从公钥无法导出私钥 是密码学几千年历史中最有意义的结果,6,公钥密码的特点 由私钥及其他密码信息容易计算出公开密钥 由公钥及算法描述，计算私钥是困难的 因此，公钥可以发布给其他人,7,注意,注意,非对称加密示意图,8,公钥密码的核心是使用一种特殊的函数单项陷门函数，从一个方向求值是容易的，但逆向计算很困难 定义：设f是一个函数，如果对于任意给定的x，计算y，使得y=f(x)是容易计算的，但对于任意给定的y，计算x是难解的，即求f的逆函数是难解的，则称f是一个单向函数,9,定义：设f是一个函数，t是与f有关的一个参数。对于任意给定的x，计算y，使得y=f(x)是容易的。 如果当不知道参数t时，计算f的逆函数是难解的 但当知道参数t时，计算f的逆函数是容易的 则称f是一个单向陷门函数，参数t称为陷门,10,公钥密码中，加密函数就是一个单向陷门函数，只有解密者知道陷门，可以容易地进行解密，而不知道陷门的人则无法有效解密,11,典型的公钥密码算法1：背包算法,背包系统是1978年Merkle和Hellman基于求解背包问题的难解性提出的一个公钥密码系统 背包问题：,12,13,14,例,15,16,加解密运算：,17,18,例,19,20,发送方（加密）,21,接收方（解密）,22,典型的公钥密码算法2：RSA,RSA是Rivest、Shamire和Adleman于1978年在美国麻省理工学院研制的 其安全性建立在“大数分解和素性检测”这一数论难题基础上 将两个大素数相乘是容易计算的 将该乘积分解成两个大素数因子是困难的（计算上不可行）,23,1. 密钥的产生 选两个互异的大素数p和q。 计算n=pq，(n)=(p-1)(q-1)，其中(n)是n的欧拉函数值。 选一整数e，满足1e(n)，且gcd(n),e)=1。 计算d，满足de1 mod (n)，即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。 以e,n为公开钥,d,p,q为秘密钥。,RSA算法,24,2. 加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文m，作加密运算： cme mod n,RSA算法,25,3. 解密 对密文分组的解密运算为：mcd mod n 证明RSA算法中解密过程的正确性. 证明过程用到数论中的知识 cd mod n med mod n m,RSA算法,26,例： 选p=7，q=17. 求得n=pq=119，(n)=(p-1)(q-1)=96. 取e=5，满足1e(n)，且gcd(n),e)=1， 计算满足de=1 mod 96且小于96的d. 因为775=385=496+1，所以d为77， 因此公开钥为5，119，秘密钥为77，7，17. 设明文m=19，则由加密过程得密文为 c195 mod 1192476099 mod 11966; 解密过程为 m 6677mod 11919.,RSA算法,27,1. RSA的加密与解密过程 RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质： (ab) mod n=(a mod n)(b mod n) mod n 就可减小中间结果。,RSA中的计算问题,28,2. 模指数运算的快速算法 例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。 求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bk bk-1b0，即 m=bk2k+bk-12k-1+b12+b0 因此,RSA中的计算问题,29,例：求a19 19=124+023+022+121+120 所以 a19=(a1)2a0)2a0)2a1)2a1,RSA中的计算问题,30,3、乘法逆元的求法（欧几里德算法） 整数e，满足1e(n)，且gcd(n),e)=1 计算d，满足de1 mod (n)，即d是e在模(n)下的乘法逆元，因e与(n)互素，它的乘法逆元一定存在,RSA中的计算问题,31,RSA中的计算问题,32,RSA中的计算问题,33,RSA中的计算问题,34,前例,则196519=5*(-19)=5*77 mod96,5771 mod96,则5的乘法逆元在 mod96下为77,35,例,36,37,验证：171728939611 mod96,38,RSA的安全性是基于分解大整数困难的假定 如果RSA的模数n被成功地分解为pq，则获得(n)=(p-1)(q-1)，从而攻击者能够从公钥e解出d，即de-1 mod (n)，攻击成功.,RSA算法的安全性,39,随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解. 例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解.,RSA算法的安全性,40,商用安全要求 n的长度在10242048比特 p和q的长度相差不能太多 p-1和q-1都应该包含大的素数因子 p-1和q-1的最大公因子要尽可能小,41,典型的公钥密码算法3：ElGamal算法,ElGamal公钥密码体制是由T.ElGamal于1985年提出的 可用于数据加密，也可用于数字签名 安全性依赖于有限域上计算离散对数的难题,42,ElGamal算法,43,特点,44,安全性分析,其安全性是建立在有限域上求离散对数难解问题的基础上 有限域上的离散对数问题：,45,46,ElGamal中参数选择的安全性要求,素数p至少应为150位以上的十进制数 p-1至少应该有一个大的素数因子,47,公钥密码的特点,计算量大，运算速度慢 主要用于密钥协商 数据加密主要用对称密码,48,对称密码算法，加/解密速度快，但密钥分发问题严重 非对称密码算法，加/解密速度较慢，但密钥分发问题易于解决 为解决每次传送更换密钥的问题，结合对称加密技术和非对称密钥加密技术的优点，产生了电子信封技术，用来传输数据,49,加密技术的使用,50,小结,典型的非对称密码（RSA） 对称密码，非对称密码 各自特点 如何用,51,作业,背包算法的练习（n8） 两位同学一组，班内序号(1,2), (3,4), 班内序号为奇数的同学：每人设计一个背包公钥密码系统，给出公开钥，保留秘密钥 班内序号为偶数的同学：每人用你同伴的公开钥加密一个明文信息，将密文交给该同学，由该同学解密 每组同学提交一个算法报告（算法的设计过程、公开钥、秘密钥、明文、密文、加解密运算过程等）,52,作业,RSA算法的练习（选择两个大于30的素数p,q） 两位同学一组，班内序号(1,2)