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;}}运行结果。

不可区分性在公钥密码学中的应用摘要：本文主要总结了不可区分性在公钥密码体制中的运用，这些运用主要包括如何刻画密码体制的安全性（语义安全性）、如何通过规约的方式利用不可区分实验证明密码体制的安全性、以及一些常见的密码体制中不可区分性的作用。

全文主要分为三个部分，第一部分主要介绍了一些基础知识，包括密码体制的组成以及完善保密密码体制的含义，如何利用不可区分性来等价描述完善保密密码体制。

第二部分主要介绍了不可区分实验（游戏）在公钥密码学中的应用。

这一部分先对攻击者的层次进行了划分，之后介绍了如何用不可区分实验来给最基本的密码体制的语义安全性下定义。

这一部分最后利用CCA2的语义安全性作为例子说明如何利用不可区分实验定义拥有特定防御功能的公钥密码体制的语义安全性。

第三部分介绍了规约证明的相关内容，规约证明现如今已成为现代公钥密码学可证明安全理论常用的证明方法，而两个问题规约的过程中与不可区分性密不可分。

第四部分主要举了一个例子来说明不可区分性在证明密码体制安全性中的应用。

本文对公钥密码学中的不可区分性理论做了比较简单的总结和归纳，不可区分性在公钥密码学可证明安全理论中有着十分重要的地位，本文对刚刚接触不可区分性的学者有着一定的帮助。

第一部分：基础知识及不可区分性的定义这一部分内容主要介绍一下有关于不可区分性的基础知识，包括密码体制的组成、完善保密密码体制、完美不可区分性的含义以及敌手不可区分性的含义。

首先先给出密码体制的定义：定义1.1 密码体制]1[一个密码体制由三个部分构成：密钥产生算法Gen、加密算法Enc、解密算法Dec。

他们的功能如下：（1）密钥产生算法Gen 是一个概率算法，能够根据方案定义的某种分布选择并输出一个密钥k .（2）加密算法Enc ，输入为密钥k 和明文m ，输出为密文c 。

把使用密钥k 加密明文m 记为Enc k (m ).（3）解密算法Dec ，输入为密钥k 和密文c ，输出为明文m 。

elgamal密码例题摘要：1.引言2.Elgamal加密算法的基本原理3.Elgamal加密算法的加密和解密过程4.Elgamal密码的例题解析5.总结正文：Elgamal密码是一种公钥加密算法，它是由Taher Elgamal在1985年提出的。

该算法基于离散对数问题，具有较高的安全性和强大的抗攻击性。

它广泛应用于网络通信、电子商务等领域。

下面，我们将通过一个例题来解析Elgamal密码的加密和解密过程。

假设Alice想给Bob发送一条加密信息，信息内容为“Hello, Bob!”。

首先，Alice需要从Bob那里获得公钥，通常是通过一个可信任的第三方机构获取。

Bob的公钥包括一个大的素数p、一个与p互质的整数x以及一个满足特定条件的y。

其中，p和x组成一个公钥对(pk)，y则作为Bob的私钥。

有了Bob的公钥(pk)，Alice就可以开始加密信息了。

加密过程如下：1.Alice随机选择一个整数k，范围在[1, p-1]之间，作为加密密钥。

2.将信息“Hello, Bob!”转换为ASCII编码的数字序列，例如“104 101 108 108 111 44 32 111 114 108 100”。

3.用k对信息中的每个数字进行加密，具体操作是将数字乘以k，然后对p取模。

得到加密后的数字序列。

4.将加密后的数字序列按照[1, p-1]的顺序排列，得到一个新的序列。

5.将新序列中的每个数字都替换为对应的x的k次幂，即x^k。

加密完成后，Alice将加密后的数字序列发送给Bob。

Bob收到信息后，使用自己的私钥y进行解密：1.Bob将收到的加密数字序列中的每个数字都替换为对应的x的-k次幂，即x^(-k)。

2.将解密后的数字序列转换回ASCII编码，得到解密后的信息。

通过这个例题，我们可以看到Elgamal密码的加密和解密过程。

值得注意的是，Elgamal密码的安全性依赖于离散对数问题的难解性。

ElGamal算法进⾏加密和解密的基本原理及实现1、准备步骤1）取⼤素数 p 和 g（g < p，g 最好是 p 的素根）注解：若 g 是素数 p 的⼀个素根，则 g mod p, g^2 mod p , …, g^p-1 mod p 是 1 到 p - 1 的排列2）随机选取⼀整数 x （2 <= x <= (p - 2)，(p，g，x) 是私钥）3）计算 y = g^x (mod p) （ (p，g，y) 是公钥）2、加密过程1）随机选取⼀整数 k （2 <= k <= (p - 2) 且 k 与 (p - 1) 互素）2）计算 a = g^k mod p，b = m*y^k mod p（m 为要加密的明⽂）3）密⽂ C = (a, b)3、解密过程1）m = b * a^(-x) mod p注解：b * a^(-x) mod p Ξ m * y^k * g^(-xk) Ξ m * g^(xk) * g^(-xk) Ξ m加密及解密的实现（Java）：import java.util.ArrayList;public class Main {static ArrayList<Integer> suArr = new ArrayList<>();public static void main(String[] args) {int max = 8096, p, g, x, y, k, a, b, buffer_data;char[] m = "abc".toCharArray(); // 加密字符串"abc"ArrayList<Integer> C = new ArrayList<>(); // 加密后的密⽂int size1;suArr.add(2);// 随机取⼀个⼩于2048的素数gfor (int i = 3; i <= 2048; i++) {if (isSuShu(i)) suArr.add(i);}size1 = suArr.size();g = getRanNum(size1);// 随机取⼀个⼤素数pfor (int i = 2049; i <= max; i++) {if (isSuShu(i)) suArr.add(i);}p = getRanNum(suArr.size() - size1, size1);// x的范围是[2,p-2]x = (int)(Math.random() * (p-3))+2;// k的范围是[2,p-2]且k与p-1互素k = (int)(Math.random() * (p-3))+2;while (isHuZhi(k, p-1) != 1) {k = (int)(Math.random() * (p-3))+2;}// y = g^x mod py = myPow(g, x, p);// a = g^k mod pa = myPow(g, k, p);C.add(a);// 特殊数据test// a = 1434;// g=1117;// k=2403;// p=6101;// x=714;// y=2271;// 加密过程，即计算b = m*y^k mod p (m是明⽂)for (char c : m) {C.add((int)c*myPow(y, k, p) % p);}buffer_data = myPow(a, x, p);buffer_data = exGcd(buffer_data, p)[0]; // 求(a^x)^(-1) mod p等价于求a^(-x) mod pif (buffer_data < 0) buffer_data += p;// 将解密后的明⽂输出for (int i = 1; i < C.size(); i++) {System.out.print((char)(C.get(i) * buffer_data % p));}}// 判断⼀个数是否为素数public static boolean isSuShu(int num) {int max = (int) Math.sqrt(num);for (int i = 2; i <= max; i++) {if (num % i == 0)return false;}return true;}// 在素数数组中随机取⼀个数public static int getRanNum(int size) {return suArr.get((int) (Math.random() * (size)));}// 在素数数组中的(left, arr.size())之间随机取⼀个数public static int getRanNum(int size, int left) {return suArr.get((int) (Math.random() * (size)) + left);}// 判断两个数是否互质public static int isHuZhi(int a, int b) {return b == 0 ? a : isHuZhi(b, a % b);}public static int myPow(int a, int b, int m) {int res = 1;a %= m;while (b != 0) {if ((b & 1) == 1)res = (res * a) % m;a = (a * a) % m;b >>= 1;}return res;}public static int getSuGen(int p) {boolean isSuGen;for (int g : suArr) {isSuGen = true;for (int i = 1; i < p; i++) {if (myPow(g, i, p) != i) isSuGen = false;}if (isSuGen) return g;}return 2; // 如果在素数数组中找不到p的素根，则返回⼀个默认值}// 扩展欧⼏⾥得算法求a模b的逆元public static int[] exGcd(int a, int b) {if (b == 0) {int[] arr = new int[]{1, 0};return arr;} else {int[] arr = exGcd(b, a % b);int x = arr[0];arr[0] = arr[1];arr[1] = x - (a / b) * arr[1];return arr;}}}/** 参考：* 素根的定义：a是素数p 的⼀个素根，如果a mod p, a^2 mod p , …, a^p-1 mod p 是1到p-1的排列，称a是P的⼀个素根* 加密时x和k的选取：https:///qq_34490018/article/details/79758620 */。