1、先搞清楚画笔的基本用法。
2、再搞清楚椭圆的函数。
3、根据别人的代码,自己多调试几次就画出有意思的图形了。
代码如下:
import turtlepen=turtle.Turtle() #定义画笔实例
a=1
for i in range(120):
if 0<=i<30 or 60<=i<90:
a=a+0.2
pen.lt(3) #向左转3度
pen.fd(a) #向前走a的步长
else:
a=a-0.2
pen.lt(3)
pen.fd(a)
print(pen)
turtle.mainloop()
椭圆曲线的公式,跟高中的椭圆曲线的公式不太一样, 样子长得也不太一样, 我们高中数学的椭圆曲线长得是这个样子的:
我们习惯的椭圆长得是这个样子的:
在密码学中,椭圆曲线公式为
样子长得是这样的:
为什么这样子的曲线也叫椭圆曲线呢?严格意义上来说我们高中学到的曲线是椭圆曲线的一种退化情形,密码学上的椭圆曲线也是标准椭圆曲线的退化情形。
密码学上,椭圆曲线的基本形式为:
a,b的值根据不同的标准不一样,例如我们常用的secp256k1的a=0, b=7. 曲线退化为:
在密码学中,椭圆曲线的基本性质如下:
第一点比较容易了解,但是第二点比较困惑,因为满足上述的公式的整数实在是太少了,例如, , 这就不是整数 ,难道在椭圆曲线上这个点就不能用?p又是什么? 为什么会有p? p为什么是素数?
模运算大家都不陌生, 在很多的语言中模运算为, 以Python 为例:
但是我们了解的模运算大部分就到此为止了,我们只是在hash 表中,或者是判断奇偶数的时候会使用模运算。但是模运算远远不止这些:
以下的定义来自于百度百科,也是来自于小学二年级的课本:
给定一个正整数 , 任意一个正整数 ,使得 , 其中: 是整数, , k为除数, r为商
模运算支持四则运算以及乘方,开方,逆元等运算,运算规则具体参见 百度百科模运算 。乘方,开方运算以及逆元运算我们需要提及一下,后面的运算中我们会使用这几种运算。
根据模运算的规则:
推广到乘方运算:
模运算的开方,并非直接求救,而是来自于开方的本质,开方是什么?
开方的本质是乘方的逆运算。
在模运算上:
假设我们y=5, p=11, 求x: 5 %11 = 5, 这个很难求,我们可以用穷举法得出答案:7。
在模运算中定义加法逆元为:
乘法逆元为:
逆元乘法以及加法的在公式上比较容易理解,但是在具体数字上,跟我们的理解还是大相径庭, 下面是p=8的加法逆元与乘法逆
逆元有什么用呢?其实逆元是用于除法运算的。小学的时候老师都会教:除于一个分数就等于乘以该分数的倒数(分数的倒数就是该分数的乘法逆元)。所以要想除于某个数,可以乘以该数的逆元。
在 数学 中, 有限域 (英语: finite field )或 伽罗瓦域 (英语: Galois field ,为纪念 埃瓦里斯特·伽罗瓦 命名)是包含有限个 元素 的 域 。与其他域一样,有限域是进行加减乘除运算都有定义并且满足特定规则的 集合 。有限域最常见的例子是当 p 为素数时,整数对 p 取模 。
有限域中元素的个数称为有限域的 阶 。每个有限域的阶必为素数的幂,即有限域的阶可表示为pⁿ(p是素数、n是正整数),该有限域通常称为Galois域(Galois Fields),记为GF(pⁿ)。
我们在上述定义中用到了:素数p,GF(pⁿ) 的阶n。 这两个也是在常用的密码学中都会定义的。例如对于secp256k1来说:
上面说的还是太抽象?我们举个例子来说明:首先定义一个素数p, 例如,我们定义素数为7, n=1, 则一个有限域为:
我们需要回答为什么是素数的问题。 我们不使用数学证明的形式完成, 而是通过一个小例子说明为什么是素数。
我们知道,有限域的所有元素(0除外)都存在加法逆元与乘法逆元,我们以p=7与p=8来看二者的逆元:
当p=7时:
当p=8时:
我们发现当p为非素数时, 有限域中很多元素都不存在逆元。
扩展欧几里得算法
在密码学中,有限域到底起到什么作用呢?
有限域是密码学的运算域,所有的密码学中的运算都在有限域中完成。例如在EC中的私钥:
在上节我们提到椭圆曲线在密码学中的有三个要素,其中要素2为:横坐标与纵坐标都是整数。 这一点可以理解为: 横坐标与纵坐标都在有限域中。 Mordell证明了整体域上的椭圆曲线是有限生成交换群 。 具体的证明我们没有必要搞懂,但是我们需要理解其含义。
首先我们排除误解, 在很多文献中的椭圆曲线的 ADD 并不是实数域上的Add, 而是在有限域上的Add。 如下图所示:
椭圆曲线的两个点 , ,P,Q不为加法逆元, 过这两个点做直线, 与椭圆曲线相较于 点。 根据几何意义, 有如下公式:
如果 , 由于P,Q不为加法逆元,也就是两点相同, 两点相同时,上述公式不能计算, 我们约定为过P点做切线,斜率变为:
在有限域上,上述几何意义的算式依然成立,不过要少做变化:
我们将斜率也做一下区分:
做了这个之后, 穷举所有点之后, 我们便得到了有限域上的椭圆曲线。让我们来看一下有限域上的椭圆曲线是什么样子(平行于y轴的范围怎么处理?记得之前处理过但是总是找不到原来的处理方式):
有几个规律我们需要点出:
上图的随机性是来自于模运算,几乎所有的加密的随机性都来自于模运算。
在密码学中,椭圆曲线的使用有如下约定:
相信上述的约定已经回答了大多数人的困惑:椭圆曲线公钥与私钥的与椭圆曲线的关系。
根据上述公式, , 是否在工程上可以快速计算(ssh -genkey的效率)?
看到这个公式,相信就会有很多人知道算法的复杂度:o(logn)
在上述公式中,P可以公开, 而s需要保密, 一个问题随之而来, P公开之后,s不怕被泄露吗?
由于G是公开的, 我们是不是科技计算出G的逆元, 然后计算 呢? 很遗憾,目前没有很好的算法计算 。
介绍完椭圆曲线,我们看一下 《Schnorr签名介绍》
Python为什么x=10,y=10,e=10呢?其实这个是10分简单的,这个呢其实是高二的一个解方程的问题,所以呢我们要看一下xyz的等量关系,也就是x-y+z=10,那么我们就可以直接根据这个等量关系是来直接列出方程,就求出pyto=x=y=z=10了,所以说x=10,y=10=10。