bign_genk/
lib.rs

1#![no_std]
2#![doc = include_str!("../README.md")]
3#![forbid(unsafe_code, clippy::unwrap_used)]
4#![warn(missing_docs, rust_2018_idioms, unreachable_pub)]
5#![doc(
6    html_logo_url = "https://raw.githubusercontent.com/RustCrypto/media/8f1a9894/logo.svg",
7    html_favicon_url = "https://raw.githubusercontent.com/RustCrypto/media/8f1a9894/logo.svg"
8)]
9
10//! ## Usage
11//!
12//! See also: the documentation for the [`generate_k`] function.
13//!
14//! ```
15//! use hex_literal::hex;
16//! use bign_genk::consts::U32;
17//! use belt_hash::{Digest, BeltHash};
18//! use belt_block::BeltBlock;
19//!
20//! // BIGN P-256 field modulus
21//! const BIGNP256_MODULUS: [u8; 32] =
22//!     hex!("FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF C95E2EAB 40309C49 56129C2E F129D6CC");
23//!
24//! // Public key for STB 34.101.45 Bign P256/BeltHash test case
25//! const KEY: [u8; 32] =
26//!     hex!("1F66B5B8 4B733967 4533F032 9C74F218 34281FED 0732429E 0C79235F C273E269");
27//!
28//! // Test message for STB 34.101.45 Bign P256/BeltHash test case
29//! const MSG: [u8; 13] =
30//!     hex!("B194BAC8 0A08F53B 366D008E 58");
31//!
32//! // Expected K for STB 34.101.45 Bign P256/BeltHash test case
33//! const EXPECTED_K: [u8; 32] =
34//!     hex!("829614D8 411DBBC4 E1F2471A 40045864 40FD8C95 53FAB6A1 A45CE417 AE97111E");
35//!
36//! let h = BeltHash::digest(MSG);
37//! let k = bign_genk::generate_k::<BeltHash, BeltBlock, U32>(
38//!     &KEY.into(),
39//!     &BIGNP256_MODULUS.into(),
40//!     &h,
41//!     &[],
42//! );
43//! assert_eq!(k.as_slice(), &EXPECTED_K);
44//! ```
45
46pub use cipher::Array;
47pub use cipher::typenum::consts;
48
49use cipher::{BlockCipherEncrypt, BlockSizeUser, KeyInit, array::ArraySize, typenum::Unsigned};
50use digest::Digest;
51use digest::const_oid::AssociatedOid;
52
53mod ct;
54
55type BlockArray<C> = <<C as BlockSizeUser>::BlockSize as ArraySize>::ArrayType<u8>;
56
57/// Deterministically generate ephemeral scalar `k`.
58///
59/// Accepts the following parameters and inputs:
60///
61/// - `x`: secret key
62/// - `q`: field modulus
63/// - `h`: hash/digest of an input message: must be reduced modulo `q` in advance
64/// - `data`: additional associated data, e.g., CSRNG output used as added entropy
65#[inline]
66pub fn generate_k<D, C, N>(
67    x: &Array<u8, N>,
68    q: &Array<u8, N>,
69    h: &Array<u8, N>,
70    data: &[u8],
71) -> Array<u8, N>
72where
73    D: BlockSizeUser + Clone + Digest + AssociatedOid,
74    C: BlockSizeUser + Clone + BlockCipherEncrypt + KeyInit,
75    N: ArraySize,
76    BlockArray<C>: Copy,
77{
78    let mut k = Array::default();
79    generate_k_mut::<D, C>(x, q, h, data, &mut k);
80    k
81}
82
83/// Deterministically generate ephemeral scalar `k` by writing it into the provided output buffer.
84///
85/// This is an API that accepts dynamically sized inputs intended for use cases where the sizes
86/// are determined at runtime, such as the legacy Digital Signature Algorithm (DSA).
87///
88/// Accepts the following parameters and inputs:
89///
90/// - `x`: secret key
91/// - `q`: field modulus
92/// - `h`: hash/digest of an input message: must be reduced modulo `q` in advance
93/// - `data`: additional associated data, e.g., CSRNG output used as added entropy
94#[inline]
95pub fn generate_k_mut<D, C>(x: &[u8], q: &[u8], h: &[u8], data: &[u8], k: &mut [u8])
96where
97    D: BlockSizeUser + Clone + Digest + AssociatedOid,
98    C: BlockSizeUser + Clone + BlockCipherEncrypt + KeyInit,
99    BlockArray<C>: Copy,
100{
101    let len = k.len();
102    assert_eq!(len, x.len());
103    assert_eq!(len, q.len());
104    assert_eq!(len, h.len());
105    assert!(len == 32 || len == 48 || len == 64);
106
107    // n = ℓ/64 (2, 3 or 4)
108    let n = len / C::BlockSize::USIZE;
109
110    // 2: θ ← belt-hash(OID(h) ‖ ⟨d⟩ ‖ t)
111    let mut hasher: D = Digest::new();
112
113    hasher.update([0x06, (D::OID.len() - 1) as u8]);
114    hasher.update(D::OID);
115    hasher.update(x);
116    hasher.update(data);
117    let theta = hasher.finalize();
118
119    // belt-block(θ)
120    let cipher = C::new_from_slice(&theta).expect("Invalid key length");
121
122    // 3. r ← H
123    // r = r₁ ‖ r₂ ‖ ... ‖ r_n, where r_i ∈ {0,1}^128
124    let mut r = [Array::<u8, C::BlockSize>::default(); 4];
125    for (i, chunk) in h.chunks(C::BlockSize::USIZE).enumerate().take(n) {
126        r[i][..chunk.len()].copy_from_slice(chunk);
127    }
128
129    // 4.
130    let mut i = 1u32;
131    loop {
132        let s = match n {
133            2 => {
134                // 4.1) s ← r₁
135                r[0]
136            }
137            3 => {
138                // 4.2.a) s ← r₁ ⊕ r₂
139                let s = xor_blocks::<C>(&r[0], &r[1]);
140                // 4.2.b) r₁ ← r₂
141                r[0] = r[1];
142                s
143            }
144            4 => {
145                // 4.3.a) s ← r₁ ⊕ r₂ ⊕ r₃
146                let mut s = xor_blocks::<C>(&r[0], &r[1]);
147                xor_assign(&mut s, &r[2]);
148                // 4.3.b) r₁ ← r₂
149                r[0] = r[1];
150                // 4.3.c) r₂ ← r₃
151                r[1] = r[2];
152                s
153            }
154            _ => unreachable!(),
155        };
156
157        // 4.4: r_(n-1) ← belt-block(s, θ) ⊕ r_n ⊕ ⟨i⟩_128
158        let mut encrypted = s;
159        cipher.encrypt_block(&mut encrypted);
160
161        // ⊕ r_n
162        xor_assign(&mut encrypted, &r[n - 1]);
163
164        // ⊕ ⟨i⟩_128
165        xor_assign(&mut encrypted, &i.to_le_bytes());
166
167        // r_(n-1)
168        r[n - 2] = encrypted;
169
170        // 4.5: r_n ← s
171        r[n - 1] = s;
172
173        // 4.6: Check every 2n iterations
174        if i % (2 * n as u32) == 0 {
175            for (j, chunk) in r.iter().enumerate().take(n) {
176                k[j * C::BlockSize::USIZE..(j + 1) * C::BlockSize::USIZE].copy_from_slice(chunk);
177            }
178
179            // Assert: k ∈ {1, 2, ..., q-1}
180            if (!ct::is_zero(k) & ct::lt(k, q)).into() {
181                return; // 5-6: k ← r, return
182            }
183        }
184
185        i = i.wrapping_add(1);
186    }
187}
188
189/// XOR two blocks of arbitrary size
190#[inline]
191fn xor_blocks<C>(
192    a: &Array<u8, C::BlockSize>,
193    b: &Array<u8, C::BlockSize>,
194) -> Array<u8, C::BlockSize>
195where
196    C: BlockSizeUser,
197    BlockArray<C>: Copy,
198{
199    let mut result = *a;
200    xor_assign(&mut result, b);
201    result
202}
203
204/// XOR-assignment
205#[inline]
206fn xor_assign(a: &mut [u8], b: &[u8]) {
207    for (a_byte, b_byte) in a.iter_mut().zip(b.iter()) {
208        *a_byte ^= b_byte;
209    }
210}
211
212#[cfg(test)]
213mod tests {
214    use super::*;
215    use belt_block::{BeltBlock, cipher::typenum::U32};
216    use belt_hash::BeltHash;
217    use hex_literal::hex;
218
219    /// Table 7 appendix G STB 34.101.45
220    #[test]
221    fn stb_table_g7() {
222        let d = hex!("1F66B5B8 4B733967 4533F032 9C74F218 34281FED 0732429E 0C79235F C273E269");
223        let q = hex!("FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF C95E2EAB 40309C49 56129C2E F129D6CC");
224        let h = hex!("9D02EE44 6FB6A29F E5C982D4 B13AF9D3 E90861BC 4CEF27CF 306BFB0B 174A154A");
225        let t = hex!("BE329713 43FC9A48 A02A885F 194B09A1 7ECDA4D0 1544AF");
226
227        let expected_k =
228            hex!("7ADC8713 283EBFA5 47A2AD9C DFB245AE 0F7B968D F0F91CB7 85D1F932 A3583107");
229
230        let k = generate_k::<BeltHash, BeltBlock, U32>(&d.into(), &q.into(), &h.into(), &t);
231
232        assert_eq!(k.as_slice(), &expected_k);
233    }
234}
bign_genk/lib.rs

bign_genk/
lib.rs
