零知识证明-公钥分发方案DH(（六）

前言
椭圆曲线配对，是各种加密构造方法(包括 确定性阀值签名、zk-SNARKs以及相似的零知识证明)的关键元素之一。椭圆曲线配对(也叫“双线性映射”)有了30年的应用历史，然而最近这些年才把它应用在密码学领域。配对带来了一种“加密乘法”的形式，这很大的拓展了椭圆曲线协议的应用范围。本文的目的是详细介绍椭圆曲线配对，并大致解释它的内部原理
先了解DH 协议
Diffie-Hellman协议
简称DH，是一种公钥分发方案，该协议允许双方通过交换窃听者可见的信息来建立共享秘密。

1:DH
Diffie-Hellman 算法是第一个公开密钥算法，早在 1976 年就发明了。其安全性源于在有限域上计算离散对数比计算指数更为困难。Diffie-Hellman 算法能够用于密钥分配 (A 和 B 能用它产生秘密密钥)，但是它不能用于加密或解密消息。

数学原理很简单。首先，A 和 B 协商一个大的素数n 和g ， g是模 n 的本原元。这两个整数不必是秘密的，故 A 和 B 可以通过即使是不安全的途径协商它们。它们可在一组用户中公用。

原根(也是循环群的生成元)(primitive root)的概念和性质
如果 a与 m互质，那么我们把满足 a^k ≡ 1 mod m 的最小正整数 k 称为 a的模 m 的阶
由欧拉定理 a^Φ(m) ≡ 1 mod m, a的模 m的阶一定是Φ(m)的因数
阶刚好等于Φ(m)的余数（同余类） 称为 模m的原根（注意1只是模2的原根，其他不是）
给定一个正整数n，如果存在一个正整数k，使得k的某个幂对n取模的结果依次不为0，并且最终结果循环出现所有取值为1,2，…，n-1，则称k为模n的原根。

n=3 简化剩余系（1,2）Φ(n) =2 阶为2 ，2 是模3的原根 k=2
2⁰ %3 =1 2¹ %3 =2 2² %3 =1 2³ %3 =2 2⁴ %3 =1 2⁵ %3 =2
n=5 简化剩余系{1,2,3,4} Φ(n) =2 阶为4
2⁰ %5= 1 -> 简写 (0,1) (1,2) (2,4) (3,3) (4,1) (5,2) (6,4)(7,3) 重复 1,2,4,3 这样重复
3⁰%5=1 -> 简写 (0,1) (1,3) (2,4) (3,2) (4,1) (5,3) (6,4)(7,2) 重复 1,3,4,2 这样重复

欧拉函数 对于任何一个正整数 n，定义 Φ(n) 为不超过 n 的与 n互质的正整数个数
模m原根存在的条件是 m=1,2,4,p^a,2p^a,其中 p为奇素数， a >=1
S是模 n的简化剩余系，是指 S是由 φ(n)个数组成的集合,其中集合中的数都与 n互质且两两模 n不同余(就是余数不重复)
eg: m=2 简化剩余系（1） Φ(n) =1 阶为1 ，1 是模2的原根
m=3 简化剩余系（1,2）Φ(n) =2 阶为2 ，2 是模3的原根 2² %3 =1
m=4 简化剩余系（1,3）Φ(n) =2 阶为2，3 是模4的原根 3² %4 =1
m=6 简化剩余系（1,5）Φ(n) =2 阶为2，5 是模6的原根 5² %6 =1
m=5 简化剩余系{1,2,3,4} Φ(n) =2 阶为4, 2⁴ % 5 = 1 3⁴ %5 =1 4²%5=1
阶为4 ，所以 4不是原根，2 ，3 都是原根
总结 可逆元^Φ(n) mod m == 1 , 可逆元 是 模 m 的原根（注意1只是模2的原根，其他不是）
协议如下：
g n 是公开的 n 为大素数 g是n的原根
A 选取一个大的随机整数ra ，并发送给 B ; X=g^ra mod n
B 选取一个大的随机整数rb，并发送给 A Y=g^rb mod n
A 计算 S=Y^ra mod n
B计算 S=X^rb mod n
S 应该等于 g^ra*rb mod n
S 作为计算出的共享密钥，可用于对称加密
即使线路上的窃听者也不可能计算出这个值，他们只知道 n,g,X,Y 除非他们计算离散对数，恢复 ra,rb，否则无济于事。因此 S 是 A 和 B 独立计算的秘密密钥。

g和n 的选取对系统的安全性有很大的影响。(n-1)/2 也应该是一个素数。最重要的是 n应该很大：因为系统的安全性取决于与 n同样长度的数的因子分解的难度。可以选择任何满足模n 的原根g ，没有理由不选择所能选择的最小g —— 通常只是个 1 位数 (实际上 g不必是素数，但它必须能产生一个大的模n 的乘法组子群)
eg: g=6 n=11 (g是n的原根) 11的原根有(2,6,7,8) 这里选择6
A 私钥ra =7 公开密钥 X= g^ra mod n = 6⁷ = 279936 %11= 8
B 私钥rrb = 12 公开密钥 Y = g^rb mod n = 6¹² = 2176782336 %11 = 3

A 计算 共享密钥 S = Y^ra mod n = 3⁷ % 11 = 2187 %11 = 9
B 计算 共享密钥 S= X^rb mod n = 8¹²%11 = 68719476736%11 = 9

g^ra*rb mod n = 6 ^7*12 = 6⁸⁴ %11 = 9 == S

package main

import (
	"fmt"
	"github.com/ethereum/go-ethereum/common/math"
	"math/big"
)

func main()  {
	valuea ,power,mod := 0,0,0
	//89 ^2011 %3127
	for ;; {

		fmt.Printf("please input value1， power and mod：")
		if _,err := fmt.Scan(&valuea,&power,&mod);err !=nil{
			fmt.Printf("input error")
			break

		}
		a := int64(valuea)
		b := int64(power)
		big1 := math.BigPow(a,b)
		m := big.NewInt(int64(mod))
	//	z := big.NewInt(0)
		big2 := m.Mod(big1,m)

		fmt.Printf("(%v ^ %v)mod %v = %v (%v)\n",valuea,power,mod,big2,big1)
	}

	fmt.Printf("ready exit \n")
}

2：三方或多方 Diffie-Hellman
以三方为例
g n 公开
1> A 私钥 选择大随机数 ra 把 X = g^ra mod n 发送给 B
2> B 私钥 选择大随机数 rb 把 Y = g^rb mod n 发送给 C
3> C 私钥 选择大随机数 rc 把 Z = g^rc mod n 发送给 A
4> A 把 Z1 = Z^ra mod n 发送给 B ,（ Z 为 C 发送给A的）
5> B 把 X1 = X^rb mod n 发送给 C （X 为 A 发送给B的）
6> C 把 Y1 = Y^rc mod n 发送给 A （Y 为 B发送给C的）
7> A 计算共享密钥 S = (Y1^)ra mod n
8> B 计算共享密钥 S = (Z1^)rb mod n
9>C 计算共享密钥 S = (x1^)rc mod n

S == g^ra*rb*rc mod n
eg: g=8 n=11 (g是n的原根) 11的原根有(2,6,7,8) 这里选择6
1> A 私钥 ra = 13 X= g^ra mod n = 8¹³ mod 11 = 549755813888 %11 = 6
2>B 私钥 rb = 16 Y= g^rb mod n = 8¹⁶ mod 11 = 281474976710656 %11 = 3
3>C 私钥 rc = 27 Z= g^rc mod n = 8²⁷ mod 11 = 2417851639229258349412352%11 = 2
4>A Z1 = Z^ra mod n = 2¹³ %11 = 8192%11 =8
5>B X1 = X^rb mod n = 6¹⁶ %11 = 2821109907456%11 = 5
6>C Y1 = Y^rc mod n = 3²⁷ %11 = 7625597484987%11 = 9

7> A S= Y1^ra mod n = 9¹³ % 11 = 2541865828329 %11 = 3 //跟B 给C的Y 相等， 因为n太小，碰撞到一起了
8> B S= Z1^rb mod n = 8¹⁶ % 11 = 281474976710656%11 = 3
8> C S= X1^rc mod n = 5²⁷ % 11 = 7450580596923828125%11 = 3

g^ra*rb*rc mod n = 8^13*16*27 % 11 = 8⁵⁶¹⁶ % 11 = 3
8⁵⁶¹⁶= 用上面的程序计算 =
(56671792158458189462788480435325250053000506492933346240406207383911706480845603129490692058630716611中间省略69124622157307694933662452678656)

DH 需要防止中间人攻击

如果觉得有用，麻烦点个赞，加个收藏