北京大学网络信息安全课件-消息验证与数字签名.ppt

,网络与信息安全 第四讲 密码学基础(三) 王 昭 北京大学信息科学技术学院 软件研究所-信息安全研究室 ,2003年春季北京大学硕士研究生课程,回顾上次课的内容,分组密码的操作模式 实用中数据格式的多样性 安全的工作模式 分组密码的分析方法 现代常规分组加密算法 Triple DES RC5、RC6 AES 加密的位置： 链路方式和端到端的方式,讨论议题,随机数的产生 密钥分配 公钥密码算法 Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC,随机数（Random number）,随机数用途，重要的角色，例如 认证过程中，避免重放攻击 会话密钥 RSA公钥算法 随机数的基本特点 随机性 均匀分布，有大量的测试方案 独立性，难以测试，只能测试足够独立 不可预测性,Random number generation,真正的随机数难以产生 伪随机数 线性同余法 Xn+1 = (aXn+c) mod m m 模数 m0 231 a 乘数 0am a=75=16807 c 增量 0 cm X0 种子 0 X0m 线性同余伪随机数缺乏不可预测性,基于密码的随机数产生,循环加密 DES输出反馈方式 ANSI X.917 伪随机数产生器 Blum Blum Shub(BBS)产生器,循环加密,DES输出反馈模型,ANSI X9.17,BBS伪随机数产生器,(1)首先选择两个大素数p,q pq 3(mod4) (2)选择s与n互素 通过了“下一位”测试(next-bit test) 不存在多项式时间的算法使得在已知前k位的情况下预测出第k+1位的概率大于0.5 BBS的安全性同样基于分解n的难度,密钥分配（Key Distribution）,保密通信双方需共享密钥 共享密钥要经常更换 A选择密钥并手工传递给B 第三方C选择密钥分别手工传递给A,B 用A,B原有共享密钥传送新密钥 与A,B分别有共享密钥的第三方C传送新密钥给A和/或B N个用户集需要N(N-1)/2个共享密钥 密钥分发中心(Key Distribution Center),Key Distribution Center,每个用户与KDC有共享密钥(Master Key) N个用户,KDC只需分发N个Master Key 两个用户间通信用会话密钥(Session Key) 用户必须信任KDC KDC能解密用户间通信的内容,（1）密钥管理量的困难 传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如: n=100 时， C(100,2)=4,995 n=5000时， C(5000,2)=12,497,500 （2）数字签名的问题 传统加密算法无法实现抗抵赖的需求。,问题的提出,起源,公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, 见 Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126,公开密钥密码的重要特性,加密与解密由不同的密钥完成 加密: XY: Y = EKU(X) 解密: YX: X = DKR(Y) = DKR(EKU(X) 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的) X = DKR(EKU(X) = EKU(DKR(X),基于公开密钥的加密过程,基于公开密钥的鉴别过程,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR) 公钥KU公开,私钥KR保密 AB: Y=EKUb(X) B: DKRb(Y)= DKRb(EKUb(X)=X,用公钥密码实现鉴别,条件: 两个密钥中任何一个都可以用作加密而另一个用作解密 鉴别: AALL: Y=DKRa(X) ALL: EKUa(Y)=EKUa(DKRa(X)=X 鉴别+保密: AB: Z= EKUb(DKRa(X) B: EKUa(DKRb(Z)=X,公钥密钥的应用范围,加密/解密 数字签名(身份鉴别) 密钥交换,基本思想和要求,涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文 公钥算法的条件： 产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的顺序可交换,陷门单向函数,单向陷门函数是满足下列条件的函数f： (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使x=fk-1(y)是不可行的。 (3)存在k，已知k 时,对给定的任何y，若相应的x存在，则计算x使fk-1(x)是容易的。,公钥密码基于的数学难题,背包问题 大整数分解问题（The Integer Factorization Problem,RSA体制） 有限域的乘法群上的离散对数问题 (The Discrete Logarithm Problem, ElGamal体制） 椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem, 类比的ElGamal体制）,Fermat定理,Fermat定理: p素数,a是整数且不能被p整除,则: ap-1 1 mod p 证明: 考虑集合1,2,p-1,对每个数乘以a,得到集合a mod p,2a mod p,(p-1)a mod p,对于p,后者两两不同且都在1与p-1之间,因此两个集合相同,于是: (p-1)! = 12(p-1) (a mod p)(2a mod p)(p-1)a mod p) mod p a2a(p-1)a mod p ap-1(p-1)! mod p 注意到(p-1)!与p互素,因此定理成立. 推论: p素数,a是任意整数,则: ap a mod p,Euler数,Euler数(n)定义为小于n且与n互素的正整数个数 p是素数,(p)=p-1 若n的因子分解为n=Piai, ai0,Pi互不相同,则 (n)= Piai(1-1/Pi) 若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数, (pq)=(p-1)(q-1) Euler定理: 若a与n为互素的正整数,则: a(n) 1 mod n,Euler数和Euler定理,欧拉定理：a (n) 1 (mod n) 其中： a对n必须是互素的； (n) =n(1-1/p1)(1-1/p2)(1-1/pn) p1,p2,pn是r的素数因子 (n) 是n的欧拉函数，它确定1,2,n中有多少个是与n互素的。 例如：20=225，有两个素数2和5，这样， (20) =20(1-1/2)(1-1/5)=8 即20中有8个整数与20是互素的，即它们没有2或5为因子： 1, 3, 7, 9, 11, 13, 17, 19,Euler定理,a(n) 1 mod n 证明: R=x1,x2,x(n)为所有小于n且与n互素的正整数,考虑集合 S=(ax1mod n), (ax2mod n), (ax(n) mod n) (aximod n)与n互素 (aximod n)两两不等: (aximod n) = (axjmod n) ximod n = xjmod n S有(n)个元素 故S也是所有小于n且与n互素的正整数,因此S=R,从而 xi=(aximod n)(axi) mod n (a(n) xi) mod n 注意到xi 与n互素,从而得到结论.,Euler定理推论,推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1 m mod n, 对任意0mn 证明:若m=0或n,结论是显然的;若m与n互素,注意到(n)=(p-1)(q-1),由Euler定理可得到结论;否则m必定是p或者q的倍数,不妨设m=sp,则0sq为正整数,m与q互素,由Euler定理得到: m(q) 1 mod q (m(q)k(p) 1 mod q mk(p-1)(q-1) = tq+1 t是整数 等式两边乘以m=sp,得到: mk(p-1)(q-1)+1 = (tq+1)sp = tspq+sp m mod n,中国剩余定理,中国剩余定理：设自然数m1,m2,mr两两互素，并记N=m1m2mr，则同余方程组 在模N同余的意义下有唯一解。,证明：考虑方程组， (1=i=r) 由于诸mi(1=i=r)两两互素，这个方程组作变量替换，令x=(N/mi)*y，方程组等价于解同余方程： (N/mi)y1(mod mi),若要得到特解yi,只要令 xi=(N/mi)yi 则方程组的解为 x0=b1x1+ b2x2+ + brxr (mod N) 模N意义下唯一。,原根(primitive root),Euler定理表明,对两个互素的整数a,n, a(n) 1 mod n 定义： 素数p的原根定义：如果a是素数p的原根，则数 a mod p, a2 mod p, , ap-1 mod p 是不同的并且包含1到p-1的整数的某种排列。 对任意的整数b，我们可以找到唯一的幂i满足 b=ai mod p 0=i=(p-1),离散对数,若a是素数p的一个原根,则对任意整数b, b0 mod p,存在唯一的整数i, 1i(p-1),使得: bai mod p i称为b以a为基模p的指数(离散对数),记作inda,p(b).容易知道: inda,p(xy)= inda,p(x)+inda,p(y) mod (p) inda,p(xr)= rinda,p(x) mod (p) 离散对数的计算: ygx mod p 已知g,x,p,计算y是容易的 已知y,g,p,计算x是困难的,经典例子,Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC,Diffie-Hellman密钥交换,允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程 算法的安全性依赖于计算离散对数的难度 素数p的原始根定义：如果a是素数p的原始根，则数 a mod p, a2 mod p, , ap-1 mod p 是不同的并且包含1到p-1的整数的某种排列。 对任意的整数b，我们可以找到唯一的幂i满足 b=ai mod p 0=i=(p-1) i 在离散对数算法中称为以a为基的指数 mod p。记为inda,p(b),Diffie-Hellman密钥交换,算法： 双方选择素数p以及p的一个原根a 用户A选择一个随机数Xa p，计算 Ya=aXa mod p 用户B选择一个随机数Xb p，计算 Yb=aXb mod p 每一方保密X值，而将Y值交换给对方 用户A计算出 K=YbXa mod p 用户B计算出 K=YaXb mod p 双方获得一个共享密钥(aXaXbmod p) 素数p以及p的原根a可由一方选择后发给对方,Generate random Xa p Calculate Ya=aXa mod p,Generate random Xb p Calculate Yb=aXb mod p,User A,User B,Ya,Yb,Calculate K=(Yb)Xa mod p,Calculate K=(Ya)Xb mod p,Diffie-Hellman Key Exchange,Diffie-Hellman密钥交换的攻击,replay攻击,中间人攻击图示,Diffie-Hellman密钥交换的攻击,中间人攻击 1 双方选择素数p以及p的一个原根a(假定O知道) 2 A选择Xap,计算Ya=aXa mod p, AB: Ya 3 O截获Ya,选Xo,计算Yo=aXo mod p,冒充AB:Yo 4 B选择Xbp,计算Yb=aXb mod p, BA: Yb 5 O截获Yb,冒充BA:Yo 6 A计算: (Xo)Xa(aXo)XaaXoXa mod p 7 B计算: (Xo)Xb(aXo)XXbaXoXb mod p 8 O计算: (Ya)XoaXaXo mod p, (Yb)XoaXbXo mod p O无法计算出aXaXb mod p O永远必须实时截获并冒充转发,否则会被发现,经典例子,Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC,背包问题,背包问题描述：给定重量分别为a1,a2,an的n个物品,装入一个背包中,要求重量等于一个给定值那么，究竟是那些物品？ 0-1背包问题： 给定一个正整数S和一个背包向量A=(a1,an)，其中ai是正整数，求满足方程 S = aixi 的二进制向量X=(x1,xn)。 这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长,背包问题用于公钥密码学,做法：明文为X，S为密文 奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能 把易解的背包问题修改成难解的背包问题 公开密钥使用难解的背包问题 私钥使用易解的背包问题,易解的背包问题超递增背包,满足下列条件的背包 ai aj (j = 1,i-1) 这样的背包也被称为简单背包 求解 从最大的ai开始，如果S大于这个数，则减去ai, 记xi为1，否则记xi为0 如此下去，直到最小的ai 例如背包序列2, 3, 6, 13, 27, 52 求解70的背包 结果为2, 3, 13, 52 所以，密文70对应的明文为110101,转换背包,简单背包用作私钥 如何产生相应的公钥转换 做法： 选择一个整数 m ai (i = 1,n) 然后选择一个与m互素的整数w，然后 ai = wai (mod m) (i = 1,n) 这里的ai 是伪随机分布的 这样得到的背包是非超递增背包,基于背包问题的公钥密码系统 MH公钥算法,加密 将明文分为长度为n的块X=(x1,xn) 然后用公钥A = (a1 , , an )，将明文变为密文S = E(X) = ai xi 解密 先计算S = w-1S mod m 再求解简单背包问题 S = aixi,Eaxmple-从私钥计算公钥,私钥2,3,6,13,27,52 N=31, m=105 2*31 mod 105= 62 3*31 mod 105=93 6*31 mod 105=81 13*31 mod 105= 88 27*31 mod 105=102 52831 mod 105= 37 公钥62,93,81,88,102,37,Eaxmple-加密,消息=011000 110101 101110 明文: 0 1 1 0 0 0 背包: 62 93 81 88 102 37 密文:93+81=174 011000 对应于93+81=174 110101对应于62+93+88+37=280 101110对应于62+81+88+102=333,Eaxmple-解密,解密者知道2,3,6,13,27,52, n,m 计算n(n-1)=1mod(m) n-1=61 174*61 mod 105=9=3+6, 对应于 011000 280*61 mod 105=70=2+3=13+52,对应于110101 333*61 mod 105=48=2+6+13+27, 对应于101110 因此, 消息=011000 110101 101110,背包密码系统的意义,是第一个公钥密码系统 有较好的理论价值 在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷,经典例子,Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC,RSA算法,1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布 是一种分组加密算法。 明文和密文在0n-1之间,n是一个正整数 应用最广泛的公钥密码算法 只在美国申请专利，且已于2000年9月到期,RSA算法描述,RSA加、解密算法(1978 Rivest,Shamir,Adelman) 分组大小为k, 2k n 2k+1 公开密钥 n（两素数p和q的乘积）（推荐p,q等长） e（与(p-1)(q-1)互素） ed1(mod(p-1)(q-1) 私人密钥 d（e-1 mod(p-1)(q-1) ) 加密 c=me mod n 解密 m=cdmod n,RSA密钥生成原理,令n=pq, pq都是素数,(n)=(p-1)(q-1)是n的Euler数 Euler定理推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1 m mod n, 对任意0mn 只要选择e,d, 满足ed=k(n)+1,即 ed 1 mod (n) d e-1 mod (n) 公钥: KU=e,n, 私钥: KR=d,n,example,（1）若Bob选择了p=101和q113 （2）那么，n=11413, (n)=10011211200； （3）然而1120026527，一个正整数e能用作加密指数，当且仅当e不能被2，5，7所整除。假设Bob选择了e=3533， （4）那么用Euclidean算法将求得： d=e -1 6597(mod 11200), 于是Bob的解密密钥d=6597. （5）Bob在一个目录中公开n=11413和e=3533 （6）现假设Alice想发送明文9726给Bob，她计算： 97263533(mod 11413)=5761，且在一个信道上发送密文5761。 （7）当Bob接收到密文5761时，他用他的秘密解密指数（私钥）d6597进行解密：57616597（mod 11413)=9726,RSA安全性依据,RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知 (n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d. （猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！）,每个合数都可以唯一地分解出素数因子 6 = 2 3 999999 = 3337111337 27641 = 131121 从2 开始试验每一个小于等于27641 的素数。,素数：只能被1和它本身整除的自然数；否则为合数。,整数n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次） 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年,对RSA的攻击方法,1、强力攻击（穷举法）：尝试所有可能的私有密钥 2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解 3、对RSA实现的攻击,90年代大数分解的进程,分解数 尺寸bits 分解日期 分解算法 RSA-100 330 1991.4 二次筛法 RSA-110 364 1992.4 二次筛法 RSA-120 397 1993.6 二次筛法 RSA-129 425 1994.4 二次筛法 RSA-130 430 1996.4 数域筛法 RSA-140 463 1999.2 数域筛法 RSA-155 512 1999.8 数域筛法,RSA-155的分解,1999.8.22，荷兰H.Riele领导的来自6个国家的研究人员组成的团队找到了一个512-bit RSA 密钥的一个素因子 512-bit RSA在电子商务中所占的比例为95% 用了5个月的时间，计算机时间估计为 8000mips years,对RSA的攻击,对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。 对RSA的选择密文攻击 对RSA的公共模攻击 对RSA的小加密指数攻击 对RSA的小解密指数攻击 时间性攻击：取决于解密算法的运算时间,对RSA的选择密文攻击,例1：E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m,使 m=cd mod n 他首先选择随机数r,使rn. 然后用A的公开密钥e计算 x=re mod n y=xc mod n t=r-1 mod n 如果x=re mod n，则 r=xd mod n,现在E让A对y签名，即解密y, A向E发送u=yd mod n 而E计算 tu mod n=r-1yd mod n =r-1xdcd mod n =cd mod n =m,对RSA的选择密文攻击,例2： E 让A对m3签名。他产生两个消息m1和m2，满足 m3=m1m2(mod n) 如果E能让A分别对m1和m2签名，则可以计算m3： m3d=(m1d mod n)( m2d mod n),注意：不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数,对RSA的公共模攻击,一种可能的RSA实现方法是给每个人相同的n,但指数d和e不同。 问题：如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不用任何一个解密密钥来恢复。 令m为明文消息，两个加密密钥为e1，e2,两个密文消息为c1,c2,c1=me1 mod n c2=me2 mod n 由于e1和e2互素，所以可以用扩展的Euclid算法找到r,s使 re1+se2=1, 假设r是负数，可以用扩展的Euclid算法计算c1-1,而 (c1-1)-r*c2s= m mod n,注意:不要让一群用户共享一个模n,对RSA的小加密指数攻击,如果使用一个较小的e值，则进行RSA签名和加密会很快，但也不安全。 如果用相同e值的不同公开密钥加密e(e+1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。 比如：消息为mj,使用同样的指数e, 模数分别为q1,q2,qs（两两互素）,则密文为mjemod q1， mjemod q2， mjemod qs，根据中国剩余定理，m= mjemod q1 q2 qs.可以计算出来，对于较小的e，可以解出mj。 解决办法：加密前将消息与随机值混合，并保证m与n有相同的长度。,对RSA的小解密指数攻击,使用较小的d会产生穷尽解密攻击的可能 当d为n的1/4长度时，而e小于n时，可以恢复d，当e,d是随机选择的时，这种情况很少发生，当e很小时不会发生。 注意：应选择一个大的d值,RSA密码体制的实现,实现的步骤如下：Bob为实现者 (1)Bob寻找出两个大素数p和q (2)Bob计算出n=pq和 (n)=(p-1)(q-1). (3)Bob选择一个随机数e(0e (n)，满足（e， (n)）1 (4)Bob使用辗转相除法计算d=e-1(mod (n) (5)Bob在目录中公开n和e作为她的公开钥。 选好这些参数后，将明文划分成块，使得每个明文报文P长 度m满足0mn。加密P时，计算CPe(mod n)，解密C时计 算PCd(mod n)。由于模运算的对称性，可以证明， 在确定的范围内，加密和解密函数是互逆的。 为实现加密，需要公开(e, n)，为实现解密需要(d, n)。,实现要求,于是要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。 模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n的长度位512比特位.至1996年，建议使用768位的模n。,素数的选取,为了抵抗现有的整数分解算法，对RSA模n的素因子 p和q还有如下要求： (1)|p-q|很大，通常 p和q的长度相同； (2)p-1 和q-1分别含有大素因子p1和q1 (3)P1-1和q1-1分别含有大素因子p2和q2 (4)p+1和q+1分别含有大素因子p3和q3,加密指数e的选取,为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定 e2161，ISO/IEC9796中甚至允许取e3。这时加密速度一般比解密速度快10倍以上。 e2161优于e3之处在于它能够抵抗对RSA的小加密指数攻击,实现中的问题,（1）如何计算ab mod n （2）如何判定一个给定的整数是素数？ （3）如何找到足够大的素数p和q ?,(1) 要点1：(a x b) mod n = (a mod n) x (b mod n) mod n 要点2：a16=aaaaaaaaaaaaaaaa =a2, a4,a8, a16,更一般性的问题：am m的二进制表示为bkbk-1b0, 则 m=2i,i0,c0; d 1 for i k downto 0 do c 2 x c d (d d) mod n if bi = 1 then c c + 1 d (d a) mod n return d,计算am mod n,am mod n = a(2i) mod n = a(2i) mod n,bi0,bi0,检测素数,直接判断一个整数是否为素数是困难的 命题: 如果p是素数,则方程 x2 1 mod p 只有平凡解x 1 mod p. 证明: x2 1 mod p p|(x2-1) p|(x+1)(x-1) p|(x+1),或者p|(x-1) x+1=kp,或者x-1=jp, k,j是整数 x=kp-1,或者x=jp+1 x 1 mod p, 或者x -1 mod p 若方程x2 1 mod p存在的解不是x 1 ，则P不是素数。,(2)目前还没有一个高效的办法，实际中应用最多 Miller and Rabin, WITNESS算法 WITNESS(a,n) 判定n 是否为素数，a是某些小于n的整数,1. 令bkbk-1b0 为(n-1)的二进制表示， 2. d 1 3. for i k downto 0 4. do x d 5. d (d d) mod n 6. if d = 1 and x 1 and x n-1 7. then return TRUE 8. if bi = 1 9. then d (d a) mod n 10. if d 1 11. then return TRUE 12. return FALSE,返回值： TRUE: n一定不是素数 FALSE: n可能是素数,应用： 随机选择a n, 计算s次， 如果每次都返回FALSE， 则这时n是素数的概率为 (1 - 1/2s),(3)通常的办法是随机选取一个大的奇数，然后进行素性检验 1. 随机选一个奇数n (如: 可使用伪随机数发生器) 2. 随机选择一个整数a n 3. 执行概率素数判定测试(如:用WITNESS(a,n),如果n 未测试通过,则拒绝数值n, 转向步骤1 4. 如果n已通过足够的测试, 则接受n, 否则转向步骤2; 说明： 随机选取大约用 ln(N)/2的次数，如 ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。 确定素数p和q以后，只需选取e, 满足gcd(e,(n)=1, 计算 d = e-1 mod (n) （sieve扩展的欧拉算法）,经典例子,Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC,ElGamal加密算法,选择: 一个素数p,p的一个原根r,一个整数a,令s=ra,公开p,r,s,保密a. 对于明文信息x, 加密: 秘密选择随机数k, 计算(rk mod p,xsk mod p)作为密文 解密: (xsk)(rk)a)-1 xrakr-ak x mod p 信息有扩张,经典例子,Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC,椭圆曲线密码介绍,1985年Miller,Koblitz 独立提出 y2+axy+by=x3+cx2+dx+e 曲线上的点连同无穷远点O的集合 运算定义： 若曲线三点在一条直线上,则其和为O O用作加法的单位：O = -O; P+O = P 一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1 = -P2 如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P1