Skip to main content

spodes_rs/security/
gost3410.rs

1//! GOST R 34.10-2018 (256-bit) digital signatures — HLS mechanism 10.
2//!
3//! No mature Rust crate implements the GOST elliptic-curve signature scheme, so
4//! it is provided here from scratch over the curve mandated by the DLMS GOST
5//! profile: `id-tc26-gost-3410-2012-256-paramSetB`, OID `1.2.643.7.1.2.1.1.2`
6//! (Р 1323565.1.024-2019, cryptographic suite 9). The message digest is
7//! Streebog-256 (GOST R 34.11-2018).
8//!
9//! During the HLS handshake (Р 1323565.1, §7.5.3) the signed message is
10//! `SystemTitle-a ‖ SystemTitle-b ‖ challenge_a ‖ challenge_b`; each party signs
11//! with its own signing key `d_sign` and verifies the peer's response with the
12//! peer's verification key `Q_sign`.
13//!
14//! Keys and signatures use the profile's fixed-width big-endian encodings:
15//! `d_sign` is `Vec256(d)` (32 octets), the verification key is
16//! `π_x(Q) ‖ π_y(Q)` (64 octets), and a signature is `Vec256(r) ‖ Vec256(s)`
17//! (64 octets), matching GOST R 34.10 and the control examples in Р 1323565.1.
18
19use hmac::{Hmac, Mac};
20use num_bigint::{BigInt, BigUint, Sign};
21use num_integer::Integer;
22use num_traits::{One, Zero};
23use streebog::{Digest, Streebog256};
24
25/// Curve parameters of `id-tc26-gost-3410-2012-256-paramSetB`.
26struct Curve {
27    p: BigUint,
28    a: BigUint,
29    b: BigUint,
30    q: BigUint,
31    gx: BigUint,
32    gy: BigUint,
33}
34
35fn hexint(s: &str) -> BigUint {
36    BigUint::parse_bytes(s.as_bytes(), 16).expect("valid curve constant")
37}
38
39fn curve() -> Curve {
40    Curve {
41        p: hexint("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97"),
42        a: hexint("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94"),
43        b: hexint("00000000000000000000000000000000000000000000000000000000000000A6"),
44        q: hexint("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893"),
45        gx: hexint("0000000000000000000000000000000000000000000000000000000000000001"),
46        gy: hexint("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14"),
47    }
48}
49
50/// Affine point on the curve; `None` is the point at infinity.
51type Point = Option<(BigUint, BigUint)>;
52
53/// Modular inverse of `x` mod `m` (m prime, x != 0).
54fn modinv(x: &BigUint, m: &BigUint) -> BigUint {
55    let g = BigInt::from_biguint(Sign::Plus, x.clone()).extended_gcd(&BigInt::from_biguint(Sign::Plus, m.clone()));
56    // g.gcd == 1 for a prime modulus and non-zero x.
57    let mm = BigInt::from_biguint(Sign::Plus, m.clone());
58    let inv = ((g.x % &mm) + &mm) % &mm;
59    inv.to_biguint().expect("non-negative inverse")
60}
61
62fn mod_sub(a: &BigUint, b: &BigUint, p: &BigUint) -> BigUint {
63    if a >= b {
64        (a - b) % p
65    } else {
66        (p - ((b - a) % p)) % p
67    }
68}
69
70/// Point addition on the short-Weierstrass curve `y^2 = x^3 + a·x + b (mod p)`.
71fn point_add(c: &Curve, p1: &Point, p2: &Point) -> Point {
72    match (p1, p2) {
73        (None, _) => p2.clone(),
74        (_, None) => p1.clone(),
75        (Some((x1, y1)), Some((x2, y2))) => {
76            if x1 == x2 && (y1 != y2 || y1.is_zero()) {
77                // P + (-P) = O, or a vertical tangent.
78                return None;
79            }
80            let lambda = if x1 == x2 {
81                // Doubling: (3·x1^2 + a) / (2·y1).
82                let num = (BigUint::from(3u32) * x1 * x1 + &c.a) % &c.p;
83                let den = (BigUint::from(2u32) * y1) % &c.p;
84                (num * modinv(&den, &c.p)) % &c.p
85            } else {
86                let num = mod_sub(y2, y1, &c.p);
87                let den = mod_sub(x2, x1, &c.p);
88                (num * modinv(&den, &c.p)) % &c.p
89            };
90            let x3 = mod_sub(&mod_sub(&(&lambda * &lambda % &c.p), x1, &c.p), x2, &c.p);
91            let y3 = mod_sub(&(&lambda * mod_sub(x1, &x3, &c.p) % &c.p), y1, &c.p);
92            Some((x3, y3))
93        }
94    }
95}
96
97/// Scalar multiplication `k·point` by double-and-add.
98fn point_mul(c: &Curve, k: &BigUint, point: &Point) -> Point {
99    let mut result: Point = None;
100    let mut addend = point.clone();
101    let mut n = k.clone();
102    while !n.is_zero() {
103        if n.bit(0) {
104            result = point_add(c, &result, &addend);
105        }
106        addend = point_add(c, &addend, &addend);
107        n >>= 1;
108    }
109    result
110}
111
112/// Streebog-256 digest of `message` as an integer. GOST R 34.10 maps the hash
113/// vector to the integer α with the first digest octet least significant.
114fn hash_to_int(message: &[u8]) -> BigUint {
115    let mut h = Streebog256::new();
116    h.update(message);
117    BigUint::from_bytes_le(&h.finalize())
118}
119
120/// Encodes an integer as a 32-octet `Vec256`. The DLMS GOST profile
121/// (Р 1323565.1) uses little-endian byte order for scalars, coordinates and
122/// signature components, unlike the big-endian mathematical notation of the
123/// GOST R 34.10 standard itself.
124fn vec256(x: &BigUint) -> [u8; 32] {
125    let bytes = x.to_bytes_le();
126    let mut out = [0u8; 32];
127    out[..bytes.len()].copy_from_slice(&bytes);
128    out
129}
130
131/// Decodes a little-endian `Vec256` scalar/coordinate.
132fn int_le(b: &[u8]) -> BigUint {
133    BigUint::from_bytes_le(b)
134}
135
136/// Errors from GOST signing or verification.
137#[derive(Debug, PartialEq, Eq)]
138pub enum GostError {
139    /// The signing key was zero or out of range.
140    InvalidPrivateKey,
141    /// The verification key was not a valid curve point.
142    InvalidPublicKey,
143    /// The signature had the wrong length or an out-of-range component.
144    InvalidSignature,
145    /// The signature did not verify.
146    VerificationFailed,
147}
148
149/// Signs `message` with signing key `d` (32-octet big-endian `Vec256`) using a
150/// caller-supplied `k` (32 octets, `1 ≤ k < q`). Returns `Vec256(r) ‖ Vec256(s)`.
151///
152/// Exposing `k` makes signing deterministic for the standard control examples;
153/// production callers use [`gost_sign`], which draws `k` from a secure RNG.
154pub fn gost_sign_with_k(d: &[u8], message: &[u8], k: &[u8]) -> Result<[u8; 64], GostError> {
155    let c = curve();
156    let d = int_le(d);
157    if d.is_zero() || d >= c.q {
158        return Err(GostError::InvalidPrivateKey);
159    }
160    let alpha = hash_to_int(message);
161    let mut e = &alpha % &c.q;
162    if e.is_zero() {
163        e = BigUint::one();
164    }
165    let k = int_le(k);
166    if k.is_zero() || k >= c.q {
167        return Err(GostError::InvalidSignature);
168    }
169    let g = Some((c.gx.clone(), c.gy.clone()));
170    let cpoint = point_mul(&c, &k, &g).ok_or(GostError::InvalidSignature)?;
171    let r = cpoint.0 % &c.q;
172    if r.is_zero() {
173        return Err(GostError::InvalidSignature);
174    }
175    let s = (&r * &d + &k * &e) % &c.q;
176    if s.is_zero() {
177        return Err(GostError::InvalidSignature);
178    }
179    let mut sig = [0u8; 64];
180    sig[..32].copy_from_slice(&vec256(&r));
181    sig[32..].copy_from_slice(&vec256(&s));
182    Ok(sig)
183}
184
185/// Signs `message` with signing key `d`, drawing a random `k` from a secure RNG.
186pub fn gost_sign(d: &[u8], message: &[u8]) -> Result<[u8; 64], GostError> {
187    use rand::Rng;
188    let c = curve();
189    let mut rng = rand::rng();
190    loop {
191        let mut kb = [0u8; 32];
192        rng.fill(&mut kb);
193        let k = BigUint::from_bytes_be(&kb) % &c.q;
194        if k.is_zero() {
195            continue;
196        }
197        match gost_sign_with_k(d, message, &vec256(&k)) {
198            Ok(sig) => return Ok(sig),
199            // A zero r or s is astronomically unlikely; just draw a fresh k.
200            Err(GostError::InvalidSignature) => (),
201            Err(e) => return Err(e),
202        }
203    }
204}
205
206/// Verifies signature `sig` (`Vec256(r) ‖ Vec256(s)`, 64 octets) over `message`
207/// with verification key `q_pub` (`π_x(Q) ‖ π_y(Q)`, 64 octets).
208pub fn gost_verify(q_pub: &[u8], message: &[u8], sig: &[u8]) -> Result<(), GostError> {
209    if q_pub.len() != 64 || sig.len() != 64 {
210        return Err(GostError::InvalidSignature);
211    }
212    let c = curve();
213    let r = int_le(&sig[..32]);
214    let s = int_le(&sig[32..]);
215    if r.is_zero() || r >= c.q || s.is_zero() || s >= c.q {
216        return Err(GostError::InvalidSignature);
217    }
218    let qx = int_le(&q_pub[..32]);
219    let qy = int_le(&q_pub[32..]);
220    if qx >= c.p || qy >= c.p {
221        return Err(GostError::InvalidPublicKey);
222    }
223    // The verification key must lie on the curve: y^2 == x^3 + a·x + b (mod p).
224    let lhs = (&qy * &qy) % &c.p;
225    let rhs = (&qx * &qx % &c.p * &qx + &c.a * &qx + &c.b) % &c.p;
226    if lhs != rhs {
227        return Err(GostError::InvalidPublicKey);
228    }
229    let q_point = Some((qx, qy));
230
231    let alpha = hash_to_int(message);
232    let mut e = &alpha % &c.q;
233    if e.is_zero() {
234        e = BigUint::one();
235    }
236    let v = modinv(&e, &c.q);
237    let z1 = (&s * &v) % &c.q;
238    let z2 = (&c.q - (&r * &v) % &c.q) % &c.q;
239    let g = Some((c.gx.clone(), c.gy.clone()));
240    let point = point_add(&c, &point_mul(&c, &z1, &g), &point_mul(&c, &z2, &q_point));
241    match point {
242        Some((x, _)) if (&x % &c.q) == r => Ok(()),
243        _ => Err(GostError::VerificationFailed),
244    }
245}
246
247/// VKO_GOST3410_2012_256 key-agreement function (R 50.1.113-2016 / RFC 7836).
248///
249/// Computes the shared key-encryption key from our private key `d`
250/// (little-endian `Vec256`), the peer public key `q_pub` (`π_x(Q) ‖ π_y(Q)`,
251/// 64 octets) and the user keying material `ukm` (little-endian). The curve has
252/// cofactor 1, so the agreed point is `S = (ukm · d mod q) · Q`; the key is
253/// `Streebog256(π_x(S) ‖ π_y(S))`.
254pub fn vko(d: &[u8], q_pub: &[u8], ukm: &[u8]) -> Result<[u8; 32], GostError> {
255    if q_pub.len() != 64 {
256        return Err(GostError::InvalidPublicKey);
257    }
258    let c = curve();
259    let d = int_le(d);
260    if d.is_zero() || d >= c.q {
261        return Err(GostError::InvalidPrivateKey);
262    }
263    let qx = int_le(&q_pub[..32]);
264    let qy = int_le(&q_pub[32..]);
265    if qx >= c.p || qy >= c.p {
266        return Err(GostError::InvalidPublicKey);
267    }
268    let q_point = Some((qx, qy));
269    let ukm = int_le(ukm);
270    // Cofactor is 1 for this curve; scalar = ukm · d mod q.
271    let scalar = (ukm * d) % &c.q;
272    let (sx, sy) = point_mul(&c, &scalar, &q_point).ok_or(GostError::InvalidPublicKey)?;
273    let mut input = Vec::with_capacity(64);
274    input.extend_from_slice(&vec256(&sx));
275    input.extend_from_slice(&vec256(&sy));
276    let mut h = Streebog256::new();
277    h.update(&input);
278    let mut kek = [0u8; 32];
279    kek.copy_from_slice(&h.finalize());
280    Ok(kek)
281}
282
283/// KDF_TREE_GOSTR3411_2012_256 (R 50.1.113-2016 / RFC 7836) with a one-octet
284/// counter (`R = 1`).
285///
286/// Derives `output_len` octets from key `k`, a `label` and a `seed`:
287/// each 256-bit block `K_i = HMAC_Streebog256(k, i ‖ label ‖ 0x00 ‖ seed ‖ L)`,
288/// where `i` is a one-octet counter (1-based) and `L` is the total output length
289/// in bits, encoded as a 16-bit big-endian integer. In the DLMS GOST profile
290/// the diversified key is 768 bits: `Key = LSB512`, `M = MSB256`.
291pub fn kdf_tree(k: &[u8], label: &[u8], seed: &[u8], output_len: usize) -> Vec<u8> {
292    let blocks = output_len.div_ceil(32);
293    // R = 1 (one-octet counter) caps this construction at 255 blocks (8160
294    // bytes) by design (RFC 7836); this crate only ever asks for 96.
295    debug_assert!(blocks <= 255, "kdf_tree output_len exceeds the one-octet-counter limit");
296    #[allow(clippy::cast_possible_truncation)]
297    let l_bits = (output_len * 8) as u16;
298    let mut out = Vec::with_capacity(blocks * 32);
299    #[allow(clippy::cast_possible_truncation)]
300    for i in 1..=blocks as u8 {
301        let mut mac =
302            <Hmac<Streebog256> as hmac::digest::KeyInit>::new_from_slice(k).expect("HMAC accepts any key length");
303        mac.update(&[i]);
304        mac.update(label);
305        mac.update(&[0x00]);
306        mac.update(seed);
307        mac.update(&l_bits.to_be_bytes());
308        out.extend_from_slice(&mac.finalize().into_bytes());
309    }
310    out.truncate(output_len);
311    out
312}
313
314/// Derives the verification key `π_x(Q) ‖ π_y(Q)` (64 octets) from a signing
315/// key `d` (`Vec256`), where `Q = d·P`.
316pub fn public_key(d: &[u8]) -> Result<[u8; 64], GostError> {
317    let c = curve();
318    let d = int_le(d);
319    if d.is_zero() || d >= c.q {
320        return Err(GostError::InvalidPrivateKey);
321    }
322    let g = Some((c.gx.clone(), c.gy.clone()));
323    let (x, y) = point_mul(&c, &d, &g).ok_or(GostError::InvalidPrivateKey)?;
324    let mut out = [0u8; 64];
325    out[..32].copy_from_slice(&vec256(&x));
326    out[32..].copy_from_slice(&vec256(&y));
327    Ok(out)
328}
329
330#[cfg(test)]
331mod tests {
332    use super::*;
333
334    fn hb(s: &str) -> Vec<u8> {
335        (0..s.len()).step_by(2).map(|i| u8::from_str_radix(&s[i..i + 2], 16).unwrap()).collect()
336    }
337
338    #[test]
339    fn ec_math_matches_gost_standard_example() {
340        // GOST R 34.10-2018 Appendix control example (test curve, e given directly).
341        let sc = Curve {
342            p: hexint("8000000000000000000000000000000000000000000000000000000000000431"),
343            a: hexint("0000000000000000000000000000000000000000000000000000000000000007"),
344            b: hexint("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E"),
345            q: hexint("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3"),
346            gx: hexint("0000000000000000000000000000000000000000000000000000000000000002"),
347            gy: hexint("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8"),
348        };
349        let d = hexint("7A929ADE789BB9BE10ED359DD39A72C11B60961F49397EEE1D19CE9891EC3B28");
350        let k = hexint("77105C9B20BCD3122823C8CF6FCC7B956DE33814E95B7FE64FED924594DCEAB3");
351        let e = hexint("2DFBC1B372D89A1188C09C52E0EEC61FCE52032AB1022E8E67ECE6672B043EE5");
352        let g = Some((sc.gx.clone(), sc.gy.clone()));
353        let r = point_mul(&sc, &k, &g).unwrap().0 % &sc.q;
354        assert_eq!(r, hexint("41AA28D2F1AB148280CD9ED56FEDA41974053554A42767B83AD043FD39DC0493"));
355        let s = (&r * &d + &k * &e) % &sc.q;
356        assert_eq!(s, hexint("1456C64BA4642A1653C235A98A60249BCD6D3F746B631DF928014F6C5BF9C40"));
357    }
358
359    #[test]
360    fn sign_matches_r1323565_a3_control_example() {
361        // Р 1323565.1, A.3 — protection of data with a digital signature.
362        let d = hb("48494a4b4c4d4e4f4041424344454647bbbbaaaa999988884444555566667777");
363        let sign_data = hb("77006611552244338899aabbccddeeff001122334455667789abcdef");
364        // Fixed k used across all SIGN_256 control examples.
365        let k = hb("43730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011");
366        let expected = hb("d3b72bb12fb7da1a06f8e11acdec034ffcf14588301a3315bbe8cd611fc4545e\
367             a9fae88aeac47cd46a0858711d942223c523bfd53cbadff97e0eec1f69a3efca");
368        let sig = gost_sign_with_k(&d, &sign_data, &k).unwrap();
369        assert_eq!(sig.to_vec(), expected);
370    }
371
372    #[test]
373    fn sign_verify_round_trip() {
374        let d = hb("48494a4b4c4d4e4f4041424344454647bbbbaaaa999988884444555566667777");
375        let pk = public_key(&d).unwrap();
376        let msg = b"SystemTitle-a||SystemTitle-b||StoC||CtoS";
377        let sig = gost_sign(&d, msg).unwrap();
378        gost_verify(&pk, msg, &sig).unwrap();
379        // Tampered message must fail.
380        assert_eq!(gost_verify(&pk, b"other message", &sig), Err(GostError::VerificationFailed));
381    }
382
383    #[test]
384    fn vko_matches_r1323565_key_agreement_example() {
385        // Р 1323565.1, key-agreement control example: P_VU = VKO256(d_e,U, Q_s,V, r_U).
386        let d = hb("68696a6b6c6d6e6f6061626364656667ddddddddccccccccaaaaaaaabbbbbbbb");
387        let q = hb("212daf02de1c91ea961e58e01e42df1733c00748998bc34d76dad96b3b256378\
388             7b9cffcfa0f24753d6d5eb6133b35a95375a0ef683b3ff5be7d61b99d7fe6617");
389        let ukm = hb("f0f0f0f0e1e1e1e1d2d2d2d2c3c3c3c3");
390        let expected = hb("4f54f663029709c0271facd5bb6d58187410477e102555a893d45a04ab0cafc0");
391        assert_eq!(vko(&d, &q, &ukm).unwrap().to_vec(), expected);
392    }
393
394    #[test]
395    fn kdf_tree_matches_r1323565_key_agreement_example() {
396        // Р 1323565.1: T_VU = KDFTREE(P_VU, AlgorithmID, sysU ‖ sysV) ∈ V768.
397        let k = hb("4f54f663029709c0271facd5bb6d58187410477e102555a893d45a04ab0cafc0");
398        let label = hb("60857406080304"); // AlgorithmID
399        let seed = hb("ff00ee11dd22cc33bb44aa5599668877"); // sysU ‖ sysV
400        let expected = hb("e7f74dc8fcafd9738fd14d5aa542834bac7e883eff37931c082a9a80b45f60dd\
401             159d1118b56f8e78e938c28715c34c3c197a2339638901de1c610180f7de34ac\
402             424237f626e9ae5b55dbfa12ffd9cb7dfb903019eecc8228876015b2c15cbc89");
403        let t = kdf_tree(&k, &label, &seed, 96);
404        assert_eq!(t, expected);
405        // M_VU = MSB256(T_VU).
406        assert_eq!(&t[..32], &hb("e7f74dc8fcafd9738fd14d5aa542834bac7e883eff37931c082a9a80b45f60dd")[..]);
407    }
408
409    #[test]
410    fn verify_rejects_wrong_lengths() {
411        assert_eq!(gost_verify(&[0u8; 63], b"m", &[0u8; 64]), Err(GostError::InvalidSignature));
412        assert_eq!(gost_verify(&[0u8; 64], b"m", &[0u8; 10]), Err(GostError::InvalidSignature));
413    }
414}