RSA&ElGamal算法实现

RSA&ElGamal算法实现 信息保障与安全 实验报告 学 院 计算机科学与技术 专 业 计算机科学与技术 年 级 2007级 姓 名 张炎辉 学 号 3007216108 2010年 4 月 28 日 简化RSA、ElGamal算法 1、试验题目 1.1题目 简化RSA、ElGamal算法》 《 1.2具体要求 任务:(1) 编写一个程序实现简化RSA加密算法如图1; (2) 编写一个程序实现简化ElGamal加密算法如图2。 要求:两个程序都应该具有一个简单的输入{密钥长度，公开密钥，明文M (?15 bits) C (?15 bits) M (?15 bits) DRAS ERAS N=pq, e (?15 N=pq, d (?15 密钥发生器 bits) bits) 图1 M (?15 bits) C (?15 bits) M (?15 bits) DElGamEElGam al al p, α, y (?15 bits) ?15 bits) p, a ( 密钥发生器 图2 M/密文C}和输出{秘密密钥，密文C /明文M }界面。所有的输入输出数据用十进制表示。 1.3 测试用例 (1) 简化RSA加密 密钥长度=15 bits，N=pq=131×191=25021，e=3，d=16467，M=24021，C=14307。 (2) 简化ElGamal加密 1520密钥长度=14 bits，p=9973，α=11，y=5445，a=1751，M=7651，C={11, 1028(mod 9973)，5905}。 1 简化RSA、ElGamal算法 2、算法实现 2.1 2 简化RSA、ElGamal算法 2.2测试结果 2.2.1 测试用例一 图一 开始界面 3 简化RSA、ElGamal算法 图二 密钥生成器 图三 加密 图四 解密 2.2.2测试用例二 4 简化RSA、ElGamal算法 图一 密钥生成器 图二 加密 图三 解密 3、代码实现 5 简化RSA、ElGamal算法 #include #include using namespace std; int gcd(long a,long b) { if(a < b){ long temp = a; a = b; b = temp; } while(a%b){ long c = a%b; a = b; b = c; } return b; } /*RSA*/ void RSA_key_generate(long length,long p,long q,long &n,long &e,long &d){ n = q * p; long t = (p - 1)*(q - 1); for(e = 2; gcd(e,t) != 1 ;e++); long de = 1; for(int k = 0;de%e != 0;k++){ de = de + t; } d = de/e; } int RSA_Encryption(long n,long e,long m){ long c = 1; for(int i = 1;i <= e; i++) { c = c*m; if(c > n) c = c%n; } return c; } int RSA_Decrypt(long n,long d,long c){ long m = 1; for(int i = 1;i <= d; i++) { 6 简化RSA、ElGamal算法 m = m*c; if(m > n) m = m%n; } return m; } /**/ /*ElGamal*/ typedef struct r_t { long r; long t; }; void ElGamal_key_generate(long length,long p,long a,long x,long &y) { y = 1; for(int i = 1;i <= x;i++) { y = y*a; if(y > p) y = y%p; } } r_t ElGamal_Encryption(long p,long a,long y,long m) { struct r_t rt; rt.r = 1; rt.t = m; /*random number*/ srand((unsigned)time(NULL)); int k = 1520;//rand()%1024; /**/ for(int i = 1;i <= k; i++){ rt.r = rt.r*a; if(rt.r > p){ rt.r = rt.r%p; } rt.t = rt.t*y; if(rt.t > p){ rt.t = rt.t%p; } } return rt; 7 简化RSA、ElGamal算法 } int ElGamal_Decrypt(long p,long x,struct r_t rt) { long r_exp_x = 1,m; for(int i = 1;i <= x; i++) { r_exp_x = r_exp_x * rt.r; if(r_exp_x > p){ r_exp_x = r_exp_x%p; } } for(int k = 0;;k++) { if(k != 0){ rt.t = rt.t + p; } else{} if(rt.t%r_exp_x == 0){ m = rt.t/r_exp_x; break; } } return m; } /**/ int main(){ while(1){ int flag,flag1,flag2; cout<<"\n"; cout<<"1---------RSA\n"; cout<<"2---------ElGamal\n"; cout<<"3---------exit\n"; cin>>flag; if(flag == 1){ system("cls"); long length,p,q,n,e,d; long c,m; cout<<"---欢迎来到RSA加密测试---\n"; cout<<"请输入length,p,q:"; cin>>length>>p>>q; RSA_key_generate(length,p,q,n,e,d); system("cls"); cout<<"密钥发生器成功生成密钥....."<>flag1; if(flag1 == 1){ cout<<"你目前所能获得的密钥n,e:"<>m; cout<<"加密得到密文:"<>c; cout<<"解密得到明文:"<>length>>p>>a>>x; ElGamal_key_generate(length,p,a,x,y); system("cls"); cout<<"密钥发生器成功生成密钥....."<>flag2; if(flag2 == 1){ cout<<"你目前所能获得的密钥p,a,y:"<>m; struct r_t rt = ElGamal_Encryption(p,a,y,m); cout<<"加密得到密文:"<>rt.r>>rt.t; cout<<"解密得到明文:"<