Skip to content

Latest commit

 

History

History
352 lines (248 loc) · 17.3 KB

readme.md

File metadata and controls

352 lines (248 loc) · 17.3 KB
Raw
title tags
40. 常用椭圆曲线
zk
abstract algebra
elliptic curve
group theory
finite field
pairing

WTF zk 教程第 40 讲：常用椭圆曲线

这一讲，我们将介绍以太坊上常用的三条椭圆曲线：secp256k1，bn128，和 bls12_381，其中 secp256k1 也被比特币采用。

1. secp256k1

我们在介绍椭圆曲线离散对数问题（ECDLP）的时候介绍了 secp256k1 曲线，这里再简单介绍一遍。secp256k1 由SECG（Standards for Efficient Cryptography Group）标准化，也是它名字的由来。

secp256k1 的椭圆曲线方程为：

$$ y^2 = x^3 + 7 \mod p $$

它定义在一个特定的有限域 $\mathbb{F}_p$ 上，其中 $p$ 是一个非常大的质数： $p = 2^{256} - 2^{32} - 977$。

secp256k1 椭圆曲线上的点群形成了一个循环群，阶为 115792089237316195423570985008687907852837564279074904382605163141518161494337，包含的点非常多，保障了算法的安全性。点 $G(G_x, G_y)$ 是 secp256k1 的一个基点/生成元，可以生成所有点，其中：

Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424

secp256k1 被用于比特币和以太坊的公钥生成和数字签名，下面我们利用 py_ecc 库给出代码示例。

1.1 公钥生成

使用 secp256k1 进行公钥生成非常简单，我们先随机生成一个私钥 $x$，然后计算公钥 $y = xG$，其中点 $G$ 是椭圆曲线的基点：

# 椭圆曲线 secp256k1 示例
# 利用标量乘法，从私钥生成公钥
from py_ecc.secp256k1 import secp256k1
import os 

def generate_public_key(private_key):
    """
    使用secp256k1椭圆曲线，根据给定的私钥生成公钥。
    
    参数:
    private_key (int): 私钥，一个大整数。
    
    返回:
    (int, int): 公钥，椭圆曲线上的点。
    """
    # secp256k1的基点
    G = secp256k1.G
    
    # 计算公钥
    public_key = secp256k1.multiply(G, private_key)
    
    return public_key

# 示例：使用一个随机的私钥
private_key = int(os.urandom(32).hex(), 16)

# 生成公钥
public_key = generate_public_key(private_key)

# 打印结果
print(f"Private Key: {private_key}")
print(f"Public Key: {public_key}")

# 示例输出
# Private Key: 40871478222817722377012551921323657605236631423958081783403470740144884256441
# Public Key: (18814187692496112820586797121940816605467606938301853840004393937958984136992, 72833048843328294920821861725991661253504985018641366317346599320677055943891)

1.2 数字签名

我们可以利用 py_ecc.secp256k1 中的 ecdsa_raw_sign 和 ecdsa_raw_recover 来实现椭圆曲线数字签名算法（ECDSA）。我们之后会更详细的介绍 ECDSA 算法。

# secp256k1 数字签名
from py_ecc.secp256k1 import secp256k1
import os
import hashlib

def sign_message(private_key, message):
    """
    使用私钥对消息进行签名。
    """
    message_hash = hashlib.sha256(message.encode()).digest()
    private_key_bytes = private_key.to_bytes(32, "big")
    signature = secp256k1.ecdsa_raw_sign(message_hash, private_key_bytes)
    return signature

def verify_signature(message, signature, public_key):
    """
    使用公钥验证消息的签名。
    """
    message_hash = hashlib.sha256(message.encode()).digest()
    recovered_public_key = secp256k1.ecdsa_raw_recover(message_hash, signature)
    return recovered_public_key == public_key

# 示例使用
private_key = int.from_bytes(os.urandom(32), 'big')
public_key = secp256k1.multiply(secp256k1.G, private_key) # 计算公钥

print(f"Private Key: {private_key}")
print(f"Public Key: {public_key}")

message = "Hello, blockchain world!"
signature = sign_message(private_key, message) # 签名消息
is_valid = verify_signature(message, signature, public_key) # 尝试从签名恢复公钥

# 比较原始公钥和恢复的公钥
print(f"Signature valid: {is_valid}")

# 示例输出
# Private Key: 100160191408028635805410835424804882729758587641862022398559246101084514055515
# Public Key: (94753041202778772959486517607721465828067708966050249355074253521404789962176, 108824044826657285606250531715029407748756362423778933890891533480553307901806)
# Signature valid: True

2. bn128

bn_128曲线，全称 Barreto-Naehrig 128位曲线，是一种在密码学中广泛使用的配对友好椭圆曲线。它的嵌入度为 12，兼顾加密安全与配对效率，常被用于零知识证明算法中。

bn_128 的椭圆曲线 $E(\mathbb{F}_p)$ 方程为：

$$ y^2 = x^3 + 3 \mod p $$

它定义在一个特定的有限域 $\mathbb{F}_p$ 上，其中 p 是一个大素数。

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

bn_128 椭圆曲线上的点群形成了一个循环群，阶为 21888242871839275222246405745257275088548364400416034343698204186575808495617，包含的点非常多，保障了算法的安全性。点 $G_1(1, 2)$ 是 bn_128 的一个基点/生成元，可以生成所有点。

在构造 Ate 配对时，配对映射 $\hat{\tau}: C_2 \times C_1 \to G_T$，其中 $C_1 = E(\mathbb{F}p), C_2 = E(\mathbb{F}{p^2}), G_T = \mathbb{F}{p^{12}}$。$C_2$ 是为了支持配对操作特别定义在扩域 $\mathbb{F}{p^2}$ 上的曲线，每个点的坐标都由复数表示，基点 $G_2$ 形式为 $(a+bi, c+di)$，其中：

a = 10857046999023057135944570762232829481370756359578518086990519993285655852781
b = 11559732032986387107991004021392285783925812861821192530917403151452391805634
c = 8495653923123431417604973247489272438418190587263600148770280649306958101930
d = 4082367875863433681332203403145435568316851327593401208105741076214120093531

2.1 公钥生成

使用 bn128 曲线生成公钥的过程和 secp256k1 类似。

# bn128 生成公钥
from py_ecc.bn128 import bn128_curve
import os

def generate_bn128_public_key(private_key):
    """
    使用bn_128曲线和给定的私钥生成公钥。
    
    参数:
    private_key (int): 私钥，一个大整数。
    
    返回:
    (int, int): 公钥，bn_128曲线上的点。
    """
    # BN128_G1是bn_128曲线的基点
    public_key = bn128_curve.multiply(bn128_curve.G1, private_key)
    return public_key

# 示例：使用一个随机的私钥
private_key = int.from_bytes(os.urandom(32), 'big')

# 生成公钥
public_key = generate_bn128_public_key(private_key)

# 打印结果
print(f"Private Key: {private_key}")
print(f"Public Key: {public_key}")

# 示例输出
# Private Key: 98359178994781335595533648854802231427270090895769248482397491373685555850978
# Public Key: (3661113004864472419130070831996330893639690693841499262022550248113059694488, 16647856845341024716707355890250833951196099189567973816478113518219363325204)

2.2 双线性配对

我们在第38讲中介绍了如何用 bn128 实现配对，要注意一点是配对是在 $C_2 \times C_1 \to G_T$ 进行的，因此第一个点是 $G_2$ 的倍点，第二个点是 $G_1$ 的倍点，不然会报错。

# bn128 双线性配对
from py_ecc.bn128 import G1, G2, pairing, add, multiply, eq

print(G1)
print(G2)
print("\n")

a = 69
b = 420
c = a * b
A = multiply(G2, a)
B = multiply(G1, b)
pair_A_B = pairing(A, B)
print("Pairing of points A and B: ",pair_A_B)
print("\n")

C = multiply(G2, c)
pair_G2_C = pairing(C, G1)
print("Pairing of points G2 and C: ",pair_G2_C)
print("\n")

print("Is pair_A_B == pair_G2_C? ", pair_A_B == pair_G2_C)

# 输出
# (1, 2)
# ((10857046999023057135944570762232829481370756359578518086990519993285655852781, 11559732032986387107991004021392285783925812861821192530917403151452391805634), (8495653923123431417604973247489272438418190587263600148770280649306958101930, 4082367875863433681332203403145435568316851327593401208105741076214120093531))


# Pairing of points A and B:  (19735667940922659777402175920395455799125563888708961631093487249968872129612, 1976543863057094994989237517814173599120655827589866703826517845909315612857, 19686523416572620016989349096902944934819162198495809257491045534399198954254, 5826646852844954420149583478015267673527445979905768896060072350584178989060, 2064185964405234542610947637037132798744921024553195185441592358018988389207, 8341934863294343910133492936755210611939463215146220944606211376003151106114, 12807669762027938768857302676393862225355612177677457846751491105239425227277, 5741126950795831539169012545403256931813076395529913201048083937620822856065, 11074901068523180915867722424807487877141140784438044188857570704539589417315, 19327019285776193278582429402961044775129507055467003359023290900912857119476, 17306986078986604236447922180440988200852103029519452658980599808670992125088, 13188937242065601189938233945175869194113210620973903647453917247887073581439)


# Pairing of points G2 and C:  (19735667940922659777402175920395455799125563888708961631093487249968872129612, 1976543863057094994989237517814173599120655827589866703826517845909315612857, 19686523416572620016989349096902944934819162198495809257491045534399198954254, 5826646852844954420149583478015267673527445979905768896060072350584178989060, 2064185964405234542610947637037132798744921024553195185441592358018988389207, 8341934863294343910133492936755210611939463215146220944606211376003151106114, 12807669762027938768857302676393862225355612177677457846751491105239425227277, 5741126950795831539169012545403256931813076395529913201048083937620822856065, 11074901068523180915867722424807487877141140784438044188857570704539589417315, 19327019285776193278582429402961044775129507055467003359023290900912857119476, 17306986078986604236447922180440988200852103029519452658980599808670992125088, 13188937242065601189938233945175869194113210620973903647453917247887073581439)


# Is pair_A_B == pair_G2_C?  True

3. bls12_381

bls12_381 属于 Barreto-Lynn-Scott (BLS) 曲线族的一员，是一种配对友好的椭圆曲线。它的嵌入度为 12，配对高效且安全，被以太坊广泛采用，比如POS的节点签名。

bls12_381 的椭圆曲线 $E(\mathbb{F}_p)$ 方程为：

$$ y^2 = x^3 + 4 \mod p $$

它定义在一个特定的有限域 $\mathbb{F}_p$ 上，其中 p 是一个大素数。

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

bls12_381 椭圆曲线上的点群形成了一个循环群，阶为 52435875175126190479447740508185965837690552500527637822603658699938581184513，包含的点非常多，保障了算法的安全性。点 $G_1(x_1, x_2)$ 是 bls12_381 的一个基点/生成元，可以生成所有点。

其中：

x1 = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
x2 = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569

在构造 Ate 配对时，配对映射 $\hat{\tau}: C_2 \times C_1 \to G_T$，其中 $C_1 = E(\mathbb{F}p), C_2 = E(\mathbb{F}{p^2}), G_T = \mathbb{F}{p^{12}}$。$C_2$ 是为了支持配对操作特别定义在扩域 $\mathbb{F}{p^2}$ 上的曲线，每个点的坐标都由复数表示，基点 $G_2$ 形式为 $(a+bi, c+di)$，其中：

a = 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
b = 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758
c = 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905
d = 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582

3.1 公钥生成

使用 bls12_381 曲线生成公钥的过程和 bn128 类似。

# bls12_381 生成公钥
from py_ecc.bls12_381 import bls12_381_curve
import os

def generate_bn12_381_public_key(private_key):
    """
    使用bn_128曲线和给定的私钥生成公钥。
    
    参数:
    private_key (int): 私钥，一个大整数。
    
    返回:
    (int, int): 公钥，bn_128曲线上的点。
    """
    # BN128_G1是bn_128曲线的基点
    public_key = bls12_381_curve.multiply(bls12_381_curve.G1, private_key)
    return public_key

# 示例：使用一个随机的私钥
private_key = int.from_bytes(os.urandom(32), 'big')

# 生成公钥
public_key = generate_bn12_381_public_key(private_key)

# 打印结果
print(f"Private Key: {private_key}")
print(f"Public Key: {public_key}")

# 示例输出
# Private Key: 56832202591799069674370871859151631253659339730808373097707650526306669655451
# Public Key: (2672943242084458229690202553507767493858110823696659228443909079159465919837314837610879707240986236828893077890320, 1516123302208562362629191397278119903430202415903098718379575356530260147717671392463098304288800407793122740332702)

3.2 双线性配对

bls12_381 的配对实现和 bn128 类似，同样要注意一点是配对是在 $C_2 \times C_1 \to G_T$ 进行的，因此第一个点是 $G_2$ 的倍点，第二个点是 $G_1$ 的倍点，不然会报错。

# bls12_381 双线性配对
from py_ecc.bls12_381 import G1, G2, pairing, add, multiply, eq

print(G1)
print(G2)
print("\n")

a = 69
b = 420
c = a * b
A = multiply(G2, a)
B = multiply(G1, b)
pair_A_B = pairing(A, B)
print("Pairing of points A and B: ",pair_A_B)
print("\n")

C = multiply(G2, c)
pair_G2_C = pairing(C, G1)
print("Pairing of points G2 and C: ",pair_G2_C)
print("\n")

print("Is pair_A_B == pair_G2_C? ", pair_A_B == pair_G2_C)

# 输出
# (3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507, 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569)
# ((352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160, 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758), (1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905, 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582))


# Pairing of points A and B:  (559875907953044229256999964908655596470329614681804657067074917348889299656574983763205735263906508658423626306192, 3251387332700024622230711712327939415422447046055926038630362608193945095062996827680637432749053965474170688846803, 1858978301495685148589092187900391308425211794249943939941796868269658435530364461212323465553496690057506398710958, 2821404563389658506867792213698964607416184520400354580766817454079710851304957653749944402097411780097914172680501, 3371394908151563362208243796489511825354821020573987752522791881868987441291678825694507113985550194783443672326288, 2297984649797609740520111469542560058998637859756636710986648527547199594538622957148043186058263511759636104385884, 3480762570907741510541555641785158658308333937734941283300383364697580261225975907843679022209374260264933745191828, 3240728397255321363427476858948130370605249287048803384220203355573990507150386888156524321441752887099266166133108, 2376364160413810038009747479244195484637259359228646277111417852748902100064937901534264975269224589631629799823776, 505616797063036550970852124247959597244795697098930755073121309023649013438395471915981324345265013483679297150493, 283646809217572597374969288842854659843926065997224794730305413934017744924705963601539908633134851567640611976585, 208748941951544416005406635656082534817221797560780462964136211816030039051269393961107822344678318294491041226308)


# Pairing of points G2 and C:  (559875907953044229256999964908655596470329614681804657067074917348889299656574983763205735263906508658423626306192, 3251387332700024622230711712327939415422447046055926038630362608193945095062996827680637432749053965474170688846803, 1858978301495685148589092187900391308425211794249943939941796868269658435530364461212323465553496690057506398710958, 2821404563389658506867792213698964607416184520400354580766817454079710851304957653749944402097411780097914172680501, 3371394908151563362208243796489511825354821020573987752522791881868987441291678825694507113985550194783443672326288, 2297984649797609740520111469542560058998637859756636710986648527547199594538622957148043186058263511759636104385884, 3480762570907741510541555641785158658308333937734941283300383364697580261225975907843679022209374260264933745191828, 3240728397255321363427476858948130370605249287048803384220203355573990507150386888156524321441752887099266166133108, 2376364160413810038009747479244195484637259359228646277111417852748902100064937901534264975269224589631629799823776, 505616797063036550970852124247959597244795697098930755073121309023649013438395471915981324345265013483679297150493, 283646809217572597374969288842854659843926065997224794730305413934017744924705963601539908633134851567640611976585, 208748941951544416005406635656082534817221797560780462964136211816030039051269393961107822344678318294491041226308)


# Is pair_A_B == pair_G2_C?  True

4. 总结

这一讲，我们介绍了比特币和以太坊上的常用椭圆曲线：secp256k1，bn128，和bls12_381，并基于ecc_py写了简单示例。secp256k1主要用于比特币和以太坊上的公钥生成和数字签名，而bn128和bls12_381是配对友好的曲线，可以被用于签名和零知识证明算法。