第4章-公钥密码

1、现代密码理论现代密码理论-UESTC第第4章章 公钥密码公钥密码1.公钥密码体制简介公钥密码体制简介2. 数论简介数论简介3. RSA算法算法4. Rabin密码体制密码体制5. 椭圆曲线密码体制椭圆曲线密码体制现代密码理论现代密码理论-UESTC对称算法对称算法 知道如何加密知道如何加密=知道如何解密知道如何解密 知道如何验证，就基本知道如何假冒知道如何验证，就基本知道如何假冒 知其然就知其所以然知其然就知其所以然 加密和解密过程中的密钥是一致的加密和解密过程中的密钥是一致的加密算法明文密文不安全信道解密算法明文密钥密钥现代密码理论现代密码理论-UESTC对称算法不适合于大规模使用对称算法不

2、适合于大规模使用 未曾谋面，缺少以前的联系未曾谋面，缺少以前的联系 难以密钥协商难以密钥协商 用户数目增多用户数目增多 分发和管理密钥（分发和管理密钥（Key Management） 困难（多，变）困难（多，变） 安全性问题（密钥泄露）安全性问题（密钥泄露） 性能问题（瓶颈）性能问题（瓶颈）现代密码理论现代密码理论-UESTC密钥交换协议m1m2skskAlice BobOscar 我们将讨论我们将讨论Alice 和和Bob怎样通过交换协议共享一个密钥怎样通过交换协议共享一个密钥.现代密码理论现代密码理论-UESTCDiffie-Hellman密钥交换密钥交换 Diffie-Hellman密钥

3、交换密钥交换 公开参数：大素数公开参数：大素数P，本原元，本原元a 协议安全的基本思想协议安全的基本思想: 如果敌手能攻破某协议的安全性如果敌手能攻破某协议的安全性, 那么我们可以利用该敌手攻破一公认的数学难题那么我们可以利用该敌手攻破一公认的数学难题. 现代密码理论现代密码理论-UESTC非对称算法非对称算法/公钥算法公钥算法 非对称密码（公钥密码）算法想法的提出非对称密码（公钥密码）算法想法的提出 1976年，年，Diffie、Hellman在在密码学的新方向密码学的新方向（New Directions in Cryptography）一文中提）一文中提出来）出来） 非对称密码，也称为公钥

4、密码算法。非对称密码，也称为公钥密码算法。 Asymmetrical cryptography Public key cryptography现代密码理论现代密码理论-UESTC非对称算法非对称算法/公钥算法公钥算法 知道加密，但不知道解密知道加密，但不知道解密 原理：数学计算巨大（原理：数学计算巨大（RSA） 提供数字签名提供数字签名 提供秘密密钥的密钥管理提供秘密密钥的密钥管理 公开公钥，秘密保存私钥公开公钥，秘密保存私钥现代密码理论现代密码理论-UESTC2021-11-188 公钥密码体制的原理公钥体制(Public key system) (Diffie和Hellman,1976)

5、每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点： 加密和解密分开 多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信） 只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。 无需事先分配密钥。现代密码理论现代密码理论-UESTC2021-11-189 公钥体制加密 公钥体制加、解密公钥体制加、解密 mm=D D ( (c c)=)=D DSKBSKB ( (E EPKBPKB( (mm) )安全保障安全保障从公开钥从公开钥PKPKB B和密文和密文c c要推出明文要推出明文mm或解密钥或解密

6、钥SKSKB B在计算上是在计算上是不可行的。不可行的。由于任一用户都可用用户由于任一用户都可用用户B B的公开钥的公开钥PKPKB B 向他发送机密消息，向他发送机密消息，因而密文因而密文c c不具有认证性。不具有认证性。发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmmSKB现代密码理论现代密码理论-UESTC基于公钥的加密过程基于公钥的加密过程现代密码理论现代密码理论-UESTC1.1 公钥密码体制简介公钥密码体制简介对称密码体制：对称密码体制：保密性，运算速度快，适合加密保密性，运算速度快，适合加密 大量数据大量数据公钥密码体制：公钥密码体制：保密性，密钥分配，认证；

7、运算保密性，密钥分配，认证；运算 速度慢，适合加密少量数据。如：速度慢，适合加密少量数据。如： 用公钥密码加密传送分组密码的密钥。用公钥密码加密传送分组密码的密钥。(1) 公钥密码体制与对称密码体制比较公钥密码体制与对称密码体制比较:现代密码理论现代密码理论-UESTC公钥密码的理论基础公钥密码的理论基础: 陷门单向函数陷门单向函数单向函数单向函数: 已知已知x, 计算计算y使得使得y=f(x)容易容易; 已知已知y, 计算计算x使得使得y=f(x)是难解的。是难解的。陷门单向函数陷门单向函数: t是与是与f有关的一个参数有关的一个参数 已知已知x, 计算计算y使得使得y=f(x)容易容易;

8、如果不知道如果不知道t，已知已知y, 计算计算x使得使得y=f(x)是难的，是难的， 但知道但知道t时，已知时，已知y, 计算计算x使得使得y=f(x)是容易的。是容易的。 参数参数t称为陷门称为陷门。现代密码理论现代密码理论-UESTC公钥密码算法应满足以下要求公钥密码算法应满足以下要求: 接收方接收方B产生密钥对（产生密钥对（PKB和和SKB）在计算上是在计算上是容易的。容易的。 发方发方A对消息对消息m加密以产生加密以产生密文密文c，即即c=EPKBm在计算上是容易的。在计算上是容易的。 收方收方B用自己的秘密钥对用自己的秘密钥对c解密，即解密，即m=DSKBc在在计算上是容易的。计算上

9、是容易的。公钥密码算法应满足的要求公钥密码算法应满足的要求现代密码理论现代密码理论-UESTC 敌手敌手由由PKB求求SKB在计算上是不可行的。在计算上是不可行的。 敌手由敌手由密文密文c和和PKB恢复明文恢复明文m在计算上是不可在计算上是不可行的。行的。以上要求的本质之处在于要求一个陷门单向函数。以上要求的本质之处在于要求一个陷门单向函数。因此，研究公钥密码算法就是要找出合适的陷门单因此，研究公钥密码算法就是要找出合适的陷门单向函数。向函数。现代密码理论现代密码理论-UESTC （1）大整数分解问题（）大整数分解问题（factorization problem） 若已知两个大素数若已知两个大

10、素数p和和q，求，求n = pq是容易的，是容易的，只需一次乘法运算，而由只需一次乘法运算，而由n，求，求p和和q则是困难的，则是困难的，这就是大整数分解问题。这就是大整数分解问题。 （2）离散对数问题（）离散对数问题（discrete logarithm problem） 给定一个大素数给定一个大素数p，p 1含另一大素数因子含另一大素数因子q，则可构造一个乘法群，它是一个则可构造一个乘法群，它是一个p 1阶循环群。设阶循环群。设g是的一个生成元，是的一个生成元，1gp 1。已知。已知x，求，求y=gx mod p是容易的，而已知是容易的，而已知y、g、p，求，求x使得使得y=gx mod

11、p成立则是困难的，这就是离散对数问题。成立则是困难的，这就是离散对数问题。几个困难问题几个困难问题现代密码理论现代密码理论-UESTC （3）多项式求根问题）多项式求根问题 有限域有限域GF（p）上的一个多项式：）上的一个多项式： 已知已知 , p和和x，求，求y是容易的，而已知是容易的，而已知y, ，求，求x则是困难的，这就是多项式求则是困难的，这就是多项式求根问题。根问题。 011,.,naaa011,.,na aa1110( )modnnnyf xxaxa xap现代密码理论现代密码理论-UESTC （4）二次剩余问题（）二次剩余问题（quadratic residue problem）

12、 给定一个合数给定一个合数n和整数和整数a，判断，判断a是否为是否为mod n的二次剩余，这就是二次剩余问题。在的二次剩余，这就是二次剩余问题。在n的分解未知时，求的分解未知时，求 a mod n的解也是一个的解也是一个困难问题。困难问题。电子科技大学电子科技大学2x现代密码理论现代密码理论-UESTC （5）背包问题（）背包问题（knapsack problem） 给定向量给定向量A= ( ) ( 为正整数为正整数)和和x = ( ) ( 0,1)，求和式：，求和式： 是容易的，而由是容易的，而由A和和S，求，求x则是困难的，这就则是困难的，这就是背包问题，又称子集和问题。是背包问题，又称子

13、集和问题。1 122( )nnsf xa xa xa x12,.,naaaia12,.,nxxxix现代密码理论现代密码理论-UESTC4.2 RSA密码算法密码算法 MIT三位年青学者三位年青学者Rivest，Shamir和和Adleman 在在1978年发现了一种用数论构造双钥体制的方法，年发现了一种用数论构造双钥体制的方法，称作称作MIT体制，后来被广泛称之为体制，后来被广泛称之为RSA体制。体制。 它既可用于加密、又可用于数字签名。它既可用于加密、又可用于数字签名。 RSARSA算法的安全性基于数论中大整数分解的困难算法的安全性基于数论中大整数分解的困难性性。现代密码理论现代密码理论-

14、UESTC现代密码理论现代密码理论-UESTC现代密码理论现代密码理论-UESTC一个数学题一个数学题 求求3801的最后两位数。的最后两位数。现代密码理论现代密码理论-UESTC(1). 费尔玛定理费尔玛定理定理定理1 (Fermat)若若p是素数，是素数，a是正整数且是正整数且gcd(a, p)=1，则则ap-11 mod p。Fermat定理也可写成如下形式：定理也可写成如下形式： 设设p是素数，是素数，a是是任一正整数，则任一正整数，则apa mod p。(2). 欧拉函数欧拉函数设设n是一正整数，是一正整数，小于小于n且与且与n互素的正整数的个数互素的正整数的个数称为称为n的欧拉函数

15、的欧拉函数，记为，记为(n)。例如：例如： (6)=2 ，(7)=6 ，(8)=4。若若n是素数，则显然有是素数，则显然有(n)=n-1。现代密码理论现代密码理论-UESTC例如：例如： 由由21=37，得，得(21)=(3)(7)=26=12。(3). 欧拉定理欧拉定理定理定理3.（Euler） 若若a和和n互素，则互素，则a(n)1 mod n。欧拉函数的求法：欧拉函数的求法： （1）如果）如果n是素数，则是素数，则?(n)=n-1 （2）npq，其中，其中p，q为素数，则为素数，则?(n)=(p-1)(q-1) （3）12111( )(1)(1).(1)ipppnn现代密码理论现代密码理

16、论-UESTC4.3.1 算法描述算法描述-密钥生成密钥生成 选取两互异大素数选取两互异大素数p p和和q q 计算计算 n n=p pq q 和其欧拉函数值和其欧拉函数值 ( (n n)=()=(p p1)(1)(q q1) 1) 选一整数选一整数e e，1 1 e e ( (n n) )，使得，使得 gcd(gcd( ( (n n), ), e e)=1)=1 在模在模 ( (n n) )下，计算下，计算e e的逆元的逆元d d. . 即求即求d, d, 使得使得 e ed d 1 1 mod mod ( (n n) ) 以以( (n n，e e ) )为公钥。为公钥。d d 为秘密钥。为

17、秘密钥。 ( (p p, , q q不再需要，可以销毁。不再需要，可以销毁。) ) 现代密码理论现代密码理论-UESTC 加密 将明文分组，各组对应的十进制数mn, 计算 c =E(m) me mod n 解密 m = D(c) cd mod n现代密码理论现代密码理论-UESTCRSA算法算法解密过程的正确性解密过程的正确性。证明：证明： 由加密过程知由加密过程知cme mod n，所以所以cd mod nmed mod n mk(n)+1 mod n分两种情况：分两种情况： m与与n互素互素，则由，则由Euler定理得定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m

18、 mod n即即cd mod nm。加密：加密： cme mod n解密：解密：mcd mod n现代密码理论现代密码理论-UESTC由由gcd(m,q)=1及及Euler定理得定理得m(q)1 mod q，所以所以mk(q)1 mod q,mk(q)(p)1 mod q, mk(n)1 mod q因此存在一整数因此存在一整数r，使得使得mk(n)=1+rq，两边同乘以两边同乘以m=cp得得mk(n)+1=m+rcpq=m+rcn即即mk(n)+1m mod n，所以所以cd mod nm。(证毕证毕)qcnm 1 ,1 gcd(m,n)1, 不妨设不妨设 m=cp，现代密码理论现代密码理论-

19、UESTC例例: p=7, q=17. n=pq=119, (n)=(p-1)(q-1)=96。取取e=5，满足满足1e(n)，且且gcd(n),e)=1。确定满足确定满足de=1 mod 96且小于且小于96的的d，因为因为775=385=496+1，故，故d=77。因此公钥为因此公钥为5, 119，私钥为，私钥为77, 119。设明文设明文m=19，则由加密过程得密文为则由加密过程得密文为c195 mod 1192476099 mod 11966解密为解密为6677mod 11919现代密码理论现代密码理论-UESTC1. RSA的加密与解密过程的加密与解密过程 RSA的加密、解密过程都为

20、求一个的加密、解密过程都为求一个整数的整数次整数的整数次幂幂，再取模再取模。如果按其含义直接计算，则中间结果。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。非常大，有可能超出计算机所允许的整数取值范围。而用模运算的性质：而用模运算的性质：(ab) mod n=(a mod n)(b mod n) mod n就可减小中间结果。就可减小中间结果。4.3.2 RSA算法中的计算问题算法中的计算问题现代密码理论现代密码理论-UESTC 再者，考虑如何提高加、解密运算中指数运算的再者，考虑如何提高加、解密运算中指数运算的有效性。例如求有效性。例如求x16，直接计算的话需做

21、直接计算的话需做15次乘法。次乘法。然而如果重复对每个部分结果做平方运算即求然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需则只需4次乘法。次乘法。求求am可如下进行，其中可如下进行，其中a，m是正整数：是正整数： 将将m表示为二进制形式表示为二进制形式bk bk-1b0，即即因此因此12012222kkkbbbbbmaaaaaa 现代密码理论现代密码理论-UESTCd=1；For i=k downto 0 do d=(dd) mod n;if bi=1 then d=(da) mod nreturn d.m=bk2k+bk-12k-1+b12+b012012222k

22、kkbbbbbmaaaaaa 快速指数算法快速指数算法现代密码理论现代密码理论-UESTC2. RSA密钥的产生密钥的产生(1) 两个大素数两个大素数p、q的选取。的选取。 Miller-Rabin算法算法;(2) e的选取和的选取和d的计算。的计算。 选取满足选取满足1e0. 则则存在唯一的整数存在唯一的整数q, r使得使得 a=bq+r, 0 rb现代密码理论现代密码理论-UESTC定理定理 整数整数a, b互素互素 存在整数存在整数 s, t 满足满足 s a + t b =1证证: 必要性显然必要性显然。充分性：已知充分性：已知s a + t b =1，则则a, b互素互素 设设 d=

23、(a, b), 则则d|a, d|b, 有有d | s a + t b =1，则则d=1, 故故a, b互素互素 求乘法逆元：求乘法逆元：如果如果gcd(a, b)=1 ，则则b在在mod a下有乘法逆元下有乘法逆元, 即即存在一存在一x (xa)，使得使得bx1 mod a。现代密码理论现代密码理论-UESTCRSA的安全性的安全性是基于是基于分解大整数的困难性假定分解大整数的困难性假定，如，如果果RSA的模数的模数n被成功地分解为被成功地分解为pq，则立即获得则立即获得(n)=(p-1)(q-1)，从而能够确定从而能够确定e模模(n)的乘法逆元的乘法逆元d，即即de-1 mod (n)，因

24、此攻击成功。因此攻击成功。4.3.3 RSA的安全性的安全性现代密码理论现代密码理论-UESTC 随着人类计算能力的不断提高，原来被认为是不随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。可能分解的大数已被成功分解。RSA129于于1994年年4月被成功分解月被成功分解RSA130于于1996年年4月被成功分解月被成功分解RSA140于于1999年年2月被成功分解月被成功分解RSA155于于1999年年8月被成功分解月被成功分解模数长度应该介于模数长度应该介于1024bit到到2048bit之间之间现代密码理论现代密码理论-UESTC是否有不通过分解大整数的其他攻击途径？

25、是否有不通过分解大整数的其他攻击途径？证明：证明： 由由n直接确定直接确定(n)对对n的分解的分解。（作业）。（作业）由此可见，由此可见，不对不对n进行因式分解而直接计算进行因式分解而直接计算(n)并不比对并不比对n进行因式分解更容易。进行因式分解更容易。现代密码理论现代密码理论-UESTC为保证算法的安全性，还对为保证算法的安全性，还对p和和q提出以下要求：提出以下要求： （1） |p-q|要大。要大。（2）p和和q的长度应该相差不多。的长度应该相差不多。（3） p-1和和q-1都应有大素因子。都应有大素因子。（4） gcd(p-1, q-1)应该很小。应该很小。现代密码理论现代密码理论-U

26、ESTC（1） |p-q|要大要大由由 ，如果，如果|p-q|小，则小，则 也小，因此也小，因此 稍大于稍大于 n ， 稍大于稍大于 。可得。可得n的如下分解步骤：的如下分解步骤： 顺序检查大于顺序检查大于 的每一整数的每一整数x，直到找到一，直到找到一个个x使得使得x2-n是某一整数（记为是某一整数（记为y）的平方。）的平方。 由由x2-n=y2，得，得n=(x+y)(x-y)。222444pqpqpqnpq24pq24pq2pqnn现代密码理论现代密码理论-UESTC（2） p-1和和q-1都应有大素因子都应有大素因子这是因为这是因为RSA算法存在着可能的重复加密攻击算法存在着可能的重复加

27、密攻击法。设攻击者截获密文法。设攻击者截获密文c，可如下进行重复加密：，可如下进行重复加密：2223111modmodmodmodtttttteeeeeeeeeeeeeeeecmmncmmncmmncmmn现代密码理论现代密码理论-UESTC若若 ，即即 ，则有则有 ，即即 ，所以在上述重复加密的倒数第所以在上述重复加密的倒数第2步就已恢复出明文步就已恢复出明文m，这种攻击法只有在，这种攻击法只有在t较小时才是可行的。为抵较小时才是可行的。为抵抗这种攻击，抗这种攻击，p、q的选取应保证使的选取应保证使t很大。很大。1m odtemcn modteemcnmodtemmn1modtecmn现代密

28、码理论现代密码理论-UESTC设设m在模在模n下阶为下阶为k，由，由 得得 ，所以，所以k|(et-1)，即，即et1(mod k)，t取为满足上式的最小值（为取为满足上式的最小值（为e在模在模k下的阶）。又下的阶）。又当当e与与k互素时互素时t|(k)。为使。为使t大，大，k就应大且就应大且(k)应应有大的素因子。又由有大的素因子。又由k|(n)，所以为使，所以为使k大，大，p-1和和q-1都应有大的素因子。都应有大的素因子。modtemmn11 modtemn现代密码理论现代密码理论-UESTC1. 共模攻击共模攻击 在实现在实现RSA时，为方便起见，可能给每一用户相时，为方便起见，可能给

29、每一用户相同的模数同的模数n，虽然加解密密钥不同，然而这样做是虽然加解密密钥不同，然而这样做是不行的。不行的。4.3.4 对对RSA的攻击的攻击现代密码理论现代密码理论-UESTC设两个用户的公开钥分别为设两个用户的公开钥分别为e1和和e2，且且e1和和e2互素，互素，明文消息是明文消息是m，密文分别是密文分别是敌手截获敌手截获c1和和c2后，可如下恢复后，可如下恢复m。用推广的用推广的Euclid算法求出满足算法求出满足re1+se2=1的两个整数的两个整数r和和s，其中一个为负，设为其中一个为负，设为r。再次用再次用推广的推广的Euclid算法求出算法求出 ，由此得由此得11 cnmccc

30、csrsrmod)(21121 nmcnmceemodmod2121 现代密码理论现代密码理论-UESTC2. 低指数攻击低指数攻击 将将RSA同时用于多个用户，然而每个用户的同时用于多个用户，然而每个用户的加密加密指数指数都很小。设都很小。设3个用户的模数分别为个用户的模数分别为ni(i=1,2,3)，当当ij时，时，gcd(ni, nj)=1，否则通过否则通过gcd(ni, nj)有可能有可能得出得出ni 和和nj 的分解。设明文消息是的分解。设明文消息是m，密文分别是密文分别是c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)由中国剩余定理可求出由中国剩余定理可求出

31、m3(mod n1 n2 n3 )。由于由于m3 n1 n2 n3 ，可直接由可直接由m3开立方根得到开立方根得到m。现代密码理论现代密码理论-UESTCRSA是是确定性的加密算法确定性的加密算法, 不能抵御不能抵御选择密文攻击选择密文攻击。3. 选择密文攻击选择密文攻击假设攻击者得到了假设攻击者得到了RSA公钥公钥(n,e)，截获到某个密文，截获到某个密文c1，假设其明文为，假设其明文为m1,即即 11modecmn然后，攻击者选取明文然后，攻击者选取明文m，构造新密文，构造新密文c2：21modeccmn攻击者让解密者对攻击者让解密者对c2解密，获得明文解密，获得明文m2，则计算，则计算

32、：21modmmnm现代密码理论现代密码理论-UESTC1. RSA算法步骤算法步骤2. 加解密的计算简化加解密的计算简化3. p, q的选取的选取4. 攻击方法攻击方法5. 安全性基于大数分解的困难性安全性基于大数分解的困难性RSA密码体制的知识要点密码体制的知识要点现代密码理论现代密码理论-UESTCRabin密码体制是对密码体制是对RSA的一种修正，它有以下两的一种修正，它有以下两个特点：个特点： 它不是以一一对应的单向陷门函数为基础，对同它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文一密文，可能有两个以上对应的明文;破译该体制等价于对大整数的分解破译该体制等

33、价于对大整数的分解。 RSA中选取的公开钥中选取的公开钥e满足满足1e(n)，且且gcd(e,(n)=1。Rabin密码体制则取密码体制则取e=2。4.4 Rabin密码体制密码体制现代密码理论现代密码理论-UESTC证证 （1）存在性）存在性 （2）唯一性）唯一性7现代密码理论现代密码理论-UESTC例例4.4 由以下方程组求由以下方程组求x。1mod22mod33mod55mod7xxxx 3042701052107532:4321MMMMm解解 47mod35mod13mod12mod144133122111MMMMMMMM(105 1 1 70 1 242 3 330 4 5)mod2

34、10173173mod210 xx 即 现代密码理论现代密码理论-UESTC1. 密钥的产生密钥的产生随机选择两个大素数随机选择两个大素数p、q，满足满足pq3 mod 4，即即这两个素数形式为这两个素数形式为4k+3； 计算计算n=pq。以以n作为公开钥，作为公开钥，p、q作为秘密钥。作为秘密钥。现代密码理论现代密码理论-UESTC2. 加密加密cm2 mod n其中其中m是明文分组，是明文分组，c是对应的密文分组。是对应的密文分组。2modxcn即解 22(mod )(mod )xcpxcq qmxpmxmodmod3. 解密解密 qmxpmxmodmod qmxpmxmodmod qmx

35、pmxmodmod qmxpmxmodmod密文对应的明密文对应的明文不惟一。可文不惟一。可在在m中加入中加入A, B的身份号、日的身份号、日期、时间等。期、时间等。现代密码理论现代密码理论-UESTC下面证明，当下面证明，当pq3 mod 4，两个方程两个方程x2c mod p, x2c mod q的平方根都可容易地求出。的平方根都可容易地求出。由由p3 mod 4得，得，p+1=4k，即即(p+1) /4是一整数。因是一整数。因c是模是模p的平方剩余，故的平方剩余，故所以所以 和和 是方程是方程x2c mod p的两个根。的两个根。41 pc41 pcp(1)/21(mod )pcp212

36、1(1)/24modpppcccccp现代密码理论现代密码理论-UESTC同理同理 和和 是方程是方程x2c mod q的两个根。的两个根。41 qc41 qcq现代密码理论现代密码理论-UESTC1. 密钥产生密钥产生: 随机选择大素数随机选择大素数p、q，pq3 mod 4，计算计算n=pq。以以n作为公开钥，作为公开钥，p、q作为秘密钥。作为秘密钥。2. 加密加密: cm2 mod n3. 解密解密: qcxpcxqpmodmod4141 qcxpcxqpmodmod4141 qcxpcxqpmodmod4141 qcxpcxqpmodmod4141Rabin密码体制总结密码体制总结破译

37、破译Rabin密码体制的困难程度等价于大整数密码体制的困难程度等价于大整数n的分解。的分解。现代密码理论现代密码理论-UESTC定理定理 已知已知n为两个素数乘积为两个素数乘积, a是模是模n的平方剩余，则的平方剩余，则求解方程求解方程x2a mod n与分解与分解n是等价的。是等价的。(1)已知已知n的分解的分解n=pq，且且a是模是模n的平方剩余，的平方剩余，就可求得就可求得a mod n的的4个平方根个平方根由中国剩余定理可求得由中国剩余定理可求得a mod n的的4个平方根，记为个平方根，记为u mod n和和w mod n，且且uw mod n。 qzxpyxmodmod qzxpy

38、xmodmod qzxpyxmodmod qzxpyxmodmodnaxmod2 qaxpaxmodmod22 qzxpyxmodmod现代密码理论现代密码理论-UESTC(2) 已知已知a mod n的两个不同的平方根（的两个不同的平方根（u mod n和和w mod n，且且uw mod n），），就可分解就可分解n。由由u2w2 mod n,得得(u+w)(u-w)0 mod n，但但n不能整不能整除除u+w也不能整除也不能整除u-w，所以必有所以必有p|(u+w), q|(u-w)或或 p|(u-w), q|(u+w)所以所以 gcd(n, u+w)=p, gcd(n, u-w)=q或

39、或gcd(n, u-w)=p, gcd(n, u+w)=q因此得到了因此得到了n的分解式。的分解式。现代密码理论现代密码理论-UESTC离散对数离散对数设设p是素数，是素数，a是是p的的本原根本原根。即即a1,a2,ap-1在在 mod p下产生下产生1到到p-1的所有值，所的所有值，所以对以对b1,p-1，有惟一的有惟一的i1,p-1使得使得bai mod p。称称 i 为 模为 模 p 下 以下 以 a 为 底为 底 b 的 离 散 对 数 ， 记 为的 离 散 对 数 ， 记 为 ilogab(mod p)。已知已知a、p、i时，容易地求出时，容易地求出b，已知已知a、b和和p，求求i则

40、非常困难。则非常困难。2133explnln lnOpp现代密码理论现代密码理论-UESTC算法复杂性算法复杂性 多项式时间算法是指时间复杂性为多项式时间算法是指时间复杂性为O(nt)的算法。的算法。n是输入长度，是输入长度，t是常数是常数 指数时间算法是指时间复杂性为指数时间算法是指时间复杂性为O(th(n)的算法。的算法。现代密码理论现代密码理论-UESTC类别类别复杂性复杂性n=106时时的运算次数的运算次数实际时间实际时间多项式多项式 常数常数 线性线性 二次二次 三次三次指数指数O(1)O(n)O(n2)O(n3)O(2n)11061012101810301,0301微秒微秒1秒秒1

41、1.6天天32,000年年约约3*10301016年年现代密码理论现代密码理论-UESTC4.5 ElGamal密码体制密码体制1. 密钥产生过程：密钥产生过程： 选择一素数选择一素数p以及小于以及小于p的随机的随机数数x， g是是p的原根的原根,计算计算ygx mod p。 (y, g, p)作为公开密钥，作为公开密钥，x作为秘密密钥作为秘密密钥。2. 加密过程：加密过程： 明文消息明文消息M，随机选一整数随机选一整数 kp-1，计算计算 C1gk mod p, C2ykM mod p，密文为密文为C=(C1,C2)。3. 解密过程：解密过程： 21modxCMpC21modmodmodmo

42、dkkxkxkCy My MpppMpCgy现代密码理论现代密码理论-UESTCElGamal密码体制：密码体制：1. 安全性基于有限域上的离散对数的难解性安全性基于有限域上的离散对数的难解性2. 加密算法是概率算法加密算法是概率算法3. 不能抵御选择密文攻击不能抵御选择密文攻击现代密码理论现代密码理论-UESTCElGamal密码的安全性密码的安全性 参数要求：参数要求：p应为应为150位以上十进制数，位以上十进制数， p-1应有应有大素数因子。大素数因子。 K必须保密而且必须是一次性的。必须保密而且必须是一次性的。 K泄露，则敌手可计算出泄露，则敌手可计算出yk从而可以计算出从而可以计算出

43、M 使用同一使用同一k加密不同的明文加密不同的明文M，M，如果敌手知道，如果敌手知道M就可由就可由C2/C2=M/M求出求出M现代密码理论现代密码理论-UESTC 为保证为保证RSA算法的安全性，它的密钥长度需一再算法的安全性，它的密钥长度需一再增大，使得运算负担越来越大。相比之下，椭圆曲增大，使得运算负担越来越大。相比之下，椭圆曲线密码体制线密码体制ECC（elliptic curve cryptography）可可用短得多的密钥获得同样的安全性，因此具有广泛用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。的应用前景。4.6 椭圆曲线密码体制椭圆曲线密码体制RSA/DSA512768

44、1024204821000ECC106132160211600ECC和和RSA/DSA体制在保持同等安全的条件下各自所需的密钥的长度体制在保持同等安全的条件下各自所需的密钥的长度现代密码理论现代密码理论-UESTC椭圆曲线的方程是以下形式的椭圆曲线的方程是以下形式的三次方程：三次方程： y2+axy+by=x3+cx2+dx+e (4.1)其中其中a，b，c，d，e是满足某些是满足某些简单条件的实数简单条件的实数。定义中包括一个称为定义中包括一个称为无穷远点的元素，记为无穷远点的元素，记为O。图图1 是椭圆曲线的两个例子。是椭圆曲线的两个例子。4.6.1 椭圆曲线椭圆曲线现代密码理论现代密码理

45、论-UESTC图图1 椭圆曲线的两个例子椭圆曲线的两个例子(b) y2=x3+x+1-10231-2 RQ P1-P123-21-10-4-224QR P1 - P1(a) y2=x3-x-4-224现代密码理论现代密码理论-UESTC点加法运算点加法运算： 如果其上的如果其上的3个点位于同一直线上，个点位于同一直线上，那么它们的和为那么它们的和为O。椭圆曲线上的加法律：椭圆曲线上的加法律： O为加法单位元，即对椭圆曲线上任一点为加法单位元，即对椭圆曲线上任一点P，有有P+O=P。 设设P1=(x,y)是椭圆曲线上的一点，它的加法逆元是椭圆曲线上的一点，它的加法逆元定义为定义为P2=-P1=(

46、x, -y)。 这是因为这是因为P1、P2的连线延长到无穷远时，得到椭的连线延长到无穷远时，得到椭圆曲线上的另一点圆曲线上的另一点O，即椭圆曲线上的即椭圆曲线上的3点点P1、P2，O共线，所以共线，所以P1+P2+O=O，P1+P2=O，即即P2=-P1。由由O+O=O，还可得还可得O=-O现代密码理论现代密码理论-UESTC 设设Q和和R是是x坐标不同的两点，坐标不同的两点，Q+R的的定义定义： 画一画一条通过条通过Q、R的直线与椭圆曲线交于的直线与椭圆曲线交于P1。由由Q+R+P1=O 得得Q+R=-P1。 点点Q的倍数：的倍数： 在在Q点做椭圆曲线的一条切线，设点做椭圆曲线的一条切线，设

47、切线与椭圆曲线交于点切线与椭圆曲线交于点S，定义定义2Q=Q+Q=-S。类似类似地可定义地可定义3Q=Q+Q+Q+，等。等。 以上定义的加法具有加法运算的一般性质，如交以上定义的加法具有加法运算的一般性质，如交换律、结合律等。换律、结合律等。现代密码理论现代密码理论-UESTC密码中普遍采用的是密码中普遍采用的是有限域上有限域上的椭圆曲线，是指曲的椭圆曲线，是指曲线方程定义式中，所有系数都是某一线方程定义式中，所有系数都是某一有限域有限域GF(p)中的元素（中的元素（p为一大素数）。其中为一大素数）。其中最为常用的是由最为常用的是由方程方程y2x3+ax+b(mod p)(a,bGF(p),4

48、a3+27b20(modp)(4.2)定义的曲线。定义的曲线。4.6.2 有限域上的椭圆曲线有限域上的椭圆曲线现代密码理论现代密码理论-UESTC例例 p=23，a=b=1，4a3+27b2(mod 23)80 ，方程方程(4.2)为为y2x3+x+1，其图形是连续曲线。其图形是连续曲线。(b) y2=x3+x+1 RQ P1-P123-21-10-4-224,0),(mod1| ),(),(32OyxpyxpxxyyxbaEp为整数为整数且且 (0,1)(0,22)(1,7)(1,16)(3,10)(3,13)(4,0)(5,4)(5,19)(6,4)(6,19)(7,11)(7,12)(9

49、,7)(9,16)(11,3)(11,20) (12,4)(12,19) (13,7)(13,16) (17,3)(17,20) (18,3)(18,20)(19,5)(19,18)点集点集E23(1,1)现代密码理论现代密码理论-UESTC一般来说，一般来说，Ep(a,b)由以下方式产生：由以下方式产生： 对每一对每一x(0 xp且且x为整数），计算为整数），计算x3+ax+b(mod p)。 决定中求得的值决定中求得的值在模在模p下是否有平方根下是否有平方根，如果，如果没有，则曲线上没有与这一没有，则曲线上没有与这一x相对应的点；如果有，相对应的点；如果有，则求出两个平方根（则求出两个平方

50、根（y=0 时只有一个平方根）。时只有一个平方根）。现代密码理论现代密码理论-UESTCEp(a,b)上的加法定义如下：上的加法定义如下： 设设P, QEp(a,b)，则则 P+O=P。 如果如果P=(x,y)，那么那么(x, y)+(x, -y)=O，即即 (x, -y)是是P的加法逆元，表示为的加法逆元，表示为-P。由由Ep(a,b)的产生方式知，的产生方式知，-P也是也是Ep(a,b)中的点，如中的点，如上例，上例，P=(13,7)E23(1,1)，-P=(13, -7)，而而 -7mod 2316，所以所以-P=(13, 16)，也在也在E23(1,1)中。中。现代密码理论现代密码理论

51、-UESTC 设设P=(x1,y1)，Q=(x2,y2)，P-Q，则则P+Q=(x3,y3)由以下规则确定：由以下规则确定：x32-x1-x2(mod p)y3(x1-x3)-y1(mod p)其中其中212121132yyPQxxxaPQy现代密码理论现代密码理论-UESTC例例 以以E23(1,1)为例，设为例，设P=(3,10)，Q=(9,7)，则则所以所以P+Q=(17,20)，仍为仍为E23(1,1)中的点。中的点。2337 103111mod239362113910917mod2311(3 17) 1016420mod23xy 现代密码理论现代密码理论-UESTC若求若求2P则则所

52、以所以2P=(7,12)。22333 31516mod232 10204633307mod236(37) 103412mod23xy 现代密码理论现代密码理论-UESTC倍点运算仍定义为重复加法，如倍点运算仍定义为重复加法，如4P=P+P+P+P。 可以看出，加法在可以看出，加法在E23(1,1)中是封闭的，且能验中是封闭的，且能验证还满足交换律。对一般的证还满足交换律。对一般的Ep(a,b)，可证其上的加可证其上的加法运算是法运算是封闭封闭的、满足的、满足交换律交换律，同样还能证明其上，同样还能证明其上的的加法逆元加法逆元运算也是封闭的，所以运算也是封闭的，所以Ep(a,b)是一个是一个Ab

53、el群群。现代密码理论现代密码理论-UESTC4.6.3 明文消息嵌入到椭圆曲线上明文消息嵌入到椭圆曲线上 设明文消息为m, k是一个足够大的整数，使得将明文消息镶嵌到椭圆曲线上时，错误概率是2-k。如取k=30，对明文m，如下计算一系列x:,0,1,2,30,301,302,xmkj jmmm直到x3+ax+b(modp)有平方根，则得到点3),(xxax b反过来，从椭圆曲线点(x,y)得到明文消息m,只需求出3 0 xm现代密码理论现代密码理论-UESTC椭圆曲线上的数学困难问题椭圆曲线上的数学困难问题在椭圆曲线构成的在椭圆曲线构成的Abel群群Ep(a,b) :PEp(a,b), P的

54、阶是一个非常大的素数，的阶是一个非常大的素数，P的阶是的阶是满足满足nP=O的最小正整数的最小正整数n。Q=kP，(1) 已知已知k和和P易求易求Q;(2) 已知已知P、Q求求k则是困难的则是困难的这就是这就是椭圆曲线上的离散对数问题椭圆曲线上的离散对数问题，可应用于构造，可应用于构造公钥密码体制。公钥密码体制。Diffie-Hellman密钥交换和密钥交换和ElGamal密码体制可推密码体制可推广到椭圆曲线来实现。广到椭圆曲线来实现。4.6.4 椭圆曲线上的密码椭圆曲线上的密码现代密码理论现代密码理论-UESTC1. Diffie-Hellman密钥交换密钥交换 W.Diffie和M.Hel

55、lman1976年提出 算法的安全性基于求离散对数的困难性用户B用户A选择随机数xp计算YA= gx mod p选择随机数yp计算YB= gy mod pYB计算K=YA y = gxy mod p计算K=YB x = gxy mod pYAp是大素数，是大素数，g g是是p的本原根，的本原根，p和和g g公开公开Diffie-Hellman密钥交换密钥交换现代密码理论现代密码理论-UESTC首先取一素数首先取一素数p2180和两个参数和两个参数a、b，则得方程则得方程(4.2)表达的椭圆曲线及其上面的点构成的表达的椭圆曲线及其上面的点构成的Abel群群Ep(a,b)。第第2步，取步，取Ep(

56、a,b)的一个生成元的一个生成元G(x1,y1)，要求要求G的的阶是一个非常大的素数，阶是一个非常大的素数，G的阶是满足的阶是满足nG=O的最小的最小正整数正整数n。Ep(a,b)和和G作为公开参数。作为公开参数。 移植到椭圆曲线上移植到椭圆曲线上：现代密码理论现代密码理论-UESTC两用户两用户A和和B之间的密钥交换如下进行：之间的密钥交换如下进行： A选一选一小于小于n的整数的整数nA，作为秘密钥，并由作为秘密钥，并由PA=nAG产生产生Ep(a,b)上的一点作为公钥。上的一点作为公钥。 B类似地选取自己的秘密钥类似地选取自己的秘密钥nB和公开钥和公开钥PB。 A、B分别由分别由K=nAP

57、B和和K=nBPA产生出双方共享产生出双方共享的秘密钥。的秘密钥。这是因为这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA。 攻击者若想获取攻击者若想获取K，则必须由则必须由PA和和G求出求出nA，或或由由PB和和G求出求出nB，即需要求椭圆曲线上的离散对数，即需要求椭圆曲线上的离散对数，因此是不可行的。因此是不可行的。现代密码理论现代密码理论-UESTC用户用户A选择一随选择一随机数机数nAn计算计算PA= nA G计算计算K= nA PB 用户用户B选择一随选择一随机数机数nBn计算计算PB= nB G计算计算K= nB PA PBPAGF(p), a 公开公开, a本原本原Ep(a,b), G公开公开, G的的阶为阶为n现代密码理论现代密码理论-UESTC例例 p=211，Ep(0,-4)，即椭圆曲线为即椭圆曲线为y2x3-4。G=(2,2)是是E211(0,-4)的阶为的阶为241的一个生成元，即的一个生成元，即241G=O。A的秘密钥取的秘密钥取nA=121，公开钥为公开钥为PA=121(2,2)=(115,48)。B的秘密钥取的秘密钥取nB=203，公开钥为公开钥为PB=203(2,2)=(130,203)。共享密钥为共享密钥为121(130,203)=203(115,48)=(161,169)。即共享密钥是一对数。即共享密钥是一对数。