[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

## 8.1 Low-level functions for cryptography

The functions prefixed with `mpn_sec_`

and `mpn_cnd_`

are designed to
perform the exact same low-level operations and have the same cache access
patterns for any two same-size arguments, assuming that function arguments are
placed at the same position and that the machine state is identical upon
function entry. These functions are intended for cryptographic purposes, where
resilience to side-channel attacks is desired.

These functions are less efficient than their “leaky” counterparts; their performance for operands of the sizes typically used for cryptographic applications is between 15% and 100% worse. For larger operands, these functions might be inadequate, since they rely on asymptotically elementary algorithms.

These functions do not make any explicit allocations. Those of these functions that need scratch space accept a scratch space operand. This convention allows callers to keep sensitive data in designated memory areas. Note however that compilers may choose to spill scalar values used within these functions to their stack frame and that such scalars may contain sensitive data.

In addition to these specially crafted functions, the following `mpn`

functions are naturally side-channel resistant: `mpn_add_n`

,
`mpn_sub_n`

, `mpn_lshift`

, `mpn_rshift`

, `mpn_zero`

,
`mpn_copyi`

, `mpn_copyd`

, `mpn_com`

, and the logical function
(`mpn_and_n`

, etc).

There are some exceptions from the side-channel resilience: (1) Some assembly
implementations of `mpn_lshift`

identify shift-by-one as a special case.
This is a problem iff the shift count is a function of sensitive data. (2)
Alpha ev6 and Pentium4 using 64-bit limbs have leaky `mpn_add_n`

and
`mpn_sub_n`

. (3) Alpha ev6 has a leaky `mpn_mul_1`

which also makes
`mpn_sec_mul`

on those systems unsafe.

- Function:
*mp_limb_t***mpn_cnd_add_n***(mp_limb_t*`cnd`, mp_limb_t *`rp`, const mp_limb_t *`s1p`, const mp_limb_t *`s2p`, mp_size_t`n`) - Function:
*mp_limb_t***mpn_cnd_sub_n***(mp_limb_t*`cnd`, mp_limb_t *`rp`, const mp_limb_t *`s1p`, const mp_limb_t *`s2p`, mp_size_t`n`) These functions do conditional addition and subtraction. If

`cnd`is non-zero, they produce the same result as a regular`mpn_add_n`

or`mpn_sub_n`

, and if`cnd`is zero, they copy {`s1p`,`n`} to the result area and return zero. The functions are designed to have timing and memory access patterns depending only on size and location of the data areas, but independent of the condition`cnd`. Like for`mpn_add_n`

and`mpn_sub_n`

, on most machines, the timing will also be independent of the actual limb values.

- Function:
*mp_limb_t***mpn_sec_add_1***(mp_limb_t **`rp`, const mp_limb_t *`ap`, mp_size_t`n`, mp_limb_t`b`, mp_limb_t *`tp`) - Function:
*mp_limb_t***mpn_sec_sub_1***(mp_limb_t **`rp`, const mp_limb_t *`ap`, mp_size_t`n`, mp_limb_t`b`, mp_limb_t *`tp`) Set

`R`to`A`+`b`or`A`-`b`, respectively, where`R`= {`rp`,`n`},`A`= {`ap`,`n`}, and`b`is a single limb. Returns carry.These functions take

*O(N)*time, unlike the leaky functions`mpn_add_1`

which are*O(1)*on average. They require scratch space of`mpn_sec_add_1_itch(`

and`n`)`mpn_sec_sub_1_itch(`

limbs, respectively, to be passed in the`n`)`tp`parameter. The scratch space requirements are guaranteed to increase monotonously in the operand size.

- Function:
*void***mpn_sec_mul***(mp_limb_t **`rp`, const mp_limb_t *`ap`, mp_size_t`an`, const mp_limb_t *`bp`, mp_size_t`bn`, mp_limb_t *`tp`) - Function:
*mp_size_t***mpn_sec_mul_itch***(mp_size_t*`an`, mp_size_t`bn`) Set

`R`to*A * B*, where`A`= {`ap`,`an`},`B`= {`bp`,`bn`}, and`R`= {`rp`,}.`an`+`bn`It is required that

.`an`>=`bn`> 0No overlapping between

`R`and the input operands is allowed. For, use`A`=`B``mpn_sec_sqr`

for optimal performance.This function requires scratch space of

`mpn_sec_mul_itch(`

limbs to be passed in the`an`,`bn`)`tp`parameter. The scratch space requirements are guaranteed to increase monotonously in the operand sizes.

- Function:
*void***mpn_sec_sqr***(mp_limb_t **`rp`, const mp_limb_t *`ap`, mp_size_t`an`, mp_limb_t *`tp`) - Function:
*mp_size_t***mpn_sec_sqr_itch***(mp_size_t*`an`) Set

`R`to*A^2*, where`A`= {`ap`,`an`}, and`R`= {`rp`,*2*}.`an`It is required that

.`an`> 0No overlapping between

`R`and the input operands is allowed.This function requires scratch space of

`mpn_sec_sqr_itch(`

limbs to be passed in the`an`)`tp`parameter. The scratch space requirements are guaranteed to increase monotonously in the operand size.

- Function:
*void***mpn_sec_powm***(mp_limb_t **`rp`, const mp_limb_t *`bp`, mp_size_t`bn`, const mp_limb_t *`ep`, mp_bitcnt_t`enb`, const mp_limb_t *`mp`, mp_size_t`n`, mp_limb_t *`tp`) - Function:
*mp_size_t***mpn_sec_powm_itch***(mp_size_t*`bn`, mp_bitcnt_t`enb`, size_t`n`) Set

`R`to*(*, where`B`raised to`E`) modulo`M``R`= {`rp`,`n`},`M`= {`mp`,`n`}, and`E`= {`ep`,*ceil(*}.`enb`/`GMP_NUMB_BITS`

)It is required that

, that`B`> 0is odd, and that`M`> 0.`E`< 2^`enb`No overlapping between

`R`and the input operands is allowed.This function requires scratch space of

`mpn_sec_powm_itch(`

limbs to be passed in the`bn`,`enb`,`n`)`tp`parameter. The scratch space requirements are guaranteed to increase monotonously in the operand sizes.

- Function:
*void***mpn_sec_tabselect***(mp_limb_t **`rp`, const mp_limb_t *`tab`, mp_size_t`n`, mp_size_t`nents`, mp_size_t`which`) Select entry

`which`from table`tab`, which has`nents`entries, each`n`limbs. Store the selected entry at`rp`.This function reads the entire table to avoid side-channel information leaks.

- Function:
*mp_limb_t***mpn_sec_div_qr***(mp_limb_t **`qp`, mp_limb_t *`np`, mp_size_t`nn`, const mp_limb_t *`dp`, mp_size_t`dn`, mp_limb_t *`tp`) - Function:
*mp_size_t***mpn_sec_div_qr_itch***(mp_size_t*`nn`, mp_size_t`dn`) -
Set

`Q`to*the truncated quotient*and`N`/`D``R`to, where`N`modulo`D``N`= {`np`,`nn`},`D`= {`dp`,`dn`},`Q`’s most significant limb is the function return value and the remaining limbs are {`qp`,`nn-dn`}, and`R`= {`np`,`dn`}.It is required that

, and that`nn`>=`dn`>= 1. This does not imply that`dp`[`dn`-1] != 0since`N`>=`D``N`might be zero-padded.Note the overlapping between

`N`and`R`. No other operand overlapping is allowed. The entire space occupied by`N`is overwritten.This function requires scratch space of

`mpn_sec_div_qr_itch(`

limbs to be passed in the`nn`,`dn`)`tp`parameter.

- Function:
*void***mpn_sec_div_r***(mp_limb_t **`np`, mp_size_t`nn`, const mp_limb_t *`dp`, mp_size_t`dn`, mp_limb_t *`tp`) - Function:
*mp_size_t***mpn_sec_div_r_itch***(mp_size_t*`nn`, mp_size_t`dn`) -
Set

`R`to, where`N`modulo`D``N`= {`np`,`nn`},`D`= {`dp`,`dn`}, and`R`= {`np`,`dn`}.It is required that

, and that`nn`>=`dn`>= 1. This does not imply that`dp`[`dn`-1] != 0since`N`>=`D``N`might be zero-padded.Note the overlapping between

`N`and`R`. No other operand overlapping is allowed. The entire space occupied by`N`is overwritten.This function requires scratch space of

`mpn_sec_div_r_itch(`

limbs to be passed in the`nn`,`dn`)`tp`parameter.

- Function:
*int***mpn_sec_invert***(mp_limb_t **`rp`, mp_limb_t *`ap`, const mp_limb_t *`mp`, mp_size_t`n`, mp_bitcnt_t`nbcnt`, mp_limb_t *`tp`) - Function:
*mp_size_t***mpn_sec_invert_itch***(mp_size_t*`n`) Set

`R`to*the inverse of*, where`A`modulo`M``R`= {`rp`,`n`},`A`= {`ap`,`n`}, and`M`= {`mp`,`n`}.**This function’s interface is preliminary.**If an inverse exists, return 1, otherwise return 0 and leave

`R`undefined. In either case, the input`A`is destroyed.It is required that

`M`is odd, and that. A safe choice is`nbcnt`>= ceil(log(`A`+1)) + ceil(log(`M`+1)), but a smaller value might improve performance if`nbcnt`= 2 *`n`* GMP_NUMB_BITS`M`or`A`are known to have leading zero bits.This function requires scratch space of

`mpn_sec_invert_itch(`

limbs to be passed in the`n`)`tp`parameter.

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

This document was generated on *March 31, 2014* using *texi2html 5.0*.