DSTU 4145-2002 — pseudocode

Re-derived 2026-07-22 from the official standard text at docs/papers/DSTU_4145-2002.pdf (a scan, no text layer — rendered page-by-page and read as images, see .claude.local.md). Previously this document was a straight transcription of Bouncy Castle’s DSTU4145Signer.java (oracles/bouncycastle-java/core/src/main/java/org/bouncycastle/crypto /signers/DSTU4145Signer.java), with a note that re-deriving it from Sections 5-13 was a follow-up. That follow-up is this pass: every algorithm below cites its own section/page of the official text directly, cross-checked against both BC’s code and this project’s own Rust implementation (crates/dstu-core/src/hazmat/dstu4145/). Two real discrepancies were found and fixed doing this — both are called out inline below rather than only in docs/DECISIONS.md D-25, since this is exactly the kind of thing this doc’s own “flag ambiguity/discrepancy inline” convention exists for.

Section numbers below (§5.8, §9.2, etc.) refer to the standard’s own numbering; PDF page numbers are the document’s own page number +5 (e.g. §9 is on the document’s page 14, PDF page 19 — see the front-matter table of contents, PDF pages 3-4).

Domain parameters (§4, §5.4, §5.5)

Curve over a binary field GF(2^m) (not the twisted-Edwards curves of DSTU 9041 — a different algorithm, see the algorithms table in CLAUDE.md):

E: y² + xy = x³ + Ax² + B,   A, B ∈ GF(2^m), B ≠ 0, A ∈ {0, 1}

Base point G (the standard calls it P) of prime order n. Private key d, integer, 0 < d < n (§9.1). Public key:

Q = -d·G

This is §9.2’s own literal text (“Відкритий ключ цифрового підпису обчислюють як точку еліптичної кривої виду Q = -dP”) — not an inference from Bouncy Castle’s code. §10.2 (private-key self-check) confirms it again: Q' = -dP, valid iff Q' = Q. This project’s original transcription of this doc said Q = d·G (no negation) — wrong, found via a proptest round-trip over random keys (the fixed KAT vector uses a pre-computed Q and never exercises key derivation, so it never caught this). Confirmed independently against DSTU4145KeyPairGenerator.java’s pub.getQ().negate() before this doc was corrected — the code and the spec text agree, this was purely a documentation error in this project. See docs/DECISIONS.md D-25’s follow-up entry. dstu_core::hazmat::dstu4145::curve163::Point::negate ((x, y) → (x, x+y), the standard char-2 negation for this curve) is what a caller needs to derive Q from d correctly; signature.rs takes Q as given and cannot enforce the negation for you.

Data conversions actually used by sign/verify

§5.8 — field element → integer (`fieldElement2Integer`, BC’s name)

Given a field element x = (x_{m-1},...,x_0) and the base-point order n:

1. If x = 0: return 0.
2. k ← L(n) - 1                          // L(n) = bit-length of n
3. a_i ← x_i for i = 0,...,k-1
   j ← the largest i with a_i = 1 (i.e. the top set bit within those k bits)
   If no such i: return 0.
4. Return the integer (a_j,...,a_0)       // i.e. x mod 2^k, as an integer

This is exactly “keep the low k = L(n) - 1 bits of x, as an integer” — L(n) = 163 for the m=163 curve, so k = 162. Matches BC’s fieldElement2Integer (truncate(fe.toBigInteger(), n.bitLength() - 1)) and this project’s truncate_162 exactly — no discrepancy found here.

§5.9 — hash-code → field element (`hash2FieldElement`, BC’s name)

Given a hash-code H, represented per §5.6 as a bit-string (h_{L_H-1},...,h_0) (same “rightmost = index 0 = least significant” convention §5.1 establishes for integers generally), and the field’s own bit-length m:

1. k ← min(m, L_H)
2. x_i ← h_i for i = 0,...,k-1
3. If k < m: x_i ← 0 for i = k,...,m-1
4. Return x = (x_{m-1},...,x_0)

This is the one real algorithmic bug this pass found. In byte terms (§5.1/§5.6’s own convention: the first byte of a bit-string holds its highest-indexed, most-significant bits), this means: keep the hash’s own last min(len, 21) bytes, as-is, masking the first of those bytes to its low 3 bits if a full 21 bytes were taken (163 bits total) — no byte reversal.

This project’s implementation originally did something else — reverse the whole hash, then keep the low 163 bits of that — copied from Bouncy Castle’s hash2FieldElement (curve.fromBigInteger(truncate(new BigInteger(1, Arrays.reverse(hash)), curve.getFieldSize()))). That reversal is not wrong for Bouncy Castle — it’s BC’s own documented parameter convention (its hash parameter is expected in the opposite byte order from what §5.6 describes directly, so BC reverses it back before doing the arithmetic; DSTU4145Test.test163() manually reverses its own hash literal before calling the signer for exactly this reason, confirmed by reading that test line-by-line). But this project’s Rust port had copied the reversal without also adopting BC’s reversed-input convention — so it only produced correct output when its own caller manually reversed the hash first, an undocumented, easy-to-forget requirement that happened to cancel out against how the gf2m163.json test vector’s source (test163()) constructs its input, masking the bug until the vector was fed to verify/sign without that extra manual step in an early draft of this project’s own test. Fixed in dstu_core::hazmat::dstu4145::signature::hash_to_field to implement §5.9 directly — take the hash’s own last bytes, no reversal, so callers just pass their Kupyna/GOST digest bytes as computed, no special convention to remember. Verified against gf2m163.json’s hash_h_of_t directly (crates/dstu-core/tests/dstu4145_signature.rs) — both sign (with the vector’s pinned ephemeral) and verify reproduce the vector exactly with this fix, no reversal anywhere in the test.

§11 — Digital pre-signature

compute_presignature(n, G):
    loop:
        e ← random integer, 0 < e < n                    // §6.3
        R ← e·G = (x_R, y_R)
    while x_R == 0
    F_e ← x_R
    return (F_e, e)                                       // e is secret, kept with F_e

§12 — Digital signature

generate_signature(T, d, n, G):
    h ← hash_to_field(H(T))                               // §5.9
    if h == 0: h ← 1

    loop:
        (F_e, e) ← compute_presignature(n, G)             // §11, or a precomputed one reused
        y ← h * F_e                                        // field multiplication
        r ← field_element_to_integer(y, n)                // §5.8
    while r == 0

    s ← (e + d*r) mod n
    if s == 0: retry from the presignature step

    return (r, s)

s = (e + dr) mod n is §12 step 12’s own literal formula (Обчислюють ціле число s = (e + dr) mod n) — same value as r*d + e (this project’s Scalar::multiply(r, d) + e), just written with the terms in the other order; no discrepancy, addition commutes.

§13 — Signature verification

verify_signature(T, r, s, Q, n, G):
    if not (0 < r < n and 0 < s < n): return "invalid"

    h ← hash_to_field(H(T))                               // §5.9
    if h == 0: h ← 1

    R ← s·G + r·Q = (x_R, y_R)                            // step 12
    y ← h * x_R                                            // step 13
    r' ← field_element_to_integer(y, n)                   // step 14, §5.8

    return "valid" if r' == r else "invalid"

The official text doesn’t special-case R being the point at infinity the way this project’s earlier BC-derived draft did (if R is infinity: return false) — but if R = O, x_R is conventionally 0 (§5.5: O may be represented as (0, 0)), giving y = 0, r' = 0, and since step 10 already rejected r = 0, r' == r fails anyway. Handling it as an explicit early return (dstu_core::hazmat::dstu4145::signature::verify does this) is a safe, equivalent shortcut, not a deviation — kept for clarity, matching BC’s own explicit R.isInfinity() check too.

Performance-only choices in Bouncy Castle, not part of the algorithm

s·G + r·Q via ECAlgorithms.sumOfTwoMultiplies (Shamir’s trick) — mathematically equivalent to two separate scalar multiplications added together, which is what this project’s Point::scalar_multiply (called twice) + Point::add do. Any correct point arithmetic gives the same result.
Signing’s e·G via FixedPointCombMultiplier (precomputed comb tables for a fixed point) — a speed optimization BC applies because G is fixed across many signatures; this project’s scalar_multiply doesn’t have this optimization (not needed for correctness, could be added later purely for speed).
The triple nested retry (F_e/r/s landing on zero) is not a performance choice — it’s required by the algorithm itself (§11/§12 above), the same class of rejection ECDSA’s own nonce handling requires, and skipping it is not the same algorithm. dstu_core’s sign returns Option::None on any of these instead of looping internally, since — like every other hazmat primitive here — it takes randomness (e) as an explicit caller-supplied parameter rather than calling an RNG itself; the caller must retry with a fresh e.

Not yet implemented / not restated here

§6 (auxiliary algorithms: random field element, trace/half-trace, quadratic-equation solving, random curve point, point compression §6.9/decompression §6.10, primitivity check, order primality check, the Menezes-Okamoto-Vanstone condition §6.13) — none of these are needed for sign/verify against an already-validated, fixed curve (which is all this project does so far); relevant if/when domain-parameter generation or compressed point encoding is implemented.
§7/§8 (choosing and validating domain parameters — field, curve, base point) — this project uses the m=163 curve from gf2m163.json/Annex B directly (already dual-sourced, §7.1’s Table 1 lists x^163+x^7+x^6+x^3+1 as its first recommended field, matching gf2m163::FieldElement’s reduction polynomial exactly), rather than generating or validating parameters from scratch.
Annex A (the standard’s own DSTU 28147-based RNG) — this project uses d/e as caller-supplied parameters at the hazmat layer (see docs/DECISIONS.md D-04: OS getrandom is the CSPRNG choice, once a higher-level layer exists to call it from).
Curve domain-parameter tables beyond m=163 (DSTU4145NamedCurves.java, Annex Г’s recommended curves), compressed/precomputed point encoding for interoperable serialization (DSTU4145PointEncoder.java, DSTU4145ECBinary.java) — separate concerns from the sign/verify core above. m=257 specifically is now planned, not just enumerated by BC — see docs/TASKS.md T-199 / docs/DECISIONS.md D-185 for why (real Diia-issued certificates, not just the standard allowing it) and the domain parameters extracted from them.

Test vectors

crates/dstu-core/tests/vectors/dstu4145/gf2m163.json — the official text’s own Annex B.1 worked example (polynomial basis), independently cross-checked byte-for-byte against Bouncy Castle’s own hardcoded KAT (DSTU4145Test.java test163()) — see docs/DECISIONS.md D-14/D-25 and docs/ORACLES.md. Both directions (sign with the vector’s pinned ephemeral, and verify) reproduce it exactly. gf2m163_arith.json (unit-level field/point arithmetic, generated via Bouncy Castle as the sole oracle at that granularity) and a proptest round-trip over random keys/hashes cover the rest — see docs/DECISIONS.md D-25 for what each layer verifies and why.

Keyboard shortcuts

uacrypt