Ed25519加密算法

文章页面

现代密码学

Ed25519加密算法

Ed25519是什么东西？一种签名算法，不过比ECDSA要更快，更安全
它基于 Curve25519 曲线，并使用 EdDSA（Edwards 签名算法）结构。

用私钥签名消息
用公钥验证签名

签名流程

生成一条 32 字节的随机私钥

Hash 私钥 → 得到扩展密钥

可以自己选择一种hash，不过现代语言库都对这个算法有封装了，一般是SHA512
前 32 字节用于生成公钥(需要“剪裁 bits”)
后 32 字节作为签名时的“私有随机数种子”

部分	用途
h[0:32]	生成公钥的 “扩展私钥” a（需要剪裁 bits）
h[32:64]	签名时生成随机数 r

h[0]  & = 248   // 清除低三位
h[31] & = 127   // 清除最高位
h[31] | = 64    // 设置次高位

剪裁的作用：让 a 落在正确阶的子群里，避免弱密钥得到扩展后的私钥 a:

a = decode_le_256(h[0:32])

计算公钥
```
a = prune(h[0:32])
A = a * B   ← 椭圆曲线点乘基点
```
A 就是公钥点；最终编码成 32 字节
- a 是扩展私钥
- B 是固定基点（已写死在 Ed25519 规范中）
- “点乘”是椭圆曲线上的操作将 A（一个几百 bit 的点）编码为 32 字节: publicKey = encode(A)
签名前处理消息输入:
- seed（私钥）
- 消息 M
- 公钥 A（用于 k 的哈希）
1. 计算 r（一次性随机数）
  r = SHA512( h[32:64] || M ) r = decode_le_256(r) mod L
  L 是 Curve25519 的子群阶
  
  R点 => R = r * B
2. 计算挑战值 k
  k = SHA512( encode(R) || encode(A) || M ) k = decode_le_256(k) mod L

计算签名的 S 值

k = SHA512(R || A || message)
S = (r + k * a) mod L

(L 是椭圆曲线的阶)

输出签名
签名 = 64 字节： signature = R || S

签名校验环节

验证者有:
- 公钥 A
- 消息 M
- 签名 (R, S) 只需要验证下面等式是否成立：
```
S * B == R + H(R || A || M) * A
```

这个我是实在不能理解理论，椭圆曲线函数我是真无法消化

// ed25519_teaching.go
// Teaching implementation of Ed25519 flow (NOT for production).
// Demonstrates key expansion, clamping, scalar mul (double-and-add), signing, verification.
// Uses math/big for field arithmetic modulo p = 2^255 - 19.
// WARNING: slow and not constant time.

package main

import (
	"bytes"
	"crypto/rand"
	"crypto/sha512"
	"encoding/hex"
	"fmt"
	"math/big"
)

// Field prime p = 2^255 - 19
var p *big.Int

// Order L of base point (group order)
var L *big.Int

// curve parameter d = -121665 * inv(121666) mod p
var d *big.Int

// Base point B (will compute from y = 4/5)
var Bx, By *big.Int

func init() {
	// p = 2^255 - 19
	p = new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 255), big.NewInt(19))

	// L = 2^252 + 27742317777372353535851937790883648493 (ed25519 subgroup order)
	L = new(big.Int)
	L.SetString("723700557733226221397318656304299424085711635937990760600195093828545425057", 10) // decimal L

	// compute d = -121665 / 121666 mod p
	num := big.NewInt(-121665)
	den := big.NewInt(121666)
	denInv := new(big.Int).ModInverse(den, p)
	d = new(big.Int).Mod(new(big.Int).Mul(num, denInv), p)
	if d.Sign() < 0 {
		d.Add(d, p)
	}

	// Base point y = 4/5 mod p
	four := big.NewInt(4)
	five := big.NewInt(5)
	fiveInv := new(big.Int).ModInverse(five, p)
	y := new(big.Int).Mod(new(big.Int).Mul(four, fiveInv), p)

	// compute x = sqrt((y^2 - 1) / (d*y^2 + 1)) mod p
	// For p mod 8 = 5, use x = (u)^{(p+3)/8} with checks (per curve25519 trick)
	// u = (y^2 - 1) * inv(d*y^2 + 1)
	ysq := modMul(y, y)
	u := modSub(ysq, big.NewInt(1))
	den2 := modAdd(modMul(d, ysq), big.NewInt(1))
	den2Inv := new(big.Int).ModInverse(den2, p)
	u = modMul(u, den2Inv)

	x, ok := modSqrt(u) // choose one sqrt (there are two signs)
	if !ok {
		panic("no sqrt found for base x")
	}
	// ensure we pick the positive x per RFC (we'll accept whichever here)
	Bx = x
	By = y
}

// --- Finite field helpers modulo p ---
func modAdd(a, b *big.Int) *big.Int {
	t := new(big.Int).Add(a, b)
	return t.Mod(t, p)
}
func modSub(a, b *big.Int) *big.Int {
	t := new(big.Int).Sub(a, b)
	return t.Mod(t, p)
}
func modMul(a, b *big.Int) *big.Int {
	t := new(big.Int).Mul(a, b)
	return t.Mod(t, p)
}
func modNeg(a *big.Int) *big.Int {
	t := new(big.Int).Neg(a)
	return t.Mod(t, p)
}
func modInv(a *big.Int) *big.Int {
	return new(big.Int).ModInverse(a, p)
}
func modExp(a, e *big.Int) *big.Int {
	return new(big.Int).Exp(a, e, p)
}

// modular sqrt for p ≡ 5 (mod 8), use algorithm:
// x = a^{(p+3)/8} ; if x^2 % p == a => ok
// else x = x * 2^{(p-1)/4} mod p (times sqrt(-1) adjustment) -- use standard checks
func modSqrt(a *big.Int) (*big.Int, bool) {
	// when a == 0
	if a.Sign() == 0 {
		return big.NewInt(0), true
	}
	exp := new(big.Int).Add(p, big.NewInt(3))
	exp.Rsh(exp, 3) // (p+3)/8
	x := new(big.Int).Exp(a, exp, p)
	// check x^2 == a ?
	x2 := modMul(x, x)
	if x2.Cmp(new(big.Int).Mod(a, p)) == 0 {
		return x, true
	}
	// otherwise, x = x * 2^{(p-1)/4}
	// compute factor = 2^{(p-1)/4} mod p
	factorExp := new(big.Int).Sub(p, big.NewInt(1))
	factorExp.Rsh(factorExp, 2) // (p-1)/4
	two := big.NewInt(2)
	factor := new(big.Int).Exp(two, factorExp, p)
	x = modMul(x, factor)
	x2 = modMul(x, x)
	if x2.Cmp(new(big.Int).Mod(a, p)) == 0 {
		return x, true
	}
	return nil, false
}

// --- Point representation on twisted Edwards curve ---
// Use affine coordinates (x,y) with values mod p
type Point struct {
	x, y *big.Int
}

func NewPoint(x, y *big.Int) *Point {
	return &Point{new(big.Int).Mod(x, p), new(big.Int).Mod(y, p)}
}

// Point at infinity in Edwards affine form doesn't exist same as Weierstrass; we'll
// represent identity as (0,1) which is neutral for Edwards curves.
func Identity() *Point {
	return NewPoint(big.NewInt(0), big.NewInt(1))
}

// point addition using Twisted Edwards formula for curve x^2 + y^2 = 1 + d x^2 y^2
// https://en.wikipedia.org/wiki/Twisted_Edwards_curve
func (P *Point) Add(Q *Point) *Point {
	x1, y1 := P.x, P.y
	x2, y2 := Q.x, Q.y

	// x3 = (x1*y2 + y1*x2) / (1 + d*x1*x2*y1*y2)
	// y3 = (y1*y2 - x1*x2) / (1 - d*x1*x2*y1*y2)
	A := modMul(x1, y2)
	B := modMul(y1, x2)
	C := modMul(modMul(x1, x2), modMul(y1, y2)) // x1*x2*y1*y2
	den1 := modAdd(big.NewInt(1), modMul(d, C))
	den2 := modSub(big.NewInt(1), modMul(d, C))
	numX := modAdd(A, B)
	numY := modSub(modMul(y1, y2), modMul(x1, x2))
	x3 := modMul(numX, modInv(den1))
	y3 := modMul(numY, modInv(den2))
	return NewPoint(x3, y3)
}

func (P *Point) Double() *Point {
	// Doubling is just Add(P,P)
	return P.Add(P)
}

// scalar multiplication (naive double-and-add, left-to-right)
func (P *Point) ScalarMult(k *big.Int) *Point {
	R := Identity()
	// iterate bits from most significant to least
	for i := k.BitLen() - 1; i >= 0; i-- {
		R = R.Double()
		if k.Bit(i) == 1 {
			R = R.Add(P)
		}
	}
	return R
}

// encode point as 32-byte little-endian per RFC: encode y, and sign bit of x in high bit.
func (P *Point) Encode() []byte {
	// y as 255-bit integer little-endian, and set bit 255 to LSB of x
	yBytes := make([]byte, 32)
	y := P.y
	// y mod p as little-endian
	yPref := y.Bytes() // big-endian
	for i := 0; i < len(yPref); i++ {
		yBytes[32-len(yPref)+i] = yPref[i]
	}
	// reverse to little-endian
	for i := 0; i < 16; i++ {
		yBytes[i], yBytes[31-i] = yBytes[31-i], yBytes[i]
	}
	// compute x LSB
	xLSB := P.x.Bit(0)
	if xLSB == 1 {
		yBytes[31] |= 0x80
	}
	return yBytes
}

// decode point from 32-byte little-endian format (basic; no full checks)
func DecodePoint(in []byte) (*Point, bool) {
	if len(in) != 32 {
		return nil, false
	}
	// copy and clear sign bit
	b := make([]byte, 32)
	copy(b, in)
	sign := (b[31] >> 7) & 1
	b[31] &^= 0x80
	// convert little-endian bytes to big.Int
	// reverse to big-endian
	for i := 0; i < 16; i++ {
		b[i], b[31-i] = b[31-i], b[i]
	}
	y := new(big.Int).SetBytes(b)
	if y.Cmp(p) >= 0 {
		return nil, false
	}
	// compute x from y: x = sqrt((y^2 -1) / (d*y^2 +1))
	ysq := modMul(y, y)
	u := modSub(ysq, big.NewInt(1))
	den := modAdd(modMul(d, ysq), big.NewInt(1))
	denInv := new(big.Int).ModInverse(den, p)
	u = modMul(u, denInv)
	x, ok := modSqrt(u)
	if !ok {
		return nil, false
	}
	if x.Bit(0) != uint(sign) {
		x = modNeg(x)
	}
	return NewPoint(x, y), true
}

// little-endian helpers
func leBytesToBig(b []byte) *big.Int {
	// expects len <= 32
	tmp := make([]byte, len(b))
	copy(tmp, b)
	// reverse
	for i := 0; i < len(b)/2; i++ {
		tmp[i], tmp[len(b)-1-i] = tmp[len(b)-1-i], tmp[i]
	}
	return new(big.Int).SetBytes(tmp)
}
func bigToLEBytes(n *big.Int) []byte {
	b := n.Bytes()
	out := make([]byte, 32)
	copy(out[32-len(b):], b)
	// reverse
	for i := 0; i < 16; i++ {
		out[i], out[31-i] = out[31-i], out[i]
	}
	return out
}

// clamp scalar per RFC8032: clear 3 LSBs of first byte, clear top bit of last byte, set bit 6 of last byte
func clampScalar(sc []byte) []byte {
	if len(sc) != 32 {
		panic("clampScalar expects 32 bytes")
	}
	out := make([]byte, 32)
	copy(out, sc)
	out[0] &= 248
	out[31] &= 127
	out[31] |= 64
	return out
}

// ---- High-level Ed25519 teaching operations ----

// KeyGen: seed(32 bytes) -> expanded h (64), a (scalar), public key A (encoded 32 bytes)
func KeyGen(seed []byte) (skSeed []byte, privExpanded []byte, aScalar *big.Int, pubKey []byte) {
	if len(seed) != 32 {
		panic("seed must be 32 bytes")
	}
	h := sha512.Sum512(seed)
	// clamp first 32 bytes to get a
	clamped := clampScalar(h[:32])
	// a scalar little-endian to big.Int
	a := leBytesToBig(clamped)
	// compute A = a * B
	B := NewPoint(Bx, By)
	Apt := B.ScalarMult(a)
	Aenc := Apt.Encode()
	return seed, h[:], a, Aenc
}

// Sign teaching: follows RFC8032 steps, but uses our scalar mult and point encoding
func SignTeaching(seed []byte, message []byte) ([]byte, map[string]string) {
	// 1. h = SHA512(seed)
	hFull := sha512.Sum512(seed)
	h := hFull[:]
	// 2. a = clamp(h[:32])
	clamped := clampScalar(h[:32])
	a := leBytesToBig(clamped)

	// 3. compute A = a*B (encoded)
	B := NewPoint(Bx, By)
	Apt := B.ScalarMult(a)
	Aenc := Apt.Encode()

	// 4. r = SHA512(h[32:64] || message) mod L
	hsuf := h[32:64]
	hr := sha512.New()
	hr.Write(hsuf)
	hr.Write(message)
	rFull := hr.Sum(nil)
	r := new(big.Int).SetBytes(rFull)
	r.Mod(r, L)

	// 5. R = r * B   (point)
	Rpt := B.ScalarMult(r)
	Renc := Rpt.Encode()

	// 6. k = SHA512(R || A || message) mod L
	khasher := sha512.New()
	khasher.Write(Renc)
	khasher.Write(Aenc)
	khasher.Write(message)
	kFull := khasher.Sum(nil)
	k := new(big.Int).SetBytes(kFull)
	k.Mod(k, L)

	// 7. s = (r + k * a) mod L
	s := new(big.Int).Mul(k, a)
	s.Add(s, r)
	s.Mod(s, L)

	// signature = Renc (32) || s (32 little-endian)
	sLE := bigToLEBytes(s)
	sig := append(Renc, sLE...)

	meta := map[string]string{
		"h (SHA512 seed)": hex.EncodeToString(h),
		"a (clamped LE)":  hex.EncodeToString(clamped),
		"A (pubkey)":      hex.EncodeToString(Aenc),
		"r":               r.Text(16),
		"R (encoded)":     hex.EncodeToString(Renc),
		"k":               k.Text(16),
		"s":               hex.EncodeToString(sLE),
	}
	return sig, meta
}

// Verify teaching: checks s*B == R + k*A
func VerifyTeaching(pubKey []byte, message []byte, signature []byte) bool {
	if len(pubKey) != 32 || len(signature) != 64 {
		return false
	}
	Renc := signature[:32]
	sLE := signature[32:]
	// decode R and A
	Rpt, ok := DecodePoint(Renc)
	if !ok {
		return false
	}
	Apt, ok2 := DecodePoint(pubKey)
	if !ok2 {
		return false
	}
	// s as little-endian big.Int
	s := leBytesToBig(sLE)
	// k = H(R || A || msg) mod L
	hasher := sha512.New()
	hasher.Write(Renc)
	hasher.Write(pubKey)
	hasher.Write(message)
	kFull := hasher.Sum(nil)
	k := new(big.Int).SetBytes(kFull)
	k.Mod(k, L)

	// left = s*B
	Bpt := NewPoint(Bx, By)
	left := Bpt.ScalarMult(s)

	// right = R + k*A
	kA := Apt.ScalarMult(k)
	right := Rpt.Add(kA)

	// compare coordinates
	return left.x.Cmp(right.x) == 0 && left.y.Cmp(right.y) == 0
}

func main() {
	// demo
	seed := make([]byte, 32)
	_, err := rand.Read(seed)
	if err != nil {
		panic(err)
	}
	fmt.Printf("Seed (hex): %s\n", hex.EncodeToString(seed))

	_, expanded, a, pub := KeyGen(seed)
	fmt.Printf("SHA512(seed): %s\n", hex.EncodeToString(expanded))
	fmt.Printf("a (scalar decimal): %s\n", a.Text(10))
	fmt.Printf("PubKey (encoded hex): %s\n\n", hex.EncodeToString(pub))

	msg := []byte("hello ed25519 teaching")

	sig, meta := SignTeaching(seed, msg)
	fmt.Println("Signature (hex):", hex.EncodeToString(sig))
	fmt.Println("Meta (intermediates):")
	for k, v := range meta {
		fmt.Printf("  %s: %s\n", k, v)
	}
	ok := VerifyTeaching(pub, msg, sig)
	fmt.Println("\nVerify result:", ok)

	// A small cross-check with stdlib
	fmt.Println("\nCross-check with crypto/ed25519 (should match pub & signature validity):")
	// NOTE: crypto/ed25519 expects seed as private key seed with function NewKeyFromSeed(seed)
	// But our teaching pub encoding should match the library's public key if everything aligns.
	// We'll show library verify result using its Sign for sanity (not comparing signatures).
	// (Production use: use crypto/ed25519 directly)
}

ECDSA加密算法 ElGamal加密算法