bignum.cpp File Reference

2048-bit Montgomery modular exponentiation for DH-group14. More...

#include "crypto/asymmetric/bignum.h"
#include "crypto/crypto_opt.h"
#include "server/mmgr/secure.h"
#include <string.h>

Go to the source code of this file.

Functions
int	bn_cmp_raw (const uint32_t *a, const uint32_t *b, int n)
	Compute out = base^exp mod group14_p.
void	bn_from_bytes (pc_bignum *out, const uint8_t *bytes, size_t len)
	Read a big-endian byte array of len bytes into a pc_bignum.
void	bn_to_bytes (uint8_t bytes[256], const pc_bignum *in)
	Write a pc_bignum as a 256-byte big-endian array.
int	bn_cmp (const pc_bignum *a, const pc_bignum *b)
	Compare two pc_bignum values.
int	bn_is_zero (const pc_bignum *a)
	Return non-zero if a is zero (all limbs zero).
int	bn_dh_validate (const pc_bignum *v)
	Validate a received DH public value.

Variables
PC_CRYPTO_HOT const pc_bignum	group14_p
	The RFC 3526 MODP group-14 prime (2048-bit).
const pc_bignum	group14_g
	Generator for group-14: g = 2.

Detailed Description

2048-bit Montgomery modular exponentiation for DH-group14.

─── Montgomery parameter for group-14 ─────────────────────────────────── The group-14 prime p ends in ...FFFFFFFF FFFFFFFF (little-endian d[0]=d[1]= 0xFFFFFFFF). The Montgomery parameter:

p_inv = (-(p mod 2^32))^(-1) mod 2^32

p mod 2^32 = 0xFFFFFFFF -(0xFFFFFFFF) mod 2^32 = 0x00000001 0x00000001^(-1) mod 2^32 = 1

So p_inv = 1 for the group-14 prime. In the SOS reduction pass: m_i = t[i] * p_inv mod 2^32 = t[i].

─── R² mod p ──────────────────────────────────────────────────────────── R = 2^2048. R² mod p = 2^4096 mod p. It is computed once at startup by bn_init() via 4096 doublings mod p, and stored in the static s_g14.r2 constant. ─────────────────────────────────────────────────────────────────────────

Definition in file bignum.cpp.

Function Documentation

bn_cmp_raw()

int bn_cmp_raw	(	const uint32_t *	a,
		const uint32_t *	b,
		int	n
	)

Compute out = base^exp mod group14_p.

Uses Montgomery modular exponentiation with left-to-right binary scan. Borrows one working set for all temporaries; it is wiped when released.

On Arduino the computation is delegated to mbedtls_mpi_exp_mod() which uses hardware multiplication and blinding.

Parameters

out	Result (base^exp mod p, 2048-bit).
base	Base value; must satisfy 1 < base < p-1.
exp	Exponent (e.g. the 2048-bit private DH scalar y).

Compare two n-limb magnitudes: -1, 0 or 1. Shared with the backends.

Definition at line 64 of file bignum.cpp.

Referenced by bn_cmp().

bn_from_bytes()

void bn_from_bytes	(	pc_bignum *	out,
		const uint8_t *	bytes,
		size_t	len
	)

Read a big-endian byte array of len bytes into a pc_bignum.

If len < 256 the most-significant limbs are zeroed. If len > 256 only the least-significant 256 bytes are read.

Parameters

out	Destination bignum.
bytes	Big-endian source bytes.
len	Number of source bytes (typically 256 for 2048-bit).

Definition at line 84 of file bignum.cpp.

References pc_bignum::d.

Referenced by ssh_kexdh_handle().

bn_to_bytes()

void bn_to_bytes	(	uint8_t	bytes[256],
		const pc_bignum *	in
	)

Write a pc_bignum as a 256-byte big-endian array.

Parameters

bytes	Destination buffer (exactly 256 bytes).
in	Source bignum.

Definition at line 96 of file bignum.cpp.

References pc_bignum::d, and PC_BN_LIMBS.

Referenced by ssh_kexdh_handle().

bn_cmp()

int bn_cmp	(	const pc_bignum *	a,
		const pc_bignum *	b
	)

Compare two pc_bignum values.

Returns

-1 if a < b, 0 if a == b, 1 if a > b.

Definition at line 108 of file bignum.cpp.

References bn_cmp_raw(), pc_bignum::d, and PC_BN_LIMBS.

Referenced by bn_dh_validate().

bn_is_zero()

int bn_is_zero

(

const pc_bignum *

a

)

Return non-zero if a is zero (all limbs zero).

Definition at line 113 of file bignum.cpp.

References pc_bignum::d, and PC_BN_LIMBS.

bn_dh_validate()

int bn_dh_validate

(

const pc_bignum *

v

)

Validate a received DH public value.

RFC 4253 §8: the received value e (or f) must satisfy 1 < e < p-1. Returns 0 if the value is valid, -1 otherwise.

Parameters

v	Received public DH value.

Definition at line 125 of file bignum.cpp.

References bn_cmp(), pc_bignum::d, group14_p, and PC_BN_LIMBS.

Referenced by ssh_kexdh_handle().

Variable Documentation

group14_p

PC_CRYPTO_HOT const pc_bignum group14_p

Initial value:

= {{
    
    0xFFFFFFFFu, 0xFFFFFFFFu, 0x8AACaa68u, 0x15728E5Au, 0x98FA0510u, 0x15D22618u, 0xEA956AE5u, 0x3995497Cu,
    0x95581718u, 0xDE2BCBF6u, 0x6F4C52C9u, 0xB5C55DF0u, 0xEC07A28Fu, 0x9B2783A2u, 0x180E8603u, 0xE39E772Cu,
    0x2E36CE3Bu, 0x32905E46u, 0xCA18217Cu, 0xF1746C08u, 0x4ABC9804u, 0x670C354Eu, 0x7096966Du, 0x9ED52907u,
    0x208552BBu, 0x1C62F356u, 0xDCA3AD96u, 0x83655D23u, 0xFD24CF5Fu, 0x69163FA8u, 0x1C55D39Au, 0x98DA4836u,
    0xA163BF05u, 0xC2007CB8u, 0xECE45B3Du, 0x49286651u, 0x7C4B1FE6u, 0xAE9F2411u, 0x5A899FA5u, 0xEE386BFBu,
    0xF406B7EDu, 0x0BFF5CB6u, 0xA637ED6Bu, 0xF44C42E9u, 0x625E7EC6u, 0xE485B576u, 0x6D51C245u, 0x4FE1356Du,
    0xF25F1437u, 0x302B0A6Du, 0xCD3A431Bu, 0xEF9519B3u, 0x8E3404DDu, 0x514A0879u, 0x3B139B22u, 0x020BBEa6u,
    0x8A67CC74u, 0x29024E08u, 0x80DC1CD1u, 0xC4C6628Bu, 0x2168C234u, 0xC90FDAA2u, 0xFFFFFFFFu, 0xFFFFFFFFu,
}}

The RFC 3526 MODP group-14 prime (2048-bit).

Definition at line 42 of file bignum.cpp.

Referenced by bn_dh_validate().

group14_g

const pc_bignum group14_g

Initial value:

= {{
    2u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
    0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
    0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u, 0u,
}}

Generator for group-14: g = 2.

Definition at line 54 of file bignum.cpp.

Referenced by ssh_dh_generate().