Skip to content

Latest commit

 

History

History
470 lines (371 loc) · 12.4 KB

mp.md

File metadata and controls

470 lines (371 loc) · 12.4 KB

Multiprecision Utils

#include <maid/mp.h>

Words are used in a little-endian way

maid_mp_word Type that contains a word: u64 on systems with 128-bits integer support, otherwise u32
size_t maid_mp_words(size_t bits); Returns minimal amount of words for a quantity of bits

Parameters

name description
bits Amount of bits

Return value

case description
Always Amount of words
void maid_mp_read(size_t words, maid_mp_word *a, const u8 *addr, bool big); Reads a biginteger from memory

Parameters

name description
words Amount of words
a Destination
addr Memory to read
big Little/Big endian
void maid_mp_write(size_t words, const maid_mp_word *a, u8 *addr, bool big); Writes a biginteger to memory

Parameters

name description
words Amount of words
a Source (NULL = 0)
addr Memory to be written
big Little/Big endian
void maid_mp_debug(size_t words, const char *name, const maid_mp_word *a); Prints a biginteger

Parameters

name description
words Amount of words
name Name to print
a Number to print (NULL = 0)
void maid_mp_not(size_t words, maid_mp_word *a); Binary NOTs a biginteger

Parameters

name description
words Amount of words
a Destination
void maid_mp_and(size_t words, maid_mp_word *a, const maid_mp_word *b); Binary ANDs a biginteger to another

Parameters

name description
words Amount of words
a Destination
b Source (NULL = -1)
void maid_mp_orr(size_t words, maid_mp_word *a, const maid_mp_word *b); Binary ORs a biginteger to another

Parameters

name description
words Amount of words
a Destination
b Source (NULL = 0)
void maid_mp_xor(size_t words, maid_mp_word *a, const maid_mp_word *b); Binary XORs a biginteger to another

Parameters

name description
words Amount of words
a Destination
b Source (NULL = 0)
s8 maid_mp_cmp(size_t words, const maid_mp_word *a, const maid_mp_word *b); Compares two bigintegers

Parameters

name description
words Amount of words
a Number 1 (NULL = 0)
b Number 2 (NULL = 0)

Return value

case description
a > b -1
a = b 0
a < b 1
void maid_mp_mov(size_t words, maid_mp_word *a, const maid_mp_word *b); Sets a biginteger to another

Parameters

name description
words Amount of words
a Destination
b Source (NULL = 0)
void maid_mp_add(size_t words, maid_mp_word *a, const maid_mp_word *b); Adds a biginteger to another

Parameters

name description
words Amount of words
a Augend -> Total
b Addend (NULL = 0)
void maid_mp_sub(size_t words, maid_mp_word *a, const maid_mp_word *b); Subtracts a biginteger from another

Parameters

name description
words Amount of words
a Minuend -> Difference
b Subtrahend (NULL = 0)
void maid_mp_shl(size_t words, maid_mp_word *a, u64 shift); Shifts a biginteger left

Parameters

name description
words Amount of words
a Number to be shifted
shift Amount of shift
void maid_mp_shr(size_t words, maid_mp_word *a, u64 shift); Shifts a biginteger right

Parameters

name description
words Amount of words
a Number to be shifted
shift Amount of shift
void maid_mp_mul(size_t words, maid_mp_word *a, const maid_mp_word *b); Multiplies a biginteger by another

Parameters

name description
words Amount of words
a Multiplicand -> Product
b Multiplier (NULL = 1)
void maid_mp_div(size_t words, maid_mp_word *a, const maid_mp_word *b); Divides a biginteger by another

Parameters

name description
words Amount of words
a Dividend -> Quotient
b Divisor (NULL = 1)
void maid_mp_mod(size_t words, maid_mp_word *a, const maid_mp_word *b); Gets the remainder of a biginteger divided by another

Parameters

name description
words Amount of words
a Dividend -> Remainder
b Divisor (NULL = 1)
void maid_mp_exp(size_t words, maid_mp_word *a, const maid_mp_word *b); Raises a big integer to the power of another

Parameters

name description
words Amount of words
a Base -> Power
b Exponent (NULL = 1)
void maid_mp_div2(size_t words, maid_mp_word *a, maid_mp_word *rem, const maid_mp_word *b); Divides a biginteger by another, and returns the remainder

Parameters

name description
words Amount of words
a Dividend -> Quotient
rem Remainder
b Divisor (NULL = 1)
void maid_mp_mulmod(size_t words, maid_mp_word *a, const maid_mp_word *b, const maid_mp_word *mod ); Modular multiplies a biginteger by another

Parameters

name description
words Amount of words
a Multiplicand -> Product
b Multiplier (NULL = 1)
mod Modulo divisor
void maid_mp_expmod(size_t words, maid_mp_word *a, const maid_mp_word *b, const maid_mp_word *mod, bool constant); Raises a big integer to the modular power of another

Parameters

name description
words Amount of words
a Base -> Power
b Exponent (NULL = 1)
mod Modulo divisor
constant Constant time for all exponents
bool maid_mp_invmod(size_t words, maid_mp_word *a, const maid_mp_word *mod); Modular multiplicative inverse of a biginteger

Parameters

name description
words Amount of words
a Number
mod Modulo divisor

Return value

case description
Exists true
Doesn't exist false
void maid_mp_expmod2(size_t words, maid_mp_word *a, const maid_mp_word *b, const maid_mp_word *mod, bool constant); Raises a big integer to the modular power of another (using Montgomery method)

Parameters

name description
words Amount of words
a Base -> Power
b Exponent (NULL = 1)
mod Odd modulo divisor
constant Constant time for all exponents
void maid_mp_random(size_t words, maid_mp_word *a, maid_rng *g, size_t bits); Generates a random number with a certain amount of bits

Parameters

name description
words Amount of words
a Output
g Random number generator
bits Amount of bits
void maid_mp_random2(size_t words, maid_mp_word *a, maid_rng *g, const maid_mp_word *low, const maid_mp_word *high); Generates a random number within a certain range

Parameters

name description
words Amount of words
a Output
g Random number generator
low Range low limit (including)
high Range high limit (excluding)
void maid_mp_prime(size_t words, maid_mp_word *a, maid_rng *g, size_t bits, size_t safety); Generates a strong probable prime with a certain amount of bits

Parameters

name description
words Amount of words
a Output
g Random number generator
bits Amount of bits
safety 1 / 2^safety chance of non-prime

Example Code

#include <stdio.h>
#include <stdlib.h>

#include <maid/mem.h>

#include <maid/mp.h>

int main(void)
{
    size_t words = maid_mp_words(128);

    /* Little endian */
    u8 base    [128 / 8] = {3};
    u8 exponent[128 / 8] = {63};

    maid_mp_word b[words];
    maid_mp_word e[words];

    maid_mp_read(words, b, base,     false);
    maid_mp_read(words, e, exponent, false);

    u8 power[128 / 8] = {0};
    maid_mp_exp(words, b, e);

    /* Big endian */
    maid_mp_write(words, b, power, true);

    for (size_t i = 0; i < sizeof(power); i++)
        printf("%02x", power[i]);
    printf("\n");

    return EXIT_SUCCESS;
}

Without installation:

cc -static -Iinclude example.c -Lbuild -lmaid

With installation:

cc example.c -lmaid