第4章公钥密码

第4章公钥密码4.1数论基础知识4.2公钥密码的基本概念4.3RSA公钥密码4.4ElGamal公钥密码4.5Rabin公钥密码4.6椭圆曲线公钥密码现代密码学电子科技大学4.1数论基础知识现代密码学电子科技大学电子科技大学现代密码学素数与互素定义1对于整数a,b（b0），若存在整数x使得b=ax，则称a整除b，或a是b的因子，记作a|b。定义2若a,b,c都是整数，a和b不全为0且c|a,c|b，则称c是a和b的公因子。如果整数d满足：①d是a和b的公因子；②a和b的任一公因子，也是d的因子。则称d是a和b的最大公因子，记作d=gcd(a,b)。如果gcd(a,b)=1，则称a和b互素。定义3若a,b,c都是整数，a和b都不为0且a|c,b|c，则称c是a和b的公倍数。如果整数d满足：①d是a和b的公倍数；②d整除a和b的任一公倍数。则称d是a和b的最小公倍数，记作d=lcm(a,b)。现代密码学电子科技大学素数与互素电子科技大学现代密码学定义4对于任一整数p(p＞1)，若p的因子只有±1和±p，则称p为素数，否则称为合数。对于任一整数a(a＞1)，都可以唯一的分解为素数的乘积，即：a=p1×p2×…×pt其中，p1＜p2＜…＜pt都是素数，pi＞0(i=1,2,…,t)。素数与互素定义5设n是一正整数，小于n且与n互素的正整数的个数称为欧拉（Euler）函数，记作。欧拉函数有如下性质：①若n是素数，则。②若m和n互素，则。③如果：其中，p1p2…pt都是素数，pi＞0(i=1,2,…,t)，则：()1n()n()()()mnmn1212taaatnppp12111()(1)(1)(1)tnnppp现代密码学电子科技大学欧拉函数定义6设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，即：其中表示小于或等于的最大整数。定义r为amodn，记作ramodn。如果两个整数a和b满足：则称a和b模n同余，记作abmodn。称与a模n同余的数的全体为a的同余类。,0,aaqnrrnqn≤xmodmodanbn现代密码学电子科技大学表示向下取整同余及其性质同余有如下性质：①若n|（ab），则abmodn。②若amodnbmodn，则abmodn。③aamodn。④若abmodn，则bamodn。⑤若abmodn，bcmodn，则acmodn。⑥若abmodn，cdmodn，则a+cb+d(modn),acbd(modn)。现代密码学电子科技大学同余及其性质一般的，定义Zn为小于n的所有非负整数集合，即Zn={0,1,…,n1}，称Zn为模n的同余类集合。Zn中的加法（+）和乘法（）都为模n运算，具有如下性质：①交换律(w+x)modn=(x+w)modn(wx)modn=(xw)modn现代密码学电子科技大学模运算电子科技大学现代密码学②结合律[(w+x)+y]modn=[w+(x+y)]modn[(wx)y]modn=[w(xy)]modn③分配律[w(x+y)]modn=[(wx)+(wy)]modn④单位元(0+w)modn=wmodn(1w)modn=wmodn模运算电子科技大学现代密码学⑤加法逆元对w∈Zn，存在x∈Zn，使得w+x0modn，称x为w的加法逆元，记作x=w。⑥乘法逆元设w∈Zn，如果存在x∈Zn，使得wx1modn，就说w是可逆的，称x为w的乘法逆元，记作x=w1。并不是每个元素都有乘法逆元，可以证明w∈Zn是可逆的，当且仅当gcd(w,n)=1。如果w是可逆的，则可以定义除法：1modxxwnw模运算定理1[费马（Fermat）定理]设p为素数，a是正整数且gcd(a,p)=1，则ap11modp。如果a是任一正整数，则ap1modp。定理2[欧拉定理]若gcd(a,n)=1，则：其中是欧拉函数.()1modnan()n现代密码学电子科技大学费马定理及欧拉定理电子科技大学现代密码学定理3[中国剩余定理]设m1,m2,…,mk是两两互素的正整数，a1,a2,…,ak是任意k个整数，则同余方程组：模M=m1m2…mk有唯一解：其中，Mi=M/mi，yi=Mi-1modmi,i=1,2,…,k。mod,1,2,,iixamik1modkiiiixaMyM中国剩余定理电子科技大学现代密码学离散对数求模下的整数幂根据欧拉定理，若gcd(a,n)=1,则a(n)≡1modn。考虑一般am≡1modn,如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。例：a=7,n=19.71≡7mod19,72≡11mod19,73≡1mod19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同电子科技大学现代密码学离散对数定理：设a的阶为m，则ak≡1modn的充分必要条件是k是m的倍数。推论：a的阶整除j(n)。本原根：a的阶m等于j(n)，a为n的本原根。如果a是n的本原根，a1,a2,...,aj(n)在模n下互不相同且与n互素。本原根不唯一。并非所有元素都有本原根，仅有以下形式的整数才有本原根：2，4，pa,2pa,p是奇素数电子科技大学现代密码学离散对数指标y=ax(a0,a≠1)的逆函数称为以a为底的对数，记为x=logay设p为素数，a是p的本原根，则a0,a1,...,ap-1产生1到p-1中所有值，且每个值只出现一次。对任一b∈{1,…,p-1}，都存在唯一的i(1≤i≤p)，使b≡aimodp。i称为模p下以a为底b的指标，记为i=inda,p(d)电子科技大学现代密码学离散对数指标的性质1.inda,p(1)=02.inda,p(a)=13.inda,p(xy)=[inda,p(x)+inda,p(y)]modj(p)4.inda,p(yr)=[r×inda,p(y)]modj(p)后两个性质基于下列结论若az≡aqmodp,a和p互素，则z≡qmodj(p)定义7设，若存在一个，使得x2amodn，则称a是一个模n的二次剩余（quadraticresiduemodulon），并称x是a的模n平方根；否则称a是一个模n的二次非剩余（quadraticnonresiduemodulon）。*naZ*nxZ现代密码学电子科技大学二次剩余4.2公钥密码的基本概念现代密码学电子科技大学现代密码学电子科技大学1976年，Diffie和Hellman在“密码学的新方向（NewDirectioninCryptography）”一文中首次提出了公钥密码体制（publickeycryptosystem）的思想。公钥密码体制的概念是为了解决传统密码系统中最困难的两个问题而提出的，这两个问题是密钥分配和数字签名。4.2公钥密码的基本概念现代密码学电子科技大学4.2.1公钥密码体制的原理公钥密码体制在加密和解密时使用不同的密钥，加密密钥简称公钥（publickey），解密密钥简称私钥（privatekey）。公钥是公开信息，不需要保密，私钥必须保密。给定公钥，要计算出私钥在计算上是不可行的。公钥密码体制有两种基本模型，一种是加密模型，另一种是认证模型。现代密码学电子科技大学（1）加密模型。如图所示，接收者B产生一对密钥PKB和SKB，其中PKB是公钥，将其公开，SKB是私钥，将其保密。如果A要向B发送消息m，A首先用B的公钥PKB加密m，表示为c=E(PKB,m)，其中c是密文，E是加密算法，然后发送密文c给B。B收到密文c后，利用自己的私钥SKB解密，表示为m=D(SKB,c)，其中D是解密算法。现代密码学电子科技大学加密模型发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmm’SK’B电子科技大学现代密码学认证模型（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，所以上述过程获得了对消息来源和数据完整性的认证。电子科技大学现代密码学发送者A加密算法（签名）SKA密钥源PKA解密算法（验证）接收者B密码分析员mcmSK’A4.2.2公钥密码体制的要求公钥体制的基本原理是陷门单向函数。定义8陷门单向函数是满足下列条件的可逆函数f：①对于任意的x，计算y=f(x)是容易的。②对于任意的y，计算x使得y=f(x)是困难的。③存在陷门t，已知t时，对于任意的y，计算x使得y=f(x)则是容易的。现代密码学电子科技大学（1）大整数分解问题（factorizationproblem）若已知两个大素数p和q，求n=pq是容易的，只需一次乘法运算，而由n，求p和q则是困难的，这就是大整数分解问题。现代密码学电子科技大学电子科技大学现代密码学（2）离散对数问题（discretelogarithmproblem）给定一个大素数p，p1含另一大素数因子q，则可构造一个乘法群，它是一个p1阶循环群。设g是的一个生成元，1＜g＜p1。已知x，求y=gxmodp是容易的，而已知y、g、p，求x使得y=gxmodp成立则是困难的，这就是离散对数问题。电子科技大学现代密码学（3）多项式求根问题有限域GF（p）上的一个多项式：已知,p和x，求y是容易的，而已知y,，求x则是困难的，这就是多项式求根问题。011,,...,naaa011,,...,naaa1110()modnnnyfxxaxaxap（5）判断Diffie-Hellman问题（decisionDiffie-Hellmanproblem,DDHP）给定素数p，令g是的一个生成元。已知,,判断等式：z=xymodp是否成立，这就是判断性Diffie-Hellman问题。xagybgzcg现代密码学电子科技大学电子科技大学现代密码学（6）二次剩余问题（quadraticresidueproblem）给定一个合数n和整数a，判断a是否为modn的二次剩余，这就是二次剩余问题。在n的分解未知时，求amodn的解也是一个困难问题。2x电子科技大学现代密码学（7）背包问题（knapsackproblem）给定向量A=()(为正整数)和x=()(∈{0,1})，求和式：是容易的，而由A和S，求x则是困难的，这就是背包问题，又称子集和问题。1122()nnsfxaxaxax12,,...,naaaia12,,...,nxxxix电子科技大学现代密码学4.3RSA公钥密码1．密钥生成①选取两个保密的大素数p和q。②计算n=pq,，其中是n的欧拉函数值。③随机选取整数e，满足1＜e＜，且。④计算d，满足。⑤公钥为(e,n)，私钥为（d,n）。()n()ngcd(,())1en()(1)(1)npq1mod()den4.3.1RSA算法描述现代密码学电子科技大学2．加密首先对明文进行比特串分组，使得每个分组对应的十进制数小于n，然后依次对每个分组m做一次加密，所有分组的密文构成的序列即是原始消息的加密结果。即m满足0≤m＜n，则加密算法为：c为密文，且0≤c＜n。modecmn现代密码学电子科技大学4.3.1RSA算法描述3．解密对于密文0≤c＜n，解密算法为：moddmcn现代密码学电子科技大学4.3.1RSA算法描述4.3.2RSA的安全性1．数学攻击用数学方法攻击RSA的途径有三种：①分解n为两个素因子。这样就可以计算从而计算出私钥。②直接确定而不先确定p和q。这同样可以确定.③直接确定d而不先确定。1mod()den()(1)(1)npq