本文主要是介绍零知识证明-椭圆曲线(四），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
零知识证明(Zero—Knowledge Proof)，是指一种密码学工具，允许互不信任的通信双方之间证明某个命题的有效性，同时不泄露任何额外信息
上章介绍了基础数字知识，这章主要讲 椭圆曲线 方程
2：椭圆曲线方程
y2+axy+by=x3+cx2+dx+e
式中，a、b、c、d、e均为实数，x和y在实数集上取值。
在加密领域一般采用如下简化后的数学形式：
有限域椭圆曲线
y2= x3+ax+b mod p (p为素数) 方程1
其中对于 a,b 两个参数有一个判定式，其值不得为零
选择两个满足下列约束条件的小于p的非负整数a、b
Δ=4a3+27b2≠ 0
假设𝑟1,𝑟2,𝑟3是方程的三个根，则((𝑟1−𝑟2)(𝑟1−𝑟3)(𝑟2−𝑟3))2=−(4a3+27b2)。若要求方程1无重根，即𝑟1,𝑟2,𝑟3互不相同，有((𝑟1−𝑟2)(𝑟1−𝑟3)(𝑟2−𝑟3))2≠0,即4a3+27b2≠0
比特币Bitcoin使用了 secp256k1这条特殊的椭圆曲线：y2 = x3+7
限场模量
在的情况下secp256k1，该字段是整数模的有限域p，其中
p = 2256 - 232 - 977
29+28+27+26+24+1 = 977
这里选择p相对接近2 256。它不是小于2 256的最大素数; p和2 256之间有很多素数。其他因素也同样影响着选择p。请注意，我们不是在整数mod p本身工作，而是在一个阿贝尔组中，其加法法则由整数mod p上的椭圆曲线定义
2256 = 10进制
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936
x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
assert((yy - xx*x - 7) % p == 0)
随便画的曲线，大概描述是这样(画的直点，歪点不要太在意)
从 A 点开始：
A dot B = -C（从 A 点至 B 点画一条直线，与曲线相交于 -C 点）
-C 点经过 X 轴反射到曲线上的 C 点
A dot C = -D (从 A 点至 C 点画一条直线，与曲线相交于 -D 点）
-D 点经过 X 轴反射到曲线上的 D 点
A dot D = -E (在 A 点至 D 点画一条直线，与曲线相交于 -E 点）
-E 点经过 X 轴反射到曲线上的 E 点
因为如果你知道起点（A）在哪里，以及到达终点（E）需要经历多少次跳跃，很容易就能找到终点。但是，如果你只知道起点 A 和终点 E 在哪里，几乎不可能知道中间经历了几次跳跃。 公钥：起点 A 、终点 E 私钥：从 A 点至 E 点需要经历几次跳跃
相关公式如下： 有限域GF§上的椭圆曲线y² = x³ + ax + b，若P(Xp, Yp), Q(Xq, Yq)，且P≠-Q，则R(Xr,Yr) = P+Q 由如下规则确定：
公式(1)
P+0 或者 Q=0 ：因为定义0为无穷远处，不能基于无穷远处划线。但是因为定义了0为单位元，所以 P+0=P 以及 0+Q=Q。
P = -Q ：因为两个点是对称的，所以基于这两个点划的线垂直于x轴，不再相交于其他点。P+Q = -Q+Q = 0。
P = Q ：如果P和Q是同一个点的话， 那存在多条线穿过这“两个”点。如果把Q看作是无限接近P的过程，可以看出，穿过P和Q的是椭圆曲线在P点的切线。如果切线和椭圆曲线相交的点为R，则 P+P+R = 0，P++ = 2P = -R
在选择椭圆曲线时，密码学家会考虑曲线的具体参数，如曲线的阶（n）、基点（G）、以及相关的数学难题的难度等。这些参数的选择直接影响到算法的安全性。因此，密码学家会通过严格的数学分析和安全审计来证明这些曲线的安全性，确保在实际应用中能够提供足够的安全保障；
为了确保加密通信的安全性，应该选择经过密码学家证明具备安全性的椭圆曲线方程
模运算法则
除法运算
(a/b)%m = ?
设定 (a/b)%m = x %m 变成 求 x 的值
(a/b)%m = x %m <=> a %m = (b * x) %m
负数 -a %m = (-a+km) %m 加k倍m 使 -a+km 值为正数
eg: 求 1/3 mod23 = ?
假如 1/3 mod 23 = x mod 23 成立
那么 1 mod 23 = 3 x mod 23 ## numa = 1 m=23,b= 3 ,xmax for循环的最大数
穷求 x = 1 到 1000 ，先设定个范围
3 * x mod 23 = 1
x=8
求 -1/3 mod 23 = ?
假如 -1/3 mod 23 = x mod 23 成立
1 mod 23 = -3 * x mod23
1mod 23 = -3 mod23 * x mod23
1 mod23 = 20 mod 23 * x mod 23
1 mod 23 = 20 * x mod23
x= 15
上代码
package mainimport "fmt"func main() {// a/b mod m 假如 a/b mod m = x mod m //x 为a/b mod m 的结果// a mod m = b x mod m//x 取一个最大范围，穷举 算出最小值numa ,m,b,xmax := 0,0,0,0for ;; {fmt.Printf("please input a,mod,b ,xmax：")if _,err := fmt.Scan(&numa ,&m,&b,&xmax);err !=nil{fmt.Printf("input error")break}if m <=0{fmt.Printf("input error2")break}///处理负数// a mod m = -b * x mod m// a mod m = (-b+m) mod m * x mod m // -b+m 加到为正数为止可以加n个mif numa < 0 || b < 0{flag := 0for ;; {if numa < 0 {numa += m}else{flag |= 1}if b < 0 {b += m}else{flag |= 2}if flag == 3 {fmt.Printf("new a=%v new b=%v \n",numa,b)break}}}/bf := falsefor i:=1;i<xmax;i++{if b*i %m == numa {bf = truefmt.Printf("x=%v \n",i)break}}if !bf{fmt.Printf("[not found]x=%v",-1)}}
}
求模代码
package mainimport ("fmt"//"strconv"
)func main() {valuea ,primenum := 0,0//fmt.Printf("prime number:%v \n",primenum)for ;; {fmt.Printf("please input value and prime：")if _,err := fmt.Scan(&valuea,&primenum);err !=nil{fmt.Printf("input error")break}m := valuea%primenumif m < 0 {m += primenum}fmt.Printf("%v mod %v =%v(%v) \n",valuea,primenum,valuea%primenum,m)}fmt.Printf("ready exit \n")}
除法运算
(a/b)%m = ?
设定 (a/b)%m = x %m 变成 求 x 的值
(a/b)%m = x %m <=> a %m = (b * x) %m
负数 -a %m = (-a+km) %m 加k倍m 使 -a+km 值为正数
椭圆曲线：y2 = x3+ x + 1 mod 23 //简单点 a=1 b=1
有点集 （0,1） （0,22）
（1,17）（1,16）
(3,10)(3,13)
(4,0) 这个说明下 43 +4+1 = 69 %23 = 0 所以 y = 0 （4,23）=（4,0）//自身对称 没有(4,23)
(5,4) (5,19)
点 相对与 y = 23/2 这条直线 对称
这里 设定为 mod 23 G点 (0,1)
2G = G+G P=G Q=G (6,19)
3G = G+2G (3,13)
4G= 2G+2G 或 G+3G (13,16)
6G= 3G+3G (7,11)
上图的4G 参数有问题，这里重写了
再上个6G的
椭圆曲线加解密算法原理
建立基于椭圆曲线的加密机制，需要找到类似RSA质因子分解或其他求离散对数这样的难题。而椭圆曲线上的已知G和xG求x，是非常困难的，此即为椭圆曲线上的的离散对数问题。此处x即为私钥，xG即为公钥。
椭圆曲线加密算法原理如下：
椭圆曲线公钥密码的关键和难点是快速计算椭圆曲线的阶(有理点的个数),椭圆曲线的阶在很大程度上决定了其
安全性。计算椭圆曲线的阶的算法主要有SCHOOF算法、SEA算法、Satoh算法和AGM算法
参考 https://github.com/ethereum/go-ethereum/wiki/Building-Ethereum
type CurveParams struct {
P *big.Int //% p中的p
N *big.Int //基点的阶，如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O∞，则将n称为P的阶
B *big.Int //曲线方程中常数b，如y² = x³ - 3x + b
Gx, Gy *big.Int //基点G(x,y)
BitSize int //基础字段的大小
Name string //椭圆曲线的名称
}
func initP224() {// See FIPS 186-3, section D.2.2p224.CurveParams = &CurveParams{Name: "P-224"}p224.P, _ = new(big.Int).SetString("26959946667150639794667015087019630673557916260026308143510066298881", 10)p224.N, _ = new(big.Int).SetString("26959946667150639794667015087019625940457807714424391721682722368061", 10)p224.B, _ = new(big.Int).SetString("b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", 16)p224.Gx, _ = new(big.Int).SetString("b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", 16)p224.Gy, _ = new(big.Int).SetString("bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34", 16)p224.BitSize = 224p224FromBig(&p224.gx, p224.Gx)p224FromBig(&p224.gy, p224.Gy)p224FromBig(&p224.b, p224.B)
}func initP384() {// See FIPS 186-3, section D.2.4p384 = &CurveParams{Name: "P-384"}p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)p384.BitSize = 384
}func initP521() {// See FIPS 186-3, section D.2.5p521 = &CurveParams{Name: "P-521"}p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)p521.BitSize = 521
}
设私钥、公钥分别为k、K，即K = kG，其中G为G点。基点G的阶数n(即nG = O)
选择一个私有密钥k（k<n）n 是一轮
公钥加密： 选择随机数r，将消息M生成密文C，该密文是一个点对 C1,C2
C1=M+rK C2 = rG
私钥解密：C1-kC2 = M + rK - k(rG) = M + r(kG) - k(rG) = M 其中k、K分别为私钥、公钥。
椭圆曲线签名算法原理
椭圆曲线签名算法，即ECDSA。
设私钥、公钥分别为k、K，即K = kG，其中G为G点。
私钥签名：
1、选择随机数r，计算点rG(x, y)。
2、根据随机数r、消息M的哈希h、私钥k，计算s = (h + kx)/r。
3、将消息M、和签名{rG, s}发给接收方。
公钥验证签名：
1、接收方收到消息M、以及签名{rG=(x,y), s}。
2、根据消息求哈希h。
3、使用发送方公钥K计算：hG/s + xK/s，并与rG比较，如相等即验签成功。
原理如下：
hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s
= r(h+xk)G / (h+kx) = rG
eg:加解密
//a,b,p,x
椭圆方程E = y2 = x3+x+1 mod 23
a=1 b=1 p=23
选择 G点 (3,10)
0G（0） 1G(3,10) 2G（7,12） 3G（19,5） 4G(17,3) 5G(9,16) 6G(12,4) 7G(11,3) 8G(13,16)
9G(0,1) 10G(6,4) 11G(18,20) 12G(5,4) 13G(1,7) 14G(4,0) 15G(1,16) 16G(5,19) 17G(18,3)
18G(6,19) 19G(0,22) 20G(13,7) 21G(11,20) 22G(12,19) 23G(9,7) 24G(17,20) 25G(19,18) 26G(7,11) 27(3,13) 后面开始循环了
28G(0)，29G = 1G（3,10）30G（7,12）31G（19,5） 32G（17,3）
网上抄的别人的图 来源 https://www.cnblogs.com/Yumeka/p/7392505.html
计算可得27G=-G=(3,13) 所以28G=O ∞ G的阶为28 这些点做成了一个循环阿贝尔群，其中生成元为G，阶数为29
G阶数n 这里 29
私钥 k = 2 < n 那么 K=2G= (6,19) //为了好手算，选择小的数
加密过程
把 E,K,G （公钥基本信息） 加密 明文
将明文 编码到曲线上的一点M（编码方法略）,产生一个随机整数 r<n
这里假如r=4,加密的信息19（x坐标） 得到一个点(19，5) 或 （19,18）
这里用 M (19,5)
C1= M+rK 查表知 (19，5) 3G
= 3G+4(2G) = 11G (18,20)
或 用公式算也可以 (19，5) +(13,16) = (18,20)
C2 = rG = 4G（17,3）
得到C1 C2 点对后
解密 用到私钥
因为 K = kG
理论 C1-kC2 = M+r(kG)-k(rG) = M
C1-kC2 = (18,20)- 2(4G）=(18,20)-8G(13,16) 可以直接查表 (18,20)11G +(13,7) 20G =31G（19,5）
=(18,20)+(13,-16) = (18,20)+(13,7) = （19,5） == M
椭圆曲线的 怎么计算 阶 子群阶，明文嵌入曲线点 放到下章补充
如果觉得有用，麻烦点个赞，加个收藏
这篇关于零知识证明-椭圆曲线(四）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
