elgamal公钥密码体制

ElGamal公钥密码体制1、问题描述设计ElGamal公钥密码体制算法。

2、算法设计(1)选取大素数p和p的一个原根a，(a,p)=1,1<a<p(2)随机选取整数d，1<d<p-1，计算b≡ad (mod p)；p,a,b为公钥，d为私钥(3)加密：对0<m<p，秘密的随机选取整数k,1<k<p-1,加密后密文为c=(c1 ，c2 ),c1 ≡ak (mod p), c2 ≡ m bk (mod p)(4)解密：明文m ≡c2 ( c1 d) -1 (mod p)主要步骤3、算法分析该算法的基础是找到一个原根，大数的原根产生过程比较慢，本人目前也只能产生8位以内的素数的原根，还有待改进。

同时也涉及到模幂运算，选取的幂指数如果较大，时间复杂度也会相应的增加。

int inverse(int a,int m){long int c,d;int j;int q[100],r[100],t[100],s[100];c=a;d=m;r[0]=c;r[1]=d;s[0]=1;s[1]=0;t[0]=0;t[1]=1;for(j=1;r[j]!=0;j++){q[j]=(int)(r[j-1]/r[j]);r[j+1]=r[j-1]-q[j]*r[j];if(j>=2){s[j]=s[j-2]-q[j-1]*s[j-1];t[j]=t[j-2]-q[j-1]*t[j-1];}}return s[j-1];}int gcd(int a,int b){int c;if(a<b){c=b;b=a;a=c;}while(b!=0){c=b;b=a%b;a=c;}return a;}void main(){int p,g,k,s,x,r,t=1,i,j,f,y,m,M;cin>>p>>g>>k;s=2;for(i=1;i<=k;i++){t*=s;t=t%p;}while(t<0){t=t+p-1;}cout<<"public key is"<<"("<<t<<","<<g<<","<<p<<")"<<endl;cin>>r;if(gcd(p-1,r)!=1)cout<<"the data is not suitable"<<endl;x=1;for(j=1;j<=r;j++){x*=s;x=x%p;}cin>>m;f=inverse(r,p-1);y=(m-k*x)*f%(p-1);while(y<0){y=y+p-1;}cout<<"the signature is"<<"("<<x<<","<<y<<")"<<endl;for(i=1;i<=m;i++){g*=g;}g=g%p;for(i=1;i<x;i++){y*=y;}for(j=1;j<y;j++){x*=x;}M=x*y%p;if(M=p){cout<<"the signature is useful"<<endl;}else{cout<<"the signature is not useful"<<endl;}}运行结果。

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

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

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

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

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

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

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

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

一一、是非判断题（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.密钥分配和协商的最大区别是：密钥分配是通信双方中一方或密钥分配中心选取一个秘密密钥发给双方，而密钥协商是保密通信双方（或更多方）通过公开信道的通信来共同形成秘密密钥的过程。

ElGamal加密算法原理ElGamal加密算法是一种公钥密码体制，由Taher Elgamal在1985年提出。

它基于离散对数问题的困难性，被广泛应用于保护数据的机密性和安全通信。

ElGamal加密算法涉及到两个关键方面：密钥生成和加解密过程。

在下面的内容中，我们将详细介绍这些方面的基本原理。

1. 密钥生成ElGamal加密算法使用一对相关联的公钥和私钥来进行加解密操作。

下面是生成这些密钥的步骤：1.选择一个大素数p作为有限域，以及一个生成元g。

2.随机选择一个整数x（0 < x < p-1），作为私钥。

3.计算y = g^x mod p，并将(x, y, p, g)作为公钥，(x)作为私钥。

在这个过程中，p和g是公开信息，而x是保密的。

2. 加解密过程加密假设Alice想要向Bob发送一条消息m。

下面是Bob使用ElGamal加密算法对消息进行加密的步骤：1.Alice首先获取Bob的公钥信息(y, p, g)。

2.Alice选择一个随机整数k（0 < k < p-1）。

3.Alice计算c1 = g^k mod p，并发送给Bob。

4.Alice计算c2 = (y^k * m) mod p，并发送给Bob。

在这个过程中，c1和c2是加密后的消息，Alice只需要将它们发送给Bob即可。

解密Bob接收到加密后的消息(c1, c2)后，可以使用ElGamal加密算法进行解密。

下面是解密的步骤：1.Bob使用自己的私钥x计算s = c1^x mod p。

2.Bob计算m’ = (s^(-1) * c2) mod p。

最终，Bob可以得到原始消息m’。

3. 安全性分析ElGamal加密算法基于离散对数问题的困难性，具有较高的安全性。

攻击者需要解决离散对数问题才能成功破解加密文本。

然而，在实际应用中，ElGamal加密算法存在一些安全性问题和限制：•密文扩张：加密后的消息长度为明文长度的两倍或更多。

信息安全与密码学院：数学与统计学院专业: 数学与应用数学班级：12级数应(3)班姓名：田佳学号： 20121010357信息安全与密码知识点总结第一章信息安全概论§1 信息安全的目标§1.1 信息系统中的主要安全问题1、网络可靠性问题（备份,网络管理，计费等)2、系统本身的缺陷（芯片、操作系统,数据库后门等)3、恶意攻击和破坏（黑客攻击,病毒破坏等)4、信息安全问题（信息窃取,假冒,抵赖等)网络与信息安全的主要任务（1）网络安全的任务：保障各种网络资源稳定可靠的运行，受控合法的使用。

（2）信息安全的任务：保证：机密性、完整性、不可否认性、可用性（3）其他方面：病毒防治，预防内部犯罪§1.2 我国信息安全的现状§1.3 信息安全威胁信息安全威胁：指某个人、物、事件或概念对信息资源的保密性、完整性、可用性或合法使用性等等所造成的危险。

虽然人为因素和非人为因素都可以对通信安全构成威胁，但是精心设计的人为攻击威胁最大。

网络安全性威协：（1）截获(interception)（2）中断(interruption)（3）篡改(modification）（4）伪造(fabrication)主动与被动攻击被动攻击：目的是窃听、监视、存储数据，但是不修改数据。

很难被检测出来，通常采用预防手段来防止被动攻击，如数据加密。

主动攻击：修改数据流或创建一些虚假数据流。

常采用数据加密技术和适当的身份鉴别技术。

网络安全攻击截获：以保密性作为攻击目标，表现为非授权用户通过某种手段获得对系统资源的访问，如搭线窃听、非法拷贝等中断：以可用性作为攻击目标，表现为毁坏系统资源，切断通信线路等篡改：以完整性作为攻击目标，非授权用户通过某种手段获得系统资源后，还对文件进行窜改，然后再把篡改过的文件发送给用户。

伪造：以完整性作为攻击目标，非授权用户将一些伪造的、虚假的数据插入到正常系统中§1.4 常见的安全威胁信息泄露，破坏完整性，拒绝服务，非法使用，窃听，业务流分析，假冒，旁路控制，授权侵犯，特洛伊木马，陷阱门，抵赖，重放，计算机病毒安全威胁分类物理环境：自然灾害 ,电源故障、设备被盗通信链路：安装窃听装置或对通信链路进行干扰网络系统：互联网的开放性、国际性操作系统：系统软件或硬件芯片中的植入威胁应用系统：木马、陷阱门、逻辑炸弹管理系统：管理上杜绝安全漏洞§1.5 信息安全基本要素机密性，完整性，可用性，可控性，可审查性§1.6 信息安全的目标安全工作的目的就是为了在安全法律、法规、政策的支持与指导下，通过采用合适的安全技术与安全管理措施，完成：1，使用访问控制机制，阻止非授权用户进入网络，即“进不来”，从而保证网络系统的可用性。

ElGamal离散对数介绍ElGamal是一种基于离散对数问题的公钥密码体制。

它由塞尔弗·埃尔加马尔在1985年提出，是非对称密钥加密算法中的一种重要算法。

ElGamal算法具有安全性高、可证明安全等特点，在实际应用中得到广泛使用。

离散对数问题在介绍ElGamal算法之前，首先需要了解离散对数问题（Discrete Logarithm Problem）。

离散对数问题是指给定一个有限群G和元素g，找到满足g^x ≡ h (mod p)的整数x。

其中p是一个大素数，g是群G的生成元，h是群G中的一个元素。

离散对数问题被认为是计算复杂度非常高的问题，目前没有有效的算法可以在多项式时间内解决。

这使得离散对数成为了很多公钥密码体制的基础。

ElGamal加密算法ElGamal加密算法利用了离散对数问题来实现公钥加密和解密过程。

它包括了密钥生成、加密和解密三个主要步骤。

密钥生成1.选择一个大素数p作为模，并选择一个生成元g。

2.随机选择一个整数a，满足1 ≤ a ≤ p-2。

3.计算h = g^a (mod p)。

4.公钥为(p, g, h)，私钥为a。

加密假设要加密的明文为m，加密过程如下： 1. 随机选择一个整数k，满足1 ≤ k ≤ p-2。

2. 计算c1 = g^k (mod p)。

3. 计算c2 = m * h^k (mod p)。

4. 密文为(c1, c2)。

解密解密过程如下： 1. 根据私钥a计算s = c1^a (mod p)。

2. 计算m’ = c2 * s^-1 (mod p)。

其中s^-1是s的模p的逆元素。

3. 明文为m’。

安全性分析ElGamal算法的安全性基于离散对数问题的困难性。

在大素数p和合适的参数选择下，破解ElGamal加密需要计算离散对数，这是一个非常耗时的任务。

然而，在实际应用中，需要注意一些安全性问题。

例如，如果相同的随机数k被重复使用来加密不同的明文，则可以通过观察两个密文之间的关系来推导出私钥a。

Elgamal算法ElGamal算法，是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系一．ElGamal算法定义：ElGamal算法，是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系。

既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。

在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K。

二．密钥产生方法密钥对产生办法。

首先选择一个素数p，获取一个素数p的一个原根g(若g模p的阶等于φ(m)，则称a为模m的一个原根。

（其中φ(m)表示m的欧拉函数）) 和一个随机数x，且g和x 均小于p, 计算y = g^x ( mod p )，则其公钥为y, g 和p。

私钥是x。

g和p 可由一组用户共享。

ElGamal用于数字签名。

被签信息为M，首先选择一个随机数k, k与p - 1互质，计算a = g^k ( mod p )再用扩展Euclidean 算法对下面方程求解b：M = xa + kb ( mod p - 1 )签名就是( a, b )。

随机数k须丢弃。

验证时要验证下式：y^a * a^b ( mod p ) = g^M ( mod p )同时一定要检验是否满足1<= a < p。

否则签名容易伪造。

ElGamal用于加密。

被加密信息为M，首先选择一个随机数k，k与p - 1互质，计算a = g^k ( mod p )b = y^k M ( mod p )( a, b )为密文，是明文的两倍长。

解密时计算M = b / a^x ( mod p )ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。

素数p必须足够大，且p-1至少包含一个大素数因子以抵抗Pohlig & Hellman算法的攻击。

M一般都应采用信息的HASH值(如SHA 算法)。

ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。