密码学04－公钥密码

null第四章 公钥密码第四章 公钥密码本科生学位课：现代密码学主讲教师：董庆宽 研究方向：密码学与信息安全 Email ：qkdong@mail.xidian.edu.cn本章提要本章提要4.1 密码学中常用数学知识 4.2 公钥密码体制的基本概念 4.3 RSA算法 4.4 背包体制 4.5 Rabin体制 4.6 NTRU公钥密码系统 4.7 椭圆曲线密码体制 4.8 基于身份的密码体制4.1 密码学中的常用数学知识4.1 密码学中的常用数学知识群、环、域、素数 模运算 费尔马定理 ap-1=1 mod p ，p是素数 欧拉函数 (n)：小于n的且与n互素的正整数个数 a(n)=1 mod n 素性检验 1.爱拉托斯散筛法(Eratosthenes) 依次删去小于 素数的倍数 2. Miller-Rabin概率检测法√ 3.AKS欧几里得算法、扩展欧几里德算法 求最大公约数和乘法的逆元 中国剩余定理 求一次同余方程组的解 离散对数，本原根 平方剩余 计算复杂性4.2 公钥密码体制的基本概念4.2 公钥密码体制的基本概念公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理论和技术基础 公钥密码算法基本工具不再是代换和置换，而是数学函数 以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。 公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，即密钥分配和数字签字null对称密码算法的缺陷 密钥分配问题： 通信双方加密通信前要通过秘密的安全信道协商加密密钥，这种安全信道可能很难实现；对这个信道安全性的要求比正常传送消息信道的安全性要高 密钥管理问题： 在多用户网络中，任何两个用户之间都需要有共享的秘密钥，n个用户需要Cn2=n(n-1)/2个密钥，n=5000时，Cn2=12,497,500，系统开销非常大 没有签名功能： 当主体A收到主体B的电子文挡时，无法向第三方证明此电子文档确实来源于B， 传统单钥加密算法无法实现抗抵赖的需求null公钥密码的主要作用 公钥加密 用于加密任何消息，象分组密码一样使用 任何人可以用公钥加密消息，私钥的拥有者可以解密消息 数字签名 (Digital Signature) 用于生成对某消息的数字签名 私钥的拥有者生成数字签名，任何人可以用公钥验证签名 签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法 基于公钥的密钥分配(Key Distribution) 用于交换秘密信息，常用于协商对称加密算法的密钥 可采用公钥加密的算法实现密钥分配 也可使用单独设计的密钥交换算法，如DH密钥交换 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 实现密钥分配 其它应用： 零知识证明，公平抛币等等，（用于各种目的的认证）null公钥密码的发展概况 1976年Diffie和Hellman在其“密码学新方向”一文中提出公钥密码： W.Diffie and M.E.Hellman, “New Directions in Cryptography”, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976：644-654 1978年Merkle和Hellman基于背包问题提出了首个公钥密码体制，但两年后被破译 1978年Rivest，Shamir & Adleman基于大数分解的困难性提出了RSA公钥算法，成为迄今为止最为成熟和完善的公钥密码体制 1985年出现了基于求解离散对数困难性的公钥密码算法DLP 90年代逐步出现椭圆曲线(ECC)等其他公钥算法 当前的公钥密码算法主要是基于大数分解困难性和离散对数困难性来构造的，椭圆曲线上也可构造这类体制，相同密钥长度下其安全性更高 参考资料：《公钥密码学》等4.2.1 公钥密码体制的原理4.2.1 公钥密码体制的原理公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开 一个密钥是公开的，称为公开密钥，简称公开钥，用于加密、验证签名，可以被任何人知道 另一个密钥是为用户专用，因而是保密的，只能被消息的接收者或签名者知道，称为秘密密钥，简称秘密钥，用于解密、产生签名 因此公钥密码体制也称为双钥密码体制 算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的 因此加密和签名的验证者不能解密和生成签名null公钥体制的加密过程 ① 密钥的产生：要求接收消息的端系统，产生一对用来加密和解密的密钥PKB和SKB，如图中的接收者B，其中PKB是公开钥，SKB是秘密钥。因此，公钥可以发布给其他人 ② 公开钥的分发：端系统B将加密密钥(PKB)予以公开。另一密钥则被保密(SKB) ③ 加密：A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKB[m]其中c是密文，E是加密算法 ④ 解密：B收到密文c后，用自己的秘密钥SKB解密，即m=DSKB[c]，其中D是解密算法。因为只有B知道SKB，所以其他人都无法对c解密。null公钥体制的认证过程 公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证 用户A用自己的秘密钥SKA对m加密，表示为c=ESKA[m] 将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKA[c] 因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。 任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。null认证符： 通过单向压缩函数解决长文件的签字(hash) 用户数目很多时，单纯加解密的认证方法需要很大的存储空间 因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容 改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符null认证符具有这样一个性质： 如果保持认证符的值不变而修改文件，在计算上是不可行的 签名过程中，往往用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。 (详见第7章) null公钥体制同时提供加密和认证的过程 认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密 先签名后加密：发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为c=EPKB[ESKA[m]] 先解密再验证：解密过程为m=DPKA[DSKB[c]] 即收方先用自己的秘密钥，再用发方的公开钥对收到的密文两次解密。 如果先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，从而实现了篡改。 4.2.2 公钥密码算法应满足的要求4.2.2 公钥密码算法应满足的要求公钥密码算法应满足以下要求 ① 收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。由私钥及其他密码信息容易计算出公开密钥(P问题) ② 发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKB[m]在计算上是容易的 ③ 收方B用自己的秘密钥对c解密，即m=DSKB[c]在计算上是容易的 ④ 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的 ⑤ 敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的 ⑥ 加、解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB (m)] 其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲签字等算法时需要类似要求 以上要求的本质之处在于要求一个陷门单向函数。 null单向函数 是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的 “易于计算”是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na 的某个倍数，其中a是一固定的常数 这时称求函数值的算法属于多项式类P，否则就是不可行的，例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的null易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别 在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。这时可能对某些情况很容易求解，复杂度很低 而在此所说的两个概念是指算法在几乎所有情况下的情形null陷门单向函数 称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 为： 陷门单向函数是一族可逆函数fk，满足 ①当k和X已知时，Y=fk(X)易于计算 ②当k和Y已知时，X=fk-1(Y)易于计算 ③当Y已知但k未知时，X=fk-1(Y)计算上是不可行的 研究公钥密码算法就是要找出合适的陷门单向函数4.2.3 对公钥密码体制的攻击 4.2.3 对公钥密码体制的攻击 以下讨论的攻击是指对所有公钥密码体制都有效的平凡的攻击 涉及到公钥算法所基于的困难问题的安全性和参数空间大小的安全性 第一种平凡的攻击：（穷搜索攻击与密钥长度） 如果密钥太短，公钥密码体制也易受到穷搜索攻击 然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用 因此公钥密码体制目前主要用于密钥管理和数字签字。即处理短消息如密钥和hash值null第二种平凡的攻击 是寻找从公开钥计算秘密钥的方法 目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的 第三种平凡的攻击：(可能字攻击) 仅适用于对公钥密码算法的攻击 例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较 如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，攻击的本质是对56比特DES密钥的穷搜索攻击 抵抗方法是在欲发送的明文消息后添加一些随机比特 不同的公钥密码算法在设计和实现中的密码协议是影响安全性的主要方面，不同算法的攻击不同。 公钥的安全性是指计算上的安全性4.3 RSA算法4.3 RSA算法1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，已得到广泛的应用 R L Rivest, A Shamir, L Adleman, "On Digital Signatures and Public Key Cryptosystems", Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 它既可用于加密、又可用于数字签字。 RSA算法的安全性是基于数论中大整数分解的困难性(但可能达不到大数分解的困难强度)4.3.1 算法描述4.3.1 算法描述1．密钥的产生 ① 选两个保密的大素数p和q ② 计算n=p×q，(n)=(p-1)(q-1)，其中(n)是n的欧拉函数值 ③ 选一整数e，满足1q，由 (n)=(p-1)(q-1)，则有 p+q=n－(n)+1，以及 p-q= 由此可见，由p、q确定(n)和由(n)确定p、q是等价的 null为保证算法的安全性，对p和q提出以下要求： (1) |p-q|要大 由(p+q)2/4－n=(p+q)2/4－pq=(p－q)2/4，如果|p-q|小，则(p－q)2/4也小，因此(p+q)2/4稍大于n，(p+q)/2稍大于n1/2。可得n的如下分解步骤： ① 顺序检查大于n的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。 ② 由x2-n=y2，得n=(x+y)(x-y)。 (2) p-1和q-1都应有大素因子(强素数) 这是因为RSA算法存在着可能的重复加密攻击法。 null重复加密攻击法 设攻击者截获密文c，可如下进行重复加密： … 若 ，即 ，则有 ， 即 所以在上述重复加密的倒数第2步就已恢复出明文m 这种攻击法只有在 t 较小时才是可行的。为抵抗这种攻击，p、q的选取应保证使 t 很大。 设m在模n下阶为k，由 得 ，所以k|(et-1)，即et≡1(mod k)，t 取为满足前式的最小值（为e在模k下的阶）。又当e与k互素时t|(k)。为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子 此外，研究表明，如果e701，得x10=1；令s=734-701=33，由33<349，得x9=0；重复该过程得第一个明文分组是1001100001，它对应的英文文本是SA；类似地得其他明文分组，解密结果为SAUNA AND HEALTH。 null背包密码体制是Diffie和Hellman 1976年提出公钥密码体制的设想后的第一个公钥密码体制，由Merkle和Hellman 1978年提出。 它表示了如何将NP完全问题用于公开密钥算法。然而又过了两年该体制即被破译 破译的基本思想是不必找出正确的模数k和乘数t（即陷门信息），只须找出任意模数k′和乘数t′，使得用k′和t′去乘公开的背包向量B时，能够产生超递增的背包向量即可。4.5 Rabin密码体制4.5 Rabin密码体制对RSA密码体制，n被分解成功，该体制便被破译，即破译RSA的难度不超过大整数的分解。 但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已得到普遍共识 Rabin密码体制已被证明对该体制的破译与分解大整数一样困难 Rabin密码体制是对RSA的一种修正，它有以下两个特点： 它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文; 破译该体制等价于对大整数的分解。 RSA中选取的公开钥e满足1p 2.密钥的产生 密钥的产生由接收方完成：随即选取两个多项式f, gLg，其中多项式f在模q和模p下均可逆，其逆元分别表示为Fq和Fp，即：Fq*f=1 mod q 和 Fp*f=1 mod p。计算h＝Fq*g mod q，以h为公钥，f作为秘密钥，接收方同时还需保存Fp 3.加密 设发送方欲将消息mLm发送给接收方，可对m作如下加密：随机选取多项式L ，用公钥h对消息进行加密 e＝p*h+m (mod q) 将e发送给接收方。null4.解密 接收方收到e后，使用秘密钥f对其作如下解密。 ①首先计算a=f*e(mod q), a的系数选在-q/2到q/2之间. ②将a作为一个整系数多项式，计算Fp*a(mod p)即可恢复明文m 解密原理： a=f*e＝f*p*h+f*m (mod q) ＝f*p*Fq*g +f*m (mod q) ＝ p*g +f*m (mod q) ＝ p*g +f*m 最后一步是由于若选择的参数合适，可保证多项式p*g +f*m的系数在-q/2到q/2之间，所以对p*g +f*m模q运算后结果不变 而Fp*a＝Fp*p*g +Fp*f*m (mod p)＝m (mod p)4.7 椭圆曲线密码体制4.7 椭圆曲线密码体制为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。 相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景 ECC已被IEEE公钥密码标准P1363采用4.7.1 椭圆曲线4.7.1 椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e (4-1) 其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。 从图可见，椭圆曲线关于x轴对称。 null椭圆曲线上的加法运算定义如下： 如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）： ① O为加法单位元，即对椭圆曲线上任一点P，有 P+O=P ② 设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=－P1=(x, -y) 这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。 由O+O=O，还可得O= -Onull③ 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1 这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q或P1=R 由Q+R+P1=O 得 Q+R=-P1 ④ 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…， 以上定义的加法具有加法运算的一般性质，如交换律、结合律等。 4.7.2 有限域上的椭圆曲线4.7.2 有限域上的椭圆曲线密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式(4-1)中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数） 其中最为常用的是由方程(4-2)定义的曲线 y2≡x3+ax+b(mod p) (4-2) (a,bGF(p),4a3+27b2(mod p)≠0)null因为＝(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b＝0的判别式，当4a3+27b2 ＝0时方程有重根，设为x0，则点Q0＝(x0,0)是方程(4-2)的重根 即x3+ax+b＝(x-x0)3或者＝(x-x0)2(x-x1)，重根将使得一阶导数3x2＋a在该Q0点为0 令F(x,y)=y2－x3－ax－b，则F/x|Q0=F/y|Q0=0 所以dy/dx=－F/x/F/y＝(3x2＋a)/2y在Q0点无定义，即曲线y2≡x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义null例： p=23，a=b=1，4a3+27b2(mod 23)≡8≠0，方程为y2≡x3+x+1(mod 23)，感兴趣的是曲线在GF(23)中的整数点 设Ep(a,b)表示方程(4-2)所定义的椭圆曲线上的点集{(x,y)|0x 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 推导示例公式推导示例null倍点运算仍定义为重复加法，如4P=P+P+P+P 快速倍点运算 kP 可采用类似于快速指数运算的相同算法 即令k=bt2t+bt-12t-1+…+b12+b0，则可写出2倍点和加法运算的迭代形式 Ep(a,b)是一个Abel群 对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，有单位元O，所以Ep(a,b)是一个Abel群4.7.3 椭圆曲线上的点数4.7.3 椭圆曲线上的点数一条椭圆曲线Ep(a,b)（含无穷远点O)的总点数关系到运算群的规模，即建立的密码系统的安全性，有以下定理： 定理4-13 GF(p)上的椭圆曲线y2＝x3+ax+b(a,bGF(p), 4a3+27b2(mod p)≠0)在第一象限中的整数点加无穷远点O共有 1+p+ = 1+p+个，其中 是Legendre符号 定理中的由以下定理给出 定理4-14(Hasse定理) |  |4.7.4 明文消息到椭圆曲线上的嵌入4.7.4 明文消息到椭圆曲线上的嵌入使用椭圆曲线构造密码体制前，需要将明文消息镶嵌到椭圆曲线上去，作为椭圆曲线上的点。 设明文消息是m(0mM)，k是一个足够大的整数，使得将明文消息镶嵌到椭圆曲线上时，错误的概率是2-k 实际情况中，k可在3050之间取值。不妨设k＝30，对明文消息m，如下计算一系列x： x＝{mk+j,j=0,1,2,…}={30m,30m+1,30m+2,…}直到x3+ax+b(mod p)是平方剩余，即得到椭圆曲线上的点 (x, )。因为在0到p的整数中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(mod p)是平方根的概率不小于1－2-k。 反之，为从椭圆曲线上的点(x,y)得到明文消息m，只须求m＝x/304.7.5 椭圆曲线上的密码4.7.5 椭圆曲线上的密码为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题 在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，QEp(a,b)，k