Main Page Modules Data Structures File List Data Fields Globals Related Pages

# beecrypt/mp32barrett.c File Reference

Barrett modular reduction, code. More...

`#include "system.h"`
`#include "mp32.h"`
`#include "mp32prime.h"`
`#include "mp32barrett.h"`
`#include "debug.h"`

Go to the source code of this file.

## Functions

void | mp32bzero (mp32barrett *b)
| mp32bzero. More...
void | mp32binit (mp32barrett *b, uint32 size)
| Allocates the data words for an mp32barrett structure. More...
void | mp32bfree (mp32barrett *b)
| mp32bfree. More...
void | mp32bcopy (mp32barrett *b, const mp32barrett *copy)
void | mp32bset (mp32barrett *b, uint32 size, const uint32 *data)
| mp32bset. More...
void | mp32bsethex (mp32barrett *b, const char *hex)
void | mp32bmu_w (mp32barrett *b, uint32 *wksp)
| Computes the Barrett 'mu' coefficient. More...
void | mp32brnd_w (const mp32barrett *b, randomGeneratorContext *rc, uint32 *result, uint32 *wksp)
| Generates a random number in the range 1 < r < b-1. More...
void | mp32brndodd_w (const mp32barrett *b, randomGeneratorContext *rc, uint32 *result, uint32 *wksp)
| Generates a random odd number in the range 1 < r < b-1. More...
void | mp32brndinv_w (const mp32barrett *b, randomGeneratorContext *rc, uint32 *result, uint32 *inverse, uint32 *wksp)
| Generates a random invertible (modulo b) in the range 1 < r < b-1. More...
void | mp32bmod_w (const mp32barrett *b, const uint32 *xdata, uint32 *result, uint32 *wksp)
| Computes the barrett modular reduction of a number x, which has twice the size of b. More...
void | mp32bsubone (const mp32barrett *b, uint32 *result)
| Copies (b-1) into result. More...
void | mp32bneg (const mp32barrett *b, const uint32 *xdata, uint32 *result)
| Computes the negative (modulo b) of x, where x must contain a value between 0 and b-1. More...
void | mp32baddmod_w (const mp32barrett *b, uint32 xsize, const uint32 *xdata, uint32 ysize, const uint32 *ydata, uint32 *result, uint32 *wksp)
| Computes the sum (modulo b) of x and y. More...
void | mp32bsubmod_w (const mp32barrett *b, uint32 xsize, const uint32 *xdata, uint32 ysize, const uint32 *ydata, uint32 *result, uint32 *wksp)
| Computes the difference (modulo b) of x and y. More...
void | mp32bmulmod_w (const mp32barrett *b, uint32 xsize, const uint32 *xdata, uint32 ysize, const uint32 *ydata, uint32 *result, uint32 *wksp)
| Computes the product (modulo b) of x and y. More...
void | mp32bsqrmod_w (const mp32barrett *b, uint32 xsize, const uint32 *xdata, uint32 *result, uint32 *wksp)
| Computes the square (modulo b) of x. More...
void | mp32bslide_w (const mp32barrett *b, const uint32 xsize, const uint32 *xdata, uint32 *slide, uint32 *wksp)
| Precomputes the sliding window table for computing powers of x modulo b. More...
void | mp32bpowmod_w (const mp32barrett *b, uint32 xsize, const uint32 *xdata, uint32 psize, const uint32 *pdata, uint32 *result, uint32 *wksp)
| mp32bpowmod_w needs workspace of 4*size+2 words. More...
void | mp32bpowmodsld_w (const mp32barrett *b, const uint32 *slide, uint32 psize, const uint32 *pdata, uint32 *result, uint32 *wksp)
void | mp32btwopowmod_w (const mp32barrett *b, uint32 psize, const uint32 *pdata, uint32 *result, uint32 *wksp)
| mp32btwopowmod_w needs workspace of (4*size+2) words. More...
int | mp32binv_w (const mp32barrett *b, uint32 xsize, const uint32 *xdata, uint32 *result, uint32 *wksp)
| Computes the inverse (modulo b) of x, and returns 1 if x was invertible. More...
int | mp32bpprime_w (const mp32barrett *b, randomGeneratorContext *rc, int t, uint32 *wksp)
| needs workspace of (7*size+2) words. More...
void | mp32bnrnd (const mp32barrett *b, randomGeneratorContext *rc, mp32number *result)
void | mp32bnmulmod (const mp32barrett *b, const mp32number *x, const mp32number *y, mp32number *result)
void | mp32bnsqrmod (const mp32barrett *b, const mp32number *x, mp32number *result)
void | mp32bnpowmod (const mp32barrett *b, const mp32number *x, const mp32number *pow, mp32number *y)
void | mp32bnpowmodsld (const mp32barrett *b, const uint32 *slide, const mp32number *pow, mp32number *y)

## Variables

byte | mp32bslide_presq [16]
byte | mp32bslide_mulg [16]
byte | mp32bslide_postsq [16]
int | _debug = 0

## Detailed Description

Barrett modular reduction, code.

For more information on this algorithm, see: "Handbook of Applied Cryptography", Chapter 14.3.3 Menezes, van Oorschot, Vanstone CRC Press

Definition in file mp32barrett.c.

## Function Documentation

void mp32baddmod_w | ( | const mp32barrett * | b,
|  | uint32 | xsize,
|  | const uint32 * | xdata,
|  | uint32 | ysize,
|  | const uint32 * | ydata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Computes the sum (modulo b) of x and y. needs a workspace of (4*size+2) words Definition at line 428 of file mp32barrett.c. References mp32addx, mp32bmod_w, mp32setx, mp32barrett::size, and uint32.

void mp32bcopy | ( | mp32barrett * | b,
|  | const mp32barrett * | copy
| ) |

| Definition at line 85 of file mp32barrett.c. References mp32barrett::modl, mp32copy, mp32barrett::mu, mp32barrett::size, and uint32.

void mp32bfree | ( | mp32barrett * | b | ) |

| mp32bfree. Definition at line 72 of file mp32barrett.c. References mp32barrett::modl, mp32barrett::mu, mp32barrett::size, and uint32.

void mp32binit | ( | mp32barrett * | b,
|  | uint32 | size
| ) |

| Allocates the data words for an mp32barrett structure. will allocate 2*size+1 words Definition at line 55 of file mp32barrett.c. References mp32barrett::modl, mp32barrett::mu, mp32barrett::size, and uint32.

int mp32binv_w | ( | const mp32barrett * | b,
|  | uint32 | xsize,
|  | const uint32 * | xdata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Computes the inverse (modulo b) of x, and returns 1 if x was invertible. Definition at line 940 of file mp32barrett.c. References _debug, mp32barrett::modl, mp32add, mp32divtwo, mp32even, mp32isone, mp32neg, mp32nz, mp32odd, mp32println, mp32sdivtwo, mp32setw, mp32setx, mp32sub, mp32subw, mp32zero, mp32barrett::size, and uint32.

void mp32bmod_w | ( | const mp32barrett * | b,
|  | const uint32 * | xdata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Computes the barrett modular reduction of a number x, which has twice the size of b. needs workspace of (2*size+2) words Definition at line 337 of file mp32barrett.c. References mp32barrett::modl, mp32addmul, mp32copy, mp32gex, mp32setmul, mp32setx, mp32sub, mp32subx, mp32barrett::mu, mp32barrett::size, and uint32.

void mp32bmu_w | ( | mp32barrett * | b,
|  | uint32 * | wksp
| ) |

| Computes the Barrett 'mu' coefficient. needs workspace of (6*size+4) words Definition at line 232 of file mp32barrett.c. References mp32barrett::modl, mp32copy, mp32ndivmod, mp32norm, mp32rshift, mp32zero, mp32barrett::mu, mp32barrett::size, and uint32.

void mp32bmulmod_w | ( | const mp32barrett * | b,
|  | uint32 | xsize,
|  | const uint32 * | xdata,
|  | uint32 | ysize,
|  | const uint32 * | ydata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Computes the product (modulo b) of x and y. needs a workspace of (4*size+2) words Definition at line 461 of file mp32barrett.c. References mp32bmod_w, mp32mul, mp32zero, mp32barrett::size, and uint32.

void mp32bneg | ( | const mp32barrett * | b,
|  | const uint32 * | xdata,
|  | uint32 * | result
| ) |

| Computes the negative (modulo b) of x, where x must contain a value between 0 and b-1. Definition at line 414 of file mp32barrett.c. References mp32barrett::modl, mp32add, mp32copy, mp32neg, mp32barrett::size, and uint32.

void mp32bnmulmod | ( | const mp32barrett * | b,
|  | const mp32number * | x,
|  | const mp32number * | y,
|  | mp32number * | result
| ) |

Note:
  Takes mp32number as parameter.

Definition at line 1218 of file mp32barrett.c.

References mp32number::data, mp32bmod_w, mp32mul, mp32nfree, mp32nsize, mp32zero, mp32number::size, mp32barrett::size, and uint32.

void mp32bnpowmod | ( | const mp32barrett * | b,
|  | const mp32number * | x,
|  | const mp32number * | pow,
|  | mp32number * | y
| ) |

Note:
  Takes mp32number as parameter.

Definition at line 1272 of file mp32barrett.c.

References mp32number::data, mp32bpowmod_w, mp32nfree, mp32nsize, mp32number::size, mp32barrett::size, and uint32.

void mp32bnpowmodsld | ( | const mp32barrett * | b,
|  | const uint32 * | slide,
|  | const mp32number * | pow,
|  | mp32number * | y
| ) |

Note:
  Takes mp32number as parameter.

Definition at line 1287 of file mp32barrett.c.

References mp32number::data, mp32bpowmodsld_w, mp32nfree, mp32nsize, mp32number::size, mp32barrett::size, and uint32.

void mp32bnrnd | ( | const mp32barrett * | b,
|  | randomGeneratorContext * | rc,
|  | mp32number * | result
| ) |

Note:
  Takes mp32number as parameter.

Definition at line 1202 of file mp32barrett.c.

References mp32number::data, mp32brnd_w, mp32nfree, mp32nsize, mp32barrett::size, and uint32.

void mp32bnsqrmod | ( | const mp32barrett * | b,
|  | const mp32number * | x,
|  | mp32number * | result
| ) |

Note:
  Takes mp32number as parameter.

Definition at line 1245 of file mp32barrett.c.

References mp32number::data, mp32bmod_w, mp32nfree, mp32nsize, mp32sqr, mp32zero, mp32number::size, mp32barrett::size, and uint32.

void mp32bpowmod_w | ( | const mp32barrett * | b,
|  | uint32 | xsize,
|  | const uint32 * | xdata,
|  | uint32 | psize,
|  | const uint32 * | pdata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| mp32bpowmod_w needs workspace of 4*size+2 words. Definition at line 566 of file mp32barrett.c. References mp32bpowmodsld_w, mp32bslide_w, mp32barrett::size, and uint32.

void mp32bpowmodsld_w | ( | const mp32barrett * | b,
|  | const uint32 * | slide,
|  | uint32 | psize,
|  | const uint32 * | pdata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Definition at line 606 of file mp32barrett.c. References mp32bmulmod_w, mp32bslide_mulg, mp32bslide_postsq, mp32bslide_presq, mp32bsqrmod_w, mp32setw, mp32barrett::size, uint32, and uint8.

int mp32bpprime_w | ( | const mp32barrett * | b,
|  | randomGeneratorContext * | rc,
|  | int | t,
|  | uint32 * | wksp
| ) |

| needs workspace of (7*size+2) words. Definition at line 1151 of file mp32barrett.c. References mp32barrett::modl, mp32gcd_w, mp32isone, mp32odd, mp32pmilrab_w, mp32setx, mp32barrett::size, SMALL_PRIMES_PRODUCT_MAX, and uint32.

void mp32brnd_w | ( | const mp32barrett * | b,
|  | randomGeneratorContext * | rc,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Generates a random number in the range 1 < r < b-1. need workspace of (size) words Definition at line 259 of file mp32barrett.c. References mp32barrett::modl, mp32copy, mp32ge, mp32leone, mp32mszcnt, mp32sub, mp32subw, randomGenerator::next, randomGeneratorContext::param, randomGeneratorContext::rng, mp32barrett::size, and uint32.

void mp32brndinv_w | ( | const mp32barrett * | b,
|  | randomGeneratorContext * | rc,
|  | uint32 * | result,
|  | uint32 * | inverse,
|  | uint32 * | wksp
| ) |

| Generates a random invertible (modulo b) in the range 1 < r < b-1. needs workspace of (6*size+6) words Definition at line 318 of file mp32barrett.c. References mp32barrett::modl, mp32binv_w, mp32brnd_w, mp32brndodd_w, mp32even, mp32barrett::size, and uint32.

void mp32brndodd_w | ( | const mp32barrett * | b,
|  | randomGeneratorContext * | rc,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Generates a random odd number in the range 1 < r < b-1. needs workspace of (size) words Definition at line 287 of file mp32barrett.c. References mp32barrett::modl, mp32copy, mp32ge, mp32leone, mp32mszcnt, mp32setlsb, mp32sub, mp32subw, randomGenerator::next, randomGeneratorContext::param, randomGeneratorContext::rng, mp32barrett::size, and uint32.

void mp32bset | ( | mp32barrett * | b,
|  | uint32 | size,
|  | const uint32 * | data
| ) |

| mp32bset. Definition at line 129 of file mp32barrett.c. References mp32barrett::modl, mp32bmu_w, mp32copy, mp32barrett::mu, mp32barrett::size, and uint32.

void mp32bsethex | ( | mp32barrett * | b,
|  | const char * | hex
| ) |

| Definition at line 166 of file mp32barrett.c. References mp32barrett::modl, mp32bmu_w, mp32barrett::mu, mp32barrett::size, uint32, and uint8.

void mp32bslide_w | ( | const mp32barrett * | b,
|  | const uint32 | xsize,
|  | const uint32 * | xdata,
|  | uint32 * | slide,
|  | uint32 * | wksp
| ) | `[static]`

Precomputes the sliding window table for computing powers of x modulo b.

needs workspace (4*size+2)

Sliding Window Exponentiation technique, slightly altered from the method Applied Cryptography:

First of all, the table with the powers of g can be reduced by about half; the even powers don't need to be accessed or stored.

Get up to K bits starting with a one, if we have that many still available

Do the number of squarings of A in the first column, the multiply by the value in column two, and finally do the number of squarings in column three.

This table can be used for K=2,3,4 and can be extended

               0 : - | -       | -
               1 : 1 |  g1 @ 0 | 0
              10 : 1 |  g1 @ 0 | 1
              11 : 2 |  g3 @ 1 | 0
             100 : 1 |  g1 @ 0 | 2
             101 : 3 |  g5 @ 2 | 0
             110 : 2 |  g3 @ 1 | 1
             111 : 3 |  g7 @ 3 | 0
            1000 : 1 |  g1 @ 0 | 3
            1001 : 4 |  g9 @ 4 | 0
            1010 : 3 |  g5 @ 2 | 1
            1011 : 4 | g11 @ 5 | 0
            1100 : 2 |  g3 @ 1 | 2
            1101 : 4 | g13 @ 6 | 0
            1110 : 3 |  g7 @ 3 | 1
            1111 : 4 | g15 @ 7 | 0

Definition at line 534 of file mp32barrett.c.

References mp32bmulmod_w, mp32bsqrmod_w, mp32setx, and uint32.

Referenced by mp32bpowmod_w.

void mp32bsqrmod_w | ( | const mp32barrett * | b,
|  | uint32 | xsize,
|  | const uint32 * | xdata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Computes the square (modulo b) of x. needs a workspace of (4*size+2) words Definition at line 481 of file mp32barrett.c. References mp32bmod_w, mp32sqr, mp32zero, mp32barrett::size, and uint32.

void mp32bsubmod_w | ( | const mp32barrett * | b,
|  | uint32 | xsize,
|  | const uint32 * | xdata,
|  | uint32 | ysize,
|  | const uint32 * | ydata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| Computes the difference (modulo b) of x and y. needs a workspace of (4*size+2) words Definition at line 444 of file mp32barrett.c. References mp32barrett::modl, mp32addx, mp32bmod_w, mp32setx, mp32subx, mp32barrett::size, and uint32.

void mp32bsubone | ( | const mp32barrett * | b,
|  | uint32 * | result
| ) |

| Copies (b-1) into result. Definition at line 401 of file mp32barrett.c. References mp32barrett::modl, mp32copy, mp32subw, mp32barrett::size, and uint32.

void mp32btwopowmod_w | ( | const mp32barrett * | b,
|  | uint32 | psize,
|  | const uint32 * | pdata,
|  | uint32 * | result,
|  | uint32 * | wksp
| ) |

| mp32btwopowmod_w needs workspace of (4*size+2) words. Definition at line 711 of file mp32barrett.c. References mp32barrett::modl, mp32add, mp32bsqrmod_w, mp32ge, mp32setw, mp32sub, mp32barrett::size, and uint32.

void mp32bzero | ( | mp32barrett * | b | ) |

| mp32bzero. Definition at line 43 of file mp32barrett.c. References mp32barrett::modl, mp32barrett::mu, mp32barrett::size, and uint32.

## Variable Documentation

int _debug = 0`[static]`

| Definition at line 932 of file mp32barrett.c. Referenced by mp32binv_w.

byte mp32bslide_mulg[16]`[static]`

Initial value:

    { 0, 0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7 }

Definition at line 554 of file mp32barrett.c.

Referenced by mp32bpowmodsld_w.

byte mp32bslide_postsq[16]`[static]`

Initial value:

    { 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 }

Definition at line 558 of file mp32barrett.c.

Referenced by mp32bpowmodsld_w.

byte mp32bslide_presq[16]`[static]`

Initial value:

    { 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 4, 2, 4, 3, 4 }

Definition at line 550 of file mp32barrett.c.

Referenced by mp32bpowmodsld_w.