现代密码学-数论基础知识课件

第4章 公钥密码4.1 数论基础知识数论基础知识4.2 公钥密码的基本概念公钥密码的基本概念4.3 RSA公钥密码公钥密码4.4 ElGamal公钥密码公钥密码4.5 Rabin公钥密码公钥密码4.6 椭圆曲线公钥密码椭圆曲线公钥密码现代密码学现代密码学1谢谢观赏2019-8-26第4章 公钥密码4.1 数论基础知识现代密码学1谢谢观赏4.1 数论基础知识数论基础知识现代密码学现代密码学2谢谢观赏2019-8-264.1 数论基础知识现代密码学2谢谢观赏2019-8-26 现代密码学素数与互素u定义定义1 1 对于整数对于整数a a,b b（b b 0 0），若存在整数），若存在整数x x使得使得b b=axax，则称，则称a a整除整除b b，或，或a a是是b b的因子，记作的因子，记作a a|b b。u定义定义2 2 若若a a,b b,c c都是整数，都是整数，a a和和b b不全为不全为0 0且且c c|a a,c c|b b，则称，则称c c是是a a和和b b的公因子。如果整数的公因子。如果整数d d满足：满足：u d d是是a a和和b b的公因子；的公因子；u a a和和b b的任一公因子，也是的任一公因子，也是d d的因子。的因子。u则称则称d d是是a a和和b b的最大公因子，记作的最大公因子，记作d d=gcd(=gcd(a a,b b)。如果如果gcd(gcd(a a,b b)=1)=1，则称，则称a a和和b b互素。互素。3谢谢观赏2019-8-26素数与互素定义1 对于整数a,b（b0），若存在整u定义定义3 3 若若a a,b b,c c都是整数，都是整数，a a和和b b都不为都不为0 0且且a a|c c,b b|c c，则称，则称c c是是a a和和b b的公倍数。如的公倍数。如果整数果整数d d满足：满足：d d是是a a和和b b的公倍数；的公倍数；d d整除整除a a和和b b的任一公倍数。的任一公倍数。则称则称d d是是a a和和b b的的最小公倍数最小公倍数，记作，记作d d=lcm lcm(a a,b b)。现代密码学现代密码学素数与互素4谢谢观赏2019-8-26定义3 若a,b,c都是整数，a和b都不为0且a|现代密码学u定义定义4 对于任一整数对于任一整数p(p1)，若，若p的因子的因子只有只有1和和p，则称，则称p为素数，否则称为合数。为素数，否则称为合数。对于任一整数对于任一整数a(a1)，都可以唯一的分解，都可以唯一的分解为素数的乘积，即：为素数的乘积，即：a=p1p2pt 其中，其中，p1p2pt都是素数，都是素数，pi0(i=1,2,t)。素数与互素5谢谢观赏2019-8-26定义4 对于任一整数p(p1)，若p的因子只有1u定义定义5 5 设设n n是一正整数，小于是一正整数，小于n n且与且与n n互素的正整数互素的正整数的个数称为欧拉（的个数称为欧拉（EulerEuler）函数，记作）函数，记作 。欧。欧拉函数有如下性质：拉函数有如下性质：若若n n是素数，则是素数，则 。若若m m和和n n互素，则互素，则 。如果如果 ：其中，其中，p p1 1 p p2 2 0,a1)(a0,a1)的逆函数称为以的逆函数称为以a a为底的对数，为底的对数，记为记为x=logx=loga ay y设设p p为素数，为素数，a a是是p p的本原根，则的本原根，则a a0 0,a,a1 1,.,a,.,a p-1p-1产生产生1 1到到p-1p-1中所有值，且每个值只出现一次。中所有值，且每个值只出现一次。对任一对任一b1,b1,p-1,p-1，都存在唯一的，都存在唯一的i(1i(1i i p)p)，使，使babai i mod p mod p。i i称为模称为模p p下以下以a a为底为底b b的的指标指标，记为，记为i=indi=inda,pa,p(d)(d)16谢谢观赏2019-8-26离散对数指标16谢谢观赏2019-8-26 现代密码学离散对数u指标的性质指标的性质1.inda,p(1)=02.inda,p(a)=13.inda,p(xy)=inda,p(x)+inda,p(y)mod j j(p)(p)4.inda,p(yr)=rinda,p(y)mod j j(p)(p)后两个性质基于下列结论后两个性质基于下列结论 若若a az zaaq q mod p,a mod p,a和和p p互素，则互素，则z q mod z q mod j j (p)(p)17谢谢观赏2019-8-26离散对数指标的性质17谢谢观赏2019-8-26u定义定义7 7 设设 ，若存在一个，若存在一个 ，使得，使得x x2 2 a a mod mod n n，则称，则称a a是一个模是一个模n n的的二次剩余（二次剩余（quadratic residue modulo quadratic residue modulo n n），并称），并称x x是是a a的模的模n n平方根；否则称平方根；否则称a a是一是一个模个模n n的二次非剩余（的二次非剩余（quadratic quadratic nonresidue modulo nonresidue modulo n n）。）。现代密码学现代密码学二次剩余18谢谢观赏2019-8-26定义7 设 ，若存在一个 4.2 公钥密码的基本概念现代密码学现代密码学19谢谢观赏2019-8-264.2 公钥密码的基本概念现代密码学19谢谢观赏2019 现代密码学19761976年，年，DiffieDiffie和和HellmanHellman在在“密码学的新方向密码学的新方向（New Direction in CryptographyNew Direction in Cryptography）”一文中首次一文中首次提出了公钥密码体制（提出了公钥密码体制（public key cryptosystempublic key cryptosystem）的思想。的思想。公钥密码体制的概念是为了解决传统密码系统中最公钥密码体制的概念是为了解决传统密码系统中最困难的两个问题而提出的，这两个问题是困难的两个问题而提出的，这两个问题是密钥分配密钥分配和和数字签名数字签名。4.2 公钥密码的基本概念现代密码学现代密码学20谢谢观赏2019-8-261976年，Diffie和Hellman在“密码学的新方向（4.2.1 公公钥密密码体制的原理体制的原理u公钥密码体制在加密和解密时使用不同的公钥密码体制在加密和解密时使用不同的密钥，加密密钥简称公钥（密钥，加密密钥简称公钥（public keypublic key），），解密密钥简称私钥（解密密钥简称私钥（private keyprivate key）。公钥）。公钥是公开信息，不需要保密，私钥必须保密。是公开信息，不需要保密，私钥必须保密。给定公钥，要计算出私钥在计算上是不可给定公钥，要计算出私钥在计算上是不可行的。行的。u公钥密码体制有两种基本模型，一种是加公钥密码体制有两种基本模型，一种是加密模型，另一种是认证模型密模型，另一种是认证模型 。现代密码学现代密码学21谢谢观赏2019-8-264.2.1 公钥密码体制的原理公钥密码体制在加密和解密时u（1 1）加密模型。如图所示，接收者）加密模型。如图所示，接收者B B产生一对密钥产生一对密钥PKPKB B和和SKSKB B，其中，其中PKPKB B是公钥，将其公开，是公钥，将其公开，SKSKB B是私钥，是私钥，将其保密。如果将其保密。如果A A要向要向B B发送消息发送消息m m，A A首先用首先用B B的公的公钥钥PKPKB B加密加密m m，表示为，表示为c c=E E(PKPKB B,m m)，其中，其中c c是密文，是密文，E E是加密算法，然后发送密文是加密算法，然后发送密文c c给给B B。B B收到密文收到密文c c后，后，利用自己的私钥利用自己的私钥SKSKB B解密，表示为解密，表示为m m=D D(SKSKB B,c c)，其中其中D D是解密算法。是解密算法。现代密码学现代密码学加密模型加密模型发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmmSKB22谢谢观赏2019-8-26（1）加密模型。如图所示，接收者B产生一对密钥PKB和SKB 现代密码学认证模型模型u（2）认证模型。如图所示，）认证模型。如图所示，A首先用自己首先用自己的私钥的私钥SKA对消息对消息m加密，表示为加密，表示为c=E(SKA,m)，然后发送，然后发送c给给B。B收到密文收到密文c后，后，利用利用A的公钥的公钥PKA对对c解密，表示为解密，表示为m=D(PKA,c)。由于是用。由于是用A的私钥对消息加密，的私钥对消息加密，只有只有A才能做到，才能做到，c就可以看做是就可以看做是A对对m的数的数字签名。此外，没有字签名。此外，没有A的私钥，任何人都不的私钥，任何人都不能篡改能篡改m，所以上述过程获得了对消息来源，所以上述过程获得了对消息来源和数据完整性的认证。和数据完整性的认证。23谢谢观赏2019-8-26认证模型（2）认证模型。如图所示，A首先用自己的私钥SKA对 现代密码学发送者A加密算法（签名）SKA密钥源PKA解密算法（验证）接收者B密码分析员mcmSKA24谢谢观赏2019-8-26发送者A加密算法SKA密钥源PKA解密算法接收者B密码分析员4.2.2 公钥密码体制的要求公钥体制的基本原理是陷门单向函数。u定义8 陷门单向函数是满足下列条件的可逆函陷门单向函数是满足下列条件的可逆函数数f f：对于任意的对于任意的x x，计算，计算y y=f f(x x)是容易的。是容易的。对于任意的对于任意的y y，计算，计算x x使得使得y y=f f(x x)是困难是困难的。的。存在陷门存在陷门t t，已知，已知t t时，对于任意的时，对于任意的y y，计算，计算x x使得使得y y=f f(x x)则是容易的。则是容易的。现代密码学现代密码学25谢谢观赏2019-8-264.2.2 公钥密码体制的要求公钥体制的基本原理是陷门单u（1）大整数分解问题（大整数分解问题（factorization problem）若已知两个大素数若已知两个大素数p和和q，求，求n=pq是是容易的，只需一次乘法运算，而由容易的，只需一次乘法运算，而由n，求，求p和和q则是困难的，这就是大整数分解问题。则是困难的，这就是大整数分解问题。现代密码学现代密码学26谢谢观赏2019-8-26（1）大整数分解问题（factorization probl 现代密码学u（2）离散对数问题（离散对数问题（discrete logarithm discrete logarithm problemproblem）给定一个大素数给定一个大素数p p，p p 1 1含另一含另一大素数因子大素数因子q q，则可构造一个乘法群，它是，则可构造一个乘法群，它是一个一个p p 1 1阶循环群。设阶循环群。设g g是的一个生成元，是的一个生成元，1 1g gp p 1 1。已知。已知x x，求，求y y=g gx x mod mod p p是容易是容易的，而已知的，而已知y y、g g、p p，求，求x x使得使得y y=g gx x mod mod p p成成立则是困难的，这就是离散对数问题。立则是困难的，这就是离散对数问题。27谢谢观赏2019-8-26（2）离散对数问题（discrete logarithm p 现代密码学u（3）多项式求根问题多项式求根问题 有限域有限域GF（p）上的一个多项式：）上的一个多项式：已知已知 ,p和和x，求，求y是容易的，是容易的，而已知而已知y,，求，求x则是困难的，这则是困难的，这就是多项式求根问题就是多项式求根问题。28谢谢观赏2019-8-26（3）多项式求根问题28谢谢观赏2019-8-26u（5）判断判断Diffie-Hellman问题（问题（decision Diffie-Hellman problem,DDHP）给定素数给定素数p，令，令g是的一个生成元。已知是的一个生成元。已知 ,判断等式：判断等式：z=xy mod p 是否成是否成立，这就是立，这就是判断性判断性Diffie-Hellman问题。问题。现代密码学现代密码学29谢谢观赏2019-8-26（5）判断Diffie-Hellman问题（decision 现代密码学u（6）二次剩余问题（二次剩余问题（quadratic residue problem）给定一个合数给定一个合数n和整数和整数a，判断，判断a是否为是否为mod n的二次剩余，这就是二次剩余问题。在的二次剩余，这就是二次剩余问题。在n的分解未的分解未知时，求知时，求 a mod n的解也是一个困难问题。的解也是一个困难问题。30谢谢观赏2019-8-2630谢谢观赏2019-8-26 现代密码学u（7）背包问题（背包问题（knapsack problem）给定向量给定向量A=()(为正整数为正整数)和和x=()(0,1)，求和式：，求和式：是容易的，而由是容易的，而由A和和S，求，求x则是困难的，这就是则是困难的，这就是背包问题，又称子集和问题。背包问题，又称子集和问题。31谢谢观赏2019-8-26（7）背包问题（knapsack problem）31谢谢观 现代密码学4.3 RSA公钥密码32谢谢观赏2019-8-264.3 RSA公钥密码32谢谢观赏2019-8-26u1密钥生成密钥生成 选取两个保密的大素数选取两个保密的大素数p和和q。计算计算n=pq,，其中，其中 是是n的欧拉函数值。的欧拉函数值。随机选取整数随机选取整数e，满足，满足1e ，且，且 。计算计算d，满足，满足 。公钥为公钥为(e,n)，私钥为（，私钥为（d,n）。）。4.3.1 RSA算法描述现代密码学现代密码学33谢谢观赏2019-8-261密钥生成4.3.1 RSA算法描述现代密码学33谢谢u2 2加密加密首先对明文进行比特串分组，使得每个分组首先对明文进行比特串分组，使得每个分组对应的十进制数小于对应的十进制数小于n n，然后依次对每个，然后依次对每个分组分组m m做一次加密，所有分组的密文构成做一次加密，所有分组的密文构成的序列即是原始消息的加密结果。即的序列即是原始消息的加密结果。即m m满满足足00m mn n，则加密算法为：，则加密算法为：c c为密文，且为密文，且00c cn n。现代密码学现代密码学4.3.1 RSA算法描述34谢谢观赏2019-8-262加密现代密码学4.3.1 RSA算法描述34谢谢观赏u3解密解密 对于密文对于密文0cn，解密算法为：，解密算法为：现代密码学现代密码学4.3.1 RSA算法描述35谢谢观赏2019-8-263解密现代密码学4.3.1 RSA算法描述35谢谢观赏4.3.2 RSA的安全性1数学攻击数学攻击用数学方法攻击用数学方法攻击RSARSA的途径有三种：的途径有三种：分解分解n n为两个素因子。这样就可以计算为两个素因子。这样就可以计算 从而计算出私钥从而计算出私钥 。直接确定直接确定 而不先确定而不先确定p p和和q q。这同。这同样可以确定样可以确定 .直接确定直接确定d d而不先确定而不先确定 。现代密码学现代密码学36谢谢观赏2019-8-264.3.2 RSA的安全性现代密码学36谢谢观赏2019u2穷举攻击穷举攻击 像其他密码体制一样，像其他密码体制一样，RSA抗穷举攻击的方法也抗穷举攻击的方法也是使用大的密钥空间，这样看来是是使用大的密钥空间，这样看来是e和和d的位数越的位数越大越好。但是由于在密钥生成和加密大越好。但是由于在密钥生成和加密/解密过程都解密过程都包含了复杂的计算，故密钥越大，系统运行速度越包含了复杂的计算，故密钥越大，系统运行速度越慢。慢。u3计时攻击计时攻击 计时攻击是通过记录计算机解密消息所用的时间来计时攻击是通过记录计算机解密消息所用的时间来确定私钥。这种攻击不仅可以用于攻击确定私钥。这种攻击不仅可以用于攻击RSA，还，还可以用于攻击其他的公钥密码系统。可以用于攻击其他的公钥密码系统。现代密码学现代密码学4.3.2 RSA的安全性的安全性37谢谢观赏2019-8-262穷举攻击现代密码学4.3.2 RSA的安全性37谢谢 现代密码学u4.选择密文攻击选择密文攻击 RSA易受选择密文攻击（易受选择密文攻击（chosen ciphertext attack）4.3.2 RSA的安全性的安全性38谢谢观赏2019-8-264.选择密文攻击4.3.2 RSA的安全性38谢谢观赏4.4 ElGamal公钥密码现代密码学现代密码学39谢谢观赏2019-8-264.4 ElGamal公钥密码现代密码学39谢谢观赏20 现代密码学1密钥生成密钥生成 选取大素数选取大素数p，且要求，且要求p 1有大素数因子。有大素数因子。是一个本原元。是一个本原元。随机选取整数随机选取整数x,1xp 2，计算，计算 。公钥为公钥为y，私钥为，私钥为x。4.4.1 ElGamal算法描述现代密码学现代密码学40谢谢观赏2019-8-261密钥生成4.4.1 ElGamal算法描述现代密码学 现代密码学 p p和和g g是公共参数，被所有用户所共享，是公共参数，被所有用户所共享，这一点与这一点与RSARSA算法是不同的。另外，在算法是不同的。另外，在RSARSA算法中，每个用户都需要生成两个大素数算法中，每个用户都需要生成两个大素数来建立自己的密钥对（这是很费时的工作）来建立自己的密钥对（这是很费时的工作），而，而ElGamalElGamal算法只需要生成一个随机数和算法只需要生成一个随机数和执行一次模指数运算就可以建立密钥对。执行一次模指数运算就可以建立密钥对。41谢谢观赏2019-8-26 p和g是公共参数，被所有用户所共享，这一点与RSA算2加密加密对于明文，首先随机选取一个整数对于明文，首先随机选取一个整数k,1kp 2，然，然后计算：后计算：,则密文则密文c=（c1,c2）。）。3解密解密为了解密一个密文为了解密一个密文c=（c1,c2），计算：），计算：现代密码学现代密码学42谢谢观赏2019-8-262加密现代密码学42谢谢观赏2019-8-264.4.2 ElGamal的安全性 在在ElGamal公钥密码体制中，公钥密码体制中，y=mod p。从。从公开参数公开参数g和和y求解私钥求解私钥x需要求解离散对数问题。需要求解离散对数问题。目前还没有找到一个有效算法来求解有限域上的目前还没有找到一个有效算法来求解有限域上的离散对数问题。因此，离散对数问题。因此，ElGamal公钥密码体制的公钥密码体制的安全性是基于有限域上离散对数问题的困难性。安全性是基于有限域上离散对数问题的困难性。为了抵抗已知的攻击，为了抵抗已知的攻击，p应该选取应该选取至少至少160位位以上以上的十进制数，并且的十进制数，并且p 1至少应该有一个大的素因至少应该有一个大的素因子。子。现代密码学现代密码学43谢谢观赏2019-8-264.4.2 ElGamal的安全性现代密码学43谢谢观赏4.5 Rabin公钥密码现代密码学现代密码学44谢谢观赏2019-8-264.5 Rabin公钥密码现代密码学44谢谢观赏2019 现代密码学u1密钥生成密钥生成选取两个大素数选取两个大素数p和和q，满足，满足p q 3 mod 4，计算计算n=pq，则公钥为，则公钥为n，私钥为（，私钥为（p,q）。）。u2加密加密对于明文对于明文m（0mn），计算密文），计算密文:c=mod n4.5.1 Rabin算法描述算法描述现代密码学现代密码学45谢谢观赏2019-8-261密钥生成4.5.1 Rabin算法描述现代密码学45u3解密解密为了解密一个密文为了解密一个密文c，利用中国剩余定理求解同余方，利用中国剩余定理求解同余方程组，计算：程组，计算：,然后选择整数然后选择整数a=q(q 1 mod p)和和b=p(p 1 mod q)，四个可能的解为：，四个可能的解为：,，现代密码学现代密码学4.5.1 Rabin算法描述算法描述46谢谢观赏2019-8-263解密现代密码学4.5.1 Rabin算法描述46谢谢 现代密码学3解密解密由中国剩余定理知解x2c mod n,等价于解方程组由于pq3 mod 4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即4.5.1 Rabin算法描述算法描述47谢谢观赏2019-8-263解密4.5.1 Rabin算法描述47谢谢观赏201 现代密码学经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。48谢谢观赏2019-8-26经过组合可得4个同余方程组48谢谢观赏2019-8-26 现代密码学下面证明，当pq3 mod 4，两个方程x2c mod p,x2c mod q的平方根都可容易地求出。49谢谢观赏2019-8-26下面证明，当pq3 mod 4，两个方程49谢谢观赏20 现代密码学雅克比符号？50谢谢观赏2019-8-26雅克比符号？50谢谢观赏2019-8-26 现代密码学所以 和 是方程x2c mod p的两个根。同理 和 是方程x2c mod q的两个 根。由4.1.8节知，求解方程x2a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。51谢谢观赏2019-8-26所以 和 是方4.6 椭圆曲线公钥密码现代密码学现代密码学52谢谢观赏2019-8-264.6 椭圆曲线公钥密码现代密码学52谢谢观赏2019-现代密码学u椭圆曲线并非椭圆，之所以称为椭圆曲线是因椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程相似。一般为它的曲线方程与计算椭圆周长的方程相似。一般的，椭圆曲线指的是由维尔斯特拉斯的，椭圆曲线指的是由维尔斯特拉斯（Weierstrass）方程：）方程：4.5.1 实数域上的椭圆曲线现代密码学现代密码学53谢谢观赏2019-8-26椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算 现代密码学u所确定的曲线，它是由方程的全体解（所确定的曲线，它是由方程的全体解（x,y）再）再加上一个无穷远点加上一个无穷远点O构成的集合，其中构成的集合，其中a、b、c、d、e是满足一些简单条件的实数，是满足一些简单条件的实数，x和和y也在实数也在实数集上取值。上述曲线方程可以通过坐标变换转化集上取值。上述曲线方程可以通过坐标变换转化为下述形式：为下述形式：4.5.1 实数域上的椭圆曲线54谢谢观赏2019-8-26所确定的曲线，它是由方程的全体解（x,y）再加上一个无穷远 现代密码学u由它确定的椭圆曲线常记为由它确定的椭圆曲线常记为E（a,b），简记为），简记为E。当当 时，称时，称E（a,b）是一条非）是一条非奇异椭圆曲线。对于非奇异椭圆曲线，我们可以奇异椭圆曲线。对于非奇异椭圆曲线，我们可以基于集合基于集合E（a,b）定义一个群。这是一个）定义一个群。这是一个Abel群，群，具有重要的具有重要的“加法规则加法规则”属性。属性。4.5.1 实数域上的椭圆曲线55谢谢观赏2019-8-26由它确定的椭圆曲线常记为E（a,b），简记为E。当 1加法的几何描述加法的几何描述 椭圆曲线上的加法运算定义如下：如果椭圆曲椭圆曲线上的加法运算定义如下：如果椭圆曲线上的线上的3个点位于同一直线上，那么它们的和个点位于同一直线上，那么它们的和为为O。从这个定义出发，我们可以定义椭圆曲。从这个定义出发，我们可以定义椭圆曲线的加法规则：线的加法规则：O为加法的单位元，对于椭圆曲线上的任何为加法的单位元，对于椭圆曲线上的任何一点一点P，有，有P+O=P。对于椭圆曲线上的一点对于椭圆曲线上的一点P=（x,y），它的逆），它的逆元为元为 P=（x,y）。注意到这里有）。注意到这里有P+（P）=P P=O。现代密码学现代密码学56谢谢观赏2019-8-261加法的几何描述现代密码学56谢谢观赏2019-8-26 现代密码学 设设P和和Q是椭圆曲线上是椭圆曲线上x坐标不同的两点，坐标不同的两点，P+Q的定义如下：作一条通过的定义如下：作一条通过P和和Q的直线的直线l与椭圆曲线相交于与椭圆曲线相交于R（这一点是唯一的，除（这一点是唯一的，除非这条直线在非这条直线在P点或点或Q点与该椭圆曲线相切，点与该椭圆曲线相切，此时我们分别取此时我们分别取R=P或或R=Q），然后过），然后过R点点作作y轴的平行线轴的平行线l，l与椭圆曲线相交的另一与椭圆曲线相交的另一点点S就是就是P+Q。如图。如图4-2所示。所示。57谢谢观赏2019-8-2657谢谢观赏2019-8-26图4-2 椭圆曲线上点的加法的几何解释 现代密码学现代密码学58谢谢观赏2019-8-26图4-2 椭圆曲线上点的加法的几何解释 现代密码学58谢谢 上述几何解释也适用于具有相同上述几何解释也适用于具有相同x坐标的两个点坐标的两个点P和和 P的情形。用一条垂直的线连接这两个，可看做是的情形。用一条垂直的线连接这两个，可看做是在无穷远点与椭圆曲线相交，因此有在无穷远点与椭圆曲线相交，因此有P+（P）=O。这与上述的第这与上述的第条叙述是一致的。条叙述是一致的。为计算点为计算点Q的两倍，在的两倍，在Q点作一条切线并找到与椭点作一条切线并找到与椭圆曲线的另一个交点圆曲线的另一个交点T，则，则Q+Q=2Q=T。以上定义的加法具有加法运算的一般性质，如以上定义的加法具有加法运算的一般性质，如交换律、结合律等。交换律、结合律等。现代密码学现代密码学59谢谢观赏2019-8-26 上述几何解释也适用于具有相同x坐标的两个点P和P的情u2加法的代数描述加法的代数描述 对于椭圆曲线上不互为逆元的两点P=(x1,y1)和Q=(x2,y2)，S=P+Q=(x3,y3)由以下规则确定：u其中现代密码学现代密码学60谢谢观赏2019-8-262加法的代数描述现代密码学60谢谢观赏2019-8-264.6.2 有限域上的椭圆曲线u椭圆曲线密码体制使用的是有限域上的椭圆曲线，椭圆曲线密码体制使用的是有限域上的椭圆曲线，即变量和系数均为有限域中的元素。有限域即变量和系数均为有限域中的元素。有限域GF(p)上的椭圆曲线是指满足方程：上的椭圆曲线是指满足方程：u的所有点的所有点(x,y)再加上一个无穷远点再加上一个无穷远点O构成的集合，构成的集合，其中，其中，a、b、x和和y均在有限域均在有限域GF(p)上取值，上取值，p是素数。我们把该椭圆曲线记为是素数。我们把该椭圆曲线记为 (a,b)。该椭圆。该椭圆曲线只有有限个点，其个数曲线只有有限个点，其个数N由由Hasse定理确定。定理确定。现代密码学现代密码学61谢谢观赏2019-8-264.6.2 有限域上的椭圆曲线椭圆曲线密码体制使用的是有限 现代密码学u定理4 （Hasse定理）设设E是有限域是有限域GF(p)上上的椭圆曲线，的椭圆曲线，N是是E上点的个数，则上点的个数，则62谢谢观赏2019-8-26定理4 （Hasse定理）设E是有限域GF(p)上的椭圆4.6.3 椭圆曲线的密码体制现代密码学现代密码学63谢谢观赏2019-8-264.6.3 椭圆曲线的密码体制现代密码学63谢谢观赏201 现代密码学4.6.3 椭圆曲线的密码体制定义9 椭圆曲线椭圆曲线 (a,b)上点上点P的阶是指满足：的阶是指满足：的最小正整数，记为的最小正整数，记为ord(P)，其中，其中O是无穷远点。是无穷远点。现代密码学现代密码学64谢谢观赏2019-8-264.6.3 椭圆曲线的密码体制现代密码学64谢谢观赏201 现代密码学椭圆曲线上的离散对数u定义10 设设G是椭圆曲线是椭圆曲线 (a,b)上的一个循环子上的一个循环子群，群，P是是G的一个生成元，的一个生成元，Q G。已知。已知P和和Q，求满，求满足：足：mP=Q 的整数的整数m,0mord(P)1，称为椭称为椭圆曲线上的离散对数问题（圆曲线上的离散对数问题（Elliptic Curve Discrete logarithm problem）。）。65谢谢观赏2019-8-26椭圆曲线上的离散对数定义10 设G是椭圆曲线 (1椭圆曲线上的椭圆曲线上的ElGamal密码体制密码体制 在使用一个椭圆曲线密码体制时，我们首先需要将发在使用一个椭圆曲线密码体制时，我们首先需要将发送的明文送的明文m编码为椭圆曲线上的点编码为椭圆曲线上的点 ，然，然后再对点后再对点 做加密变换，在解密后还得将做加密变换，在解密后还得将 逆向逆向译码才能获得明文。下面对椭圆曲线上的译码才能获得明文。下面对椭圆曲线上的ElGamal密密码体制进行介绍。码体制进行介绍。u 密钥生成密钥生成 在椭圆曲线在椭圆曲线 (a,b)上选取一个阶为上选取一个阶为n（n为一个大素数）的生成元为一个大素数）的生成元P。随机选取整数。随机选取整数x(1xn)，计算，计算Q=xP。公钥为。公钥为Q，私钥为，私钥为x。现代密码学现代密码学66谢谢观赏2019-8-26 1椭圆曲线上的ElGamal密码体制现代密码学66谢谢观 现代密码学u加密加密 为了加密为了加密 ，随机选取一个整数，随机选取一个整数k,1kn，计算：，计算：,则密文则密文c=()。u解密解密 为了解密一个密文为了解密一个密文c=()，计算：，计算：攻击者要想从攻击者要想从c=()计算出计算出 ，就必须知，就必须知道道k。而要从。而要从P和和kP中计算出中计算出k将面临求解椭圆将面临求解椭圆曲线上的离散对数问题。曲线上的离散对数问题。67谢谢观赏2019-8-26加密 为了加密 ，随机选取一个整数k,1kn，2椭圆曲线密码体制的优点椭圆曲线密码体制的优点与基于有限域上的离散对数问题的公钥密码体制与基于有限域上的离散对数问题的公钥密码体制相比，椭圆曲线密码体制有如下优点：相比，椭圆曲线密码体制有如下优点：安全性高安全性高 密钥长度小密钥长度小 算法灵活性好算法灵活性好现代密码学现代密码学68谢谢观赏2019-8-262椭圆曲线密码体制的优点现代密码学68谢谢观赏2019-8习题u1为什么对于长消息来说，最好是先采用公钥密码为什么对于长消息来说，最好是先采用公钥密码算法来传输一个对称密钥，然后再用该对称密钥来传算法来传输一个对称密钥，然后再用该对称密钥来传递消息？递消息？u2RSA公钥密码体制、公钥密码体制、ElGamal公钥密码体制、公钥密码体制、Rabin公钥密码体制和椭圆曲线公钥密码体制的安全公钥密码体制和椭圆曲线公钥密码体制的安全性依据是什么？性依据是什么？u3在在RSA密码体制中，已知素数密码体制中，已知素数p=3，q=11，公，公钥钥e=7，试计算私钥，试计算私钥d并给出对明文并给出对明文m=5的加密和解的加密和解密过程。密过程。现代密码学现代密码学69谢谢观赏2019-8-26习题1为什么对于长消息来说，最好是先采用公钥密码算法来传输 现代密码学u4在在ElGamal密码体制中，设素数密码体制中，设素数p=71，本原元，本原元g=7：u 如果接收者如果接收者B的公钥为的公钥为yB=3，发送者，发送者A随机选择整数随机选择整数k=2，求明文，求明文m=30所对应的所对应的密文。密文。u 如果发送者如果发送者A选择另一个随机整数选择另一个随机整数k，使，使得明文得明文m=30加密后的密文为加密后的密文为c=（59,c2），），求求c2。70谢谢观赏2019-8-264在ElGamal密码体制中，设素数p=71，本原元g=u5在在Rabin密码体制中，密码体制中，p=127,q=131，试给出对明文试给出对明文m=4410的加密和解密过程。的加密和解密过程。u6在椭圆曲线上的在椭圆曲线上的ElGamal密码体制中，设密码体制中，设椭圆曲线为椭圆曲线为 (1,6)，生成元，生成元P=(2,7)，接收，接收者的私钥者的私钥x=7。u 求接收者的公钥求接收者的公钥Q。u 发送者欲发送消息发送者欲发送消息 =(10,9)，选择随机，选择随机数数k=3，求密文，求密文c。u 给出接收者从密文给出接收者从密文c恢复消息恢复消息 的过程。的过程。现代密码学现代密码学71谢谢观赏2019-8-265在Rabin密码体制中，p=127,q=131，试 现代密码学72谢谢观赏2019-8-2672谢谢观赏2019-8-26