首页
社区
课程
招聘
[求助]椭圆曲线加密的疑惑
发表于: 2009-6-23 00:42 7537

[求助]椭圆曲线加密的疑惑

2009-6-23 00:42
7537
最近在学习椭圆曲线密码知识,资料很少,所以了解起来比较难。看了椭圆曲线ECC加密算法入门介绍(很好),还是不太清楚。有几个疑惑想请教:
文中有这样一段话:
运算法则:任意取椭圆曲线上两点P、Q (若P、Q两点重合,则做P点的切线)做直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R。我们规定P+Q=R。

这里[[  我们规定P+Q=R  ]]是指根据曲线方程来计算,P+Q一定等于R?如果是这样,那么R-Q是否可以计算呢?

我发现作者没有提到减法的定义,是不是如果试图计算R-Q,那么可能结果=P不成立,或不在有限域Fp中?如果这样,我是否可以理解为椭圆曲线加密的关键是:
因为没有定义减法和除法,或减法、除法无效?!

文中说:
  考虑如下等式:
  K=kG  [其中 K,G为Ep(a,b)上的点,k为小于n(n是点G的阶)的整数]
  不难发现,给定k和G,根据加法法则,计算K很容易;但给定K和G,求k就相对困难了。

也就是说,没有除法,比如K/G=k,只能穷举m*G,等于K时,才能确定k?

(隐含的关键就是说取余操作没有逆运算)

菜鸟乱飞 求教

[课程]Android-CTF解题方法汇总!

收藏
免费 0
支持
分享
最新回复 (13)
雪    币: 213
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
这个加减乘除不是代数中的意义。
你要先学习一下离散数学。
2009-6-23 02:58
0
雪    币: 100
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
请问在实际中,kG是怎样计算的?是k个G的加法,还是什么其他方法?
因为我计算了P+P的结果,不等于用坐标x,y直接乘以2的结果,那么当k是一个100位的数,k个G相加岂不是太漫长了?文中没有提到kG的计算方法啊,只是定义说满足乘法a*b=c(mod p),可是到底怎么算呢?k是一个正整数,而G是一个元,有x,y的坐标。奇怪阿。
2009-6-23 22:48
0
雪    币: 213
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
这个可以快速计算,P+P=2P, 4P=2P+2P
2009-6-23 23:18
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
5
给定R和Q, 按定义是可以计算出P的, 但正如你下面所说的, P不一定在有限域Fp中.


正确, 没有定义减法和除法.


定义上就是k个G的加法.


vrain说得对, 计算 kG 并不需要把 G 加 k 次的, 可以拆成 G + G = 2G, 2G + 2G = 4G, 4G + 4G = 8G 这样计算的. 比如说
7G = 1G + 2G + 4G
100G = 4G + 32G + 64G
2009-6-24 23:40
0
雪    币: 539
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
请问在实际中,kG是怎样计算的?是k个G的加法,还是什么其他方法?
同样问题,这个实在迷惑  求解
2009-6-25 11:56
0
雪    币: 100
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
感谢解答!
由此引发的问题更多了,我是不是可以这样通俗的理解:
Fp是一个有限域,可以看成的是一些点的集合,这些点有一个重要的属性,就是他们的xy值是某些值取余的结果,而[某些值]对应的是某个二元曲线方程(比如形状类似于椭圆曲线方程)的根。
由于曲线方程的根可能无限多,所以要规定x<p,y<p,由于某种奇妙的联系,使得这些有限数量的根和有限集合中的点一一对应。再说取余运算,恰恰是不可逆的,10 mod 3=1,而1对应的可能为4,7,10.....。
如果这些点的值不是取余的结果,那么减法、除法可能就存在了。所以,这种加密实际依赖于一种不可逆的运算,运算结果单向指向了一个一一对应有限的集合。
2009-6-25 19:21
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
8
ECC 的加法,很類似 public key 的 exponential ,通常我們稱這樣的情況為 sub exponential calculate。
它的狀況不是不可逆,是因為要逆的話,很困難,就如同挑戰 DLP 的情況一樣,不是不可能,是很難到幾乎沒辦法。至少就現在已知的知識及技術是很難辦到的。
我建議想要接觸多一點ECC 方面的 information,可以先讀 number theory 及 group theory 裏的一些 chapter 為佳,然後再 study ECC,這樣比較有一點點的 conception.
2009-6-25 20:16
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
9
就是k个G的加法. 但是不需要计算k次. 如同我前面所说的, 把k表示成2进制, 然后依次计算2G, 4G, 8G...
7 = 1 + 2 + 4, 则 7G = 1G + 2G + 4G
100 = 4 + 32 + 64, 则 100G = 4G + 32G + 64G.
这样计算量远远小于直接做  k 次 G+P 加法.
2009-6-29 22:06
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
10
[QUOTE=shangwg;646882]由此引发的问题更多了,我是不是可以这样通俗的理解:
Fp是一个有限域,可以看成的是一些点的集合,这些点有一个重要的属性,就是他们的xy值是某些值取余的结果,而[某些值]对应的是某个二元曲线方程(比如形状类似于椭圆曲线方程)的根。
由于曲线方程的根可能无限多,所以要规定x<p,...[/QUOTE]
不好意思, 那天时间紧, 用词不太严谨, 有些误导了.
1. 其实ECC定义的就是一个加法群, 因此它只有加法, 没有减法/乘法/除法.
2. 做为一个加法群, ECC只定义了加法, 倍点两种运算.
3. kG的写法其实是倍点的写法而不是乘法, 真正的乘法(如果有的话)应该是定义在两个元素之间的, 即G*G.
4. Fp的确是某些点的集合, 这些点的属性是因为它们的xy值满足给定的椭圆曲线方程, 而且是整数.
5. 同余运算是为了保证Fp是一个有限群.
6. 由于同余的关系, x+kp形成的图像和x形成的图像有着对应的关系, 因此只需要研究x<p的情况.
7. ECC的难点在于加法的计算不可逆. 因此已知k求kG易, 但已知kG求k难.
2009-6-29 22:30
0
雪    币: 100
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
11
感谢arab!
这样说我就清楚了,因为没有基础,看公式实在迷糊,当然我相信文章中的结论都是数学家证明了的,只是没有通俗的理解他。
我想说说我这几天思考的结果,不对之处请多多指正:
这种加密方式的要点正如文章说的,通过K,G(基点)求k很难,那么,没有定义的减法,是不存在还是没有发现?我指的是公式计算,不是穷举之类的。
另一个重要的问题是,Fp这个域中的元素,有没有大小关系?(从文章中看,也属于没有定义的情况)如果有大小关系,也能很快算出r了。
2009-6-30 00:51
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
12
某种意义上来说是存在的. 因为加法群需要定义一个单位元O和一个逆元素-P, 使得 P + (-P) = O.
因此, 减法可以表示为 A - B = A + (-B), 最终还是回到加法计算.


你指的是类似5>2这样的大小关系? ECC没有定义, 因为有同余的关系, 你不能说 x + 1 一定比 x + kp 大.
2009-6-30 21:58
0
雪    币: 100
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
非常感谢,arab,真心希望论坛中多一些你这样的老师。希望以后的帖子继续得到这样的帮助!
菜鸟乱飞
2009-6-30 23:40
0
雪    币: 100
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
同时鸣谢vrain,rockinuk!!
2009-6-30 23:44
0
游客
登录 | 注册 方可回帖
返回
//