公开密钥密码-5

密码学公开密钥密码一、公开密钥密码体制的基本思想1、传统密码的缺点：①收发双方持有相同密钥，密钥分配困难，网络环境更突出。②不能方便地实现数字签名，商业等应用不方便。Ke＝Kd一、公开密钥密码体制的基本思想2、公开密钥密码的基本思想：①将密钥K一分为二，一个专门加密，一个专门解密：Ke≠Kd②且由Ke不能计算出Kd，于是可将Ke公开，使密钥分配简单。③由于Ke≠Kd且由Ke不能计算出Kd，所以Kd便成为用户的指纹，于是可方便地实现数字签名。一、公开密钥密码体制的基本思想3、公开密钥密码的基本条件：①E和D互逆；基本条件，保密条件D（E（M））＝M②Ke≠Kd且由Ke不能计算出Kd；安全条件③E和D都高效。实用条件④E（D（M））＝M保真条件如果满足①②③可保密，如果满足②③④可保真，如果4个条件都满足，可同时保密保真。二、公开密钥密码的基本工作方式设M为明文，C为密文，E为公开密钥密码的加密算法，D为解密算法，Ke为公开的加密钥，Kd为保密的解密钥，每个用户都分配一对密钥，而且将所有用户的公开的加密钥Ke存入共享的密钥库PKDB。二、公开密钥密码的基本工作方式1、确保数据秘密性：AB发方：①A首先查PKDB，查到B的公开的加密钥KeB。②A用KeB加密M得到密文C：C=E（M，KeB）③A发C给B。收方：①B接受C。②B用自己的KdB解密，得到明文M=D(C，KdB)。M二、公开密钥密码的基本工作方式1、确保数据秘密性：安全性分析：①只有B才有KdB，因此只有B才能解密，所以确保了秘密性。②任何人都可查PKDB得到A的KeA，所以任何人都可冒充A给B发送数据。不能确保真实性。二、公开密钥密码的基本工作方式2、确保数据真实性：AB发方：①A首先用自己的KdA对M解密，得到C=D(M，KdA)。②A发C给B。收方：①B接受C。②B查PKDB查到A的公开的加密钥KeA。③B用KeA加密C，得到明文M=E（C，KeA）。M二、公开密钥密码的基本工作方式2、确保数据真实性：安全性分析：①只有A才有KdA，因此只有A才能解密产生C，所以确保了真实性。②任何人都可查PKDB得到A的KeA，所以任何人都可加密得到明文。不能确保秘密性。二、公开密钥密码的基本工作方式3、同时确保数据秘密性和真实性：AB发方：①A首先用自己的KdA对M解密，得到S：S=D(M，KdA)②查PKDB，查到B的公开的加密钥KeB。③用KeB加密S得到C：C=E（S，KeB）④A发C给B。M二、公开密钥密码的基本工作方式3、同时确保数据秘密性和真实性：收方：①B接受C。②B用自己的KdB解密C，得到S：S=D（C，KdB）③B查PKDB查到A的公开的加密钥KeA。④B用A的公开的加密钥KeA加密S，得到M：M=E（S，KeA）二、公开密钥密码的基本工作方式3、同时确保数据秘密性和真实性：安全性分析：①只有A才有KdA，因此只有A才能解密产生S，所以确保了真实性。②只有B才有KdB，因此只有B才能获得明文，所以确保了秘密性。三、RSA公开密钥密码1978年美国麻省理工学院的三名密码学者R.L.Rivest,A.Shamir和L.Adleman提出了一种基于大合数因子分解困难性的公开密钥密码，简称为RSA密码。RSA密码被誉为是一种风格幽雅的公开密钥密码。既可用于加密，又可用于数字签名，安全、易懂。RSA密码已成为目前应用最广泛的公开密钥密码。三、RSA公开密钥密码1、加解密算法①随机地选择两个大素数p和q，而且保密；②计算n=pq，将n公开；③计算φ(n)=(p-1)(q-1)，对φ(n)保密；④随机地选取一个正整数e，1eφ(n)且（e，φ(n)）=1，将e公开；⑤根据ed＝1modφ(n)，求出d，并对d保密；⑥加密运算：C＝Memodn⑦解密运算：M＝Cdmodn三、RSA公开密钥密码2、算法论证①E和D的可逆性要证明：D(E(M))=MM＝Cd＝(Me)d＝Medmodn因为ed＝1modφ(n)，这说明ed＝tφ(n)+1,其中t为某整数。所以，Med＝Mtφ(n)+1modn。因此要证明Med＝Mmodn，只需证明Mtφ(n)+1＝Mmodn。三、RSA公开密钥密码2、算法论证①E和D的可逆性在（M，n）＝1的情况下，根据数论(Euler定理)，Mtφ(n)＝1modn，于是有，Mtφ(n)+1＝Mmodn。三、RSA公开密钥密码2、算法论证①E和D的可逆性在（M，n）≠1的情况下，分两种情况：第一种情况：M∈{1,2,3,…,n-1}因为n=pq，p和q为素数，M∈{1,2,3,…,n-1}，且（M，n）≠1。这说明M必含p或q之一为其因子，而且不能同时包含两者，否则将有M≥n，与M∈{1,2,3,…,n-1}矛盾。三、RSA公开密钥密码2、算法论证①E和D的可逆性不妨设M＝ap。又因q为素数，且M不包含q，故有（M，q）＝1，于是有，Mφ(q)＝1modq。进一步有，Mt(p-1)φ(q)＝1modq。因为q是素数，φ(q)＝（q-1），所以t(p-1)φ(q)＝tφ(n)，所以有Mtφ(n)＝1modq。三、RSA公开密钥密码2、算法论证①E和D的可逆性于是，Mtφ(n)＝bq+1，其中b为某整数。两边同乘M，Mtφ(n)+1＝bqM+M。因为M＝ap，故Mtφ(n)+1＝bqap+M=abn+M。取模n得，Mφ(n)+1＝Mmodn。三、RSA公开密钥密码2、算法论证①E和D的可逆性在（M，n）≠1的情况下，分两种情况：第二种情况：M＝0当M＝0时，直接验证，可知命题成立。三、RSA公开密钥密码2、算法论证②加密和解密运算的可交换性D(E(M))=(Me)d=Med=(Md))e=E(D(M))modn所以，RSA密码可同时确保数据的秘密性和数据的真实性。③加解密算法的有效性RSA密码的加解密运算是模幂运算，有比较有效的算法。三、RSA公开密钥密码2、算法论证④在计算上由公开密钥不能求出解密钥小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于O（EXP（lnNlnlnN）1/2）。根据这一结论，只要合数足够大，进行因子分解是相当困难的。三、RSA公开密钥密码2、算法论证④在计算上由公开密钥不能求出解密钥假设截获密文C，从中求出明文M。他知道M≡Cdmodn，因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但他知道，ed≡1modφ(n)，e是公开的，要从中求出d，必须先求出φ(n)，而φ(n)是保密的。三、RSA公开密钥密码2、算法论证④在计算上由公开密钥不能求出解密钥但他又知道，φ(n)=(p-1)(q-1)，要从中求出φ(n)，必须先求出p和q，而p和q是保密的。但他知道，n=pq，要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。三、RSA公开密钥密码2、算法论证④在计算上由公开密钥不能求出解密钥只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译RSA密码的困难性≤对n因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。目前只有Rabin密码具有：破译Rabin密码的困难性=对n因子分解的困难性。四、RSA密码的实现1、参数选择为了确保RSA密码的安全，必须认真选择密码参数：①p和q要足够大；一般应用：p和q应512b重要应用：p和q应1024b②p和q应为强素数文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子，n就容易分解。③p和q的差要大；四、RSA密码的实现1、参数选择④（p-1）和（q-1）的最大公因子要小。如果（p-1）和（q-1）的最大公因子太大，则易受迭代加密攻击。⑤e的选择随机且含1多就安全，但加密速度慢。于是，有的学者建议取e＝216+1＝65537⑥d的选择d不能太小，要足够大⑦不要许多用户共用一个模n；易受共模攻击四、RSA密码的实现2、大素数的产生①概率产生目前最常用的概率性算法是Miller检验算法。Miller检验算法已经成为美国的国家标准。②确定性产生确定性测试确定性构造四、RSA密码的实现3、大素数的运算①快速乘方算法反复平方乘算法：设e的二进制表示为e＝ek-12k-1+ek-22k-2+...,+e121+e0则Me=((…(Mek-1)2Mek-2)2…Me1)2Me0modn设e为k位二进制数，w(e)为e的二进制系数中为1的个数，则最多只需要计算w(e)-1次平方和w(e)次数的模乘。从而大大简化了计算。四、RSA密码的实现3、大素数的运算②快速模乘算法反复平方乘算法解决了快速乘方取模的问题，仍未解决快速模乘的问题；Montgomery算法是一种快速模乘的好算法；将以上两种算法结合成为实现RSA密码的有效方法。硬件协处理器是提高运算效率的有效方法。四、RSA密码的实现3、大素数的运算Montgomery算法的思路：要计算Y=ABmodn,因为n很大，取模运算困难，采取一个小的模R，回避大模的计算。利用空间换时间，多用存储空间换取快速。缺点：不能直接计算出Y=ABmodn，只能计算出中间值ABR-1modn，因此还需要预处理和调整运算。一次性计算Y=ABmodn并不划算。适合：RSA等密码中多次的模乘计算。公钥密码方案的实际应用实现速度通常用于交换对称算法的加密密钥数字签名算法五、ELGamal公钥密码的基本情况1、基本情况：①ELGamal密码是除了RSA密码之外最有代表性的公开密钥密码。②RSA密码建立在大合数分解的困难性之上。③ELGamal密码建立在离散对数的困难性之上。所谓离散对数，就是给定正整数x，y，n，求出正整数k（如果存在的‍话），使y≡xk(modn)。五、ELGamal公钥密码的基本情况2、离散对数问题：①设p为素数，则模p的剩余构成有限域：Fp={0,1,2,…,p-1}Fp的非零元构成循环群Fp*Fp*={1,2,…,p-1}={α，α2，α3，，αp-1}，则称α为Fp*的生成元或模p的本原元。②求α的摸幂运算为:y=αxmodp，1≤x≤p-1,五、ELGamal公钥密码的基本情况2、离散对数问题：求对数X的运算为x=logαy，1≤x≤p-1由于上述运算是定义在模p有限域上的，所以称为离散对数运算。③从x计算y是容易的。可是从y计算x就困难得多，利用目前最好的算法，对于小心选择的p将至少需用O(p½)次以上的运算，只要p足够大，求解离散对数问题是相当困难的。六、ELGamal公钥密码准备：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。⑴密钥生成用户随机地选择一个整数d作为自己的秘密的解密钥，2≤d≤p-2。计算y=αdmodp，取y为自己的公开的加密钥。由公开钥y计算秘密钥d，必须求解离散对数，而这是极困难的。六、ELGamal公钥密码⑵加密将明文消息M（0≤M≤p-1)加密成密文的过程如下：①随机地选取一个整数k，2≤k≤p-2。②计算：U＝ykmodp；C1＝αkmodp；C2＝UMmodp；③取C＝（C1，C2）作为的密文。六、ELGamal公钥密码⑶解密将密文（C1，C2）解密的过程如下：①计算V＝C1dmodp；②计算M＝C2V-1modp。六、ELGamal公钥密码解密的可还原性可证明如下：C2V-1modp＝(UM)V-1modp＝UM（C1d）-1modp＝UM（（αk）d）-1modp＝UM（（αd）k）-1modp＝UM（（y）k）-1modp＝UM（U）-1modp＝Mmodp六、ELGamal公钥密码⑷安全性由于ELGamal密码的安全性建立在GF（p）离散对数的困难性之上，而目前尚无求解GF（p）离散对数的有效算法，所以在p足够大时ELGamal密码是安全