Elgamal加密算法原理及实现 |
您所在的位置：网站首页 › rsa安全性基于什么 › Elgamal加密算法原理及实现 |
Elgamal加密算法原理及实现
|
目录
一、概述 二、知识准备 1、阶 2、本原元 三、算法流程 1、密钥生成 2、加密 3、解密 四、代码实现 一、概述Rsa是基于大质数分解难题；而Elgamal是基于G上的离散对数难题 ElGamal算法是由Tather ElGamal在1985年提出的，它是一种基于离散对数难题的加密体系，与RAS算法一样，既能用于数据加密，也能用于数字签名。ElGamal算法是基于因数分解，而ElGamal算法是基于离散对数问题。与RSA算法相比，ElGamal算法哪怕是使用相同的私钥，对相同的明文进行加密，每次加密后得到的签名也各不相同，有效的防止了网络中可能出现的重放攻击。 二、知识准备 1、阶假设n>1,a和n互质，则必有一个x (1≤x ≤n-1)使得： 满足 观察方程 当a模n的阶为φ(n)，也就是说当且仅当x是φ(n)的倍数，使得 举个例子：
定义：如果一个元素a的x次方模素数p的阶等于p-1,则称a是模p的本原元或本原根。 上述式子中 a = 5 ， p = 7 ,且满足 这些余数构成了一个模7的完全剩余系1,2,3,4,5,6，也就是对于任意a，都可以找到x使得: 三、算法流程
同样是通过一个案例来介绍，还是Alice欲使用ElGamal加密算法向 Bob 发送信息。。 1、密钥生成对于Bob,首先要随机选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。我们为了方便计算取p = 37,则Z37的一个本原元α = 2. 随机选择一个整数d作为密钥，2≤d≤p-2 。我们选择d = 5, 计算β=αd mod p，β=25 mod 37 = 32 私钥：d 公钥：p ,a ,β 2、加密假设Alice 想发送消息 x = 29 首先选取随机数k , 假设k = 7 则： y1 = αk mod p = 27 mod 37 = 17 y2 = x βk mod p = 29×327 mod 37 = 33 将密文y = (17,33)发送给Bob 3、解密Bob收到密文y = (17,33) 后恢复明文如下： x = y2 (y1^d) -1 mod p = 33 (17^5) -1 mod 37 = 33×2 mod 37 = 29 四、代码实现go语言的简易实现 func main(){ data :=[]byte("王辉逛北京") fmt.Println("原文=",string(data)) C := make([]int , 0) //选取一个小的素数,这里为了执行的快一些 ， 所以选定的比较小 g:=selectP(2,48) //选取一个大的素数,这里为了执行的快一些 ， 所以选定的比较小 p:=selectP(48 , 600) //随机定义一个私钥 priKey := rand.Intn(p) fmt.Println("priKey=",priKey) //生成公钥 pubKey := pow(g , priKey , p) fmt.Println("pubKey=",pubKey) //公钥加密的随机数 k := rand.Intn(priKey) y1 := pow(g , k ,p) C = append(C , y1) entryData :=make([]byte , 0) //加密 for _,v := range data{ newV :=int(v) * pow(pubKey , k ,p)% p C = append(C , newV) entryData = append(entryData, byte(newV)) } fmt.Printf("密文[%s]\n",string(entryData)) //y1的d次方 y1d := pow(y1,priKey,p) //yi1 d次方的逆元 y1d_1,_ := exGcd(y1d ,p) decryptData :=make([]byte , 0) //解密 for i:=1 ; i< len(C) ; i++{ newV :=(C[i] * y1d_1)%p decryptData = append(decryptData , byte(newV)) } fmt.Println("解密后的原文=",string(decryptData)) } func exGcd(a,b int) (c ,d int){ if b == 0{ return 1,0 }else{ c ,d = exGcd(b , a%b) return d , c - (a/b)*d } } func pow(a,b,m int)int{ res :=1 a %=m for ;b != 0;{ if (b & 1) == 1{ res = (res * a) % m } a = (a * a) % m b >>= 1 } return res } func selectP(min ,max int) int{ suArr :=make([]int , 0) for i := min; i |
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |