1、第4章 公钥密码,4.1 数论基础知识 4.2 公钥密码的基本概念 4.3 RSA公钥密码 4.4 ElGamal公钥密码 4.5 Rabin公钥密码 4.6 椭圆曲线公钥密码,现代密码学,电子科技大学,4.1 数论基础知识,现代密码学,电子科技大学,素数与互素,定义1 对于整数a, b（b0），若存在整数x使得b=ax，则称a整除b，或a是b的因子，记作a|b。定义2 若a, b, c都是整数，a和b不全为0且c|a, c|b，则称c是a和b的公因子。如果整数d满足： d是a和b的公因子； a和b的任一公因子，也是d的因子。 则称d是a和b的最大公因子，记作d =gcd (a, b)。如果g
2、cd (a, b)=1，则称a和b互素。,定义3 若a, b, c都是整数，a和b都不为0且a|c, b|c，则称c是a和b的公倍数。如果整数d满足： d是a和b的公倍数； d整除a和b的任一公倍数。则称d是a和b的最小公倍数，记作d =lcm (a, b)。,现代密码学,电子科技大学,素数与互素,定义4 对于任一整数p (p1)，若p的因子只有1和p，则称p为素数，否则称为合数。对于任一整数a (a1)，都可以唯一的分解为素数的乘积，即：a= p1p2pt其中，p1p2pt都是素数，pi0 (i=1, 2, , t)。,素数与互素,定义5 设n是一正整数，小于n且与n互素的正整数的个数称为欧
3、拉（Euler）函数，记作 。欧拉函数有如下性质： 若n是素数，则 。 若m和n互素，则 。 如果 ：其中，p1p2pt都是素数，pi0 (i=1, 2, , t)，则：,现代密码学,电子科技大学,欧拉函数,定义6 设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，即：其中表示小于或等于 的最大整数。定义r为a mod n，记作r a mod n。如果两个整数a和b满足：则称a和b模n同余，记作a b mod n。称与a模n同余的数的全体为a的同余类。,现代密码学,电子科技大学,表示向下取整,同余及其性质,同余有如下性质： 若n|（ab），则a b mod n。 若a mod n b
4、 mod n，则a b mod n。 a a mod n。 若a b mod n，则b a mod n。 若a b mod n，b c mod n，则a c mod n。 若a b mod n，c d mod n，则a+c b+d (mod n), ac bd (mod n)。,现代密码学,电子科技大学,同余及其性质,一般的，定义Zn为小于n的所有非负整数集合，即Zn=0, 1, n1，称Zn为模n的同余类集合。Zn中的加法（+）和乘法（）都为模n运算，具有如下性质： 交换律 (w+x)mod n = (x+w) mod n(wx)mod n = (xw) mod n,现代密码学,电子科技大学
5、,模运算, 结合律 (w+x)+y mod n =w+ (x+y) mod n(wx)y mod n =w (xy) mod n 分配律 w(x+y) mod n = (wx)+(wy) mod n 单位元 (0+w)mod n =w mod n (1w)mod n =w mod n,模运算, 加法逆元 对wZn，存在xZn，使得w+x 0 mod n，称 x为w的加法逆元，记作x = w。 乘法逆元 设wZn，如果存在xZn，使得wx 1 mod n，就说w是可逆的，称x为w的乘法逆元，记作x=w1。并不是每个元素都有乘法逆元，可以证明wZn是可逆的，当且仅当gcd (w, n)=1。如果w
6、是可逆的，则可以定义除法：,模运算,定理1 费马（Fermat）定理 设p为素数，a是正整数且gcd (a, p) =1，则ap1 1 mod p。如果a是任一正整数，则ap 1 mod p。定理2 欧拉定理若gcd (a, n) =1，则：其中 是欧拉函数 .,现代密码学,电子科技大学,费马定理及欧拉定理,定理3 中国剩余定理设m1, m2, , mk是两两互素的正整数，a1, a2, , ak是任意k个整数，则同余方程组：模M = m1m2mk有唯一解：其中，Mi=M/mi，yi=Mi -1 mod mi, i=1, 2, , k。,中国剩余定理,离散对数,求模下的整数幂 根据欧拉定理，若
7、gcd(a,n)=1,则af(n) 1 mod n。考虑一般am 1 mod n, 如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。 例：a=7,n=19. 71 7 mod 19, 72 11 mod 19, 73 1 mod 19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同,离散对数,定理：设a的阶为m，则ak1mod n的充分必要条件是k是m的倍数。 推论：a的阶整除j(n)。 本原根：a的阶m等于j(n)，a为n的本原根。 如果a是n的本原根，a1,a2,.,a j(n)在模n下互不相同且与n互素。 本原根不唯一。 并
8、非所有元素都有本原根，仅有以下形式的整数才有本原根：2，4，pa,2pa, p是奇素数,离散对数,指标 y=ax(a0,a1)的逆函数称为以a为底的对数，记为x=logay 设p为素数，a是p的本原根，则a0,a1,.,a p-1产生1到p-1中所有值，且每个值只出现一次。对任一b1,p-1，都存在唯一的i(1i p)，使bai mod p。i称为模p下以a为底b的指标，记为i=inda,p(d),离散对数,指标的性质 inda,p(1)=0 inda,p(a)=1 inda,p(xy)=inda,p(x)+ inda,p(y) mod j(p) inda,p(yr)=rinda,p(y) m
9、od j(p)后两个性质基于下列结论若azaq mod p ,a和p互素，则z q mod j (p),定义7 设 ，若存在一个 ，使得x2 a mod n，则称a是一个模n的二次剩余（quadratic residue modulo n），并称x是a的模n平方根；否则称a是一个模n的二次非剩余（quadratic nonresidue modulo n）。,现代密码学,电子科技大学,二次剩余,4.2 公钥密码的基本概念,现代密码学,电子科技大学,1976年，Diffie和Hellman在“密码学的新方向（New Direction in Cryptography）”一文中首次提出了公钥密码体
10、制（public key cryptosystem）的思想。 公钥密码体制的概念是为了解决传统密码系统中最困难的两个问题而提出的，这两个问题是密钥分配和数字签名。,4.2 公钥密码的基本概念,现代密码学,电子科技大学,4.2.1 公钥密码体制的原理,公钥密码体制在加密和解密时使用不同的密钥，加密密钥简称公钥（public key），解密密钥简称私钥（private key）。公钥是公开信息，不需要保密，私钥必须保密。给定公钥，要计算出私钥在计算上是不可行的。 公钥密码体制有两种基本模型，一种是加密模型，另一种是认证模型 。,现代密码学,电子科技大学,（1）加密模型。如图所示，接收者B产生一对密
11、钥PKB和SKB，其中PKB是公钥，将其公开，SKB是私钥，将其保密。如果A要向B发送消息m，A首先用B的公钥PKB加密m，表示为c =E (PKB, m)，其中c是密文，E是加密算法，然后发送密文c给B。B收到密文c后，利用自己的私钥SKB解密，表示为m =D (SKB, c)，其中D是解密算法。,现代密码学,电子科技大学,加密模型,认证模型,（2）认证模型。如图所示，A首先用自己的私钥SKA对消息m加密，表示为c=E (SKA, m)，然后发送c给B。B收到密文c后，利用A的公钥PKA对c解密，表示为m=D (PKA, c)。由于是用A的私钥对消息加密，只有A才能做到，c就可以看做是A对m
12、的数字签名。此外，没有A的私钥，任何人都不能篡改m，所以上述过程获得了对消息来源和数据完整性的认证。,发送者A,加密算法 （签名）,SKA,密钥源,PKA,解密算法 （验证）,接收者B,密码分析员,m,c,m,SKA,4.2.2 公钥密码体制的要求,公钥体制的基本原理是陷门单向函数。 定义8 陷门单向函数是满足下列条件的可逆函数f： 对于任意的x，计算y = f (x)是容易的。 对于任意的y，计算x使得y = f (x)是困难的。 存在陷门t，已知t时，对于任意的y，计算x使得y = f (x)则是容易的。,现代密码学,电子科技大学,（1）大整数分解问题（factorization prob
13、lem）若已知两个大素数p和q，求n = pq是容易的，只需一次乘法运算，而由n，求p和q则是困难的，这就是大整数分解问题。,现代密码学,电子科技大学,（2）离散对数问题（discrete logarithm problem）给定一个大素数p，p1含另一大素数因子q，则可构造一个乘法群，它是一个p1阶循环群。设g是的一个生成元，1gp1。已知x，求y=gx mod p是容易的，而已知y、g、p，求x使得y=gx mod p成立则是困难的，这就是离散对数问题。,（3）多项式求根问题有限域GF（p）上的一个多项式：已知 , p和x，求y是容易的，而已知y, ，求x则是困难的，这就是多项式求根问题。
14、,（5）判断Diffie-Hellman问题（decision Diffie-Hellman problem, DDHP）给定素数p，令g是的一个生成元。已知 , , 判断等式：z=xy mod p 是否成立，这就是判断性Diffie-Hellman问题。,现代密码学,电子科技大学,（6）二次剩余问题（quadratic residue problem）给定一个合数n和整数a，判断a是否为mod n的二次剩余，这就是二次剩余问题。在n的分解未知时，求 a mod n的解也是一个困难问题。,（7）背包问题（knapsack problem）给定向量A= ( ) ( 为正整数)和x = ( ) (
15、 0,1)，求和式：是容易的，而由A和S，求x则是困难的，这就是背包问题，又称子集和问题。,4.3 RSA公钥密码,1密钥生成 选取两个保密的大素数p和q。 计算n = pq, ，其中 是n的欧拉函数值。 随机选取整数e，满足1e ，且 。 计算d，满足 。 公钥为(e,n)，私钥为（d, n）。,4.3.1 RSA算法描述,现代密码学,电子科技大学,2加密 首先对明文进行比特串分组，使得每个分组对应的十进制数小于n，然后依次对每个分组m做一次加密，所有分组的密文构成的序列即是原始消息的加密结果。即m满足0mn，则加密算法为：c为密文，且0cn。,现代密码学,电子科技大学,4.3.1 RSA算
16、法描述,3解密对于密文0cn，解密算法为：,现代密码学,电子科技大学,4.3.1 RSA算法描述,4.3.2 RSA的安全性 1数学攻击 用数学方法攻击RSA的途径有三种： 分解n为两个素因子。这样就可以计算 从而计算出私钥 。 直接确定 而不先确定p和q。这同样可以确定 . 直接确定d而不先确定 。,现代密码学,电子科技大学,2穷举攻击像其他密码体制一样，RSA抗穷举攻击的方法也是使用大的密钥空间，这样看来是e和d的位数越大越好。但是由于在密钥生成和加密/解密过程都包含了复杂的计算，故密钥越大，系统运行速度越慢。 3计时攻击计时攻击是通过记录计算机解密消息所用的时间来确定私钥。这种攻击不仅可
17、以用于攻击RSA，还可以用于攻击其他的公钥密码系统。,现代密码学,电子科技大学,4.3.2 RSA的安全性,4. 选择密文攻击RSA易受选择密文攻击（chosen ciphertext attack）,4.3.2 RSA的安全性,4.4 ElGamal公钥密码,现代密码学,电子科技大学,1密钥生成 选取大素数p，且要求p1有大素数因子。是一个本原元。 随机选取整数x,1xp2，计算 。 公钥为y，私钥为x。,4.4.1 ElGamal算法描述,现代密码学,电子科技大学,p和g是公共参数，被所有用户所共享，这一点与RSA算法是不同的。另外，在RSA算法中，每个用户都需要生成两个大素数来建立自己的
18、密钥对（这是很费时的工作），而ElGamal算法只需要生成一个随机数和执行一次模指数运算就可以建立密钥对。,2加密 对于明文，首先随机选取一个整数k,1kp2，然后计算： , 则密文c =（ c1, c2）。3解密 为了解密一个密文c=（c1, c2），计算：,现代密码学,电子科技大学,4.4.2 ElGamal的安全性在ElGamal公钥密码体制中，y = mod p。从公开参数g和y求解私钥x需要求解离散对数问题。目前还没有找到一个有效算法来求解有限域上的离散对数问题。因此，ElGamal公钥密码体制的安全性是基于有限域上离散对数问题的困难性。为了抵抗已知的攻击，p应该选取至少160位以上
19、的十进制数，并且p1至少应该有一个大的素因子。,现代密码学,电子科技大学,4.5 Rabin公钥密码,现代密码学,电子科技大学,1密钥生成 选取两个大素数p和q，满足p q 3 mod 4，计算n=pq，则公钥为n，私钥为（p, q）。2加密 对于明文m（0mn），计算密文: c = mod n,4.5.1 Rabin算法描述,现代密码学,电子科技大学,3解密 为了解密一个密文c，利用中国剩余定理求解同余方程组，计算：, , 然后选择整数a = q (q1 mod p)和b=p (p1 mod q)，四个可能的解为：, ，,现代密码学,电子科技大学,4.5.1 Rabin算法描述,3解密 由中
20、国剩余定理知解x2c mod n, 等价于解方程组由于pq3 mod 4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即,4.5.1 Rabin算法描述,经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。,下面证明，当pq3 mod 4，两个方程 x2c mod p,x2c mod q 的平方根都可容易地求出。,雅克比符号？,所以 和 是方程x2c mod p的两个根。同理 和 是方程x2c mod q的两个 根。由4.1.8节知，求解方程
21、x2a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。,4.6 椭圆曲线公钥密码,现代密码学,电子科技大学,椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程相似。一般的，椭圆曲线指的是由维尔斯特拉斯（Weierstrass）方程：,4.5.1 实数域上的椭圆曲线,现代密码学,电子科技大学,所确定的曲线，它是由方程的全体解（x, y）再加上一个无穷远点O构成的集合，其中a、b、c、d、e是满足一些简单条件的实数，x和y也在实数集上取值。上述曲线方程可以通过坐标变换转化为下述形式：,4.5.1 实数域上的椭圆曲线,由它确定的椭圆曲线
22、常记为E（a, b），简记为E。当 时，称E（a, b）是一条非奇异椭圆曲线。对于非奇异椭圆曲线，我们可以基于集合E（a, b）定义一个群。这是一个Abel群，具有重要的“加法规则”属性。,4.5.1 实数域上的椭圆曲线,1加法的几何描述椭圆曲线上的加法运算定义如下：如果椭圆曲线上的3个点位于同一直线上，那么它们的和为O。从这个定义出发，我们可以定义椭圆曲线的加法规则： O为加法的单位元，对于椭圆曲线上的任何一点P，有P+O=P。 对于椭圆曲线上的一点P =（x, y），它的逆元为P =（x, y）。注意到这里有P+（P）=PP=O。,现代密码学,电子科技大学,设P和Q是椭圆曲线上x坐标不同的
23、两点，P+Q的定义如下：作一条通过P和Q的直线l与椭圆曲线相交于R（这一点是唯一的，除非这条直线在P点或Q点与该椭圆曲线相切，此时我们分别取R=P或R=Q），然后过R点作y轴的平行线l，l与椭圆曲线相交的另一点S就是P+Q。如图4-2所示。,图4-2 椭圆曲线上点的加法的几何解释,现代密码学,电子科技大学, 上述几何解释也适用于具有相同x坐标的两个点P和P的情形。用一条垂直的线连接这两个，可看做是在无穷远点与椭圆曲线相交，因此有P+（P）=O。这与上述的第条叙述是一致的。 为计算点Q的两倍，在Q点作一条切线并找到与椭圆曲线的另一个交点T，则Q+Q=2Q = T。以上定义的加法具有加法运算的一般
24、性质，如交换律、结合律等。,现代密码学,电子科技大学,2加法的代数描述对于椭圆曲线上不互为逆元的两点P = (x1, y1)和Q= (x2, y2)，S = P+Q = (x3, y3)由以下规则确定：其中,现代密码学,电子科技大学,4.6.2 有限域上的椭圆曲线,椭圆曲线密码体制使用的是有限域上的椭圆曲线，即变量和系数均为有限域中的元素。有限域GF (p)上的椭圆曲线是指满足方程：的所有点 (x, y)再加上一个无穷远点O构成的集合，其中，a、b、x和y均在有限域GF (p)上取值，p是素数。我们把该椭圆曲线记为 (a, b)。该椭圆曲线只有有限个点，其个数N由Hasse定理确定。,现代密码
25、学,电子科技大学,定理4 （Hasse定理）设E是有限域GF (p)上的椭圆曲线，N是E上点的个数，则,4.6.3 椭圆曲线的密码体制,现代密码学,电子科技大学,4.6.3 椭圆曲线的密码体制,定义9 椭圆曲线 (a, b)上点P的阶是指满足：的最小正整数，记为ord (P)，其中O是无穷远点。,现代密码学,电子科技大学,椭圆曲线上的离散对数,定义10 设G是椭圆曲线 (a, b)上的一个循环子群，P是G的一个生成元，QG。已知P和Q，求满足：mP = Q 的整数m,0mord (P)1，称为椭圆曲线上的离散对数问题（Elliptic Curve Discrete logarithm prob
26、lem）。,1椭圆曲线上的ElGamal密码体制在使用一个椭圆曲线密码体制时，我们首先需要将发送的明文m编码为椭圆曲线上的点 ，然后再对点 做加密变换，在解密后还得将 逆向译码才能获得明文。下面对椭圆曲线上的ElGamal密码体制进行介绍。密钥生成 在椭圆曲线 (a, b)上选取一个阶为n（n为一个大素数）的生成元P。随机选取整数x (1xn)，计算Q=xP。公钥为Q，私钥为x。,现代密码学,电子科技大学,加密 为了加密 ，随机选取一个整数k,1kn，计算：, 则密文c = ( )。 解密 为了解密一个密文c = ( )，计算：攻击者要想从c = ( )计算出 ，就必须知道k。而要从P和kP中
27、计算出k将面临求解椭圆曲线上的离散对数问题。,2椭圆曲线密码体制的优点 与基于有限域上的离散对数问题的公钥密码体制相比，椭圆曲线密码体制有如下优点： 安全性高 密钥长度小 算法灵活性好,现代密码学,电子科技大学,习题,1为什么对于长消息来说，最好是先采用公钥密码算法来传输一个对称密钥，然后再用该对称密钥来传递消息？ 2RSA公钥密码体制、ElGamal公钥密码体制、Rabin公钥密码体制和椭圆曲线公钥密码体制的安全性依据是什么？ 3在RSA密码体制中，已知素数p =3，q =11，公钥e=7，试计算私钥d并给出对明文m=5的加密和解密过程。,现代密码学,电子科技大学,4在ElGamal密码体制中，设素数p =71，本原元g=7： 如果接收者B的公钥为yB=3，发送者A随机选择整数k=2，求明文m=30所对应的密文。 如果发送者A选择另一个随机整数k，使得明文m=30加密后的密文为c=（59, c2），求c2。,5在Rabin密码体制中，p =127, q =131，试给出对明文m=4410的加密和解密过程。 6在椭圆曲线上的ElGamal密码体制中，设椭圆曲线为 (1, 6)，生成元P= (2, 7)，接收者的私钥x=7。 求接收者的公钥Q。 发送者欲发送消息 = (10, 9)，选择随机数k=3，求密文c。 给出接收者从密文c恢复消息 的过程。,现代密码学,电子科技大学,
