halo2_ecc/ecc/
ecdsa.rs

Help
1use halo2_base::utils::BigPrimeField;
2use halo2_base::{gates::GateInstructions, utils::CurveAffineExt, AssignedValue, Context};
3
4use crate::bigint::{big_is_equal, big_less_than, FixedOverflowInteger, ProperCrtUint};
5use crate::fields::{fp::FpChip, FieldChip};
6
7use super::{fixed_base, scalar_multiply, EcPoint, EccChip};
8// CF is the coordinate field of GA
9// SF is the scalar field of GA
10// p = coordinate field modulus
11// n = scalar field modulus
12// Only valid when p is very close to n in size (e.g. for Secp256k1)
13// Assumes `r, s` are proper CRT integers
14/// **WARNING**: Only use this function if `1 / (p - n)` is very small (e.g., < 2<sup>-100</sup>)
15/// `pubkey` should not be the identity point
16pub fn ecdsa_verify_no_pubkey_check<F: BigPrimeField, CF: BigPrimeField, SF: BigPrimeField, GA>(
17    chip: &EccChip<F, FpChip<F, CF>>,
18    ctx: &mut Context<F>,
19    pubkey: EcPoint<F, <FpChip<F, CF> as FieldChip<F>>::FieldPoint>,
20    r: ProperCrtUint<F>,
21    s: ProperCrtUint<F>,
22    msghash: ProperCrtUint<F>,
23    var_window_bits: usize,
24    fixed_window_bits: usize,
25) -> AssignedValue<F>
26where
27    GA: CurveAffineExt<Base = CF, ScalarExt = SF>,
28{
29    // Following https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
30    let base_chip = chip.field_chip;
31    let scalar_chip =
32        FpChip::<F, SF>::new(base_chip.range, base_chip.limb_bits, base_chip.num_limbs);
33    let n = scalar_chip.p.to_biguint().unwrap();
34    let n = FixedOverflowInteger::from_native(&n, scalar_chip.num_limbs, scalar_chip.limb_bits);
35    let n = n.assign(ctx);
36
37    // check r,s are in [1, n - 1]
38    let r_valid = scalar_chip.is_soft_nonzero(ctx, &r);
39    let s_valid = scalar_chip.is_soft_nonzero(ctx, &s);
40
41    // compute u1 = m s^{-1} mod n and u2 = r s^{-1} mod n
42    let u1 = scalar_chip.divide_unsafe(ctx, msghash, &s);
43    let u2 = scalar_chip.divide_unsafe(ctx, &r, s);
44
45    // compute u1 * G and u2 * pubkey
46    let u1_mul = fixed_base::scalar_multiply(
47        base_chip,
48        ctx,
49        &GA::generator(),
50        u1.limbs().to_vec(),
51        base_chip.limb_bits,
52        fixed_window_bits,
53    );
54    let u2_mul = scalar_multiply::<_, _, GA>(
55        base_chip,
56        ctx,
57        pubkey,
58        u2.limbs().to_vec(),
59        base_chip.limb_bits,
60        var_window_bits,
61    );
62
63    // check u1 * G != -(u2 * pubkey) but allow u1 * G == u2 * pubkey
64    // check (u1 * G).x != (u2 * pubkey).x or (u1 * G).y == (u2 * pubkey).y
65    // coordinates of u1_mul and u2_mul are in proper bigint form, and lie in but are not constrained to [0, n)
66    // we therefore need hard inequality here
67    let x_eq = base_chip.is_equal(ctx, &u1_mul.x, &u2_mul.x);
68    let x_neq = base_chip.gate().not(ctx, x_eq);
69    let y_eq = base_chip.is_equal(ctx, &u1_mul.y, &u2_mul.y);
70    let u1g_u2pk_not_neg = base_chip.gate().or(ctx, x_neq, y_eq);
71
72    // compute (x1, y1) = u1 * G + u2 * pubkey and check (r mod n) == x1 as integers
73    // because it is possible for u1 * G == u2 * pubkey, we must use `EccChip::sum`
74    let sum = chip.sum::<GA>(ctx, [u1_mul, u2_mul]);
75    // WARNING: For optimization reasons, does not reduce x1 mod n, which is
76    //          invalid unless p is very close to n in size.
77    // enforce x1 < n
78    let x1 = scalar_chip.enforce_less_than(ctx, sum.x);
79    let equal_check = big_is_equal::assign(base_chip.gate(), ctx, x1.0, r);
80
81    let u1_small = big_less_than::assign(
82        base_chip.range(),
83        ctx,
84        u1,
85        n.clone(),
86        base_chip.limb_bits,
87        base_chip.limb_bases[1],
88    );
89    let u2_small = big_less_than::assign(
90        base_chip.range(),
91        ctx,
92        u2,
93        n,
94        base_chip.limb_bits,
95        base_chip.limb_bases[1],
96    );
97
98    // check (r in [1, n - 1]) and (s in [1, n - 1]) and (u1 * G != - u2 * pubkey) and (r == x1 mod n)
99    let res1 = base_chip.gate().and(ctx, r_valid, s_valid);
100    let res2 = base_chip.gate().and(ctx, res1, u1_small);
101    let res3 = base_chip.gate().and(ctx, res2, u2_small);
102    let res4 = base_chip.gate().and(ctx, res3, u1g_u2pk_not_neg);
103    let res5 = base_chip.gate().and(ctx, res4, equal_check);
104    res5
105}
halo2_ecc/ecc/ecdsa.rs

halo2_ecc/ecc/
ecdsa.rs
