精华内容
下载资源
问答
  • 椭圆曲线加密

    2017-08-21 22:33:41
    椭圆曲线加密算法。安全相关
  • 自制椭圆曲线加密算法ppt 老师要求上课讲解用自制椭圆曲线加密算法ppt 老师要求上课讲解用自制椭圆曲线加密算法ppt 老师要求上课讲解用自制椭圆曲线加密算法ppt 老师要求上课讲解用自制椭圆曲线加密算法ppt 老师要求...
  • 在FPGA实现椭圆曲线加密系统时,基于GF(2)的多项式有限域中的乘法、求逆运算是其中的两大难点。本文提供了一种椭圆曲线加密的FPGA实现的结构,着重讨论了基于GF(2)的多项式有限域中的乘法、求逆运算的实现,并与软件...
  • 离散对数和椭圆曲线加密原理

    万次阅读 多人点赞 2017-08-03 11:35:05
    现代公钥加密系统中,常用的加密算法除了RSA还有离散对数加密和椭圆曲线加密。这两者原理比较相似,在这里一并介绍。 离散对数问题 我们在中学里学的对数问题是指, 给定正实数aaa和axaxa^x,求xxx。也就是...

    为什么是椭圆曲线加密?

    椭圆曲线加密(以下简称ECC)实际上已经应用到了各个网站的HTTPS连接中。你平常访问的网站,大部分都是基于椭圆曲线加密,比如你现在正在浏览的CSDN。如果你用的是chrome浏览器,按下F12,点开Security,可以看到下图这样的内容:
    在这里插入图片描述
    这里的ECDHE就是椭圆曲线密钥交换的简称。能进行密钥交换的算法并非只有ECC,但是现在的大型网站(除了某些老旧的银行网站)都不约而同地选择了ECC。还有大火的比特币,先不论比特币的争议,设计相当精妙,其身份认证机制便是以ECC为基础。为何比特币选择的也是ECC?

    如果你是一个服务端程序员或者运维人员,那么肯定没少用SSH连接服务器。SSH连接里面经常会用公钥进行登录。这时会要求先在本机使用ssh-keygen生成密钥对,然后把密钥对里的公钥上传到服务器。但是用多了有没有发现ssh-keygen默认生成的密钥有点长?比如这个公钥:

    ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCypa+az50x7bi0vweyY2dVQIztS9Q/v4DL3OQMPCPDR85bFsvsXWB5r/fbETDlo25ZDyWBInOVxqR96H0vKeWE28tbbQSqne41WAobPe1Z4gxq5o2WJXsC44qjW9ne34dJFVYNX9DrcnvddyZdTxw4Apa6A/hixMtaPDueQF6lct8EsVhkRqFSbdYfumABxUlGW4kKbwA86zT+jDCbnOHyk7EOvtUuLqlTntZmko7gm46QSuYNuhlFeGQirzmVmU8C55wABvVjeVw/wXZe96Q5faPEqAvY+X3o0ku1eliQuI/7BGq9j9s8q2WqSTBweOhJ5mHhf+kyra0jm70WYRlb

    但是你只需要把ssh-keygen的密钥类型从默认的RSA切换到ECC,也就是运行ssh-keygen -t ed25519,就可以得到一个短得多的公钥:

    ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIHzJZ8pHw7wVIFWp9zmLIeYyhk81QAp42FuCQkdbG1bb

    一般来说,密钥越长安全性越高,但是这个短密钥的安全性比上面长的还要高。破解它的难度相当于破解长度为3000位(二进制位)的RSA密钥。而ssh-keygen默认生成的是长度为2048位的RSA密钥。为什么ECC的密钥可以这么短但是安全性却更高?

    序言


    不管是RSA、离散对数加密还是椭圆曲线加密,公钥加密算法都是依赖于某个正向计算很简单(比如多项式时间复杂度),而逆向计算很难(比如指数时间复杂度)的数学难题。对于RSA,这个问题是大整数因子分解问题;对于离散对数加密,是离散对数问题;对于椭圆曲线加密,则是椭圆曲线上的离散对数问题。

    本文主要介绍椭圆曲线加密,但是离散对数加密和椭圆曲线加密原理比较相似,在这里一起介绍。

    离散对数问题


    我们在中学里学的对数问题是指,

    给定正实数aaaaxa^xax,求xxx。也就是计算x=log⁡aaxx=\log_a{a^x}x=logaax

    这是实数域上的对数问题,不是什么难算的东西,随便按一下计算器结果就出来了。

    而离散对数问题是指这样的问题:

    给定素数ppp和正整数ggg,知道gxmod  pg^x\mod pgxmodp的值,求xxx

    对于符合特定条件的pppggg,这个问题是很难算的,更准确地说,是没有多项式时间的解法。而gxmod  pg^x \mod pgxmodp的计算却非常快,由此造成了正向和逆向天差地别的计算速度。打个比方,就像随手一扔,玻璃杯就摔碎成渣,而想要将一堆玻璃渣拼回完整的玻璃杯,即使做得到,所需的人力物力也远远大于当初那随手一扔。

    Diffie–Hellman密钥交换


    Diffie–Hellman密钥交换(以下简称DH)是用于双方在可能被窃听环境下安全交换密钥的一种方法。
    算法的安全性是由上面提到的离散对数难题保证。

    具体算法流程如下:

    • 小红和小明约定pppggg的值
    • 小红生成私钥xxx,计算gxmod  pg^x\mod pgxmodp作为公钥公布出去
    • 小明生成私钥yyy,计算gymod  pg^y\mod pgymodp作为公钥公布出去
    • 小红得知gymod  pg^y\mod pgymodp后,计算
      s=(gymod  p)xmod  p=(gy)xmod  p=gxymod  ps=(g^y\mod p)^x\mod p=(g^y)^x\mod p=g^{xy}\mod ps=(gymodp)xmodp=(gy)xmodp=gxymodp
    • 小明得到gxmod  pg^x\mod pgxmodp后,计算
      s=(gxmod  p)ymod  p=(gx)ymod  p=gxymod  ps=(g^x\mod p)^y\mod p=(g^x)^y\mod p=g^{xy}\mod ps=(gxmodp)ymodp=(gx)ymodp=gxymodp
    • 双方都得到了相同的密钥的sss,交换完毕

    上面的流程中,xxxyyy始终由两人自行保管的,第三方窃听得到的只有pppggggxmod  pg^x\mod pgxmodpgymod  pg^y\mod pgymodp这几个值。
    上面说过,离散对数是很难算的,所以第三方不能由这些信息计算出xxxyyy,也就没办法计算出密钥sss了。

    椭圆曲线


    中学的时候我们学过圆锥曲线,比如椭圆、双曲线和抛物线。因为描述这些曲线的方程都是二次方程,圆锥曲线又被称为二次曲线。而椭圆曲线是则是由三次方程描述的一些曲线。更准确地说,椭圆曲线是由下面的方程描述的曲线:
    y2=x3+ax+b4a3+27b2≠0y^2=x^3+ax+b\\ 4a^3+27b^2 \neq 0y2=x3+ax+b4a3+27b2=0

    需要注意的是,椭圆曲线之所以叫“椭圆曲线”,是因为其曲线方程跟利用微积分计算椭圆周长的公式相似。实际上它的图像跟椭圆完全不搭边。

    下图是椭圆曲线y2=x3−x+1y^2=x^3-x+1y2=x3x+1的图像
    椭圆曲线

    椭圆曲线有这样的两个性质:

    1. 关于X轴对称
    2. 画一条直线跟椭圆曲线相交,它们最多有三个交点

    椭圆曲线上的运算


    椭圆曲线加密之所以难破解,是因为其加密、解密运算是在椭圆曲线上进行的,所以接下来需要定义一些椭圆曲线上的运算。可以回想一下小学的时候第一次学整数加减法的情景,两者其实是类似的。

    首先定义椭圆曲线上点的加法。设椭圆曲线上有两点,A和B点,那么作过这两点的直线与该曲线相交于第三点(C点),然后关于X轴对称得到D点,则D为这两个点的和,记作D=A+BD=A+BD=A+B。很明显,D点也在该曲线上。所以椭圆曲线上两点之和也是曲线上的点。、

    这个性质我们称之为封闭性,也就是只要A和B是曲线上的点,他们的和也必然是曲线上的点。类比于整数加法,只要相加的两个数是整数,那么他们的和也必然是整数。

    特别地,如果两点重合,则作椭圆曲线在A点处的切线,与曲线相交于第二点(B点),然后关于X轴对称得到C点,则C点为A点与自身的和,记作C=A+AC=A+AC=A+A
    A+A
    看到这里很多人可能会觉得疑惑,为什么要定义一个这么奇怪的加法?
    实际上这个加法来源于椭圆曲线上利用已知有理点(横、纵坐标都是有理数的点)寻找其它有理点的方法,叫切线法(tangent and chord method)。这种加法可以保证以下两个结论是成立的:

    1. A+B=B+AA+B=B+AA+B=B+A
      交换律。这是显而易见的,直线没有方向,过A点作直线经过B点,和过B点作直线经过A点,得到的是同一条直线。
    2. (A+B)+C=A+(B+C)(A+B)+C=A+(B+C)(A+B)+C=A+(B+C)
      结合律。读者可以到GeoGebra自己试着画一下。这个结论的证明并不直观,详细的过程可以参考这里

    这个时候聪明如你可能会发现,如果相加的两个点,A点和B点形成的直线恰好垂直于X轴,那么这条直线与椭圆曲线不管怎么算最多只有两个交点,上面的加法岂不是没法做了?为了补足这个缺陷,这里我们定义坐标系中距离X轴无穷远点为椭圆曲线上的一个特殊点,称为0点(零点)。 因为任意一条垂直于X轴的直线都会与椭圆曲线相交于0点。这里可能有点难以理解,实际上可以类比平面上平行线的定义。我们知道,两条直线必定有交点这一结论是错的,因为平行线是个例外。但是如果我们定义,两条平行的直线相交于无穷远点,那么这个结论就是成立的。

    对于这个0点,有以下结论:

    1. 对于椭圆曲线上任意一点A,都存在曲线上另一点B,使得A+B=0A+B=0A+B=0
      因为椭圆曲线关于X轴对称,所以对于曲线上任意一点A,总存在另一点B使得过A、B的直线垂直于X轴,也就是该直线与曲线交于0点,所以A+B=0
    2. A+0=0+A=AA+0=0+A=AA+0=0+A=A
      因为0点是距离X轴无穷远的点,所以过A点与0点的直线是垂直于X轴的,它与曲线相交于另一点B点,那么B点关于X轴对称的点就是A点,即A点为A点和0点之和。
      A+0
      实际上这里“顺便”定义了椭圆曲线中的负数,若A+B=0A+B=0A+B=0,那么B=−AB=-AB=A。椭圆曲线上点的减法也就自然而然地出现了,A−B=A+(−B)A-B=A+(-B)AB=A+(B)

    就这样,我们得到了一个新的加法运算“体系”,类似整数加法,它有零,满足交换律、结合律,还有对应的减法。只是里面的基本元素从整数变成椭圆曲线上的点,加法的运算也变得略微有点奇怪。

    我们对这个“体系”进一步拓展,在加法的基础上,定义椭圆曲线上点的乘法

    PPP是椭圆曲线上的一个点,那么正整数kkk乘以点PPP的结果由下面的式子定义,注意式子中的加法是上面提到的椭圆曲线上点的加法:
    1∗P=P1*P=P1P=P
    2∗P=P+P2*P=P+P2P=P+P
    3∗P=2∗P+P3*P=2*P+P3P=2P+P

    k∗P=(k−1)∗P+Pk*P=(k-1)*P+PkP=(k1)P+P

    这个乘法满足以下性质:

    对于任意正整数kkkjjj,有
    k∗(j∗P)=(kj)∗P=(jk)∗P=j∗(k∗P)k*(j*P)=(kj)*P=(jk)*P=j*(k*P)k(jP)=(kj)P=(jk)P=j(kP)

    这个性质在下文中的椭圆曲线密钥交换中会用到。

    椭圆曲线上的离散对数问题


    从程序实现的角度来考虑,假设有这么一个函数:

     Point add(Point A, Point B) {...}
    

    函数参数是两个椭圆曲线上的点,返回值是过两个点的直线与椭圆曲线相交的第三个点关于X轴对称的点。
    那么按照如下方式调用函数我们就实现了椭圆曲线上点的乘法:

    Point result = P;
    for (int i = 0; i < k - 1; i++)
    	result = add(P, result);
    sendTo((result, P), others);
    

    但是很显然,通过累加k−1k-1k1次的方式计算k∗Pk*PkP是一种很笨的办法,其时间复杂度是线性的。上面我们提到过,椭圆曲线上点的加法是满足结合律的,即(A+B)+C=A+(B+C)(A+B)+C=A+(B+C)(A+B)+C=A+(B+C),扩展一下,就有

    P+P+P+P=(P+P)+(P+P)=2P+2PP+P+P+P=(P+P)+(P+P)=2P+2PP+P+P+P=(P+P)+(P+P)=2P+2P

    于是就有这么一种骚操作,比如计算16P16P16P,我们可以先计算2P=P+P2P=P+P2P=P+P;然后计算4P=P+P+P+P=2P+2P4P=P+P+P+P=2P+2P4P=P+P+P+P=2P+2P;再计算8P=P+P...+P=4P+4P8P=P+P...+P=4P+4P8P=P+P...+P=4P+4P;最后计算16P=8P+8P16P=8P+8P16P=8P+8P。这里我们把15次加法减少到了4次。

    当然,k的值不可能总是2的幂。实际上上面的操作可以推广到k为任意正整数的情况。比如计算23P,首先计算2P=P+P,然后

    4P=2P+2P4P=2P+2P4P=2P+2P

    8P=4P+4P8P=4P+4P8P=4P+4P

    16P=8P+8P16P=8P+8P16P=8P+8P

    因为23=16+4+2+123=16+4+2+123=16+4+2+1,所以23P=16P+4P+2P+P23P=16P+4P+2P+P23P=16P+4P+2P+P。总共只需要7次加法。

    分析一下,对于任意正整数kkk,我们都可以利用这个方法将计算k∗Pk*PkP所需的加法计算次数降低到2⋅⌊log⁡2k⌋−12\cdot \lfloor \log_2k\rfloor-12log2k1

    也就是说,从时间复杂度的角度来看,这个算法是一个O(log⁡k)O(\log k)O(logk)的算法。

    这个方法被称为快速幂算法,原本常用于快速计算某个数的k次幂,这里将其推广到椭圆曲线点乘的快速计算中。

    为什么要在介绍了椭圆曲线上点的乘法后突然冒出一个快速幂算法?快速幂算法对于椭圆曲线加密有什么意义?因为密码学家发现,利用快速幂算法计算k∗Pk*PkP的时间复杂度是对数级的,但是要在知道k∗Pk*PkPPPP的前提下,倒推出kkk的值,没有比挨个尝试kkk的值快太多的算法。于是椭圆曲线加密依赖的数学难题就这么诞生了。

    kkk为正整数,PPP是椭圆曲线上的点(称为基点),已知k∗Pk*PkPPPP,计算kkk

    如果我们改一种记法,把椭圆曲线上点的加法记作乘法,原来的乘法就变成了幂运算,那么上述难题的形式跟离散对数问题应该是一致的。即:

    kkk为正整数,PPP是椭圆曲线上的点,已知PkP^kPkPPP,计算k=log⁡PPkk=\log_PP^kk=logPPk

    所以这个难题叫椭圆曲线上的离散对数问题。

    尽管两个的形式一致,但是他们并不等价。实际上这个问题比大整数质因子分解(RSA)和离散对数(DH)难题都要难不少,目前还没有出现亚指数级时间复杂度的算法(大整数质因子分解和离散对数问题都有),这就是文章开头提到的同样甚至更高的安全强度下,椭圆曲线加密的密钥比RSA和DH的短不少的原因。

    有限域上的椭圆曲线


    但是密码学中,并不能直接用上面说的实数域上的椭圆曲线。因为

    1. 实数域上的椭圆曲线是连续的,有无限个点,密码学要求有限点。
    2. 实数域上的椭圆曲线的运算有误差,不精确。密码学要求精确。

    所以我们需要引入有限域上的椭圆曲线。

    所谓有限域上的椭圆曲线,简单来说就是满足下面式子要求的曲线(x, y, a, b都是小于素数p的非负整数):
    y2=x3+ax+bmod  p其中4a3+27b2≠0mod  py^2 =x^3+ax+b \mod p\\ 其中4a^3+27b^2\neq 0\mod py2=x3+ax+bmodp4a3+27b2=0modp

    对比一下原先的椭圆曲线的方程:
    y2=x3+ax+b其中4a3+27b2≠0y^2=x^3+ax+b\\ 其中4a^3+27b^2\neq 0y2=x3+ax+b4a3+27b2=0
    可以看到这个只是对原式进行了简单的取模处理而已。实际上RSA和DH中也是基于这种形式的取模运算。

    下图是椭圆曲线y2=x3−x+1y^2 = x^3 - x + 1y2=x3x+1对素数97取模后的图像(图片来自参考文献)

    原本连续光滑的曲线变成了离散的点,基本已经面目全非了,但是依然可以看到它是关于某条水平直线(y=97/2)对称的。

    而且上面定义的椭圆曲线的加法仍然可用(当然乘法也可以)(图片来自参考文献)。

    注意:密码学中有限域上的椭圆曲线一般有两种,一种是定义在以素数p为模的整数域GF(p)GF(p)GF(p),也就是上面介绍的;另一种则是定义在特征为2的伽罗瓦域GF(2m)GF(2^m)GF(2m)上,篇幅所限,这里就不介绍了。

    基于椭圆曲线的DH密钥交换(ECDH)


    ECDH跟DH的流程基本是一致的。

    • 小红和小明约定使用某条椭圆曲线(包括曲线参数,有限域参数以及基点P等)
    • 小红生成私钥xxx,计算x∗Px*PxP作为公钥公布出去
    • 小明生成私钥yyy,计算y∗Py*PyP作为公钥公布出去
    • 小红得知y∗Py*PyP后,计算
      s=x∗(y∗P)=xy∗Ps=x*(y*P)=xy*Ps=x(yP)=xyP
    • 小明得到x∗Px*PxP后,计算
      s=y∗(x∗P)=yx∗Ps=y*(x*P)=yx*Ps=y(xP)=yxP
    • 双方都得到了相同的密钥的sss,交换完毕

    由于计算椭圆曲线上的离散对数是很难的,所以第三方没办法在只知道x∗Px*PxPy∗Py*PyP的情况下计算出xxxyyy的值。

    实际业务应用中,我们不用管椭圆曲线这一堆参数该怎么选(要选对参数对于普通用户来说并不现实),已经有一大批现成的曲线,集成在OpenSSL之类的基础库里,从里面选一个就行了。比如prime256v1是比较常用的曲线,很多常见网站的ECC加密算法都是用的它;而Curve25519是比较新的曲线,安全性和效率都很高,而且密钥更短,现在颇受青睐。比特币用的是secp256k1,它效率比较高,更重要的是它的参数是通过可预测(predictable)的方式选出来的,大大降低了包含后门的可能性。相比之下有的曲线虽然至今还没被发现有安全性问题,但是他们的参数选择却一直无法给出有效的解释,所以经常被怀疑藏有后门。

    参考文献

    浅说椭圆曲线
    A (relatively easy to understand) primer on elliptic curve cryptography
    Wikipedia: Elliptic curve
    Wikipedia: Elliptic curve cryptography
    Bitcoin加密技术之椭圆曲线密码学
    椭圆曲线密码体制

    展开全文
  • libecc project:椭圆曲线加密
  • 椭圆曲线加密算法代码.doc
  • ECC椭圆曲线加密

    2013-01-16 16:31:57
    详细介绍了椭圆曲线的数学原理和椭圆曲线加密和密钥交换算法的实现原理和设计思路。
  • 椭圆曲线加密算法的 C 语言设计和实现 椭圆曲线加密算法于 1985 年提出由于自身优点它一出现便受到关注现在密码学界普 遍认为它将替代 RSA 加密算法 成为通用的公钥加密算法那么我们今天就来看看椭圆曲线 加密算法是...
  • 椭圆曲线加密ECC

    千次阅读 2017-06-23 14:28:59
    title: 椭圆曲线加密ECC type: categories date: 2017-06-23 13:39:43 categories: iOStags: [ECC, ECDSA, ECDH] 椭圆曲线加密是一种类似于RSA的非对称加密算法,具体介绍可以参考这篇文章...

    title: 椭圆曲线加密ECC
    type: categories
    date: 2017-06-23 13:39:43
    categories: iOS

    tags: [ECC, ECDSA, ECDH]

    椭圆曲线加密是一种类似于RSA的非对称加密算法,具体介绍可以参考这篇文章http://www.itye.org/archives/3254, 写得很明白。

    本文内容翻译自

    openssl生成指令

    https://github.com/konstantinpavlikhin/Watchdog

    生成DSA密钥对

    1、生成DSA私钥

    $ openssl dsaparam -genkey 2048 -noout -out DSAPrivateKey.pem

    2、导出公钥

    openssl dsa -in DSAPrivateKey.pem -pubout -outform PEM -out DSAPublicKey.pem

    生成ECDSA密钥对

    1、查看支持的曲线类型,常用的如:secp521r1,secp128r1, secp192r1, secp256r1, secp384r1等

    $ openssl ecparam -list_curves

    2、生成ECDSA私钥

    $ openssl ecparam -genkey -name secp521r1 -noout -out ECDSAPrivateKey.pem

    3、从私钥中导出公钥

    $ openssl ec -in ECDSAPrivateKey.pem -pubout -outform PEM -out ECDSAPublicKey.pem

    Objective-C中的ECC库

    https://github.com/ricmoo/GMEllipticCurveCrypto

    ECDSA允许通过私钥进行签名,然后通过公钥进行验签;

    ECDH是通过用户自己拥有的私钥和另一个用户的公钥来创建一个密钥,通过这个密钥在进行加密操作。

    API

    创建一个ECC密钥对
    GMEllipticCurveCrypto *crypto = [GMEllipticCurveCrypto generateKeyPairForCurve:
                                                             GMEllipticCurveSecp192r1];
    NSLog(@"Public Key: %@", crypto.publicKeyBase64);
    NSLog(@"Private Key: %@", crypto.privateKeyBase64);
    使用

    key可以是base64加密过的字符串,也可以是data类型

    crypto.publicKeyBase64 = @"AtF8hCxh9h1zlExuOZutuw+tRzmk3zVdfA==";
    NSLog(@"Public Key: base64=%@, rawBinary=%@", crypto.publicKeyBase64, crypto.publicKey);
    
    char bytes[] = { 2, 209, 124, 132, 44, 97, 246, 29, 115, 148, 76, 110, 57, 155, 173, 
                     187, 15, 173, 71, 57, 164, 223, 53, 93, 124 };
    crypto.publicKey = [NSData dataWithBytes:bytes length:25];
    NSLog(@"Public Key: base64=%@, rawBinary=%@", crypto.publicKeyBase64, crypto.publicKey);
    签名

    需要注意的是:签名的内容长度要和所选取的曲线类型一致。

    用ECDSA签名的话,产生的签名是所选曲线的两倍。如:secp192k1类型的曲线,产生的签名的长度为384bit(48字节)。

    还需要注意的是:因为有随机k的存在,所以每次产生的签名是不一样的。

    // The first 24 bytes of the SHA-256 hash for "Hack the Planet!"
    char bytes[] = { 56, 164, 34, 250, 121, 21, 2, 18, 65, 4, 161, 90, 126, 145, 111, 204, 
                     151, 65, 181, 4, 231, 177, 117, 154 };
    NSData *messageHash = [NSData dataWithBytes:bytes length:24];
    
    GMEllipticCurveCrypto *crypto = [GMEllipticCurveCrypto cryptoForCurve:
                                                    GMEllipticCurveSecp192r1];
    crypto.privateKeyBase64 = @"ENxb+5pCLAGT88vGmE6XLQRH1e8i/0rz";
    NSData *signature = [crypto signatureForHash:messageHash];
    NSLog(@"Signature: %@", signature);
    验签
    rypto = [GMEllipticCurveCrypto cryptoForCurve:GMEllipticCurveSecp192r1];
    crypto.publicKeyBase64 = @"AtF8hCxh9h1zlExuOZutuw+tRzmk3zVdfA==";;
    BOOL valid = [crypto verifySignature:signature forHash:messageHash];
    NSLog(@"Valid Signature: %@", (valid ? @"YES": @"NO"));
    密钥的交换

    使用ECDH方式生成与选取的曲线类型相同长度的交换密钥,如,192bit的曲线产生的是192bit的密钥。

    NSString *alicePublicKey = @"A9N+XWIjLCYAwa8Hb7T6Rohttqo91CF8HQ==";
    NSString *alicePrivateKey = @"frs4puAKipcbevvwJb7l77xACgB/FyBv";
    
    NSString *bobPublicKey = @"A35aoteno4wnAdJgV8AXKKl1AfPVRrSZQA==";
    NSString *bobPrivateKey = @"LP83qv81MsXVyPOFV7V5jKVOoU4DKPUS";
    
    
    // Alice performs...
    GMEllipticCurveCrypto *alice = [GMEllipticCurveCrypto cryptoForCurve:
                                                   GMEllipticCurveSecp192r1];
    alice.privateKeyBase64 = alicePrivateKey;
    NSData *aliceSharedSecret = [alice sharedSecretForPublicKeyBase64:bobPublicKey];
    NSLog(@"Shared Secret Alice: %@", aliceSharedSecret);
    
    // Bob performs...
    GMEllipticCurveCrypto *bob = [GMEllipticCurveCrypto cryptoForCurve:
                                                 GMEllipticCurveSecp192r1];
    bob.privateKeyBase64 = bobPrivateKey;
    NSData *bobSharedSecret = [bob sharedSecretForPublicKeyBase64:alicePublicKey];
    NSLog(@"Shared Secret Bob: %@", bobSharedSecret);
    
    // And now both parties have the same secret!
    NSLog(@"Shared secrets equal? %d", [aliceSharedSecret isEqualToData:bobSharedSecret]);

    部分原文

    Elliptic Curve Crypto

    An Objective-C library for Elliptic Curve Digital Signing Algorithm (ECDSA) and for Elliptic Curve Diffie-Hellman (ECDH).

    ECDSA allows signatures to be generated using a private key and validated using a public key.

    ECDH allows two identities to use their own private keys and each other’s public key to generate a shared secret, which can then be used for encryption.

    This library is largely based on the easy-ecc library (https://github.com/kmackay/easy-ecc).

    Features

    • Supports: secp128r1, secp192r1, secp256r1, secp384r1
    • Automatically detects curve based on private or public key
    • Supports keys as raw bytes or as base64 encoded strings
    • BSD 2-clause license

    API

    Generate a new ECC key pair

    GMEllipticCurveCrypto *crypto = [GMEllipticCurveCrypto generateKeyPairForCurve:
                                                             GMEllipticCurveSecp192r1];
    NSLog(@"Public Key: %@", crypto.publicKeyBase64);
    NSLog(@"Private Key: %@", crypto.privateKeyBase64);

    Using keys

    Keys can be accessed and set interchangably in either raw bytes or as base64 encoded strings.

    crypto.publicKeyBase64 = @"AtF8hCxh9h1zlExuOZutuw+tRzmk3zVdfA==";
    NSLog(@"Public Key: base64=%@, rawBinary=%@", crypto.publicKeyBase64, crypto.publicKey);
    
    char bytes[] = { 2, 209, 124, 132, 44, 97, 246, 29, 115, 148, 76, 110, 57, 155, 173, 
                     187, 15, 173, 71, 57, 164, 223, 53, 93, 124 };
    crypto.publicKey = [NSData dataWithBytes:bytes length:25];
    NSLog(@"Public Key: base64=%@, rawBinary=%@", crypto.publicKeyBase64, crypto.publicKey);

    Generate a signature for a message

    The signing operations require a message the same length as the curve; so generally, a hash algorithm is used to fix the original message’s length.

    Signatures using ECDSA will be twice the curve size. So, the 192 bit curve will produce a signature that is 48 bytes (384 bits) long.

    Also note that the signature is intentionally different each time because ECDSA uses a random k value.

    // The first 24 bytes of the SHA-256 hash for "Hack the Planet!"
    char bytes[] = { 56, 164, 34, 250, 121, 21, 2, 18, 65, 4, 161, 90, 126, 145, 111, 204, 
                     151, 65, 181, 4, 231, 177, 117, 154 };
    NSData *messageHash = [NSData dataWithBytes:bytes length:24];
    
    GMEllipticCurveCrypto *crypto = [GMEllipticCurveCrypto cryptoForCurve:
                                                    GMEllipticCurveSecp192r1];
    crypto.privateKeyBase64 = @"ENxb+5pCLAGT88vGmE6XLQRH1e8i/0rz";
    NSData *signature = [crypto signatureForHash:messageHash];
    NSLog(@"Signature: %@", signature);

    Verify a signature

    // messageHash and signature from above
    
    crypto = [GMEllipticCurveCrypto cryptoForCurve:GMEllipticCurveSecp192r1];
    crypto.publicKeyBase64 = @"AtF8hCxh9h1zlExuOZutuw+tRzmk3zVdfA==";;
    BOOL valid = [crypto verifySignature:signature forHash:messageHash];
    NSLog(@"Valid Signature: %@", (valid ? @"YES": @"NO"));

    Shared secret

    Shared secrets using ECDH are the same length as the curve. So, the 192 bit curve will produce a shared secret that is 24 bytes (192 bits) long.

    NSString *alicePublicKey = @"A9N+XWIjLCYAwa8Hb7T6Rohttqo91CF8HQ==";
    NSString *alicePrivateKey = @"frs4puAKipcbevvwJb7l77xACgB/FyBv";
    
    NSString *bobPublicKey = @"A35aoteno4wnAdJgV8AXKKl1AfPVRrSZQA==";
    NSString *bobPrivateKey = @"LP83qv81MsXVyPOFV7V5jKVOoU4DKPUS";
    
    
    // Alice performs...
    GMEllipticCurveCrypto *alice = [GMEllipticCurveCrypto cryptoForCurve:
                                                   GMEllipticCurveSecp192r1];
    alice.privateKeyBase64 = alicePrivateKey;
    NSData *aliceSharedSecret = [alice sharedSecretForPublicKeyBase64:bobPublicKey];
    NSLog(@"Shared Secret Alice: %@", aliceSharedSecret);
    
    // Bob performs...
    GMEllipticCurveCrypto *bob = [GMEllipticCurveCrypto cryptoForCurve:
                                                 GMEllipticCurveSecp192r1];
    bob.privateKeyBase64 = bobPrivateKey;
    NSData *bobSharedSecret = [bob sharedSecretForPublicKeyBase64:alicePublicKey];
    NSLog(@"Shared Secret Bob: %@", bobSharedSecret);
    
    // And now both parties have the same secret!
    NSLog(@"Shared secrets equal? %d", [aliceSharedSecret isEqualToData:bobSharedSecret]);

    Convenience functions

    Automatically detects curve and sets up the private or public key

    + (GMEllipticCurveCrypto*)cryptoForKey: (NSData*)privateOrPublicKey;
    + (GMEllipticCurveCrypto*)cryptoForKeyBase64: (NSString*)privateOrPublicKey;

    Automatically hash and compute the signature for a message

    Include the GMEllipticCurveCrypto+hash.h category to hash data automatically before signing and verifying. The hash algorithm used must be at least the length of the curve. The hash will have the right-most bytes truncated, if necessary.

    - (NSData*)hashSHA256AndSignData: (NSData*)data;
    - (BOOL)hashSHA256AndVerifySignature: (NSData*)signature forData: (NSData*)data;
    
    - (NSData*)hashSHA384AndSignData: (NSData*)data;
    - (BOOL)hashSHA384AndVerifySignature: (NSData*)signature forData: (NSData*)data;

    Why?

    Kenneth MacKay’s easy-ecc is an awesome, simple-to-use implementation of essential Elliptic Curve Cryptographic functions, however, the curve used is specified as a compile-time constant, so it cannot be changed at runtime.

    This library allows any and as many different curves to be used at once.

    Donations?

    Sure! :-)

    Bitcoin - 1LNdGsYtZXWeiKjGba7T997qvzrWqLXLma

    展开全文
  • 椭圆曲线加密算法

    2020-06-11 22:35:00
    椭圆曲线加密算法 椭圆曲线加密算法,即:Elliptic Curve Cryptography,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全。据研究,...

    椭圆曲线加密算法

    椭圆曲线加密算法,即:Elliptic Curve Cryptography,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全。据研究,160位ECC加密安全性相当于1024位RSA加密,210位ECC加密安全性相当于2048位RSA加密。

    一般椭圆曲线方程式表示为:(其中a,b,c,d为系数)
    > y2=ax3+ bx2+cx+d
    典型的椭圆曲线如:y2=x3−4x2+16
    椭圆曲线

    先摆一个栗子:

    小米只会加法,不会乘法,一天小王问小米。
    
    小王: 你知道几个5相加等于15?
    小米: 3个。
    小王:再考考你,几个5相加等于55?
    小米:算了半天,终于算出来了,11对吧。
    小王: 我就不行考不到你,那‭390625呢?
    小米:.............‬
    

    小米很难算到的那个数,就是公钥密码算法中的私钥(一个公钥密码算法安全的必要条件(非充分)是“由公钥不能反推出私钥”),公钥密码算法最根本的原理是利用信息的不对称性:即掌握私钥的人在整个通信过程中掌握最多的信息。
    椭圆曲线加密算法是一个基于加法阶数难求问题的密码方案。 对于椭圆曲线来讲,椭圆曲线的基点就是例子里面的5,而私钥就是基点的加法阶数(例子里面的11),公钥是基点(5)进行对应阶数的加法(11次)得到的结果(55)。

    简单描述就是:G * k = K (G,K公开,k保密)

    • k就是传说中的密钥
    • K就是传说中的公钥
    • G一般在算法里写死了,也叫做曲线参数(例子中的G点)

    上述例子相对简单,椭圆曲线加密算法里的加法建立在 “有限域上的二元三次曲线上的点”上 ,组成一个“有限加法循环群”。具体的说,这个加法的几何定义如下图,两个点的加法结果是指这两点的连线和曲线的交点关于x轴的镜像。

    • 加法 :过曲线上的两点A、B画一条直线,找到直线与椭圆曲线的交点,交点关于x轴对称位置的点,定义为A+B,即为加法。如下图所示:A + B = C。

    • 如果A=B时,即两点重合的情况,将椭圆曲线在A点的切线,与椭圆曲线的交点,交点关于x轴对称位置的点,定义为A + A,即2A。如图:
      A+B

    • 将A关于x轴对称位置的点定义为-A,即椭圆曲线的正负取反运算,如图:
      2A

    如果我们从某一点出发(所谓的单位元,比如正整数域的1,代表一个空间里的最基本单元),不停做自增操作(所谓群操作,比如++),枚举出整个空间的集合元素。如图:

    因此给定椭圆曲线的某一点G,从G出发,不停做切线,找对称点,依次得到-2G,2G,-4G,4G,-8G,8G… 。即:当给定G点时,已知x,求xG点并不困难。反之,已知xG点,求x则非常困难。即Q = NG,N就是我们的私钥,Q就是我们的公钥。

    展开全文
  • 基于国家商用密码开放动态库开发的椭圆曲线加密算法密钥生成器
  • 有趣的椭圆曲线加密

    2020-03-18 23:02:44
    椭圆曲线加密算法依赖于椭圆曲线理论,后者理论涵盖的知识比较深广,而且涉及数论中比较深奥的问题。经过数学家几百年的研究积累,已经有很多重要的成果,一些很棘手的数学难题依赖椭圆曲线理论得以解决(比如费马大...

    一、概述

    椭圆曲线加密算法依赖于椭圆曲线理论,后者理论涵盖的知识比较深广,而且涉及数论中比较深奥的问题。经过数学家几百年的研究积累,已经有很多重要的成果,一些很棘手的数学难题依赖椭圆曲线理论得以解决(比如费马大定理)。

    本文涉及的椭圆曲线知识只是抽取与密码学相关的很小的一个角落,涉及到很浅的理论的知识,同时也是一点比较肤浅的总结和认识,重点是利用椭圆曲线结合数学技巧阐述加密算法的过程和原理。

    本文特意构造有比较多的实例方便理解其过程和原理。

    二、椭圆曲线

    椭圆曲线方程来源于椭圆积分,后者来最初来源于计算椭圆周长的问题,有一段时间的历史了,在欧拉时期就开始研究。椭圆周长没有精确的初等函数的公式表示,只有近似的公式表示,精确的椭圆周长可以用不定积分表示。

    现在一般将形如如下形式的积分定义为椭圆积分:
    f(x)=cxR[t,P(t)]dtf(x)=\int_c^x {R[t, \sqrt{P(t)}]} d_t
    其中RR是其两个参数的有理函数,PP是一个无重根的3或4阶多项式,而cc是一个常数。椭圆曲线方程与P(t)P(t)表现形式比较相像。

    数学上的椭圆曲线一般由如下形式给出:
    E:y2=x3+ax2+bx+cE:y^2=x^3+ax^2+bx+c,其中判别式Δ(E)=4a3c+a2b24b327c2+18abc0Δ(E)=−4a^3c+a^2b^2−4b^3−27c^2+18abc≠0
    椭圆曲线都是关于X轴对称的曲线。

    典型的椭圆曲线如:y2=x34x2+16y^2=x^3−4x^2+16,其图像为:
    在这里插入图片描述
    更多的椭圆曲线图像:
    在这里插入图片描述
    限定Δ不为零有特殊的意义。如果判别式Δ(E)等于零,由三次方程判别式判定理可知,方程x3+ax2+bx+c=0x^3+ax^2+bx+c=0存在二重根或者三重根,曲线表现为"自相交"或者有“尖点”。

    两个典型的例子是:
    C1:y2=x3C1:y^2=x^3

    C2:y2=x3+x2C2:y^2=x^3+x2
    C1C1有三重根,表现为有"尖点";C2C2有二重根,表现为“自相交”,它们都不是椭圆曲线,其图像分别如下:
    在这里插入图片描述
    在这里插入图片描述
    在密码学中用到的椭圆曲线方程一般限定为:

    E:y2=x3+ax+bE:y^2=x^3+ax+b其中4a3+27b204a^3+27b^2≠0

    也即是这里的二次项系数为0。

    三、椭圆曲线算术

    椭圆曲线上可以定义一些很有意思的特殊运算规则。一般来说会定义两种运算:加法和数乘运算。加法运算是点与点之间的运算;数乘运算基于加法运算,重复的加法运算就是数乘。

    3.1实数域的加法运算

    3.1.1加法运算的几何解释

    已知椭圆曲线上两个不同的点PPQQ,则这两个点之和R=P+QR=P+Q可以通过如下操作得到:过PQP、Q两点做直线L,与椭圆曲线相交于第三点,该点关于X轴的对称点即是所求的RR点。椭圆曲线的这种加法运算有比较明确的几何含义。如下所示:
    在这里插入图片描述
    以这种比较奇特的规则来定义加法运算会让人觉得比较怪异,其思想很可能是借鉴于求椭圆曲线有理解的方法(没有去严格考据)。

    求椭圆曲线有理解考虑的问题是寻找有理点(x,y)使其满足椭圆曲线方程。其求解过程是在有限的已知有理点的集合中,选两个点P1,P2P1,P2,作直线与椭圆曲线相交与第三点个有理点Q3Q3。此时如果再利用P1,P2,Q3P1,P2,Q3三个点中的任意两点作直线不能在产生新的有理解(因为他们本身是已经在一条直线上,不会产生新的交点),但是考虑Q3关于X轴对称的点Q3Q^{′}3必定也是有理点,于是可以利用Q3Q^{′}3P1P1或者Q3Q^{′}3P2P2继续做直线与椭圆曲线相交得到新的有理解,对新的交点再取对称点,以此迭代下去。由此利用交点的对称点作直线来生成新的交点,进而可逐步求解满足椭圆曲线的有理解。

    椭圆曲线加法运算的规则中“取交点的对称点”正是与上述求解过程及其相似。

    对于加法运算也有另外一种描述:若椭圆曲线上三个点在同一直线上,则他们的和为O,也即是P+Q+R=OP+Q+R′=O,其中的OO是无穷远点或者零点。

    更完整的椭圆曲线加法运算规则如下:

    1、O+O=OO+O=O,对任意的P,有P+O=PP+O=POO看做零点,对加法运算没有实际贡献(类似于四则运算加法运算中的0)。

    2、P=(x,y)P=(x,y)的负元是关于X中对称的点P=(x,y)−P=(x,−y)(而不是关于原点对称),P+(P)=OP+(−P)=O。过PPP−P的直线与X轴垂直,实际上可以看做它与椭圆曲线相交于无穷远点(射影平面,也即是在欧式平面上添加了无穷远点和无穷远直线的平面),因此将也将O视作无穷远点。

    3、计算PPQQ的和是通过做过PPQQ两点的直线,与椭圆曲线相交于第三点,再取该点关于X轴的对称点以此作为P,QP,Q之和,正如上面的几何图形展示的那样。

    4、计算PPPO(P≠O)的两倍时,是做该点的切线,再取交点SS关于X轴的对称点S−S,也即是2P=P+P=S2P=P+P=−S
    容易验证,对于椭圆曲线上的点和O点组成的集合,以及集合上定义的二元加法运算,构成一个Abel群。单位元是OO点,P(x,y)P(x,y)的逆元是P(x,y)P(x,−y),封闭性,结合性以及交换性也是显然满足的。

    3.1.2加法运算的代数解释

    几何解释更直观,代数解释更有利于数值计算。

    过曲线上P(xp,yp)P(x_p,y_p)Q(xQ,yQ)Q(x_Q,y_Q)两点(PPQQ不互为负元)做直线,求与曲线的第三个交点的问题是很容易用代数的方法来描述的。
    也即是求:
    {y2=x3+ax+b(1)yyp=k(xxp)(2)\begin{cases} y^2= x^3+ax+b & \text {(1)} \\ y-y_p=k(x-x_p) & \text{(2)} \end{cases}
    其中斜率k=yQyPxQxPk=\frac{y_Q−y_P}{x_Q−x_P}

    将(2)代入(1)再利用次数对齐的方式容易求得第三个交点的对称点也即P,QP,Q之和R(xR,yR)R(x_R,y_R)为:

    xR=k2xPxQx_R=k^2−x_P−x_Q

    yR=yP+k(xPxR)y_R=−y_P+k(x_P−x_R)

    如果需要计算倍乘,可以让多个点自身重复相加得到。例如P+P=2P=RP+P=2P=R,当yP0y_P≠0时,代数描述为:

    xR=(3xP2+a2yP)22xPx_R=(\frac{3x^2_P+a}{2y_P})^2−2x_P

    yR=(3xP2+a2yP)(xPxR)yPy_R=(\frac{3x^2_P+a}{2y_P})(x_P−x_R)−y_P

    3.2模素数P的加法运算

    密码学中普遍采用的是有限域上的椭圆曲线,也即是变元和系数均在有限域中取值的椭圆曲线。使用模素数p的有限域Zp,将模运算引入到椭圆曲线算术中,变量和系数从集合0,1,2,...,p10,1,2,...,p−1中取值而非是在实数上取值。

    此时讨论椭圆曲线形式如下:

    y2modp=(x3+ax+b)modpy^2modp=(x^3+ax+b)modp

    其中(4a3+27b2)modp0(4a^3+27b^2)modp≠0,变量和系数均在Zp中取值。

    将满足上式的所有非负整数对和OO点记为集合Ep(a,b)E_p(a,b),这是一个有限的离散点集。由此可知集合中的点分布在(0,0)(0,0)(p1,p1)(p−1,p−1)的象限中,集合中的点有可能刚好也在椭圆曲线上,更多的可能是在椭圆曲线外。例如点(13,7)(13,7)是满足y2mod23=(x3+x+1)mod23y^2mod23=(x^3+x+1)mod23的点,但是(13,7)(13,7)并不在椭圆曲线上。

    实际上,集合Ep(a,b)E_p(a,b)与模p的加法运算构成循环阿贝尔群,其生成元,阶和生成子群问题在本节后面会讨论。

    对于较小的素数p,完全可以暴力穷举找出集合Ep(a,b)E_p(a,b)中的点。比如参数a=1,b=3,p=23E23(1,3)a=1,b=3,p=23,E_{23}(1,3)有27个点(包含O点),暴力穷举这些点分别为(第八节给出了一些分析椭圆曲线问题的demo实现):

    (0,7)        (6,15)        (15,9)
    (0,16)       (7,10)        (15,14)
    (2,6)        (7,13)        (19,2)
    (2,17)       (10,1)        (19,21)
    (4,5)        (10,22)       (21,4)
    (4,18)       (12,8)        (21,19)
    (5,8)        (12,15)       (22,1)
    (5,15)       (14,1)        (22,22)
    (6,8)        (14,22)        O
    

    Ep(a,b)E_p(a,b)上的加法规则和实数域上的加法基本一致,只是多加了模运算。但是模pp的加法没有显而易见的几何解释,只有代数描述。

    求解(xR,yR)(x_R,y_R)的代数表达式为:

    xR=(λ2xPxQ)modpx_R=(λ^2−x_P−x_Q)modp

    yR=(λ(xPxR)yP)modpy_R=(λ(x_P−x_R)−y_P)modp

    其中
    λ={yQyPxQxPmodp,(PQ)3xP2+a2yPmodp,(P = Q) λ= \begin{cases} \frac{y_Q-y_P}{x_Q-x_P}modp, & (P \neq Q) \\ \frac{3x^2_P+a}{2yP}modp, & \text{(P = Q)} \end{cases}

    例如a=1,b=1,p=23,P(3,10),Q(13,16)a=1,b=1,p=23,P(3,10),Q(13,16),求R=P+QR=P+Q.

    此时PQP≠Q,计算λ=(yQyPxQxP)modp=(1610133)mod23=6×101mod23λ=(y_Q−y_Px_Q−x_P)modp=(16−1013−3)mod23=6×10−1mod23.

    要计算上式首先要计算101mod2310^{−1}mod23.

    x101(mod23)x≡10−1(mod23),由于1010(mod23)10≡10(mod23),所以10x1(mod23)10x≡1(mod23),利用扩展欧几里德算法求得x=7x=7.
    λ=6×7mod23=19λ=6×7mod23=19

    所以
    xR=(λ2xPxQ)modp=(192313)mod23=345mod23=0x_R=(λ^2−x_P−x_Q)modp=(19^2−3−13)mod23=345mod23=0

    yR=(λ(xPxR)yP)modp=(19×(30)10)mod23=47mod23=1y_R=(λ(x_P−x_R)−y_P)modp=(19×(3−0)−10)mod23=47mod23=1

    所以R=(0,1)R=(0,1).

    还可以按照以上规则计算2P,3P2P,3P等等倍乘点。

    实际上E23(1,1)E_{23}(1,1)中共有28个点(包含无穷远点O),以P(3,10)P(3,10)开始的所有倍乘点:P,2P,3P...27P,28PP,2P,3P...27P,28P可以暴力计算得出:

    P=(3,10)
    2P=(7,12)
    3P=(19,5)
    4P=(17,3)
    5P=(9,16)
    6P=(12,4)
    7P=(11,3)
    8P=(13,16)
    9P=(0,1)
    10P=(6,4)
    11P=(18,20)
    12P=(5,4)
    13P=(1,7)
    14P=(4,0)
    15P=(1,16)
    16P=(5,19)
    17P=(18,3)
    18P=(6,19)
    19P=(0,22)
    20P=(13,7)
    21P=(11,20)
    22P=(12,19)
    23P=(9,7)
    24P=(17,20)
    25P=(19,18)
    26P=(7,11)
    27P=(3,13)
    28P=O
    

    容易验证,上述计算过程中Q(13,16)Q(13,16)点就是8PP+Q=P+8P=9P=(0,1)8P,P+Q=P+8P=9P=(0,1),与上述计算结果是吻合的,读者也可以验证更多的结果。

    现在提出一个问题:Ep(a,b)E_p(a,b)中有多少个点呢?这个问题的准确答案并不好回答,但是有一些粗略的规律。

    Ep(a,b)E_p(a,b)中点的个数为NpN_p,并且ap=pNpa_p=p−N_p,实际上NpN_ppp比较接近。

    Hasse定理表明:

    ap<2p|a_p|<2\sqrt{p}
    这实际上解释了apa_p的误差,从而有2p<ap=pNp<2p−2\sqrt{p}<a_p=p−N_p<2\sqrt{p}
    也就是p2p<Np<p+2pp−2\sqrt{p}<N_p<p+2\sqrt{p},等价于p+12pNpp+1+2pp+1−2\sqrt{p}⩽N_p⩽p+1+2\sqrt{p}
    接下来的一个问题是子群、生成元和阶:

    不难得知,有限域上的椭圆曲线的点和加法运算构成一个有限交换群SS

    以一个点GG作为生成元,进行重复的加法运算,能够生成一个子群SS^′。群SS^′有可能与SS相同,更有可能是SS的一个真子群。

    比如椭圆曲线为y2=x3+x+1p=23y2=x^3+x+1,p=23
    G=(3,10)G=(3,10)生成的子群刚好等于SS,因为28G=O28G=O,说明此时SS还是一个有限循环群,群中每个元素都能由(3,10)通过重复的加法运算得到,群中元素的个数为28,其阶为28(最小的使得nG=OnG=O成立的n),生成元为(3,10)(3,10)

    但是以G=(6,19)G=(6,19)生成的子群是S的真子群,因为14G=O14G=O,它也是一个有限循环群,因为群中每个元素都能由(6,19)(6,19)通过重复的加法运算得到,该子群的元素个数为1414,阶为1414(最小的使得nG=OnG=O的成立n),生成元为(6,19)(6,19)

    拉格朗日定理还告诉我们,生成的子群SS′的阶与原来的群SS的阶存在约数关系,也就是说子群S′的阶只能是1,2,4,7,14,281,2,4,7,14,28。群S的阶与子群S′的阶的比值一般称为协因子(cofactor):h=SSh=\frac{|S|}{∣S^′∣}。一般会取h=1h=1,以保证生成子群的阶比较大。

    G=(6,19)G=(6,19)生成子群过程(为方便计算,取O=(1,1)O=(−1,−1)):

    1P=(6,19)        15P=(6,19)
    2P=(13,16)       16P=(13,16)
    3P=(7,11)        17P=(7,11)
    4P=(5,19)        18P=(5,19)
    5P=(12,4)        19P=(12,4)
    6P=(17,20)       20P=(17,20)
    7P=(4,0)         21P=(4,0)
    8P=(17,3)        22P=(17,3)
    9P=(12,19)       23P=(12,19)
    10P=(5,4)        24P=(5,4)
    11P=(7,12)       25P=(7,12)
    12P=(13,7)       26P=(13,7)
    13P=(6,4)        27P=(6,4)
    14P=(-1,-1)      28P=(-1,-1)
    

    在后面的ECC加密算法过程中会有一个给定的基点GG(也就是生成元)生成一个子群,然后秘钥空间在此子群取得,一般会要求保证子群的阶会尽量大,基点及其子群的阶nn都是公开的信息。

    四、椭圆曲线密码学中的离散对数问题

    构造一个数学难题来保证加密的安全性是现代密码学中加密算法的主要思想。类似RSA算法中大数的质因子分解难题一样,椭圆曲线也有类似的数学难题。

    考虑Q=kPQ=kP,其中Q,PEp(a,b),k<pQ,P∈Ep(a,b),k<p

    对于给定的k,pk,p计算QQ是很容易的;反过来给定Q,PQ,P,计算k是相当困难的,这就是椭圆曲线的离散对数问题(这里之所以称之为离散对数问题大概是为了与其他加密算法的说法保持一致,便于理解)。

    正因为如此,可以将QQ作为公钥,公开出去;kk作为私钥,秘密保管,通过公钥来破解私钥十分困难。

    目前由椭圆曲线公钥求解私钥的最有效算法复杂度为O(p)O(\sqrt{p}),其中pp是阶数nn的最大素因子。

    五、椭圆曲线实现秘钥协商(ECDHE)

    5.1原理和流程

    利用模pp有限域上椭圆曲线算术规则可以用来实现秘钥协商,其流程如下:

    (1)Alice和Bob会共享一些椭圆曲线的参数信息:(p,a,b,G,n,h)(p,a,b,G,n,h),其中a,ba,b确定了椭圆曲线方程,pp确定了模pp的有限域,GG是中的生成元,用于生成子群,要求GG的阶n应该尽量大,GG的阶是使得nG=OnG=O成立的最小的整数,也即是(n1)G(n−1)G所代表的点与GG点的横坐标刚好相同,协因子hh一般等于1。

    (2)Alice选择小于nn整数nAn_A,然后计算PA=nA×GP_A=n_A×G,将PAP_A发送给Bob。

    (3)同理,Bob也选择小于nn整数nBn_B,然后计算PB=nB×GP_B=n_B×G,将PBP_B发送给Alice。

    (4)Alice通过如下计算得出协商的秘钥:KA=nA×PBK_A=n_A×P_B;Bob通过如下计算得出协商的秘钥:KB=nB×PBK_B=n_B×P_B,容易证明,KA=KBK_A=K_B

    因为KA=nA×PB=nA×(nB×G)=nB×(nA×G)=KBK_A=n_A×P_B=n_A×(n_B×G)=n_B×(n_A×G)=K_B

    由此Alice和Bob计算得到相同的秘钥,达到秘钥协商的目的。

    5.2实例

    例如,参数a=0,b=4a=0,b=−4,椭圆曲线方程为y2=x34p=211,G=(2,2)y^2=x^3−4,p=211,G=(2,2),因为240G=(2,209)240G=(2,209)所以n=241。

    Alice选择nA=151PA=151G=(62,59)n_A=151,P_A=151G=(62,59)

    Bob选择nB=171PB=171G=(209,153)n_B=171,P_B=171G=(209,153)

    他们协商的秘钥K=151PB=171PA=151(209,153)=171(62,59)=(95,194)=(151171%n)G=34GK=151P_B=171P_A=151(209,153)=171(62,59)=(95,194)=(151∗171\%n)G=34G

    六、椭圆曲线实现加解密

    6.1原理和流程

    利用椭圆曲线来进行加密和解密也是与RSA一定程度的类似,每一个用户都有属于自己的公钥和私钥。私钥就是用户选定的数字nn,私钥自己保存;公钥就是由P=nGP=nG,计算出来的点,公钥公开。

    假设Alice与Bob进行加密通信,其加密的流程如下:

    (1)Alice首先将明文消息转换(编码)为Ep(a,b)E_p(a,b)中的Pm(x,y)P_m(x,y),然后随机选定一个正整数k,并且利用Bob的公钥PB通过如下计算出密文:Cm=kG,Pm+kPBC_m={kG,P_m+kP_B}.。因此,密文实际上是有两个点组成。

    (2)Bob收到密文CmC_m,利用自己的私钥nBn_B进行如下计算,可以解密得到明文:

    Pm+kPBnB(kG)=Pm+k(nBG)nB(kG)=PmP_m+kP_B−n_B(kG)=P_m+k(n_BG)−n_B(kG)=P_m

    也就是用第二个点Pm+kPBP_m+k_PB减去第一个点kGkG与自己的私钥nn之积。

    6.2实例

    考虑参数a=0,b=4,p=199,G=(2,2)a=0,b=−4,p=199,G=(2,2),椭圆曲线方程为y2=x34y^2=x^3−4,Bob选定的私钥为nB=119n_B=119,其公钥PB=119G=(183,173)P_B=119G=(183,173)

    Alice希望将消息Pm=(76,66)P_m=(76,66)加密后发送给Bob,于是Alice随机选定正整数k=133k=133,并通过Bob的公钥加密得到密文:
    Cm=133(2,2),(76,66)+133(183,173)=(40,147),(180,163)Cm={133(2,2),(76,66)+133(183,173)}={(40,147),(180,163)}

    Bob收到密文消息利用自己的私钥nB=119n_B=119进行解密:

    Pm+kPBnB(kG)=(180,163)119(40,147)=(180,163)(98,52)=(76,66)=PmP_m+kP_B−n_B(kG)=(180,163)−119(40,147)=(180,163)−(98,52)=(76,66)=Pm

    由此,Bob顺利解密得到明文消息,Alice与Bob之间完成加密通信。

    七、杂项

    公钥加密算法中除了ECC,还有另外一个广泛使用的加密算法–RSA公钥加密算法。

    ECC与RSA相比,主要的优点是在相同的安全级别下ECC使用的秘钥长度要短很多,由此带来处理速度、带宽和存储空间上的额外优势。下表展示了不同加密算法秘钥的位数对比情况:
    在这里插入图片描述
    比特币中使用椭圆曲线密码算法,以保证比特币网络中信息安全性和签名认证问题。每个用户都有属于自己的公钥和私钥。利用私钥可以对交易信息进行签名(ECDSA),其他人可以利用其公钥进行认证,公钥也用来构造钱包地址。所使用的椭圆曲线是采用了Certicom推荐的椭圆曲线secp256k1 ,其参数由六元组构成:D=(p,a,b,G,n,h)D=(p,a,b,G,n,h),其中pp是很大的质数,hh就是协因子,表征由生成元GG生成子群的阶与母群的阶的关系,前文有解释;参数信息都是公开的,有兴趣可以到网上查到。

    八、References

    [1] 密码编码学与网络安全原理与实践
    [2] http://andrea.corbellini.name/
    [3] 数论概述.第四十三章-第四十八章
    [4] https://mp.weixin.qq.com/s/jOcVk7olBDgBgoy56m5cxQ
    [5] https://blog.csdn.net/mrpre/article/details/72850598

    展开全文
  • 椭圆曲线加密数学原理 实数椭圆曲线 什么是椭圆曲线,想必大家都会首先想到的是高中时学到的标准椭圆曲线方程。 x2a2+y2b2=1(a>b,焦点在x轴,a<b,焦点在y轴) \frac{x^2} {a^2}+\frac {y^2}{b^2}=1(a>b,...
  • 为了防止私人数据泄露并完善已有的移动网络匿名漫游认证方案,提出了一种利用椭圆曲线加密结合散列函数的移动网络匿名安全认证方案。该方案利用椭圆曲线加密,结合散列函数,以随机数代替公开密钥加密和时间戳。首先...
  • 针对物联网(IoT)中终端设备接入网络服务器的安全性问题,提出了一种基于椭圆曲线加密(ECC)和cookie信息的物联网终端安全认证协议。协议首先将用户身份信息、服务器私钥、随机数和cookie有效期信息组成一个cookie...
  • 椭圆曲线加密的论文

    2015-12-04 15:03:01
    很不错的椭圆曲线加密论文 。使用 matlab实现 ,是关于 Ecc的方面 适合学习 ,加油加油
  • 椭圆曲线加密系统的性能分析
  • 椭圆曲线加密理解

    2019-01-26 17:59:26
    椭圆曲线加密学 http://www.secg.org/sec1-v2.pdf TLS1.2 ECDH https://tools.ietf.org/html/rfc4492 需要理解的知识点 椭圆曲线方程及其性质 同余运算 有限域 伽瓦罗有限域 简化的椭圆曲线方程为 (注意, ...
  • ECC椭圆曲线加密算法

    千次阅读 2016-12-25 16:14:37
    椭圆曲线加密也是一种公钥加密算法,和RSA与离散对数一样,它也是基于一个数学求解的难题,并且它的难度比RSA和离散对数都要大,它基于的数字难题就是求取定义在椭圆曲线上的离散对数的求取难题。
  • 椭圆曲线加密算法的发展趋势.椭圆曲线加密算法的发展趋势.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,605
精华内容 3,842
关键字:

椭圆曲线加密