ElGamal和背包体制

信息安全工程师综合知识大纲考点：密码体制分类【考点分析】：重点掌握。

【考点内容】：根据密钥的特点，密码体制分为私钥和公钥密码体制两种，而介入私钥和公钥之间的密码体制称为混合密码体制。

一、私钥密码体制私钥密码体制又称为对称密码体制，当用户应用这种体制时，消息的发送者和接收者必须事先通过安全渠道交换密钥，以保证发送消息或接收消息时能够有供使用的密钥。

特点：一个密钥（加密和解密使用相同的密钥）。

优点：加解密简单（私钥密码算法处理速度快，常将其用作数据加密处理）。

缺点：密钥分配问题、密钥管理问题、无法认证源。

典型算法：DES、IDEA、AES等。

二、公钥密码体制1976年，W.Diffie和M.E.Hellman发表《密码学新方向》提出公钥密码体制思想。

公钥密码体制又称为非对称密码体制，其基本原理是在加密和解密的过程中使用不同的密钥处理方式，其中，加密密钥可以公开，而只需要把解密密钥安全存放即可。

在安全性方面，密码算法即使公开，由加密密钥推知解密密钥也是计算不可行的。

不适合大数据、明文加密。

特点：双密钥、用公钥推私钥在计算上不可行。

优点：密钥分发方便、密钥保管量少、支持数字签名。

缺点：加密速度慢（密钥有1024位，计算量大，不适合加密大数据）。

原理：发送方甲方和接收方乙方都分别有各自的公钥和私钥，且甲方的公钥加密只能由甲方的私钥解密，乙方同。

双方的公钥是可以共享的，但是私钥只能自己保密，此时，甲方要传输数据给乙方，明显应该使用乙方的公钥来加密，这样，只有使用乙方的私钥才能解密，而乙方的私钥只有乙方才有，保证了数据的保密性，也不用分发解密的密钥。

目前由三种公钥密码体制类型被证明是安全和有效的，即RSA体制，ELGamal体制及椭圆曲线密码体制。

三、混合密码体制混合密码体制利用公钥密码体制分配私钥密码体制的密钥，消息的收发双方共用这个密钥，然后按照私钥密码体制的方式，进行加密和解密运算。

混合密码体制的工作原理：第一步，消息发送者Alice用对称密钥把需要发送的消息加密。

ElGamal公钥密码体制是一种基于离散对数问题的非对称加密算法，由Tahir ElGamal 在1985年提出。

在ElGamal密码体制中，公钥包括一个大素数和该素数的一个本原元，私钥则是一个随机数。

通过公钥加密的消息可以使用私钥进行解密，而私钥签名的消息可以使用公钥进行验证。

ElGamal公钥密码体制的安全性基于离散对数问题的难解性，即在一个有限域中，给定元素g和h，找到整数x使得h=g^x在计算上是不可行的。

由于离散对数问题的难解性，ElGamal密码体制可以提供较高的安全性。

与RSA算法相比，ElGamal算法在加密和签名方面都具有较高的效率和灵活性。

此外，由于ElGamal算法是基于离散对数问题的，因此它可以用于构造其他密码学方案，如数字签名、密钥协商等。

需要注意的是，虽然ElGamal公钥密码体制具有较高的安全性，但在实际应用中仍需要注意密钥的生成、存储和使用安全，以避免潜在的安全风险。

对称密码体制和非对称密码体制一、对称加密(Symmetric Key Encryption)对称加密是最快速、最简单的一种加密方式，加密（encryption）与解密（decryption）用的是同样的密钥（secret key）。

对称加密有很多种算法，由于它效率很高，所以被广泛使用在很多加密协议的核心当中。

自1977年美国颁布DES（Data Encryption Standard）密码算法作为美国数据加密标准以来，对称密码体制迅速发展，得到了世界各国的关注和普遍应用。

对称密码体制从工作方式上可以分为分组加密和序列密码两大类。

对称加密算法的优点：算法公开、计算量小、加密速度快、加密效率高。

对称加密算法的缺点：交易双方都使用同样钥匙，安全性得不到保证。

此外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的惟一钥匙，这会使得发收信双方所拥有的钥匙数量呈几何级数增长，密钥管理成为用户的负担。

对称加密算法在分布式网络系统上使用较为困难，主要是因为密钥管理困难，使用成本较高。

而与公开密钥加密算法比起来，对称加密算法能够提供加密和认证却缺乏了签名功能，使得使用范围有所缩小。

对称加密通常使用的是相对较小的密钥，一般小于256 bit。

因为密钥越大，加密越强，但加密与解密的过程越慢。

如果你只用1 bit来做这个密钥，那黑客们可以先试着用0来解密，不行的话就再用1解；但如果你的密钥有1 MB大，黑客们可能永远也无法破解，但加密和解密的过程要花费很长的时间。

密钥的大小既要照顾到安全性，也要照顾到效率，是一个trade-off。

分组密码：也叫块加密(block cyphers)，一次加密明文中的一个块。

是将明文按一定的位长分组，明文组经过加密运算得到密文组，密文组经过解密运算（加密运算的逆运算），还原成明文组，有 ECB、CBC、CFB、OFB 四种工作模式。

序列密码：也叫流加密(stream cyphers)，一次加密明文中的一个位。

公钥加密体制私钥加密体制（对称加密体制、单钥加密体制）公钥加密体制（非对称加密体制、双钥加密体制）私钥加密体制的优缺点：1．运算速度快，密钥产生容易。

2．当用户很多、分布很广时，密钥的分配的存储就成了大问题；3．不能实现数字签名。

一、Diffie －Hellman 加密体制二、 RSA 加密体制RSA 体制是由R.L.Rivest, A.Shamir 和L.Adlemansh 在1978年提出的。

它既可用于加密、也可用于数字签名，标准化组织ISO ，ITU 及SWIFT 等均已接受RSA 体制作为标准。

RSA 密码体制的提出是密码学史上的一个里程碑，RSA 的基础是数论中的欧拉定理，安全性依赖于大数的因数分解的困难性(即哥德巴赫猜想这一难题)。

由于其算法简单，在实际应用中容易实现，因此在理论上是最为成功的密码体制，它是目前应用最为广泛的公钥密码体制之一。

基于此，第4章中我们采用该密码体制来加密传送会话密钥。

下面给出几个定理及推论，它们是RSA 体制的数学理论背景。

定理2.1（欧拉定理）若整数a 和n 互素，则n a n mod 1)(≡ϕ其中)(n ϕ是比n 小但与n 互素的整数的个数。

特别地，当n 为素数时，由欧拉定理可得下面的推论：推论2.1（费马小定理）若p 为素数，1),(=p a ，则：p a p mod 11≡-根据欧拉定理，可以证明下面的定理，它直接给出关于RSA 密码体制中的解密变换是加密变换的逆的证明。

定理2.2 设p 和q 是两个不同的素数，pq n =，对任意的整数x (n x <≤0)，及任意的非负整数k ，有：)(mod 1)(n x x n k ≡+ϕ定理2.3（中国剩余定理）设k m m m ,,,21 是两两互素的正整数，k m m m M 21=， ii m M M =),,2,1(k i =，则同余式组 k i m b x i i ,,2,1),(mod =≡有唯一解)(mod 222111M y M b y M b y M b x k k k +++≡其中.,2,1),(mod 1k i m y M i i i =≡由于篇幅关系，以上定理及推论的证明略。

1数字签名《现代密码学》第八讲2上章内容回顾公钥密码体制的提出及分类公钥密码体制的基本概念单向陷门函数的概念设计公钥加密算法--背包密码体制RSA算法及攻击方法ElGmal算法椭圆曲线密码体制3本章主要内容数字签名的基本概念一般数字签名算法Z RSA数字签名技术Z 数字签名标准Z 基于离散对数的数字签名Z 椭圆曲线数字签名4数字签名的基本概念手写签名与数字签名的区别手写签名是一种传统的确认方式，如写信、签订协议、支付确认、批复文件等.手写签名是所签文件的物理组成部分；数字信息没有固定的物理载体，如何使数字签名与所签文件捆绑在一起？手写签名通过与标准签名比较或检查笔迹来验证，受验证人主观影响大；二进制数字信息无法用人眼辨识，但可以使用数学算法来验证数字签名，不受验证人主观影响。

手写签名不易复制；二进制数字信息，十分容易复制，所以必须防止数字签名重复使用。

5数字签名和消息认证码的异同：消息完整性验证、消息源认证.消息认证的作用是保护通信双方以防第三方的攻击，然而却不能保护通信双方中的一方防止另一方的欺骗或伪造.①B伪造一个消息并使用与A共享的密钥产生该消息的认证码，然后声称该消息来自于A.②由于B有可能伪造A发来的消息，所以A就可以对自己发过的消息予以否认.数字签名的基本概念6数字签名技术则可有效解决这一问题, 类似于手书签名，数字签名应具有以下性质：①能够验证签名产生者的身份，以及产生签名的日期和时间.②能保证被签消息的内容的完整性.③数字签名可由第三方公开验证，从而能够解决通信双方的上述争议.数字签名在网络安全中提供数据完整性、数据源认证性、数据不可否认性等性质数字签名的基本概念7所谓数字签名（Digital Signature ），也称电子签名，是指附加在某一电子文档中的一组特定的符号或代码，它是利用数学方法对该电子文档进行关键信息提取并与用户私有信息进行混合运算而形成的，用于标识签发者的身份以及签发者对电子文档的认可，并能被接收者用来验证该电子文档在传输过程中是否被篡改或伪造.81976，W Diffie 和M Hellman 在“New Directions in Cryptography ”, 首先提出了数字签名的思想并猜测存在这样的方案1978，R Rivest, A Shamir, 和L Adleman 发明了RSA 算法可以用作数字签名算法.1984, S Goldwasser, S Micali, 和R Rivest 首次粗略提出了数字签名算法的安全性要求. 2004，中国颁布电子签章法9一般签名算法包含密钥生成（公钥/私钥）消息签名S=Sig x (M)用私钥对消息（消息摘要）进行签名运算 消息验证用公钥验证消息的签名是否正确，输出“True ”或“False ”一般数字签名算法()()(),x x x True S Sig M Ver S M False S Sig M =⎧⎪=⎨≠⎪⎩10数字签名的攻击：惟密钥攻击：攻击者只有用户公开的密钥. 已知消息攻击：攻击者拥有一些消息的合法签名，但是消息不由他选择.选择消息攻击：攻击者可以自由选择消息并获取消息的签名.攻击结果：完全破译：攻击者恢复出用户的密钥. 一致伪造：攻击者对于任意消息可以伪造其签名. 选择性伪造：攻击者可以对一个自己选取的消息伪造签名.存在性伪造：攻击者可以生成一些消息的签名，但在伪造前对该消息一无所知.数字签名的基本概念11①参数和密钥生成选两个保密的大素数p 和q ，计算n=p ×q ，φ(n)=(p-1)(q-1)；选一整数e ，满足1<e<φ(n)，且gcd(φ(n),e)=1；计算d ，满足d ·e ≡1 mod φ(n)；以{e,n}为公开钥, {d,n}为秘密密钥.一般数字签名算法--RSA12②签名过程设消息为m ，对其签名为s ≡m d mod n③验证过程接收方在收到消息m 和签名s 后，验证是否成立，若成立，则发送方的签名有效.?mod e m s n≡一般数字签名算法--RSA13加密算法和签名算法同用，攻击者可以方便解密一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。

密码学的发展简史中国科学院研究生院信息安全国家重点实验室聂旭云学号：2004 密码学是一门年轻又古老的学科，它有着悠久而奇妙的历史。

它用于保护军事和外交通信可追溯到几千年前。

这几千年来，密码学一直在不断地向前发展。

而随着当今信息时代的高速发展，密码学的作用也越来越显得重要。

它已不仅仅局限于使用在军事、政治和外交方面，而更多的是与人们的生活息息相关：如人们在进行网上购物，与他人交流，使用信用卡进行匿名投票等等，都需要密码学的知识来保护人们的个人信息和隐私。

现在我们就来简单的回顾一下密码学的历史。

密码学的发展历史大致可划分为三个阶段：第一个阶段为从古代到1949年。

这一时期可看作是科学密码学的前夜时期，这段时间的密码技术可以说是一种艺术，而不是一门科学。

密码学专家常常是凭直觉和信念来进行密码设计和分析，而不是推理证明。

这一个阶段使用的一些密码体制为古典密码体制，大多数都比较简单而且容易破译，但这些密码的设计原理和分析方法对于理解、设计和分析现代密码是有帮助的。

这一阶段密码主要应用于军事、政治和外交。

最早的古典密码体制主要有单表代换密码体制和多表代换密码体制。

这是古典密码中的两种重要体制，曾被广泛地使用过。

单表代换的破译十分简单，因为在单表代换下，除了字母名称改变以外，字母的频度、重复字母模式、字母结合方式等统计特性均未发生改变，依靠这些不变的统计特性就能破译单表代换。

相对单表代换来说，多表代换密码的破译要难得多。

多表代换大约是在1467年左右由佛罗伦萨的建筑师Alberti发明的。

多表代换密码又分为非周期多表代换密码和周期多表代换密码。

非周期多表代换密码，对每个明文字母都采用不同的代换表（或密钥），称作一次一密密码，这是一种在理论上唯一不可破的密码。

这种密码可以完全隐蔽明文的特点，但由于需要的密钥量和明文消息长度相同而难于广泛使用。

为了减少密钥量，在实际应用当中多采用周期多表代换密码。

在16世纪，有各种各样的多表自动密钥密码被使用，最瞩目的当属法国人Vigtnère的Vigenère密码体制。

一一、是非判断题（10分）1.差分分析是一种攻击迭代密码体制的选择明文攻击方法，所以，对于DES和AES都有一定的攻击效果。

（对）2.反馈移位寄存器输出序列生成过程中，抽头位对输出周期长度的影响起着决定性的作用，而初态对输出周期长度没影响。

（对）二、选择题（15分）1.公钥密码体制至少能抵御的攻击是（C.选择明文攻击）2.适合文件加密，而且有少量错误时不会造成同步失败，是软件加密的最好选择，这种分组密码的操作模式是指（D.输出反馈模式）3.按目前的计算能力，RC4算法的密钥长度至少应为（C.128）位才能保证安全强度。

4.密钥在其生命生命周期中处于不同的状态，每种状态包含若干时期，那么密钥备份时期是密钥处于（B.使用状态）5.量子密码更适合实现下面哪项密码技术。

（D.密钥分发）6.当用户收到一个证书是，应当从（C.CRL）中检查证书是否已经被撤销。

（CRL：证书撤销列表）A.在PKI中，关于RA的功能，下面说法正确的是（B.验证申请者身份）。

7.数字水印是信息隐藏技术研究领域的重要分支，现主要应用领域是（A.版权保护）8.在DES算法中，如果给定初始密钥K，经子密钥产生器产生的各个子密钥都相同，则称该密钥K为弱密钥，DES算法中弱密钥的个数为（B.4个）。

9.生日攻击是针对于下面哪种密码算法的分析方法（D.MD5）。

10.指数积分法是针对下面哪种密码算法的分析方法（C.ElGamal）11.密钥存档是密钥处于（C.过期状态）三、填空题（15分）1.关于DES算法的安全性，若Ek（m）=Dk（m），则这样的密钥称为弱密钥，又其互补性使DES在选择明文攻击下所需的工作量减半。

2.选择合适的n级线性反馈移位寄存器可使序列的周期达到最大值2^n-1，这样序列称为m 序列，但敌手知道这序列中一段长为 n 的明密文对即能破译其后序列的密文。

3.密钥分配和协商的最大区别是：密钥分配是通信双方中一方或密钥分配中心选取一个秘密密钥发给双方，而密钥协商是保密通信双方（或更多方）通过公开信道的通信来共同形成秘密密钥的过程。