第4章公钥密码.ppt

第4章 公钥密码4.1 数论基础知识数论基础知识4.2 公钥密码的基本概念公钥密码的基本概念4.3 RSA公钥密码公钥密码4.4 ElGamal公钥密码公钥密码4.5 Rabin公钥密码公钥密码4.6 椭圆曲线公钥密码椭圆曲线公钥密码现代密码学现代密码学电子科技大学电子科技大学4.1 数论基础知识数论基础知识现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学素数与互素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 bu定义定义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互素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) )现代密码学现代密码学电子科技大学电子科技大学素数与互素电子科技大学 现代密码学u定义定义4 对于任一整数对于任一整数p (p＞＞1)，若，若p的因子的因子只有只有±1和和±p，则称，则称p为素数，否则称为合数为素数，否则称为合数。

对于任一整数对于任一整数a (a＞＞1)，都可以唯一的分解，都可以唯一的分解为素数的乘积，即：为素数的乘积，即： a= p1×p2×…×pt 其中，其中，p1＜＜p2＜＜…＜＜pt都是素数，都是素数，pi＞＞0 (i=1, 2, …, t)素数与互素u定义定义5 5 设设n n是一正整数，小于是一正整数，小于n n且与且与n n互素的正整数互素的正整数的个数称为欧拉（的个数称为欧拉（EulerEuler）函数，记作）函数，记作 欧拉函数有如下性质：拉函数有如下性质： ① ① 若若n n是素数，则是素数，则 ② ② 若若m m和和n n互素，则互素，则 ③ ③ 如果如果 ：： 其中，其中，p p1 1<

的最大整数定义定义r r为为a a mod mod n n，记作，记作r r   a a mod mod n n如果两个整数两个整数a a和和b b满足：满足： 则称则称a a和和b b模模n n同余，记作同余，记作a a   b b mod mod n n称与与a a模模n n同余的数的全体为同余的数的全体为a a的同余类的同余类现代密码学现代密码学电子科技大学电子科技大学表示向下取整同余及其性质u同余有如下性质同余有如下性质：u①① 若若n|（（a b），则），则a  b mod nu②② 若若a mod n   b mod n，则，则a   b mod nu③③ a   a mod nu④④ 若若a   b mod n，则，则b   a mod nu⑤⑤ 若若a   b mod n，，b   c mod n，则，则a   c mod nu⑥⑥ 若若a   b mod n，，c   d mod n，则，则a+c   b+d (mod n), ac   bd (mod n) 现代密码学现代密码学电子科技大学电子科技大学同余及其性质u一般的，定义一般的，定义Zn为小于为小于n的所有非负整数集合，的所有非负整数集合，即即Zn={0, 1,…, n 1}，称，称Zn为模为模n的同余类的同余类集合。

集合Zn中的加法（中的加法（+）和乘法（）和乘法（ ）都为模）都为模n运算，具有如下性质：运算，具有如下性质： ①① 交换律交换律 (w+x)mod n = (x+w) mod n (w x)mod n = (x w) mod n 现代密码学现代密码学电子科技大学电子科技大学模运算电子科技大学 现代密码学 ②② 结合律结合律 [(w+x)+y] mod n =[w+ (x+y)] mod n [(w x) y] mod n =[w  (x y)] mod n ③③ 分配律分配律 [w (x+y)] mod n =[ (w x)+(w y)] mod n ④④ 单位元单位元 (0+w)mod n =w mod n (1 w)mod n =w mod n 模运算电子科技大学 现代密码学⑤⑤ 加法逆元加法逆元 对对w∈ ∈Zn，存在，存在x∈ ∈Zn，使得，使得w+x   0 mod n，称，称 x为为w的加法逆元，记作的加法逆元，记作x =  w。

⑥⑥ 乘法逆元乘法逆元 设设w∈ ∈Zn，如果存在，如果存在x∈ ∈Zn，使得，使得w x   1 mod n，就说，就说w是可逆的，称是可逆的，称x为为w的乘法逆的乘法逆元，记作元，记作x=w 1 并不是每个元素都有乘法逆元，可以证明并不是每个元素都有乘法逆元，可以证明w∈ ∈Zn是可逆的，当且仅当是可逆的，当且仅当gcd (w, n)=1如果w是可逆的，则可以定义除法：是可逆的，则可以定义除法：模运算u定理1 [费马（Fermat）定理] 设设p为素数，为素数，a是正整数且是正整数且gcd (a, p) =1，则，则ap 1   1 mod p如果a是任一正整数，则是任一正整数，则ap   1 mod pu定理2 [欧拉定理]若若gcd (a, n) =1，则：，则：其中其中 是欧拉函数是欧拉函数 .现代密码学现代密码学电子科技大学电子科技大学费马定理及欧拉定理电子科技大学 现代密码学u定理3 [中国剩余定理]设设m1, m2, …, mk是两两互是两两互素的正整数，素的正整数，a1, a2, …, ak是任意是任意k个整数，则同个整数，则同余方程组：余方程组： 模模M = m1m2…mk有唯一解：有唯一解：其中，其中，Mi=M/mi，，yi=Mi -1 mod mi, i=1, 2, …, k。

中国剩余定理电子科技大学 现代密码学离散对数u求模下的整数幂求模下的整数幂Ø根据欧拉定理，若根据欧拉定理，若gcd(a,n)=1,则则af(f(n) ≡1 mod n考虑一般考虑一般a am m ≡1 mod n1 mod n, 如果如果a,na,n互素，至少互素，至少有一个整数有一个整数m m满足这一方程称满足这一方程的满足这一方程称满足这一方程的最小正整数最小正整数m m为模为模n n下下a a的的阶阶Ø例：例：a=7,n=19. 7a=7,n=19. 71 1 ≡7 mod 19, 7 72 2 ≡11 mod 19, 7 73 3 ≡1 mod 19,所以所以7模模19的阶为的阶为3从幂次为从幂次为4开始出现循环，循环周期与元素的阶相同开始出现循环，循环周期与元素的阶相同电子科技大学 现代密码学离散对数u定理：设定理：设a的阶为的阶为m，则，则a ak k≡1mod n≡1mod n的充分必要条的充分必要条件是件是k k是是m m的倍数u推论：推论：a a的阶整除的阶整除j j(n)(n)u本原根：本原根：a a的阶的阶m m等于等于j j(n)(n)，，a a为为n n的本原根。

的本原根u如果如果a a是是n n的本原根，的本原根，a a1 1,a,a2 2,...,a ,...,a j j(n)(n)在模在模n n下互不下互不相同且与相同且与n n互素u本原根不唯一本原根不唯一u并非所有元素都有本原根，仅有以下形式的整数并非所有元素都有本原根，仅有以下形式的整数才有本原根：才有本原根：2 2，，4 4，，p pa a,2p,2pa a, p, p是奇素数是奇素数电子科技大学 现代密码学离散对数u指标指标Øy=ay=ax x(a>0,a≠1)(a>0,a≠1)的逆函数称为以的逆函数称为以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中所有值，且每个值只出现一次中所有值，且每个值只出现一次对任一对任一b∈{1,…,p-1}b∈{1,…,p-1}，都存在唯一的，都存在唯一的i(1i(1≤≤i i ≤≤p)p)，使，使b≡ab≡ai i mod p mod pi i称为模称为模p p下以下以a a为底为底b b的的指标指标，记为，记为i=indi=inda,pa,p(d)(d)电子科技大学 现代密码学离散对数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)=[r×inda,p(y)] mod j j(p(p) ) 后两个性质基于下列结论后两个性质基于下列结论 若若a az z≡a≡aq q mod p ,a mod p ,a和和p p互素，则互素，则z ≡q mod z ≡q mod j j (p)(p)u定义定义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）。

现代密码学现代密码学电子科技大学电子科技大学二次剩余4.2 公钥密码的基本概念现代密码学现代密码学电子科技大学电子科技大学 现代密码学电子科技大学19761976年，年，DiffieDiffie和和HellmanHellman在在““密码学的新方向密码学的新方向（（New Direction in CryptographyNew Direction in Cryptography））””一文中首次一文中首次提出了公钥密码体制（提出了公钥密码体制（public key cryptosystempublic key cryptosystem））的思想 公钥密码体制的概念是为了解决传统密码系统中最公钥密码体制的概念是为了解决传统密码系统中最困难的两个问题而提出的，这两个问题是困难的两个问题而提出的，这两个问题是密钥分配密钥分配和和数字签名数字签名 4.2 公钥密码的基本概念现代密码学现代密码学电子科技大学电子科技大学4.2.1 公钥密码体制的原理公钥密码体制的原理u公钥密码体制在加密和解密时使用不同的公钥密码体制在加密和解密时使用不同的密钥，加密密钥简称公钥（密钥，加密密钥简称公钥（public keypublic key），），解密密钥简称私钥（解密密钥简称私钥（private keyprivate key）。

公钥）公钥是公开信息，不需要保密，私钥必须保密是公开信息，不需要保密，私钥必须保密给定公钥，要计算出私钥在计算上是不可给定公钥，要计算出私钥在计算上是不可行的u公钥密码体制有两种基本模型，一种是加公钥密码体制有两种基本模型，一种是加密模型，另一种是认证模型密模型，另一种是认证模型 现代密码学现代密码学电子科技大学电子科技大学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 BB B收到密文收到密文c c后，后，利用自己的私钥利用自己的私钥SKSKB B解密，表示为解密，表示为m m = =D D ( (SKSKB B, , c c) )，，其中其中D D是解密算法。

是解密算法现代密码学现代密码学电子科技大学电子科技大学加密模型加密模型发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmm’SK’B电子科技大学 现代密码学认证模型认证模型u（（2）认证模型如图所示，）认证模型如图所示，A首先用自己首先用自己的私钥的私钥SKA对消息对消息m加密，表示为加密，表示为c=E (SKA, m)，然后发送，然后发送c给给BB收到密文收到密文c后，后，利用利用A的公钥的公钥PKA对对c解密，表示为解密，表示为m=D (PKA, c)由于是用由于是用A的私钥对消息加密，的私钥对消息加密，只有只有A才能做到，才能做到，c就可以看做是就可以看做是A对对m的数的数字签名此外，没有字签名此外，没有A的私钥，任何人都不的私钥，任何人都不能篡改能篡改m，所以上述过程获得了对消息来源，所以上述过程获得了对消息来源和数据完整性的认证和数据完整性的认证电子科技大学 现代密码学发送者A加密算法（签名）SKA密钥源PKA解密算法（验证）接收者B密码分析员mcmSK’A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) )则是容易的则是容易的现代密码学现代密码学电子科技大学电子科技大学u（1）大整数分解问题（大整数分解问题（factorization problem）） 若已知两个大素数若已知两个大素数p和和q，求，求n = pq是是容易的，只需一次乘法运算，而由容易的，只需一次乘法运算，而由n，求，求p和和q则是困难的，这就是大整数分解问题则是困难的，这就是大整数分解问题现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u（2）离散对数问题（离散对数问题（discrete logarithm discrete logarithm problemproblem）） 给定一个大素数给定一个大素数p p，，p p 1 1含另一含另一大素数因子大素数因子q q，则可构造一个乘法群，它是，则可构造一个乘法群，它是一个一个p p 1 1阶循环群。

设阶循环群设g g是的一个生成元，是的一个生成元，1 1＜＜g g＜＜p 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成成立则是困难的，这就是离散对数问题立则是困难的，这就是离散对数问题电子科技大学 现代密码学u（3）多项式求根问题多项式求根问题 有限域有限域GF（（p）上的一个多项式：）上的一个多项式： 已知已知 , p和和x，求，求y是容易的，是容易的，而已知而已知y, ，求，求x则是困难的，这则是困难的，这就是多项式求根问题就是多项式求根问题 u（5）判断判断Diffie-Hellman问题（问题（decision Diffie-Hellman problem, DDHP）） 给定素数给定素数p，令，令g是的一个生成元已知是的一个生成元已知 , , 判断等式：判断等式：z=xy mod p 是否成是否成立，这就是立，这就是判断性判断性Diffie-Hellman问题。

问题现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u（6）二次剩余问题（二次剩余问题（quadratic residue problem）） 给定一个合数给定一个合数n和整数和整数a，判断，判断a是否为是否为mod n的二次剩余，这就是二次剩余问题在的二次剩余，这就是二次剩余问题在n的分解未的分解未知时，求知时，求   a mod n的解也是一个困难问题的解也是一个困难问题电子科技大学 现代密码学u（7）背包问题（背包问题（knapsack problem）） 给定向量给定向量A= ( ) ( 为正整数为正整数)和和x = ( ) ( ∈ ∈{0,1})，求和式：，求和式： 是容易的，而由是容易的，而由A和和S，求，求x则是困难的，这就是则是困难的，这就是背包问题，又称子集和问题背包问题，又称子集和问题电子科技大学 现代密码学4.3 RSA公钥密码u1．密钥生成．密钥生成①① 选取两个保密的大素数选取两个保密的大素数p和和q。

②② 计算计算n = pq, ，其中，其中 是是n的欧拉函数值的欧拉函数值③③ 随机选取整数随机选取整数e，满足，满足1＜＜e＜＜ ，且，且 ④④ 计算计算d，满足，满足 ⑤⑤ 公钥为公钥为(e,n)，私钥为（，私钥为（d, n）4.3.1 RSA算法描述现代密码学现代密码学电子科技大学电子科技大学u2 2．加密．加密首先对明文进行比特串分组，使得每个分组首先对明文进行比特串分组，使得每个分组对应的十进制数小于对应的十进制数小于n n，然后依次对每个，然后依次对每个分组分组m m做一次加密，所有分组的密文构成做一次加密，所有分组的密文构成的序列即是原始消息的加密结果即的序列即是原始消息的加密结果即m m满满足足0≤0≤m m＜＜n n，则加密算法为：，则加密算法为：c c为密文，且为密文，且0≤0≤c c＜＜n n现代密码学现代密码学电子科技大学电子科技大学4.3.1 RSA算法描述u3．解密．解密 对于密文对于密文0≤c＜＜n，解密算法为：，解密算法为：现代密码学现代密码学电子科技大学电子科技大学4.3.1 RSA算法描述4.3.2 RSA的安全性1．．数学攻击数学攻击用数学方法攻击用数学方法攻击RSARSA的途径有三种：的途径有三种：① ① 分解分解n n为两个素因子。

这样就可以计算为两个素因子这样就可以计算 从而计算出私钥从而计算出私钥 ② ② 直接确定直接确定 而不先确定而不先确定p p和和q q这同样可以确定样可以确定 . . ③ ③ 直接确定直接确定d d而不先确定而不先确定 现代密码学现代密码学电子科技大学电子科技大学u2．穷举攻击．穷举攻击 像其他密码体制一样，像其他密码体制一样，RSA抗穷举攻击的方法也抗穷举攻击的方法也是使用大的密钥空间，这样看来是是使用大的密钥空间，这样看来是e和和d的位数越的位数越大越好但是由于在密钥生成和加密大越好但是由于在密钥生成和加密/解密过程都解密过程都包含了复杂的计算，故密钥越大，系统运行速度越包含了复杂的计算，故密钥越大，系统运行速度越慢u3．计时攻击．计时攻击 计时攻击是通过记录计算机解密消息所用的时间来计时攻击是通过记录计算机解密消息所用的时间来确定私钥这种攻击不仅可以用于攻击确定私钥。

这种攻击不仅可以用于攻击RSA，还，还可以用于攻击其他的公钥密码系统可以用于攻击其他的公钥密码系统现代密码学现代密码学电子科技大学电子科技大学4.3.2 RSA的安全性的安全性电子科技大学 现代密码学u4. 选择密文攻击选择密文攻击 RSA易受选择密文攻击（易受选择密文攻击（chosen ciphertext attack））4.3.2 RSA的安全性的安全性4.4 ElGamal公钥密码现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学1．密钥生成．密钥生成①① 选取大素数选取大素数p，且要求，且要求p 1有大素数因子有大素数因子是一个本原元是一个本原元②② 随机选取整数随机选取整数x,1≤x≤p 2，计算，计算 ③③ 公钥为公钥为y，私钥为，私钥为x4.4.1 ElGamal算法描述现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学 p p和和g g是公共参数，被所有用户所共享，是公共参数，被所有用户所共享，这一点与这一点与RSARSA算法是不同的。

另外，在算法是不同的另外，在RSARSA算法中，每个用户都需要生成两个大素数算法中，每个用户都需要生成两个大素数来建立自己的密钥对（这是很费时的工作）来建立自己的密钥对（这是很费时的工作），而，而ElGamalElGamal算法只需要生成一个随机数和算法只需要生成一个随机数和执行一次模指数运算就可以建立密钥对执行一次模指数运算就可以建立密钥对 2．加密．加密对于明文，首先随机选取一个整数对于明文，首先随机选取一个整数k,1≤k≤p 2，然，然后计算：后计算： , 则密文则密文c =（（ c1, c2）3．解密．解密为了解密一个密文为了解密一个密文c=（（c1, c2），计算：），计算：现代密码学现代密码学电子科技大学电子科技大学4.4.2 ElGamal的安全性 在在ElGamal公钥密码体制中，公钥密码体制中，y = mod p从公开参数公开参数g和和y求解私钥求解私钥x需要求解离散对数问题需要求解离散对数问题目前还没有找到一个有效算法来求解有限域上的目前还没有找到一个有效算法来求解有限域上的离散对数问题因此，离散对数问题。

因此，ElGamal公钥密码体制的公钥密码体制的安全性是基于有限域上离散对数问题的困难性安全性是基于有限域上离散对数问题的困难性为了抵抗已知的攻击，为了抵抗已知的攻击，p应该选取应该选取至少至少160位位以上以上的十进制数，并且的十进制数，并且p 1至少应该有一个大的素因至少应该有一个大的素因子现代密码学现代密码学电子科技大学电子科技大学4.5 Rabin公钥密码现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u1．密钥生成．密钥生成选取两个大素数选取两个大素数p和和q，满足，满足p   q   3 mod 4，，计算计算n=pq，则公钥为，则公钥为n，私钥为（，私钥为（p, q）u2．加密．加密对于明文对于明文m（（0≤m＜＜n），计算密文），计算密文:c = mod n4.5.1 Rabin算法描述算法描述现代密码学现代密码学电子科技大学电子科技大学u3．解密．解密为了解密一个密文为了解密一个密文c，利用中国剩余定理求解同余方，利用中国剩余定理求解同余方程组，计算：程组，计算： , , 然后选择整数然后选择整数a = q (q 1 mod p)和和b=p (p 1 mod q)，四个可能的解为：，四个可能的解为： , ，， 现代密码学现代密码学电子科技大学电子科技大学4.5.1 Rabin算法描述算法描述 现代密码学电子科技大学3．解密．解密由中国剩余定理知解x2≡c mod n, 等价于解方程组由于p≡q≡3 mod 4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即4.5.1 Rabin算法描述算法描述 现代密码学电子科技大学经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。

为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等 现代密码学电子科技大学下面证明，当p≡q≡3 mod 4，两个方程x2≡c mod p,x2≡c mod q的平方根都可容易地求出 现代密码学电子科技大学雅克比符号？ 现代密码学电子科技大学所以 和 是方程x2≡c mod p的两个根同理 和 是方程x2≡c mod q的两个 根由4.1.8节知，求解方程x2≡a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解4.6 椭圆曲线公钥密码现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u椭圆曲线并非椭圆，之所以称为椭圆曲线是因椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程相似一般为它的曲线方程与计算椭圆周长的方程相似一般的，椭圆曲线指的是由维尔斯特拉斯的，椭圆曲线指的是由维尔斯特拉斯（（Weierstrass）方程：）方程：4.5.1 实数域上的椭圆曲线现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u所确定的曲线，它是由方程的全体解（所确定的曲线，它是由方程的全体解（x, y）再）再加上一个无穷远点加上一个无穷远点O构成的集合，其中构成的集合，其中a、、b、、c、、d、、e是满足一些简单条件的实数，是满足一些简单条件的实数，x和和y也在实数也在实数集上取值。

上述曲线方程可以通过坐标变换转化集上取值上述曲线方程可以通过坐标变换转化为下述形式：为下述形式：4.5.1 实数域上的椭圆曲线电子科技大学 现代密码学u由它确定的椭圆曲线常记为由它确定的椭圆曲线常记为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））=P P=O现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学 ③③设设P和和Q是椭圆曲线上是椭圆曲线上x坐标不同的两点，坐标不同的两点，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 以上定义的加法具有加法运算的一般性质，如以上定义的加法具有加法运算的一般性质，如交换律、结合律等交换律、结合律等现代密码学现代密码学电子科技大学电子科技大学u2．加法的代数描述．加法的代数描述 对于椭圆曲线上不互为逆元的两点P = (x1, y1)和Q= (x2, y2)，S = P+Q = (x3, y3)由以下规则确定：u其中现代密码学现代密码学电子科技大学电子科技大学4.6.2 有限域上的椭圆曲线u椭圆曲线密码体制使用的是有限域上的椭圆曲线，椭圆曲线密码体制使用的是有限域上的椭圆曲线，即变量和系数均为有限域中的元素有限域即变量和系数均为有限域中的元素有限域GF (p)上的椭圆曲线是指满足方程：上的椭圆曲线是指满足方程：u的所有点的所有点 (x, y)再加上一个无穷远点再加上一个无穷远点O构成的集合，构成的集合，其中，其中，a、、b、、x和和y均在有限域均在有限域GF (p)上取值，上取值，p是素数。

我们把该椭圆曲线记为是素数我们把该椭圆曲线记为 (a, b)该椭圆曲线只有有限个点，其个数曲线只有有限个点，其个数N由由Hasse定理确定定理确定现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u定理4 （Hasse定理）设设E是有限域是有限域GF (p)上上的椭圆曲线，的椭圆曲线，N是是E上点的个数，则上点的个数，则4.6.3 椭圆曲线的密码体制现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学4.6.3 椭圆曲线的密码体制定义9 椭圆曲线椭圆曲线 (a, b)上点上点P的阶是指满足：的阶是指满足：的最小正整数，记为的最小正整数，记为ord (P)，其中，其中O是无穷远点是无穷远点现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学椭圆曲线上的离散对数u定义10 设设G是椭圆曲线是椭圆曲线 (a, b)上的一个循环子上的一个循环子群，群，P是是G的一个生成元，的一个生成元，Q∈ ∈G已知P和和Q，求满，求满足：足：mP = Q 的整数的整数m,0≤m≤ord (P) 1，，称为椭称为椭圆曲线上的离散对数问题（圆曲线上的离散对数问题（Elliptic Curve Discrete logarithm problem）。

 1．椭圆曲线上的．椭圆曲线上的ElGamal密码体制密码体制 在使用一个椭圆曲线密码体制时，我们首先需要将发在使用一个椭圆曲线密码体制时，我们首先需要将发送的明文送的明文m编码为椭圆曲线上的点编码为椭圆曲线上的点 ，然，然后再对点后再对点 做加密变换，在解密后还得将做加密变换，在解密后还得将 逆向逆向译码才能获得明文下面对椭圆曲线上的译码才能获得明文下面对椭圆曲线上的ElGamal密密码体制进行介绍码体制进行介绍u 密钥生成密钥生成 在椭圆曲线在椭圆曲线 (a, b)上选取一个阶为上选取一个阶为n（（n为一个大素数）的生成元为一个大素数）的生成元P随机选取整数随机选取整数x (1＜＜x＜＜n)，计算，计算Q=xP公钥为Q，私钥为，私钥为x现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u加密加密 为了加密为了加密 ，随机选取一个整数，随机选取一个整数k,1＜＜k＜＜n，计算：，计算： , 则密文则密文c = ( )u解密解密 为了解密一个密文为了解密一个密文c = ( )，计算：，计算：攻击者要想从攻击者要想从c = ( )计算出计算出 ，就必须知，就必须知道道k。

而要从而要从P和和kP中计算出中计算出k将面临求解椭圆将面临求解椭圆曲线上的离散对数问题曲线上的离散对数问题 2．椭圆曲线密码体制的优点椭圆曲线密码体制的优点与基于有限域上的离散对数问题的公钥密码体制与基于有限域上的离散对数问题的公钥密码体制相比，椭圆曲线密码体制有如下优点：相比，椭圆曲线密码体制有如下优点：①① 安全性高安全性高②② 密钥长度小密钥长度小③③ 算法灵活性好算法灵活性好现代密码学现代密码学电子科技大学电子科技大学习题u1．为什么对于长消息来说，最好是先采用公钥密码．为什么对于长消息来说，最好是先采用公钥密码算法来传输一个对称密钥，然后再用该对称密钥来传算法来传输一个对称密钥，然后再用该对称密钥来传递消息？递消息？u2．．RSA公钥密码体制、公钥密码体制、ElGamal公钥密码体制、公钥密码体制、Rabin公钥密码体制和椭圆曲线公钥密码体制的安全公钥密码体制和椭圆曲线公钥密码体制的安全性依据是什么？性依据是什么？u3．在．在RSA密码体制中，已知素数密码体制中，已知素数p =3，，q =11，公，公钥钥e=7，试计算私钥，试计算私钥d并给出对明文并给出对明文m=5的加密和解的加密和解密过程。

密过程现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学u4．在．在ElGamal密码体制中，设素数密码体制中，设素数p =71，本原元，本原元g=7：：u①① 如果接收者如果接收者B的公钥为的公钥为yB=3，发送者，发送者A随机选择整数随机选择整数k=2，求明文，求明文m=30所对应的所对应的密文u②② 如果发送者如果发送者A选择另一个随机整数选择另一个随机整数k，使，使得明文得明文m=30加密后的密文为加密后的密文为c=（（59, c2），），求求c2u5．在．在Rabin密码体制中，密码体制中，p =127, q =131，，试给出对明文试给出对明文m=4410的加密和解密过程的加密和解密过程u6．在椭圆曲线上的．在椭圆曲线上的ElGamal密码体制中，设密码体制中，设椭圆曲线为椭圆曲线为 (1, 6)，生成元，生成元P= (2, 7)，接收，接收者的私钥者的私钥x=7u①① 求接收者的公钥求接收者的公钥Qu②② 发送者欲发送消息发送者欲发送消息 = (10, 9)，选择随机，选择随机数数k=3，求密文，求密文cu③③ 给出接收者从密文给出接收者从密文c恢复消息恢复消息 的过程。

的过程 现代密码学现代密码学电子科技大学电子科技大学。