1use hmac::{Hmac, Mac};
20use num_bigint::{BigInt, BigUint, Sign};
21use num_integer::Integer;
22use num_traits::{One, Zero};
23use streebog::{Digest, Streebog256};
24
25struct 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
50type Point = Option<(BigUint, BigUint)>;
52
53fn 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 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
70fn 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 return None;
79 }
80 let lambda = if x1 == x2 {
81 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
97fn 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
112fn 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
120fn 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
131fn int_le(b: &[u8]) -> BigUint {
133 BigUint::from_bytes_le(b)
134}
135
136#[derive(Debug, PartialEq, Eq)]
138pub enum GostError {
139 InvalidPrivateKey,
141 InvalidPublicKey,
143 InvalidSignature,
145 VerificationFailed,
147}
148
149pub 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
185pub 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 Err(GostError::InvalidSignature) => (),
201 Err(e) => return Err(e),
202 }
203 }
204}
205
206pub 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 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
247pub 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 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
283pub fn kdf_tree(k: &[u8], label: &[u8], seed: &[u8], output_len: usize) -> Vec<u8> {
292 let blocks = output_len.div_ceil(32);
293 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
314pub 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 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 let d = hb("48494a4b4c4d4e4f4041424344454647bbbbaaaa999988884444555566667777");
363 let sign_data = hb("77006611552244338899aabbccddeeff001122334455667789abcdef");
364 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 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 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 let k = hb("4f54f663029709c0271facd5bb6d58187410477e102555a893d45a04ab0cafc0");
398 let label = hb("60857406080304"); let seed = hb("ff00ee11dd22cc33bb44aa5599668877"); let expected = hb("e7f74dc8fcafd9738fd14d5aa542834bac7e883eff37931c082a9a80b45f60dd\
401 159d1118b56f8e78e938c28715c34c3c197a2339638901de1c610180f7de34ac\
402 424237f626e9ae5b55dbfa12ffd9cb7dfb903019eecc8228876015b2c15cbc89");
403 let t = kdf_tree(&k, &label, &seed, 96);
404 assert_eq!(t, expected);
405 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}