草庐IT

关于ECC-Elgamal同态加密

木子-欣 2023-04-22 原文

关于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=(X1,Y1),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 = {kG,Pm+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),
可以将他的原理引用到椭圆曲线中。(如果有时间的话,我会在后续写一下,还请读者自行查找信息)。

提供一篇论文进行参考:
https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CJFD&dbname=CJFD2009&filename=XDJS200904057&uniplatform=NZKPT&v=pRDZYuOSvHSZmOOdRSfbOP6_cX5qXtTmoSDIMGFvKECAuhzEB6X9F_zKZOj2OCYA

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。有一句说的好–存在缺点的战士好过完美的苍蝇!还是要把自己所学的分享出来,你们以后就是密码学大佬!(如果有错误的地方还请大佬多多指正!我虚心求教!)

有关关于ECC-Elgamal同态加密的更多相关文章

  1. ruby - 使用 AES 的 Rails 加密,过于复杂 - 2

    我在加密来self正在使用的第三方供应商的值时遇到问题。他们的指令如下:1)Converttheencryptionpasswordtoabytearray.2)Convertthevaluetobeencryptedtoabytearray.3)Theentirelengthofthearrayisinsertedasthefirstfourbytesontothefrontofthefirstblockoftheresultantbytearraybeforeencryption.4)EncryptthevalueusingAESwith:1.256-bitkeysize,2.25

  2. ruby-on-rails - 关于 Ruby 的一般问题 - 2

    我在我的rails应用程序中安装了来自github.com的acts_as_versioned插件,但有一段代码我不完全理解,我希望有人能帮我解决这个问题class_eval我知道block内的方法(或任何它是什么)被定义为类内的实例方法,但我在插件的任何地方都找不到定义为常量的CLASS_METHODS,而且我也不确定是什么here,并且有问题的代码从lib/acts_as_versioned.rb的第199行开始。如果有人愿意告诉我这里的内幕,我将不胜感激。谢谢-C 最佳答案 这是一个异端。http://en.wikipedia

  3. ruby - 如何使用私钥加密完全加密 Ruby 中的数据? - 2

    首先,关于我们系统的一些信息,它基本上是建筑行业的电子招标解决方案。所以:列表项我们的系统有多家公司每个公司都有多个用户每家公司可以创建多个拍卖然后其他公司可以为可用的拍卖提交他们的出价。一个出价包含数百或数千个单独的项目,我们只需要加密这些记录的“价格”部分。我们面临的问题是,我们的大客户不希望我们知道投标价格,至少在投标过程中是这样,这是完全可以理解的。现在,我们只是通过对称加密对价格进行加密,因此即使价格在数据库中有效加密,他们担心的是我们拥有解密价格的key。因此,我们正在研究某种形式的公钥加密系统。以下是我们对解决方案的初步想法:当一家公司注册时,我们会使用OpenSSL为其

  4. ruby-on-rails - 我如何比较 'Bcrypt' Gem解密的密码和加密的密码 - 2

    我正在尝试对某些帖子的评论使用简单的身份验证。用户使用即时ID和密码输入评论我使用“bcrypt”gem将密码存储在数据库中。在comments_controller.rb中像这样@comment=Comment.new(comment_params)bcrypted_pwd=BCrypt::Password.create(@comment.user_pwd)@comment.user_pwd=bcrypted_pwd当用户想要删除他们的评论时,我使用data-confirm-modalgem来确认数据在这部分,我必须解密用户输入的密码以与数据库中的加密密码进行比较我怎样才能解密密码,

  5. ruby - 我怎样才能更好地了解/了解更多关于 Ruby 的知识? - 2

    按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visitthehelpcenter指导。关闭9年前。我最近开始学习Ruby,这是我的第一门编程语言。我对语法感到满意,并且我已经完成了许多只教授相同基础知识的教程。我已经写了一些小程序(包括我自己的数组排序方法,在有人告诉我谷歌“冒泡排序”之前我认为它非常聪明),但我觉得我需要尝试更大更难的东西来理解更多关于Ruby.关于如何执行此操作的任何想法?

  6. ruby - 关于 Ruby 中 Dir[] 和 File.join() 的混淆 - 2

    我在Ruby中遇到了一个关于Dir[]和File.join()的简单程序,blobs_dir='/path/to/dir'Dir[File.join(blobs_dir,"**","*")].eachdo|file|FileUtils.rm_rf(file)ifFile.symlink?(file)我有两个困惑:首先,File.join(@blobs_dir,"**","*")中的第二个和第三个参数是什么意思?其次,Dir[]在Ruby中有什么用?我只知道它等价于Dir.glob(),但是,我对Dir.glob()确实不是很清楚。 最佳答案

  7. elasticsearch源码关于TransportSearchAction【阶段三】 - 2

    1.回顾.TransportServicepublicclassTransportServiceextendsAbstractLifecycleComponentTransportService:方法:1publicfinalTextendsTransportResponse>voidsendRequest(finalTransport.Connectionconnection,finalStringaction,finalTransportRequestrequest,finalTransportRequestOptionsoptions,TransportResponseHandlerT>

  8. ruby - 如何在Elixir中使用AES CBC 128进行加密和解密 - 2

    我在Rails中有一个具有以下方法的应用程序,该方法可以加密和解密文本并与Java客户端通信。defencrypt(string,key)cipher=OpenSSL::Cipher::AES.new(128,:CBC)cipher.encryptcipher.padding=1cipher.key=hex_to_bin(Digest::SHA1.hexdigest(key)[0..32])cipher_text=cipher.update(string)cipher_textexcenddefhex_to_bin(str)[str].pack"H*"enddefbin_to_hex(

  9. 关于Qt程序打包后运行库依赖的常见问题分析及解决方法 - 2

    目录一.大致如下常见问题:(1)找不到程序所依赖的Qt库version`Qt_5'notfound(requiredby(2)CouldnotLoadtheQtplatformplugin"xcb"in""eventhoughitwasfound(3)打包到在不同的linux系统下,或者打包到高版本的相同系统下,运行程序时,直接提示段错误即segmentationfault,或者Illegalinstruction(coredumped)非法指令(4)ldd应用程序或者库,查看运行所依赖的库时,直接报段错误二.问题逐个分析,得出解决方法:(1)找不到程序所依赖的Qt库version`Qt_5'

  10. ruby - 关于 Ruby/ChefSpec 编码风格的反馈 - 2

    我是Ruby的新手,但过去两周我一直在对Chef测试进行大量研究。该测试使用ChefSpec和Fauxhai,但它看起来不是很“像ruby”,我希望社区能给我一些编码风格的建议。有没有更好的方法来编写这样的嵌套循环?Recipe/foo/recipes/default.rbpackage"foo"doaction:installendRecipe/foo/spec/default_spec.rbrequire'chefspec'describe'foo::default'doplatforms={"debian"=>['6.0.5'],"ubuntu"=>['12.04','10.04

随机推荐