现现代密码学8讲RSA课件

1、第四章 公钥密码4.1 数论简介4.2 公钥密码体制的基本概念4.3 RSA算法4.4 背包密码体制4.5 Rabin密码体制4.6 NTRU公钥密码系统4.7 椭圆曲线密码体制4.8 基于身份的密码体制2022/9/251第四章 公钥密码4.1 数论简介2022/9/2414.2 公钥密码体制的基本概念Basic Concept of Public Key Cryptography2022/9/2524.2 公钥密码体制的基本概念Basic Concept o公钥密码体制的原理公钥体制(Public key system) (Diffie和Hellman,1976) 每个用户都有一对选定的密

2、钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。解决了单钥密码体制中最难解决的两个问题：数字签字、密钥分配2022/9/253公钥密码体制的原理公钥体制(Public key syste公钥体制加密 公钥体制加、解密 m=D (c)=DSKB (EPKB(m)安全保障从公开钥PKB和密文c要推出明文m或解密钥SKB在计算上是不可行的。由于任一用户都可用用户B的公开钥PKB 向他

3、发送机密消息，因而密文c不具有认证性。发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmmSKB2022/9/254公钥体制加密 公钥体制加、解密 m=D (c)公钥密码认证体制 用户A以自己的秘密钥SkA对消息m进行A的专用变换DSKA，A计算密文：c=DSKA(m)送给用户B，B验证c： m=EPKA（c）=EPKA(DSKA(m)安全性： 由于SkA 是保密的，其他人都不可能伪造密文c，可用A的 公开钥解密时得到有意义的消息m。因此可以验证消息m来自A而不是其他人，而实现了对A所发消息的认证。发送者A加密算法SKA密钥源PKA解密算法接收者B密码分析员mcmSKA2022

4、/9/255公钥密码认证体制 用户A以自己的秘密钥SkA对消息m公钥保密和认证体制公开保密公开保密保密认证为了同时提供认证功能和保密性，可使用双重加、解密加密c=EPKBESKAm解密m=DPKADSKBc2022/9/256公钥保密和认证体制公开保密公开保密保密认证为了同时提供认证功公钥密码应满足的要求接收方B产生密钥对在计算上是容易的发送方A用收方的公开钥对消息m加密以产生密文c在计算上是容易的。收方B用自己的秘密钥对密文c解密在计算上是容易的。敌手由密文c和B的公开密钥恢复明文在计算上是不可行的。敌手由密文c和B的公开密钥恢复秘密密钥在计算上是不可行的加解密次序可换，即EPKBDSKB(

5、m)=DSKBEPKB(m) ,不是对任何算法都做此要求。以上要求本质就是找出合适的单向陷门函数2022/9/257公钥密码应满足的要求接收方B产生密钥对在计算上是容易的以上要单向函数一个可逆函数f：AB，若它满足： 1o 对所有xA，易于计算f(x)。 2o 对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即若输入长度为n，计算函数的时间是na的倍数，a为一固定的常数。若计算函数时间是an的倍数，则为不可能做到的。算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量

6、的2022/9/258单向函数一个可逆函数f：AB，若它满足：算法的复杂度是以算陷门单向函数单向函数是求逆困难的函数，而单向陷门函数(Trapdoor one-way function)，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。陷门单向函数是一族可逆函数fk，满足Y=fk(X)易于计算（当k和X已知）Xf-1k(Y)易于计算（当k和Y已知）Xf-1k(Y)计算上不可行（Y已知但k未知）2022/9/259陷门单向函数单向函数是求逆困难的函数，而单向陷门函数(Tra4.3 RSA算法RSA Algorithm2022/9/25104.3 RSA算法RSA Algor

7、ithm2022/9/概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman等1978, 1979发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。2022/9/2511概况MIT三位年青数学家R.L.Rivest，A.Shami算法描述密钥产生独立地选取两大素数p和q(各100200位十进制数字)计算 n=pq，其欧拉函数值(n)=(p1)(q1) 随机选一整数e，1e(n)，gcd(n), e)=1在模(n)下，计算e的有逆元d=e -1 mod (n)

8、以n，e为公钥。秘密钥为d。(p, q不再需要，可以销毁。) 加密将明文分组，各组对应的十进制数小于n c=me mod n解密 m=cd mod n2022/9/2512算法描述密钥产生独立地选取两大素数p和q(各100200解密正确性证明cd mod n med mod n m1 modj(n) mod n mkj(n)+1 mod ngcd(m,n) =1 mj(n)1 mod n欧拉定理 mkj(n)1 mod n mkj(n)+1m mod ngcd(m,n) 1m是p的倍数或q的倍数，设m=cp，gcd(m,q)=1, mj(q)1 mod q， mkj(q)1 mod q， mk

9、j(q) j(p)1 mod q mkj(n)1 mod q，存在一整数r，使mkj(n)1rq两边同乘m=cp, mkj(n)+1m+rcpq=m+rcn,即mkj(n)+1m mod n2022/9/2513解密正确性证明cd mod n med mod n gcd选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。设明文m=19，则由加密过程得密文为c195 mod 1192476099 m

10、od 11966解密为6677mod 11919例题2022/9/2514选p=7，q=17。例题2022/9/2414用RSA算法加密与解密的过程：例：明文=“RSA ALGORITHM”(1) 明文用数字表示 空白=00， A=01, B=02, , Z=26 (两位十进制数表示)1819 0100 0112 0715 1809 2008 1300(2) 利用加密变换公式 C=me mod r, 即C = 18191223 mod 2867=27562756 2001 0542 0669 2347 0408 1815p=47, q=61, (n)=2760时，d=167n=2867e=12

11、232022/9/2515用RSA算法加密与解密的过程：2756 2001 054RSA算法实现如何判定一个给定的大整数是素数？已知d如何计算e，使e * d1 mod(n)？如何计算C Me mod n或MCd mod n？2022/9/2516RSA算法实现如何判定一个给定的大整数是素数？2022/9/Miller-Rabin 素性检验算法2022/9/2517Miller-Rabin 素性检验算法2022/9/241求模逆元的扩展欧几里德算法2022/9/2518求模逆元的扩展欧几里德算法2022/9/2418求模幂的模重复平方计算法求am，其中a，m是正整数： 将m表示为二进制形式bk

12、 bk-1b0，m=bk2k+bk-12k-1+b12+b02022/9/2519求模幂的模重复平方计算法求am，其中a，m是正整数： 202RSA的快速实现加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，CRT 对RSA解密算法生成两个解密方程（利用M=Cd mod pq）即: M1 = M mod p = (C mod p)d mod (p-1) mod p M2 = M mod q = (C mod q)d mod (q-1) mod q 解方程 M = M1 mod p M = M2 mod q 具有唯一解（利用CRT ）2022/9/2520RSA的快速实现加密很快，指数

13、小2022/9/2420RSA的安全性RSA的安全性是基于分解大整数的困难性假定如果分解n=pq，则立即获得(n)=(p1)(q1)，从而能够确定e的模(n)乘法逆d由n直接求(n)等价于分解nRSA-129历时8个月被于1996年4月被成功分解，RSA130于1996年4月被成功分解密钥长度应该介于1024bit到2048bit之间2022/9/2521RSA的安全性RSA的安全性是基于分解大整数的困难性假定如果2022/9/25222022/9/2422DES和RSA性能比较（同等强度）2022/9/2523DES和RSA性能比较（同等强度）2022/9/2423RSA的安全性|p-q|要

14、大p-1,q-1都应有大的素因子。en且dn1/4,则d能被容易的确定。2022/9/2524RSA的安全性|p-q|要大2022/9/2424|p-q|要大?如果|p-q|小稍大于n稍大于 顺序检查大于 的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。 由x2-n=y2，得n=(x+y)(x-y)。2022/9/2525|p-q|要大?如果|p-q|小稍大于n稍大于 顺序检查大重复加密攻击p-1和q-1都应有大素因子?(针对重复加密攻击)设攻击者截获密文c，使t足够大2022/9/2526重复加密攻击p-1和q-1都应有大素因子?(针对重复加密攻击当t= （(n)）， e

15、t1(mod (n) （(n)）足够大， p-1和q-1都应有大的素因子。Euler 定理2022/9/2527当t= （(n)）， et1(mod (n)Eul共模攻击每一用户有相同的模数n设用户的公开密钥分别为e1,e2,且e1,e2互素，明文消息为m,密文为因为（e1,e2)=1,用欧几里德算法可求 r e1+s e2=1假定r为负数，计算 (c1-1)-r c2s=m mod n2022/9/2528共模攻击每一用户有相同的模数n2022/9/2428低指数攻击令网中三用户的加密钥e均选3，而有不同的模n1, n2, n3若有一用户将消息x传给三个用户的密文分别为 y1=x 3 mod n1 x n1y2=x 3 mod n2 x n2y3=x 3 mod n3 x n3一般选n1, n2, n3互素，利用中国剩余定理，求出 y=x 3 mod (n1 n2 n3)。 由xn1, xn2, xn3，可得x3 n1 n2, n3，故有2022/9/2529低指数攻击令网中三用户的加密钥e均选3，而有不同的模n1, RSA可用于数字签名签名：对任意消息 mM, 用户用自己的私钥签名如下： Smd (mod n), 得到签了名的消息：（m, S）验证签名：由该用户的公开密钥（e, n），验证 m Se (mod n)是否成立. 2022/9/2530 RSA可用于数字签名签