关于ECC-Elgamal同态加密
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
关于ECC-Elgamal同态加密
1.什么是ECC(elliptic curve)
1.有限域
首先我们要知道椭圆曲线加密是在有限域进行加密的对于无限域上的加密我没有了解过在椭圆曲线
加密上有限域分为1.GF(p)素数域2.GF(2^m)伽罗华域。本次我们讨论素数域上的椭圆曲线加密。
2.模运算
由于我们要在有限域上进行加密而椭圆曲线是连续的并不适合加密所以必须把椭圆曲线变成离散的点
要把椭圆曲线定义在有限域上这时我们就要用到模运算把点映射到有限域上。
模运算运算符(mod n)将所有整数映射到集合｛0,1,...,(n-1)｝中。性质有如下
(1)[(a mod n) + (b mod n)] mod n = (a+b)mod n
(2)[(a mod n) - (b mod n)] mod n = (a-b)mod n
(3)[(a mod n) * (b mod n)] mod n = (a*b)mod n
这个运算在很多非对称加密中都要用到像RSA,paillier等都会涉及。关于他们的证明还请读者去寻找初等数论知识。
还有一个知识点也要补充一下--同余
同余设m是正整数a和b是整数。如果m|a-b(|是整除的意思)则称a模m同余于b或a与b模m同余记作a≡b(mod n).
在数论中 同余关系是等价关系我也不知道为什么反正他们规定的 但是要满足下列三个属性
(1)自反性a≡a(mod n)
(2)传递性a≡b(mod n),b≡c(mod n),a≡c(mod n)
(3)对称性a≡b(mod n) => b≡a(mod n)
后续我们会经常用到同余所以当对于一个椭圆曲线公式左右值求出来不相等的时候肯定是你忘记mod n了
左右两边都记得 y^2(mod n) = x^3+a*x+b(mod n) (mod n不是单单对bmod的是x值带入全部计算出来之后在取mod
我第一次就犯错误了!)
3.椭圆曲线上的加法运算
首先椭圆曲线并不是椭圆在上面进行加法是有特殊的法则的我们讨论GF(p)上的加法运算
设p=23,a=b=1,考虑曲线方程y^2 = x^3+a*x+b(a,b代入)
(1)P+O=P (其中P是椭圆曲线上的点O是无穷远点)
(2)若P=(X1,Y1),则P+(X1,-Y1)=O.点(X1-Y1)是点P的逆元记作-P.
(3)若P=(X1Y1),Q=(X2,Y2),且P≠-Q则R=P+Q=(Xr,Yr)有下列规则确定
Xr = (λ^2-X1-X2)mod p
Yr = (λ(Xr-X1)-Y1)mod p
其中
若P≠Q λ=[(Y2-Y1)/(X2-X1)]mod p
若P=Q λ=[(3*X1^2+a)/2*Y1]mod p
(4)乘法定义为重复相加4P=P+P+P+P.
2.非同态加密的椭圆曲线加密
1.公私钥生成
1.Alice首先构造一条椭圆曲线E,在曲线上选择一点G作为生成元并求G的阶为n,要求n必须为质数。
2.Alice选择一个私钥(d<n),生成公钥Q=d*G多次调用椭圆曲线上的加法运算
3.Alice将公钥组Ep(a,b),Q,G发送给Bob
https://zhuanlan.zhihu.com/p/40243602 很不错的一篇文章来讲解阶和基点
2.明文嵌入
1.Bob拿到Alice的公钥组后对消息m进行加密如果是字符串的话可以把明文信息存入char[]数组逐个转换成ASCII
在明文嵌入椭圆曲线这里为了方便我直接假设明文消息m是一个整数。
2.计算嵌入点Pm的x坐标
step 1. 设m满足(m+1)K<p (K为Bob选择的一个大整数)明文m将用数字x=mK+j表示其中0<=j<=K,计算(x^3+a*x+b)mod p
step 2.当p为大于3的素数奇素数时用勒让德符号来判断A=x^3+a*x+b是否**二次剩余**若A是模p的二次剩余则存在A的模p平方根x可以作为哦明文m的植入点坐标。
step3.若A是模p的二次非剩余则返回step1将j+1,用新的x值再试一次重复上面的步骤直到找到一个x使得A是模p的二次剩余或j=K,如果j始终等于K,则不能把信息映射到一点。
3.计算G(x,y)的y坐标
当A=x^3+a*x+b是模p二次剩余那我们就要求解y^2 ≡A(mod p),我采用的是Tonelli-shanks算法。(后续我会讲解这个算法的目前还请读者自行补充知识),此时我们就得到一个椭圆曲线上的坐标Pm(x,y).
3.加密
椭圆曲线的密文形式为C = {kGPm+kQ} (其中k为Bob选取的随机正整数Pm为明文嵌入的点Q为Alice的公钥)
令C1 = kG 椭圆曲线的标量乘法k次调用椭圆曲线加法
令C2 = Pm+kQ同上
发送密文给Alice
4.解密
Alice拿到密文C后,计算Pm = C2-C1*d;(我觉得这个加密要把x嵌入点时的K与j传送过来方便解码)
然后取Pm的x坐标计算:m=(x-j)/K,得到明文信息。
我们假设有一个敌手获取到了以上信息；但是由于Alice的密钥时不可知的那么Pm=C2-C1*d也是一个难题
对于上述的明文嵌入的ECC加密是不支持同态加密的假设存在Pm1与Pm2点,密文的相加时进行的时椭圆曲线域上的加法不满足代数域上的逻辑得不到m1+m2的结果
3.同态加密的椭圆曲线加密ECC-Elgamal
对比上述的非同态加密ECC加密算法两者的区别在于明文嵌入的方式。
1.同态加密明文嵌入
Pm = m*G(其中m为明文消息转换而成的大整数G为椭圆曲线的基点)由于G点是椭圆曲线的生成元所以进行标量乘法
之后的点依旧在椭圆曲线上
2.加密
此时我们加密的密文变成C= {kG,mG+kQ}(mG既是明文嵌入点)将密文传输给Alice
3.解密
Alcie拿到密文后计算mG=m*G+k*Q-k*G*d,然后求解mg的离散对数问题。目前我接触到的算法是BSGS(Baby Step Giant Step)
可以将他的原理引用到椭圆曲线中。如果有时间的话我会在后续写一下还请读者自行查找信息。
4.同态加密
当我们对上述运算过的密文进行解密时得到的消息就是m1+m2;
3.关于椭圆曲线的选择
T(p,a,b,G,n,h)这六个椭圆曲线的主要参数 其中n是G点的阶h是T上所有点个数m与n相除的整数部分
1.一般来说p越大越安全但是越大速度也就会下降一般选取200位左右
2.P≠n*h
3.p*t 不同余 1(mod n) 1<=t<=20
4.4a^3+27b^2 不同余 0 mod p
5.n为素数
6.h<=4
4.总结
其实上述的功能我用C++粗略实现了。但是代码写的太差了还有很多未知的bug。有一句说的好–存在缺点的战士好过完美的苍蝇还是要把自己所学的分享出来你们以后就是密码学大佬(如果有错误的地方还请大佬多多指正我虚心求教)