椭圆曲线加密中的加法乘法浅析

本文不深入椭圆曲线加密算法的全部知识,只针对椭圆曲线加密中需要用到的加法和乘法计算规则进行浅析。

实际练习中碰到一个比较简单密码学的问题,但是涉及到了椭圆曲线加密算法,题目描述如下:

已知椭圆曲线加密Ep(a,b)参数为
p = 15424654874903
a = 16546484
b = 4548674875
G(6478678675,5636379357093)

私钥为
k = 546768
求公钥K(x,y)
提示:K=kG

这里需要介绍一下椭圆曲线
一般,椭圆曲线可以用以下二元三阶方程的形式来表示:
  y² = x³ + ax + b,其中a、b为系数。
它大概的几何形状如下图:

椭圆曲线.png

而本文要介绍的加法和乘法,就是基于这样一个奇怪的几何图形来做到的。

椭圆曲线加法(非有限域):

在椭圆曲线上取一点P(Xp,Yp),再取一点Q(Xq,Yq),连接P、Q两点作一条直线,这条直线将在椭圆曲线上交于第三点G,过G点作垂直于X轴的直线,将过椭圆曲线另一点R(一般是关于X轴对称的点),R点则被定义为P+Q的结果,既P+Q=R:

P+Q=R

当P=Q的情况下,直线将是椭圆曲线在P(Q)点上的切线,而G点是这条切线和曲线的另一个交点,同样,P+Q=R:

P=Q.png

通过上述的图片和文字描述,已经在几何图形上给出了椭圆曲线加法的定义,可是如果要公式化,该如何快速计算呢?
这里只提供快速计算公式,不提供证明,证明可以自己再去解方程组推导一下:

计算P+Q=R

当P!=Q时,两点纵坐标相减的值与横坐标相减的值就是直线的斜率:
λ = (Yq - Yp)/(Xq - Xp)
当P=Q,计算过P(Q)点切线的斜率,既椭圆曲线公式两边求导相除:
λ = (3Xp² + a)/2Yp
斜率计算之后,对点R的坐标进行计算,公式如下:

Xr = (λ² - Xp - Xq) 
Yr = (λ(Xp - Xr) - Yp)

通过上述公式,可以快速计算椭圆曲线上任意两点的加法和,这里给出加法实现的python代码:

if P == Q:
      aaa=(3*pow(P[0],2) + a)
      bbb=(2*G[1])
      k=(aaa/bbb) 
else:
      aaa=(Q[1]-P[1])
      bbb=(Q[0]-P[0])
      k=(aaa/bbb) 

Rx=(pow(k,2)-P[0] - Q[0]) 
Ry=(k*(P[0]-Rx) - P[1]) 
椭圆曲线加法(有限域)

实数范围上光滑的椭圆曲线在密码学应用上并不合适,需要进行有限域下的离散化操作才能使用。


离散化示例图.png

现在将上述的椭圆曲线加法计算公式适当修改,以适应有限域下的计算:
当P!=Q时,两点纵坐标相减的值与横坐标相减的值需要与p进行取余操作:
λ = (Yq - Yp)/(Xq - Xp) mod p
当P=Q,计算过P(Q)点切线的斜率,既椭圆曲线公式两边求导相除,结果也需要与p进行取余操作:
λ = (3Xp² + a)/2Yp mod p
斜率计算之后,对点R的坐标进行计算,公式如下:

Xr = (λ² - Xp - Xq) mod p
Yr = (λ(Xp - Xr) - Yp) mod p

通过比较,有限域下的计算只是对结果进行了取余操作,上述公式看起来已经解决了有限域下的椭圆曲线加法。
但是如果在编写代码,计算实际的例子时,有很大可能会得到错误的结果,
其根源在于λ = (Yq - Yp)/(Xq - Xp) mod pλ = (3Xp² + a)/2Yp mod p在进行取余计算之前,除数和被除数之前可能并不是一个整除的关系。
如:1/4 mod 23,如果直接进行处理,将会得到结果0。
但是在分数求模计算中,是如下定义的:

计算a/b(mod n) 
a/b (mod n)=a*b^-1(mod n) 
计算1/b mod n   
=b^(-1) mod n  
就是求y,满足:  
yb = 1 mod n
y是有限域F(n)上x的乘法逆元素

简单点说,假设需要求上述的1/4 mod 23,可以转化为1*4(-1次方) mod 23,又可以转化为1*(4和23的乘法逆元) mod 23
而计算乘法逆元,可以通过拓展欧几里得计算得到,这里对拓展欧几里得不作展开,只提供一个简单算法流程描述:

ExtendedEuclid(d,f) 
1 (X1,X2,X3):=(1,0,f) 
2   (Y1,Y2,Y3):=(0,1,d) 
3  if (Y3=0) then return  d'=null//无逆元 
4  if (Y3=1) then return  d'=Y2  //Y2为逆元 
5  Q:=X3 div Y3 
6  (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3) 
7 (X1,X2,X3):=(Y1,Y2,Y3) 
8  (Y1,Y2,Y3):=(T1,T2,T3) 
9  goto 3

得到乘法逆元后,椭圆曲线上的加法运算计算就简单了,实现Python代码如下:

#coding:utf-8
#欧几里得算法求最大公约数
def get_gcd(a, b):
    k = a // b
    remainder = a % b
    while remainder != 0:
        a = b 
        b = remainder
        k = a // b
        remainder = a % b
    return b
    
#改进欧几里得算法求线性方程的x与y
def get_(a, b):
    if b == 0:
        return 1, 0
    else:
        k = a // b
        remainder = a % b       
        x1, y1 = get_(b, remainder)
        x, y = y1, x1 - k * y1          
    return x, y

#返回乘法逆元
def yunsle(a,b):
    #将初始b的绝对值进行保存
    if b < 0:
        m = abs(b)
    else:
    m = b
    flag = get_gcd(a, b)

    #判断最大公约数是否为1,若不是则没有逆元
    if flag == 1:   
    x, y = get_(a, b)   
    x0 = x % m #对于Python '%'就是求模运算,因此不需要'+m'
    #print(x0) #x0就是所求的逆元
        return x0
    else:
    print("Do not have!")


if P == Q:
        aaa=(3*pow(P[0],2) + a)
        bbb=(2*P[1])
        if aaa % bbb !=0:
            val=yunsle(bbb,mod)
            y=(aaa*val) % mod
        else:
            y=(aaa/bbb) % mod 
else:
        aaa=(Q[1]-P[1])
        bbb=(Q[0]-P[0])
        if aaa % bbb !=0:
            val=yunsle(bbb,mod)
            y=(aaa*val) % mod
        else:
            y=(aaa/bbb) % mod 

Rx=(pow(k,2)-P[0] - Q[0])  % mod
Ry=(k*(P[0]-Rx) - P[1])  % mod
椭圆曲线乘法

简单介绍完椭圆曲线上定义的加法运算,椭圆曲线上的乘法运算就比较简单了,因为加法可以退化为加法运算,就像算数上的1*3等价与1+1+1。
假设我们需要求2P,则可以化简为P+P=2P
同理,当我们需要求3P时,可以化简为P+2P=3P,其中2P=P+P
最后,我们可以得到规律,当求nP时(n为任意正整数),P+(n-1)P=nP,其中(n-1)P=P+(n-2)P
这样,通过上述介绍的椭圆曲线加法公式,完全可以进行椭圆曲线的乘法计算
以本文开头的题目为例,给出Python代码实现:

#coding:utf-8
#欧几里得算法求最大公约数
def get_gcd(a, b):
    k = a // b
    remainder = a % b
    while remainder != 0:
        a = b 
        b = remainder
        k = a // b
        remainder = a % b
    return b
    
#改进欧几里得算法求线性方程的x与y
def get_(a, b):
    if b == 0:
        return 1, 0
    else:
        k = a // b
        remainder = a % b       
        x1, y1 = get_(b, remainder)
        x, y = y1, x1 - k * y1          
    return x, y

#返回乘法逆元
def yunsle(a,b):
    #将初始b的绝对值进行保存
    if b < 0:
        m = abs(b)
    else:
    m = b
    flag = get_gcd(a, b)

    #判断最大公约数是否为1,若不是则没有逆元
    if flag == 1:   
    x, y = get_(a, b)   
    x0 = x % m #对于Python '%'就是求模运算,因此不需要'+m'
    #print(x0) #x0就是所求的逆元
        return x0
    else:
    print("Do not have!")


mod=15424654874903
#mod=23
a=16546484
#a=1
b=4548674875
#b=1
G=[6478678675,5636379357093]
#G=[3,10]
#次数
k=546768
temp=[6478678675,5636379357093]
#temp=[3,10]
for i in range(0,k):
    if i == 0:
        aaa=(3*pow(G[0],2) + a)
        bbb=(2*G[1])
        if aaa % bbb !=0:
            val=yunsle(bbb,mod)
            y=(aaa*val) % mod
        else:
            y=(aaa/bbb) % mod
    else:
        aaa=(temp[1]-G[1])
        bbb=(temp[0]-G[0])
        if aaa % bbb !=0:
            val=yunsle(bbb,mod)
            y=(aaa*val) % mod
        else:
            y=(aaa/bbb) % mod

    #print y
    Rx=(pow(y,2)-G[0] - temp[0]) % mod
    Ry=(y*(G[0]-Rx) - G[1]) % mod
    temp=[Rx,Ry]
    #print temp

print temp
参考文献:

http://blog.51cto.com/11821908/2057726
讲解了受限域的曲线下的加法实现计算
https://www.jianshu.com/p/2e6031ac3d50
只讲解了无受限域下曲线的加法
https://wenku.baidu.com/view/6f2879cca1c7aa00b52acb5f.html
分数求模原理介绍
https://www.pediy.com/kssd/pediy06/pediy6014.htm
看雪论坛上的详细介绍,提供了加法运算的验证集
https://blog.csdn.net/baidu_38271024/article/details/78881031
乘法逆元求解的python实现

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容