现现代密码学-8讲RSA教学课件

4.2

公钥密码体制的基本概念BasicConceptofPublicKeyCryptography2023/7/251公钥密码体制的原理公钥体制(Publickeysystem)(Diffie和Hellman,1976)

每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。解决了单钥密码体制中最难解决的两个问题：数字签字、密钥分配2023/7/252公钥体制加密

公钥体制加、解密

m=D

(c)=DSKB(EPKB(m))安全保障从公开钥PKB和密文c要推出明文m或解密钥SKB在计算上是不可行的。由于任一用户都可用用户B的公开钥PKB

向他发送机密消息，因而密文c不具有认证性。发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmm’SK’B2023/7/253公钥密码认证体制

用户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密码分析员mcmSK’A2023/7/254公钥保密和认证体制公开保密公开保密保密认证为了同时提供认证功能和保密性，可使用双重加、解密加密c=EPKB[ESKA[m]]解密m=DPKA[DSKB[c]]2023/7/255公钥密码应满足的要求接收方B产生密钥对在计算上是容易的发送方A用收方的公开钥对消息m加密以产生密文c在计算上是容易的。收方B用自己的秘密钥对密文c解密在计算上是容易的。敌手由密文c和B的公开密钥恢复明文在计算上是不可行的。敌手由密文c和B的公开密钥恢复秘密密钥在计算上是不可行的加解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)],不是对任何算法都做此要求。以上要求本质就是找出合适的单向陷门函数2023/7/256单向函数一个可逆函数f：AB，若它满足：

1o

对所有xA，易于计算f(x)。

2o对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即若输入长度为n，计算函数的时间是na的倍数，a为一固定的常数。若计算函数时间是an的倍数，则为不可能做到的。算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的2023/7/257陷门单向函数单向函数是求逆困难的函数，而单向陷门函数(Trapdoorone-wayfunction)，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。陷门单向函数是一族可逆函数fk，满足Y=fk(X)易于计算（当k和X已知）X＝f-1k(Y)易于计算（当k和Y已知）X＝f-1k(Y)计算上不可行（Y已知但k未知）2023/7/2584.3RSA算法

RSAAlgorithm2023/7/259概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。2023/7/2510算法描述－密钥产生独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值(n)=(p－1)(q－1)

随机选一整数e，1e<(n)，gcd((n),e)=1在模(n)下，计算e的有逆元d=e-1mod(n)以n，e为公钥。秘密钥为d。(p,q不再需要，可以销毁。)

加密将明文分组，各组对应的十进制数小于nc=memodn解密

m=cd

modn2023/7/2511解密正确性证明cd

modn≡med

modn≡m1

modj(n)

modn≡mkj(n)+1modngcd(m,n)=1

mj(n)≡1modn—欧拉定理mkj(n)≡1modnmkj(n)+1≡mmodngcd(m,n)≠1m是p的倍数或q的倍数，设m=cp，gcd(m,q)=1,

mj(q)≡1modq，

mkj(q)≡1modq，

[mkj(q)]j(p)≡1modqmkj(n)≡1modq，存在一整数r，使mkj(n)≡1＋rq两边同乘m=cp,mkj(n)+1≡m+rcpq=m+rcn,即mkj(n)+1≡mmodn2023/7/2512选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确定满足d·e=1mod96且小于96的d，因为77×5=385=4×96+1，所以d为77公开钥为{5，119}，秘密钥为{77}。设明文m=19，则由加密过程得密文为c≡195mod119≡2476099mod119≡66解密为6677mod119≡19例题2023/7/2513用RSA算法加密与解密的过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)

1819010001120715180920191300(2)利用加密变换公式C=memodr,即C=18191223mod2867=2756

2756201905420669234704081815p=47,q=61,(n)=2760时，d=167n=2867e=12232023/7/2514RSA算法实现如何判定一个给定的大整数是素数？已知d如何计算e，使e*d≡1modΦ(n)？如何计算C≡Memodn或M≡Cdmodn？2023/7/2515Miller-Rabin素性检验算法

2023/7/2516求模逆元的扩展欧几里德算法

2023/7/2517求模幂的模重复平方计算法求am，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，m=bk2k+bk-12k-1+…+b12+b02023/7/2518RSA的快速实现加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，CRT对RSA解密算法生成两个解密方程（利用M=Cdmodpq）即:M1=Mmodp=(Cmodp)dmod(p-1)

modp

M2=Mmodq=(Cmodq)dmod(q-1)modq解方程M=M1modpM=M2modq具有唯一解（利用CRT）2023/7/2519RSA的安全性RSA的安全性是基于分解大整数的困难性假定如果分解n=p×q，则立即获得(n)=(p－1)(q－1)，从而能够确定e的模(n)乘法逆d由n直接求(n)等价于分解nRSA-129历时8个月被于2019年4月被成功分解，RSA－130于2019年4月被成功分解密钥长度应该介于1024bit到2048bit之间2023/7/25202023/7/2521DES和RSA性能比较（同等强度）2023/7/2522RSA的安全性|p-q|要大p-1,q-1都应有大的素因子。e<n且d<n1/4,则d能被容易的确定。2023/7/2523|p-q|要大?如果|p-q|小稍大于n稍大于①顺序检查大于的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。②由x2-n=y2，得n=(x+y)(x-y)。2023/7/2524重复加密攻击p-1和q-1都应有大素因子?(针对重复加密攻击)设攻击者截获密文c，使t足够大2023/7/2525当t=φ（φ(n)），et≡1(modφ(n))

φ（φ(n)）足够大，p-1和q-1都应有大的素因子。Euler定理2023/7/2526共模攻击每一用户有相同的模数n设用户的公开密钥分别为e1,e2,且e1,e2互素，明文消息为m,密文为因为（e1,e2)=1,用欧几里德算法可求

re1+se2=1假定r为负数，计算

(c1-1)-r

c2s=mmodn2023/7/2527低指数攻击令网中三用户的加密钥e均选3，而有不同的模n1,n2,n3若有一用户将消息x传给三个用户的密文分别为

y1=x3modn1

x<n1y2=x3modn2

x<n2y3=x3modn3

x<n3一般选n1,n2,n3互素，利用中国剩余定理，求出y=x3mod(n1

n2

n3)。

由x<n1,x<n2,x<n3，可得x3<n1

n2,n3，故有2023/7/2528

RSA可用于数字签名签名：对任意消息m∈M,用户用自己的私钥签名如下：

S≡md(modn),得到签了名的消息：（m,S）验证签名：由该用户的公开密钥（e,n），验证m≡Se(modn)是否成立.2023/7/2529选择密文攻击攻击者通过选取不同的待解密的密文，以得到对应的被加密的明文。原始的RSA不能抵抗这种攻击