第2章密码学基础

第2章密码学基础密码学基础知识密码技术在信息安全中的作用信息安全的重要和核心部分之一是数据安全数据安全的目标包括机密性、真实性、完整性、不可否认性、可用性、可控性实现数据安全目标的重要手段是密码技术密码技术具有几千年的历史密码学（Cryptology）是密码技术的基础，包括：密码编码学（Cryptography）密码分析学（Cryptanalysis）密码学基础知识密码编码学：研究如何进行数据加密和解密（机密性），以及防止和发现数据的伪造、篡改（真实性、完整性、不可否认性）密码分析学：分析发现密码算法的弱点、缺陷，破解密码算法或者破译密码数据数据加密、解密的基本过程明文明文密文密文解密加密破解密钥kc密钥kd明文:plaintext密文:ciphertext加密:encrypt解密:decrypt密钥:key密码算法的基本定义设：M是可能明文的集合，称为明文空间C是可能密文的集合，称为密文空间K是一切可能密钥构成的集合，称为密钥空间E为加密算法，对密钥空间的任一密钥k都能进行加密运算，即Ek:MCD为解密算法，对密钥空间的任一密钥都能进行解密运算，即Dk:CM则密码算法具有如下性质：（1）Dk(Ek(x))=x，x属于M，k属于K（2）密码破译者获得密文c=Ek(x)后无法在有效的时间内破解出密钥k和/或明文x密码体制分类古典密码(ClassicCryptography)对称密钥密码(SymmetricKeyCryptography)公开密钥密码体系(PublicKeyCryptography)古典密码代替表代换密码移位密码乘数密码仿射密码对照表代替密码abcdefghijklmXNYAHPOGZQWBTnopqrstuvwxyzSFLRCVMUEKJDIABCDEFGHIJKLMdlryvohEzxwptNOPQRSTUVWXYZbgfjqnmuskaci加密代替表解密代替表iamateacherZXTXMHXYGHC一些关于模余数的基本知识定义1.设n为大于1的正整数，a为任一整数，a可表示为a=kn+r，r≥0，则记为：amodn=r，称r为a的模n余数注意：负数的模n余数是正整数！例，若–n<a<0，则amodn=n+a定义2.设n为大于1的正整数，a、b为任意整数，如果amodn=bmodn，即a、b有相同模n余数，则称a、b模n同余表示为a≡b(modn)a、b模n同余当且仅当n整除a-b一些关于模余数的基本知识注意以下差别：a=bmodna≡b(modn)前者表示：b的模n余数是a；后者表示：a和b模n同余，即有相同的模n余数在本课中用前一种表示，即mod作为一种算子一些关于模余数的基本知识定义3.n为大于1的正整数，a、b为整数，则a+bmodn，a*bmodn，abmodn分别称为整数的模n加法、乘法和乘方(幂)一些关于模余数的基本知识设n为大于1的正整数，a、b为任意整数，则1)a+bmodn=(amodn)+(bmodn)modn2)a–bmodn=(amodn)+(–bmodn)modn=(amodn)–(bmodn)modn3)abmodn=(amodn)*(bmodn)modn4)amodn=a+knmodn=a–knmodn5)a+(bmodn)modn=a+bmodn一些关于模余数的基本知识6)a*(bmodn)modn=a*bmodn7)(amodn)pmodn=apmodn注意：mod的运算优先级最低结论：

对于同一个模n，只要保存最外层的mod算子，给加、减、乘、乘方运算中的数据加上或去掉mod算子，不影响结果

请尝试证明一下！模余数举例例1.求9mod69=6+3，故9mod6=3例2.求–7mod6–7=-12+5，故–7mod6=5而2X6+(–7)mod6=5故，–7mod6=2X6+(–7)mod6=5(即amodn=a+knmodn)模余数举例(续)例3.求9–7mod69–7=2，故9–7mod6=2而(9mod6)+(–7mod6)mod6=3+5mod6=8mod6=2(9mod6)–(7mod6)mod6=3–1mod6=2故9-7mod6=(9mod6)+(–7mod6)mod6=(9mod6)–(7mod6)mod6(即a–bmodn=(amodn)+(–bmodn)modn=(amodn)–(bmodn)modn)模余数举例(续)例4.求2+(9mod6)mod6=2+3mod6=5而2+9mod6=11mod6=5故2+(9mod6)mod6=2+9mod6(即a+(bmodn)modn=a+bmodn)例5.求2*(9mod6)mod6=2*3mod6=0

而2*9mod6=18mod6=0故，2*(9mod6)mod6=2*9mod6(即a*(bmodn)modn=a*bmodn)一些关于模余数的基本知识定义4.设n为大于1的正整数，a、b为任意整数，若a+bmodn=0，则b称为a的模n加法逆，记为-a注意：a的模n加法逆不止一个，它们相差kn定义5.设n为大于1的正整数，a、b为任意整数，若abmodn=1，则b称为a的模n乘法逆，记为a-1注意：a的模n乘法逆不止一个，它们相差kn模余数举例(续)例6.求5的模6加法和乘法逆5+1mod6=0故，1是5的模6加法逆，5的模6加法逆是6k+15*5mod6=25mod6=1故，5是5的模6乘法逆，5的模6乘法逆是6k+5例7.求3的模6加法和乘法逆3+3mod6=0故，3是3的模6加法逆，3的模6加法逆是6k+30,1,..,5都不是3的模6乘法逆，故3无模6乘法逆一些关于模余数的基本知识定义6.设p是大于1的正整数，若p只能分解为1和自己的乘积，则p称为素数定义7.设a和b是大于1的正整数，

且a和b的最大公因子是1，即

gcd(a,b)=1，则称为a和b互素定理1.设a和n是大于1的正整数，且a和n互素，则a存在模n乘法逆a-1推理1.设n是素数，则任何非kn整数a存在模n乘法逆a-1移位密码加密函数：c=Ek(m)=(m+k)modn，其中0≤m<n，m是待加密的明文数据(当作数)，1<k<n，k是密钥解密函数：m=Dk(c)=(c–k)modn–k如何理解？有效性Dk(c)=(c–k)modn=((m+k)modn)-kmodn=m+k–kmodn=mmodn=mc-k<0怎办？移位密码凯撒密码每个字母用后移3位的字母代换用0,1,…,25对应26个字母M=C={0,1,…,25},n=26,k=3明文信息M=meetmeafterthetogaparty密文信息C=phhwphdiwhowkhwrjdsduwb乘数密码加密函数：c=Ek(m)=k*mmodn，其中0≤m<n，gcd(k,n)=1，1<k<n解密函数：m=Dk(c)=k-1*cmodn，其k-1是k的模n乘法逆有效性Dk(c)=k-1*cmodn=k-1*(k*mmodn)modn=(k-1*k*m)modn=((k-1*k)modn)*(mmodn)modn=1*mmodn=m仿射密码加密函数：c=Ek(m)=k*m+hmodn其中，0≤m<n,gcd(k,n)=1,0<k<n，0≤h<n(k=1,h=0除外)解密函数：m=Dk(c)=k-1*(c–h)modn，其中，k-1是k的模n乘法逆仿射密码对英文字母的密码运算如下：M=C={0,1,…,25},h∈M模n=26k∈{1,3,5,7,9,11,15,17,19,21,23,25}，k-1是k的模26乘法逆k=1,h=0组合除外，故有26X12-1=311可能仿射密码例设k=5,h=3,5的模26乘法逆是21，故，Ek(m)=5m+3mod26Dk(c)=21*(c–3)mod26=21c–11mod26yesEk=254185×+333=192315=txptxpDk=19231521×-111111=25418=yesmod26移位、乘数、仿射密码适用性问题适用于有限的明文空间MM中的每个元素对应一个非负整数模数n大于M中的元素对应的最大整数，且n大于等于2密文空间是{0,1,2,…,n-1}移位、乘数、仿射密码安全性不但k、h要保密，n也要保密，否则，可以采用简单的选择明文攻击，比如移位密码k=c–mmodn

乘数密码k=c*m-1modn,选择gcd(m,n)=1仿射密码k=(c1–c2)*(m1–m2)-1modn,选择gcd(m1–m2,n)=1n必须非常大，否则，用蛮力攻击就可破解对古典代换密码的攻击针对古典代换密码(包括替换表、移位、乘数、仿射密码)可采用统计分析攻击蛮力攻击对移位、乘数、仿射密码，选择明文攻击英文字母相对使用频度分布英文字母相对使用频度分布多表代换密码用多个代替表依次对明文消息的字母进行代换的加密方法隐藏字母出现的频度对称密钥密码SymmetricKeyCryptography加密和解密使用同一个密钥对称密钥数字加密分为流加密和分组加密非公共网络Key安全信道Thisisasecretletter明文密文加密密文解密Thisisasecretletter明文AliceBob流加密(streamcipher)用一个伪随机密钥流(pseudorandomkeystream)与数据流(按位或按字节)进行异或(XOR)操作发送方，用一个伪随机密钥流对明文数据进行异或(XOR)操作(加密)接收方，用同一个伪随机密钥流对密文数据进行异或(XOR)操作(解密)根据伪随机密钥流生成方式的不同分为同步流加密(synchronousstreamcipher)自同步流加密(self-synchronousstreamcipher)或异步流加密(asynchronousstreamcipher)同步流加密密钥流的生成与密文流独立(无依赖关系)σi+1=f(σi,k)zi=g(σi,k)ciσiσi+1+fgmizikci=zi⊕mi加密移位σiσi+1+fgcimizikmi=zi⊕ci解密移位∵mi=zi⊕(zi⊕mi)σi是一位或多位的内部状态zi

是伪随机密钥流同步流加密的特点发送和接收方要求严格密钥流和数据同步，如果密码数据流出现丢失或插入，则后续的整个解密解密失败（密钥流与密文流失步）无错误传递，如果传输过程中一位密文出现错误（非丢失或插入），不会影响后续密文的解密易于遭受攻击：（1）攻击者通过删除、插入或重播密文位导致无法正确解密；（2）攻击者可能可通过改变密文的某些位导致出现他预期的结果，比如，修改某些密文位导致订单数量的改变自同步流加密密钥流的生成与密文流的1位或多位相关σi=(ci-t,…,ci-2,ci-1)zi=g(σi,k)σi=有个初始值(初始化向量)σi+gmicizikci=zi⊕mi加密ci-t…

ci-2

ci-1mikmi=zi⊕ci解密+gciziσici-t…

ci-2

ci-1σi是状态向量zi

是伪随机密钥流自同步流加密的特点接收方能自同步：如果密文的某些位被删除或插入，接收方能够自同步，因为接收方的解密仅依赖于前面固定数量的密文位有限的错误传递：如果密文的某位出现修改、删除或插入，最多导致后续有限位的数据解密错误，因为解密只依赖于前面的固定数量的密文位对密文修改攻击防护能力增加：对一个密文位的修改，导致多个密文位解密不正确，因此，更易于发现对密文的修改发散对明文的统计分析：因为之前的明文影响了对后面明文加密的结果，使得攻击者难于通过统计分析找到明文和密文的关系分组加密LbitLbitLbitLbit……BLOCK1BLOCK2BLOCK3BLOCKn明文分组加密E加密E加密E加密EMbitMbitMbitMbit……密文分组解密D解密D解密D解密DLbitLbitLbitLbit……明文分组BLOCK1BLOCK2BLOCK3BLOCKnBLOCK1BLOCK2BLOCK3BLOCKnKeyKeyKeyKey分组加密算法DES(DataEncryptionStandard)3DES(TripleDES)RC5IDEA(InternationalDataEncryptionAlgorithm)AES(AdvancedEncryptionStandard)DES算法曾经使用非常广泛的著名分组密码算法(已不安全)其产生过程是：1973美国国家标准局(NationalBureauofStandard,NBS)征集国家密码标准方案1974年NBS第二次征集时，IBM公司提出他们的方案LUCIFER1975年NBS公开了IBM算法并安排两个小组进行评价1976年NBS在征询了美国国家安全局(NationalSecurityAgency，NSA)的意见，并由NSA对IBM算法中的S-Box(替换表，substitutiontable)进行微小变化、降低了密钥长度后发表，命名为DES(曾引起密码界的广泛怀疑)DES算法64位的分组加密算法密钥64位，但实际密钥长度是56位，其他8位是奇偶校验位通过移位(shift)、排列(permutation)、代换(substitution)、异或(ExclusiveOR)操作实现密码运算加密、解密过程是对称的DES算法的安全性DES最大的安全问题是它的密钥长度才56位1990年S.Biham和A.Shamir用差分攻击方法，采用选择明文攻击，最终破解了密钥1994年的世界密码大会上，M.Matsui采用线性分析方法，利用243个已知明文成功地破译了DES算法1997年RSA公司发起了首届“向DES挑战”的竞赛，罗克.维瑟用96天破解了用DES加密的一段信息1999年12月，RSA公司发起第三届DES挑战赛，2000年1月电子前沿基金会研制的DES解密机以22.5小时成功破解了DES加密3DES随着计算技术的发展，DES越来越不能满足安全要求，特别是其密钥长度56位太短，使得可以通过蛮力攻击(brutalforceattack)破解密码通过应用三重DES算法、使用超过56位的密钥提高DES的安全3DES的四种模式DES-EEE3，使用三个不同的DES密钥顺序进行三次加密变换，解密是逆过程，密钥长度168位DES-EDE3，加密时使用三个不同的DES密钥依次进行加密-解密-加密变换，解密是逆过程，密钥长度168位DES-EEE2，进行三次加密变换，其中第一次、第三次变换的密钥相同，解密是逆过程，密钥长度112位DES-EDE2，加密时依次进行加密-解密-加密变换，其中第一次、第三次变换的密钥相同，解密是逆过程，密钥长度112位RC5由RSA公司的首席科学家RonRivest于1994年设计、1995年正式公开的一种加密算法一种分组长度w、密钥长度b和迭代轮数r都可变的分组迭代式密码，简记RC5-w/r/b采用了三种运算：异或、加和循环移位RC5的特点形式简单易于软件或硬件实现，运算速度快能适用于不同字长的系统，不同字长派生出相异的算法加密的轮数可变，这个参数用来调整加密速度和安全性的程度密钥长度可变，加密强度可调节对存储要求不高，可在SmartCard内存有限的系统中使用具有高保密性对数据实行位循环位移，增强抗抵赖能力RC5的安全性到目前为止尚未发现有效的攻击手段分析表明，r为12的RC5可抵抗差分分析和线性分析攻击IDEA1990年由瑞士联邦技术学院的来学嘉(X.J.Lai)和Massey提出64位分组密码算法，密钥长度128位使用了异或、模216加法、模216+1乘法1992年命名为IDEA(InternationalDataEncryptionAlgorithm，国际数据加密算法)IDEA的安全性到目前为止尚未发现算法的明显弱点减少密码运算的轮次，可导致算法被攻破存在一些弱密钥需要避免AES为了替代DES和3DES，1997年4月美国国家标准和技术研究院(NationalInstituteofStandardsandTechnology，NIST)发布征集AES(AdvancedEncryptionStandard)的活动1997年9月NIST公布AES要求的通告，要求AES比3DES快，至少同3DES一样安全，分组长度128位，密钥长度128/192/256位经过反复的评选、论证最后两个比利时密码学家JoanDaemen和VincentRijmen提出的Rijndael密码算法胜出，AES规范发布AES的安全性到目前为止，AES是安全的，尚未有有效的攻击分组加密的工作模式电子编码本(ElectronicCodeBook,ECB)密码分组链接(CipherBlockChaining,CBC)密码反馈(CipherFeedback,CFB)输出反馈(OutputFeedback,OFB)电子编码本(ECB)明文分组1加密密文分组1密文分组1解密明文分组1明文分组2加密密文分组2密文分组2解密明文分组2明文分组n加密密文分组n密文分组n解密明文分组n………………时间ECB的特点简单和有效可实现并行加密不能隐藏明文的模式信息，即相同明文对应相同密文，同样的信息多次出现造成泄露错误传递小：加密、传输或解密时，一块密文出错、修改、损坏仅对对应的明文造成影响对明文的主动攻击是可能的：信息块可被替换、重排、删除、重放密码分组链接(CBC)明文分组1加密密文分组1密文分组1解密明文分组1IV⊕⊕IV明文分组2加密密文分组2密文分组2解密明文分组2⊕⊕明文分组n加密密文分组n密文分组n解密明文分组n⊕⊕时间CBC的特点没有已知的并行实现算法能隐藏明文的模式信息，相同明文对应不同密文错误传递较大：加密时一块密文出错、损坏导致后续所有密文出错传输时一块密文损坏、删除、插入导致最多两块明文块无法解密还原对明文的主动攻击是不易的：一块密文被替换、重排、删除、重放，解密会出现错误安全性好于ECB密码反馈(CFB)明文分组n密文分组iIV⊕明文分组2明文分组1移位寄存器加密选择S位丢弃S明文分组1IV⊕明文分组2明文分组n移位寄存器加密选择S位丢弃L－S

S……加密解密SSL－S

S

L

LCFB的特点适用于分组密码和流密码没有已知的并行实现算法能够隐藏明文模式，相同明文对应不同密文需要共同的移位寄存器初始值误差传递较大：加密时一块密文出错、损坏使得所有后续密文出错传递时一块密文修改、损坏、插入、删除可能使得1+[(L+S-1)/S]块明文块无法解密还原输出反馈(OFB)明文分组n密文分组iIV⊕明文分组2明文分组1移位寄存器加密选择S位丢弃L－S

SS位明文分组1IV⊕明文分组2明文分组n移位寄存器加密选择S位丢弃L－S

S……加密解密SS

L

LOFB的特点适用于分组密码和流密码没有已知的并行实现算法能够隐藏明文模式，相同明文对应不同密文需要共同的移位寄存器初始值误差传递小加密或传输时一个密文块损坏只影响对应的明文块安全性较CFB差(伪随机密钥序列的周期短)分组加密的填充(padding)数据长度不一定就是分组的倍数，在数据尾部填充适当的数据使得最后一块数据的长度等于分组长度要求：(1)满足分组长度要求；(2)解密者知道哪些是原始数据哪些是填充数据ANSIX.923尾部填充字节0，最后一个字节表示填充个数…|3AC34B78258BCD7D|3AC34B7800000004PKCS7填充的字节内容就是填充的字节数…|3AC34B78258BCD7D|3AC34B7804040404ISO/IEC7816-4填充的第一个字节内容是80，后面填充00…|3AC34B78258BCD7D|3AC34B7880000000对称密钥加密的特点算法实现简单速度快密钥短密钥分发难作业问题1：将移位、乘数、仿射密码用于英文26个字母的密码变换时，n不是26行吗？26个字母不按0~25连续编号行吗？为什么？问题2：如果被加密的数据的长度正好是分组长度的整数倍，是否还需要填充？如果不需要，说明理由；如果需要，说明如何填充。假设分组长度是8字节，采用的填充方案是填充字节的内容是填充字节数。公开密钥密码体系PublicKeyCryptography也称非对称密钥密码体系，AsymmetricKeyCryptography公开密钥密码算法思想的来源1976年WhitefieldDiffie和MartinHellman在其《密码学新方向》中提出了公开密钥密码算法的思想首次提出了单向陷门(trapdoor)函数的概念，并提出了Diffie-Hellman密钥交换算法(加上使用密钥进行加密部分，它实质上也是一个公开密钥加密算法！)单向陷门函数一个单向陷门函数f(x)满足如下三个条件给定x，计算y=f(x)是容易的给定y，计算x使得y=f(x)是困难的存在δ，已知δ时对给定的任何y，若相应的x存在，则计算x使得y=f(x)是容易的Diffie-Hellman算法数学基础素数的原根(PrimitiveRoot)素数p的一个原根是一个正整数g，gmodp、g2modp，…，gp-1modp不同，且包含了1到p-1的所有整数；若g是素数p的一个原根，则（1）g，gmodp、g2modp，…，gp-1modp生成了{1,2,…,p-1}；（2）对应任意整数1≤b≤p-1，存在一个唯一的1≤i≤p-1，使得b=gimodp定理.对于任意素数p存在原根(一个或多个)Diffie-Hellman算法数学基础离散对数若n为大于1的正整数，m为整数，若b=mimodn，则b称为m的模n下的i次幂，i称为b的以m为基数的模n下的幂指数，即b的离散对数离散对数难题对于函数y=mxmodn，已知m、n、x计算y是容易的，反之，已知m、n、y计算x是困难的Diffie-Hellman密钥交换算法描述Alice和Bob共享一个公开的大素数p和大整数g，1<g<p，g是p的原根Alice随机选取大的随机整数1<x<p，并计算W=gxmodpBob随机选取大的随机整数1<y<p，并计算Z=gymodpAlice将W发送给BobBob将Z发送给AliceAlice计算K1=Zxmodp=gxymodpBob计算K2=Wymodp=gxymodpK1=K2=KAlice和Bob用密钥K进行数据加密、解密ThisisasecretletterThisisasecretletterBobAlice(y,p,g)是Bob的私钥，(Z,p,g)是Bob的公钥(x,p,g)是Alice的私钥，(W,p,g)是Alice的公钥BobAlice易于遭受中间人攻击BobAlice我是Bob我是AliceEveRSA公开密钥算法目前应用最广泛、也是最早能同时用于加密和签名的公开密钥算法由美国的RonRivest、AdiShamir、LeonardAdleman三人于1978年提出数学基础：数论中的欧拉(Euler)定理或费马小定理(Fermat’slittletheorem)和大整数的因子分解问题RSA公开密钥算法的数学基础1）Fermat’slittletheorem若p为素数，则对于任意整数a，有apmodp=amodp若进一步地，如p不能除a(即a≠kp)，则有ap-1modp=12）欧拉定理如果a和n是互素的正整数，则aφ(n)modn=1

φ(n)是Euler’stotientfunction

若n是素数，则φ(n)=n-1若n=pq，p、q是互异的素数，则φ(n)=(p-1)(q-1)RSA公开密钥算法的数学基础3）若p、q是两个互异的素数，n=pq，0≤m<n，则对于任意正整数k，根据欧拉定理或Fermat’slittletheorem可导出如下结果：

mkφ(n)+1modn=m,其中,φ(n)=(p-1)(q-1)4）已知两个互异的大素数p、q，计算n=pq是容易的；反之，若已知n是两个素数p、q的乘积，分解出p、q却是很困难的，目前无有效办法RSA公开密钥算法描述1）选择两个互异的大素数p和q，计算n=pq，计算φ(n)=(p-1)(q-1)2）选择整数1<e<φ(n)使得gcd(e,φ(n))=1(互素)3）计算得到e的模φ(n)乘法逆元d，即e*dmodφ(n)=1，其中，1<d<φ(n)4）公开密钥是P=(e,n)，私钥是S=(d,n,p,q)以上（1）到（4）由私钥拥有者完成5）对于明文m加密运算：c=memodn(使用公钥)解密运算：m=cdmodn(使用私钥)RSA公开密钥算法描述算法有效性：d是e的模φ(n)乘法逆元，e*dmodφ(n)=1，故存在一个正整数k使得e*d=kφ(n)+1cdmodn=(memodn)dmodn=medmodn=mkφ(n)+1modn=m6）将使用e、d的顺序换一下，结果同样正确（用于数字签名）加密运算：c=mdmodn(使用私钥d)解密运算：m=cemodn(使用公钥e)RSA公开密钥算法的应用BobAlice公钥私钥ThisisasecretletterThisisasecretletter公钥发布给BobAlice公钥用Alice公钥加密用私钥解密RSA公开密钥算法的中间人攻击BobAlice这是Bob公钥这是Alice公钥Eve需采用其他方案如PKI解决公钥的发布问题Eve的密钥对RSA公开密钥密码算法的安全性算法的安全性1）

加密函数c=memodn是单向门限函数：已知m求c是容易的，

反之已知c求m是困难的；若已知p、q(陷门信息)，则由c可计算出m2）安全性依赖大数n=pq的因子分解难题，及解密函数m=cdmodn的离散对数难题算法的安全性被认为等同于大数分解的难度，但缺乏理论证明(也许除了分解之外，还有其他破解方案？)要保证安全，p和q必须是足够大的素数，目前n=pq是1024位的二进制数已不很安全RSA公开密钥算法的特性首个既可以用于加密，又可以用于签名的公开密钥密码算法密钥长度(模n)要足够长RSA的加密、解密采用了大整数的指数运算，故速度比采用移位、排列、代换、异或操作的对称密钥密码算法要慢很多为了提高加密速度通常将整数e取为固定的小整数，如EDI国际标准中规定e=216+1，ISO/IEC9796中规定允许e=3，但d很大，故加密和验签速度比解密和签名速度快很多Rabin公开密钥密码算法MichaelO.Rabin提出基于大数分解难题随机选两个大的素数p和q，计算n=pq，n是公钥，p和q是私钥加密：c=m2modn,0≤m<n是明文解密：求c的{0,1,…,n-1}内的模n平方根经证明其安全性等同于大数分解难题ElGamal公开密钥密码算法由TaherElGamal提出基于Diffie-Hellman密钥交换算法和循环群上的离散对数难题包括加密算法和签名算法ElGamal加密算法ElGamal加密算法，基于循环群(Cyclicgroup)，可用于任何循环群，包括椭圆曲线上的点构成的循环群(ECC密码算法)，故其方案被广泛用于其他公开密钥加密算法群一个定义了乘法(或加法)，包含”1”(或”0”)元素的集合，集合中的任何一个元素都存在乘法(或加法)逆循环群，集合中的所有元素可由一个元素g按乘法幂gi生成(或加法倍乘i*g生成)例如：若Z*p={1,2,…,p-1}，p为素数，定义模p乘法：任意a、b

∈

Z*p，a*b定义为abmodp，则Z*p就是一个循环群，它的一个原根g可生成Z*p的所有元素，即Z*p={g,g2,…,gp-1}ElGamal加密算法描述(Z*p群)设g是Z*p的一个大原根(Primitiveroot)，即gimodp，i=1,…,p-1，生成Z*p的所有元素密钥生成Alice随机生成一个整数x，1<x

<p-1Alice计算h=gxmodpAlice保存x作为其私钥，将(h,g,p)作为公钥发布数据加密Bob随机生成一个整数y,1<y

<p-1并计算c1=gymodpBob计算共享秘密s=hymodp=gxymodp(D-H密钥)Bob计算(加密)c2=m*smodpBob将(c1,c2)=(gymodp,m*smodp)发送给AliceElGamal加密算法描述(Z*p群)数据解密Alice计算共享秘密(c1)xmodp=gxymodp=s(D-H密钥)Alice计算得到s模p乘法逆s-1Alice计算(解密)c2*s-1modp=(m*s*s-1modp)=(mmodp)*(s*s-1modp)modp=m对于Z*p群，ElGamal加密算法实际上是D-H密钥交换算法+乘数密码算法ElGamal加密算法的特点安全性依赖于离散对数难题要保证安全性，密钥要很长(p要很大)计算对称密钥采用了大整数的指数运算，速度慢密文成倍增长非对称密钥算法的特点算法实现复杂相对于对称密钥密码算法，速度较慢，故通常采用非对称密钥密码算法和对称密钥密码算法相结合的方案：随机对称密钥加密数据，非对称密钥加密随机对称密钥有的算法密钥长度长(如RSA,EIGamal算法)密钥分发容易有些算法既可用于数据加密，又可用于抗抵赖数字签名消息鉴别消息(Message)，即传输的一帧包含信息的数据消息鉴别(MessageAuthentication)即判断、确定消息的真实性和完整性，即是否由声称的发送者发送，不是伪造的，在传输过程中是否被篡改或出错，并兼顾抗抵赖常用的几种方法消息加密消息编码消息鉴别码(MessageAuthenticationCode,MAC)数字签名消息鉴别-消息加密对称密钥加密只有拥有同样密钥的人或实体才能正确对消息加密和解密：接收方能正确解密消息则说明（1）消息发送方拥有密钥；（2）传输中未修改（但有可能插入、删除）ThisisasecretletterThisisasecretletterBobAlice消息鉴别-消息加密非对称密钥加密(数字签名)私钥拥有者用私钥对发送的消息加密，接收者用发送者公钥解密，成功解密说明：（1）消息发送者拥有私钥；（2）传输中未修改(但有可能插入、删除)BobAlice公钥私钥ThisisasecretletterThisisasecretletter公钥发布给BobAlice公钥用Alice公钥解密用私钥加密消息编码采用外界不知晓的特定编码规则来保证消息的出处只能保证消息的源发性，不能保证消息的完整性很少采用消息鉴别-消息鉴别码(MAC)散列函数(HASH)，也称哈希、杂凑函数获取消息的特征(信息指纹)将任意长度的消息映射成一个固定长度的数据，称为散列值，也称消息摘要(MessageDigest)散列函数的特性单向性，从散列值无法倒推出消息无碰撞性，任何两个不同的消息的散列值不同(即不同的消息有不同的散列值)散列函数实质是多到一的映射，因此，理想的无碰撞性是不存在的，只存在概率无碰撞性，即发生碰撞的概率极小，几乎不能发生散列函数的无碰撞性弱无碰撞性散列函数h(x)的弱无碰撞性是指在消息特定的明文空间X，给定任一消息x∈X，在计算上几乎找不到不同于x的xˊ∈X，使得h(x)=h(xˊ)强无碰撞性散列函数h(x)的强无碰撞性是指给定消息x∈X，X为x的所有可能明文数据空间，在计算上几乎找不到不同于x的xˊ∈X，使得h(x)=h(xˊ)（x在更大的数据空间）散列函数的设计要考虑强无碰撞性，实际应用中真正有