ReactOS  0.4.12-dev-945-g5a2911d
mpi.c File Reference
#include <stdarg.h>
#include <windef.h>
#include <winbase.h>
#include "tomcrypt.h"
Include dependency graph for mpi.c:

Go to the source code of this file.

Macros

#define s_mp_mul(a, b, c)   s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1)
 

Functions

static void mp_clamp (mp_int *a)
 
static int mp_cmp_mag (const mp_int *a, const mp_int *b)
 
static int mp_cnt_lsb (const mp_int *a)
 
static int mp_montgomery_calc_normalization (mp_int *a, const mp_int *b)
 
static int mp_montgomery_reduce (mp_int *a, const mp_int *m, mp_digit mp)
 
static int mp_montgomery_setup (const mp_int *a, mp_digit *mp)
 
static int mp_reduce (mp_int *a, const mp_int *b, const mp_int *c)
 
static int mp_reduce_2k (mp_int *a, const mp_int *n, mp_digit d)
 
static int mp_reduce_2k_setup (const mp_int *a, mp_digit *d)
 
static int mp_reduce_setup (mp_int *a, const mp_int *b)
 
static void mp_set (mp_int *a, mp_digit b)
 
static int mp_sqr (const mp_int *a, mp_int *b)
 
static int mp_sqrmod (const mp_int *a, mp_int *b, mp_int *c)
 
static void bn_reverse (unsigned char *s, int len)
 
static int s_mp_add (mp_int *a, mp_int *b, mp_int *c)
 
static int s_mp_exptmod (const mp_int *G, const mp_int *X, mp_int *P, mp_int *Y)
 
static int s_mp_mul_digs (const mp_int *a, const mp_int *b, mp_int *c, int digs)
 
static int s_mp_mul_high_digs (const mp_int *a, const mp_int *b, mp_int *c, int digs)
 
static int s_mp_sqr (const mp_int *a, mp_int *b)
 
static int s_mp_sub (const mp_int *a, const mp_int *b, mp_int *c)
 
static int mp_exptmod_fast (const mp_int *G, const mp_int *X, mp_int *P, mp_int *Y, int mode)
 
static int mp_invmod_slow (const mp_int *a, mp_int *b, mp_int *c)
 
static int mp_karatsuba_mul (const mp_int *a, const mp_int *b, mp_int *c)
 
static int mp_karatsuba_sqr (const mp_int *a, mp_int *b)
 
static int mp_grow (mp_int *a, int size)
 
static int mp_div_2 (const mp_int *a, mp_int *b)
 
static void mp_exch (mp_int *a, mp_int *b)
 
static int mp_init (mp_int *a)
 
static int mp_init_size (mp_int *a, int size)
 
static void mp_clear (mp_int *a)
 
static void mp_zero (mp_int *a)
 
static int mp_abs (const mp_int *a, mp_int *b)
 
static int fast_mp_invmod (const mp_int *a, mp_int *b, mp_int *c)
 
static int fast_mp_montgomery_reduce (mp_int *x, const mp_int *n, mp_digit rho)
 
static int fast_s_mp_mul_digs (const mp_int *a, const mp_int *b, mp_int *c, int digs)
 
static int fast_s_mp_mul_high_digs (const mp_int *a, const mp_int *b, mp_int *c, int digs)
 
static int fast_s_mp_sqr (const mp_int *a, mp_int *b)
 
static int mp_2expt (mp_int *a, int b)
 
int mp_add (mp_int *a, mp_int *b, mp_int *c)
 
static int mp_add_d (mp_int *a, mp_digit b, mp_int *c)
 
void mp_clear_multi (mp_int *mp,...)
 
int mp_cmp (const mp_int *a, const mp_int *b)
 
int mp_cmp_d (const mp_int *a, mp_digit b)
 
int mp_copy (const mp_int *a, mp_int *b)
 
int mp_count_bits (const mp_int *a)
 
static int mp_mod_2d (const mp_int *a, int b, mp_int *c)
 
static void mp_rshd (mp_int *a, int b)
 
static int mp_div_2d (const mp_int *a, int b, mp_int *c, mp_int *d)
 
static int mp_lshd (mp_int *a, int b)
 
static int mp_mul_2d (const mp_int *a, int b, mp_int *c)
 
static int mp_mul_d (const mp_int *a, mp_digit b, mp_int *c)
 
static int mp_div (const mp_int *a, const mp_int *b, mp_int *c, mp_int *d)
 
static BOOL s_is_power_of_two (mp_digit b, int *p)
 
static int mp_div_d (const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
 
static int mp_dr_reduce (mp_int *x, const mp_int *n, mp_digit k)
 
static void mp_dr_setup (const mp_int *a, mp_digit *d)
 
int mp_exptmod (const mp_int *G, const mp_int *X, mp_int *P, mp_int *Y)
 
int mp_gcd (const mp_int *a, const mp_int *b, mp_int *c)
 
unsigned long mp_get_int (const mp_int *a)
 
int mp_init_copy (mp_int *a, const mp_int *b)
 
int mp_init_multi (mp_int *mp,...)
 
int mp_invmod (const mp_int *a, mp_int *b, mp_int *c)
 
int mp_lcm (const mp_int *a, const mp_int *b, mp_int *c)
 
int mp_mod (const mp_int *a, mp_int *b, mp_int *c)
 
static int mp_mod_d (const mp_int *a, mp_digit b, mp_digit *c)
 
static int mp_mul_2 (const mp_int *a, mp_int *b)
 
int mp_mul (const mp_int *a, const mp_int *b, mp_int *c)
 
int mp_mulmod (const mp_int *a, const mp_int *b, mp_int *c, mp_int *d)
 
static int mp_prime_is_divisible (const mp_int *a, int *result)
 
static int mp_prime_miller_rabin (mp_int *a, const mp_int *b, int *result)
 
static int mp_prime_is_prime (mp_int *a, int t, int *result)
 
int mp_prime_rabin_miller_trials (int size)
 
int mp_prime_random_ex (mp_int *a, int t, int size, int flags, ltm_prime_callback cb, void *dat)
 
int mp_read_unsigned_bin (mp_int *a, const unsigned char *b, int c)
 
int mp_set_int (mp_int *a, unsigned long b)
 
int mp_shrink (mp_int *a)
 
int mp_sub (mp_int *a, mp_int *b, mp_int *c)
 
int mp_sub_d (mp_int *a, mp_digit b, mp_int *c)
 
int mp_to_unsigned_bin (const mp_int *a, unsigned char *b)
 
int mp_unsigned_bin_size (const mp_int *a)
 

Variables

static const int KARATSUBA_MUL_CUTOFF = 88
 
static const int KARATSUBA_SQR_CUTOFF = 128
 
static const int lnz [16]
 
static const mp_digit __prime_tab []
 
struct {
   int   k
 
   int   t
 
sizes []
 

Macro Definition Documentation

◆ s_mp_mul

#define s_mp_mul (   a,
  b,
  c 
)    s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1)

Definition at line 95 of file mpi.c.

Function Documentation

◆ bn_reverse()

static void bn_reverse ( unsigned char s,
int  len 
)
static

Definition at line 3907 of file mpi.c.

3908 {
3909  int ix, iy;
3910  unsigned char t;
3911 
3912  ix = 0;
3913  iy = len - 1;
3914  while (ix < iy) {
3915  t = s[ix];
3916  s[ix] = s[iy];
3917  s[iy] = t;
3918  ++ix;
3919  --iy;
3920  }
3921 }
GLdouble GLdouble t
Definition: gl.h:2047
int t
Definition: mpi.c:3369
int iy
Definition: tritemp.h:491
GLenum GLsizei len
Definition: glext.h:6722
GLdouble s
Definition: gl.h:2039

Referenced by mp_to_unsigned_bin().

◆ fast_mp_invmod()

static int fast_mp_invmod ( const mp_int a,
mp_int b,
mp_int c 
)
static

Definition at line 314 of file mpi.c.

315 {
316  mp_int x, y, u, v, B, D;
317  int res, neg;
318 
319  /* 2. [modified] b must be odd */
320  if (mp_iseven (b) == 1) {
321  return MP_VAL;
322  }
323 
324  /* init all our temps */
325  if ((res = mp_init_multi(&x, &y, &u, &v, &B, &D, NULL)) != MP_OKAY) {
326  return res;
327  }
328 
329  /* x == modulus, y == value to invert */
330  if ((res = mp_copy (b, &x)) != MP_OKAY) {
331  goto __ERR;
332  }
333 
334  /* we need y = |a| */
335  if ((res = mp_abs (a, &y)) != MP_OKAY) {
336  goto __ERR;
337  }
338 
339  /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
340  if ((res = mp_copy (&x, &u)) != MP_OKAY) {
341  goto __ERR;
342  }
343  if ((res = mp_copy (&y, &v)) != MP_OKAY) {
344  goto __ERR;
345  }
346  mp_set (&D, 1);
347 
348 top:
349  /* 4. while u is even do */
350  while (mp_iseven (&u) == 1) {
351  /* 4.1 u = u/2 */
352  if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
353  goto __ERR;
354  }
355  /* 4.2 if B is odd then */
356  if (mp_isodd (&B) == 1) {
357  if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
358  goto __ERR;
359  }
360  }
361  /* B = B/2 */
362  if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
363  goto __ERR;
364  }
365  }
366 
367  /* 5. while v is even do */
368  while (mp_iseven (&v) == 1) {
369  /* 5.1 v = v/2 */
370  if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
371  goto __ERR;
372  }
373  /* 5.2 if D is odd then */
374  if (mp_isodd (&D) == 1) {
375  /* D = (D-x)/2 */
376  if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
377  goto __ERR;
378  }
379  }
380  /* D = D/2 */
381  if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
382  goto __ERR;
383  }
384  }
385 
386  /* 6. if u >= v then */
387  if (mp_cmp (&u, &v) != MP_LT) {
388  /* u = u - v, B = B - D */
389  if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
390  goto __ERR;
391  }
392 
393  if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
394  goto __ERR;
395  }
396  } else {
397  /* v - v - u, D = D - B */
398  if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
399  goto __ERR;
400  }
401 
402  if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
403  goto __ERR;
404  }
405  }
406 
407  /* if not zero goto step 4 */
408  if (mp_iszero (&u) == 0) {
409  goto top;
410  }
411 
412  /* now a = C, b = D, gcd == g*v */
413 
414  /* if v != 1 then there is no inverse */
415  if (mp_cmp_d (&v, 1) != MP_EQ) {
416  res = MP_VAL;
417  goto __ERR;
418  }
419 
420  /* b is now the inverse */
421  neg = a->sign;
422  while (D.sign == MP_NEG) {
423  if ((res = mp_add (&D, b, &D)) != MP_OKAY) {
424  goto __ERR;
425  }
426  }
427  mp_exch (&D, c);
428  c->sign = neg;
429  res = MP_OKAY;
430 
431 __ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
432  return res;
433 }
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
int mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:891
void mp_clear_multi(mp_int *mp,...)
Definition: mpi.c:1032
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
static int mp_abs(const mp_int *a, mp_int *b)
Definition: mpi.c:290
int mp_cmp(const mp_int *a, const mp_int *b)
Definition: mpi.c:1046
#define MP_LT
Definition: tomcrypt.h:193
static void mp_set(mp_int *a, mp_digit b)
Definition: mpi.c:3679
int mp_cmp_d(const mp_int *a, mp_digit b)
Definition: mpi.c:1067
smooth NULL
Definition: ftsmooth.c:416
#define MP_EQ
Definition: tomcrypt.h:194
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define mp_isodd(a)
Definition: tomcrypt.h:250
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
const GLubyte * c
Definition: glext.h:8905
#define mp_iszero(a)
Definition: tomcrypt.h:248
#define MP_VAL
Definition: tomcrypt.h:202
#define MP_OKAY
Definition: tomcrypt.h:200
#define mp_iseven(a)
Definition: tomcrypt.h:249
#define D(name, bit)
const GLdouble * v
Definition: gl.h:2040
#define MP_NEG
Definition: tomcrypt.h:198
#define B(row, col)
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
static int mp_div_2(const mp_int *a, mp_int *b)
Definition: mpi.c:142
GLuint res
Definition: glext.h:9613
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
int mp_sub(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:3771
int mp_init_multi(mp_int *mp,...)
Definition: mpi.c:2354

Referenced by mp_invmod().

◆ fast_mp_montgomery_reduce()

static int fast_mp_montgomery_reduce ( mp_int x,
const mp_int n,
mp_digit  rho 
)
static

Definition at line 444 of file mpi.c.

445 {
446  int ix, res, olduse;
448 
449  /* get old used count */
450  olduse = x->used;
451 
452  /* grow a as required */
453  if (x->alloc < n->used + 1) {
454  if ((res = mp_grow (x, n->used + 1)) != MP_OKAY) {
455  return res;
456  }
457  }
458 
459  /* first we have to get the digits of the input into
460  * an array of double precision words W[...]
461  */
462  {
463  register mp_word *_W;
464  register mp_digit *tmpx;
465 
466  /* alias for the W[] array */
467  _W = W;
468 
469  /* alias for the digits of x*/
470  tmpx = x->dp;
471 
472  /* copy the digits of a into W[0..a->used-1] */
473  for (ix = 0; ix < x->used; ix++) {
474  *_W++ = *tmpx++;
475  }
476 
477  /* zero the high words of W[a->used..m->used*2] */
478  for (; ix < n->used * 2 + 1; ix++) {
479  *_W++ = 0;
480  }
481  }
482 
483  /* now we proceed to zero successive digits
484  * from the least significant upwards
485  */
486  for (ix = 0; ix < n->used; ix++) {
487  /* mu = ai * m' mod b
488  *
489  * We avoid a double precision multiplication (which isn't required)
490  * by casting the value down to a mp_digit. Note this requires
491  * that W[ix-1] have the carry cleared (see after the inner loop)
492  */
493  register mp_digit mu;
494  mu = (mp_digit) (((W[ix] & MP_MASK) * rho) & MP_MASK);
495 
496  /* a = a + mu * m * b**i
497  *
498  * This is computed in place and on the fly. The multiplication
499  * by b**i is handled by offsetting which columns the results
500  * are added to.
501  *
502  * Note the comba method normally doesn't handle carries in the
503  * inner loop In this case we fix the carry from the previous
504  * column since the Montgomery reduction requires digits of the
505  * result (so far) [see above] to work. This is
506  * handled by fixing up one carry after the inner loop. The
507  * carry fixups are done in order so after these loops the
508  * first m->used words of W[] have the carries fixed
509  */
510  {
511  register int iy;
512  register mp_digit *tmpn;
513  register mp_word *_W;
514 
515  /* alias for the digits of the modulus */
516  tmpn = n->dp;
517 
518  /* Alias for the columns set by an offset of ix */
519  _W = W + ix;
520 
521  /* inner loop */
522  for (iy = 0; iy < n->used; iy++) {
523  *_W++ += ((mp_word)mu) * ((mp_word)*tmpn++);
524  }
525  }
526 
527  /* now fix carry for next digit, W[ix+1] */
528  W[ix + 1] += W[ix] >> ((mp_word) DIGIT_BIT);
529  }
530 
531  /* now we have to propagate the carries and
532  * shift the words downward [all those least
533  * significant digits we zeroed].
534  */
535  {
536  register mp_digit *tmpx;
537  register mp_word *_W, *_W1;
538 
539  /* nox fix rest of carries */
540 
541  /* alias for current word */
542  _W1 = W + ix;
543 
544  /* alias for next word, where the carry goes */
545  _W = W + ++ix;
546 
547  for (; ix <= n->used * 2 + 1; ix++) {
548  *_W++ += *_W1++ >> ((mp_word) DIGIT_BIT);
549  }
550 
551  /* copy out, A = A/b**n
552  *
553  * The result is A/b**n but instead of converting from an
554  * array of mp_word to mp_digit than calling mp_rshd
555  * we just copy them in the right order
556  */
557 
558  /* alias for destination word */
559  tmpx = x->dp;
560 
561  /* alias for shifted double precision result */
562  _W = W + n->used;
563 
564  for (ix = 0; ix < n->used + 1; ix++) {
565  *tmpx++ = (mp_digit)(*_W++ & ((mp_word) MP_MASK));
566  }
567 
568  /* zero oldused digits, if the input a was larger than
569  * m->used+1 we'll have to clear the digits
570  */
571  for (; ix < olduse; ix++) {
572  *tmpx++ = 0;
573  }
574  }
575 
576  /* set the max used and clamp */
577  x->used = n->used + 1;
578  mp_clamp (x);
579 
580  /* if A >= m then A = A - m */
581  if (mp_cmp_mag (x, n) != MP_LT) {
582  return s_mp_sub (x, n, x);
583  }
584  return MP_OKAY;
585 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
#define MP_MASK
Definition: tomcrypt.h:189
GLdouble n
Definition: glext.h:7729
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
int iy
Definition: tritemp.h:491
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
#define MP_LT
Definition: tomcrypt.h:193
Definition: polytest.cpp:35
static int s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:4412
struct W W
#define MP_WARRAY
Definition: tomcrypt.h:222
#define MP_OKAY
Definition: tomcrypt.h:200
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_exptmod_fast(), and mp_montgomery_reduce().

◆ fast_s_mp_mul_digs()

static int fast_s_mp_mul_digs ( const mp_int a,
const mp_int b,
mp_int c,
int  digs 
)
static

Definition at line 604 of file mpi.c.

605 {
606  int olduse, res, pa, ix, iz;
608  register mp_word _W;
609 
610  /* grow the destination as required */
611  if (c->alloc < digs) {
612  if ((res = mp_grow (c, digs)) != MP_OKAY) {
613  return res;
614  }
615  }
616 
617  /* number of output digits to produce */
618  pa = MIN(digs, a->used + b->used);
619 
620  /* clear the carry */
621  _W = 0;
622  for (ix = 0; ix <= pa; ix++) {
623  int tx, ty;
624  int iy;
625  mp_digit *tmpx, *tmpy;
626 
627  /* get offsets into the two bignums */
628  ty = MIN(b->used-1, ix);
629  tx = ix - ty;
630 
631  /* setup temp aliases */
632  tmpx = a->dp + tx;
633  tmpy = b->dp + ty;
634 
635  /* This is the number of times the loop will iterate, essentially it's
636  while (tx++ < a->used && ty-- >= 0) { ... }
637  */
638  iy = MIN(a->used-tx, ty+1);
639 
640  /* execute loop */
641  for (iz = 0; iz < iy; ++iz) {
642  _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
643  }
644 
645  /* store term */
646  W[ix] = ((mp_digit)_W) & MP_MASK;
647 
648  /* make next carry */
649  _W = _W >> ((mp_word)DIGIT_BIT);
650  }
651 
652  /* setup dest */
653  olduse = c->used;
654  c->used = digs;
655 
656  {
657  register mp_digit *tmpc;
658  tmpc = c->dp;
659  for (ix = 0; ix < digs; ix++) {
660  /* now extract the previous digit [below the carry] */
661  *tmpc++ = W[ix];
662  }
663 
664  /* clear unused digits [that existed in the old copy of c] */
665  for (; ix < olduse; ix++) {
666  *tmpc++ = 0;
667  }
668  }
669  mp_clamp (c);
670  return MP_OKAY;
671 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
#define MP_MASK
Definition: tomcrypt.h:189
int iy
Definition: tritemp.h:491
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
T MIN(T a, T b)
Definition: polytest.cpp:79
Definition: polytest.cpp:35
GLbyte ty
Definition: glext.h:8756
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
#define MP_WARRAY
Definition: tomcrypt.h:222
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_mul(), and s_mp_mul_digs().

◆ fast_s_mp_mul_high_digs()

static int fast_s_mp_mul_high_digs ( const mp_int a,
const mp_int b,
mp_int c,
int  digs 
)
static

Definition at line 683 of file mpi.c.

684 {
685  int olduse, res, pa, ix, iz;
687  mp_word _W;
688 
689  /* grow the destination as required */
690  pa = a->used + b->used;
691  if (c->alloc < pa) {
692  if ((res = mp_grow (c, pa)) != MP_OKAY) {
693  return res;
694  }
695  }
696 
697  /* number of output digits to produce */
698  pa = a->used + b->used;
699  _W = 0;
700  for (ix = digs; ix <= pa; ix++) {
701  int tx, ty, iy;
702  mp_digit *tmpx, *tmpy;
703 
704  /* get offsets into the two bignums */
705  ty = MIN(b->used-1, ix);
706  tx = ix - ty;
707 
708  /* setup temp aliases */
709  tmpx = a->dp + tx;
710  tmpy = b->dp + ty;
711 
712  /* This is the number of times the loop will iterate, essentially it's
713  while (tx++ < a->used && ty-- >= 0) { ... }
714  */
715  iy = MIN(a->used-tx, ty+1);
716 
717  /* execute loop */
718  for (iz = 0; iz < iy; iz++) {
719  _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
720  }
721 
722  /* store term */
723  W[ix] = ((mp_digit)_W) & MP_MASK;
724 
725  /* make next carry */
726  _W = _W >> ((mp_word)DIGIT_BIT);
727  }
728 
729  /* setup dest */
730  olduse = c->used;
731  c->used = pa;
732 
733  {
734  register mp_digit *tmpc;
735 
736  tmpc = c->dp + digs;
737  for (ix = digs; ix <= pa; ix++) {
738  /* now extract the previous digit [below the carry] */
739  *tmpc++ = W[ix];
740  }
741 
742  /* clear unused digits [that existed in the old copy of c] */
743  for (; ix < olduse; ix++) {
744  *tmpc++ = 0;
745  }
746  }
747  mp_clamp (c);
748  return MP_OKAY;
749 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
#define MP_MASK
Definition: tomcrypt.h:189
int iy
Definition: tritemp.h:491
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
T MIN(T a, T b)
Definition: polytest.cpp:79
Definition: polytest.cpp:35
GLbyte ty
Definition: glext.h:8756
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
#define MP_WARRAY
Definition: tomcrypt.h:222
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by s_mp_mul_high_digs().

◆ fast_s_mp_sqr()

static int fast_s_mp_sqr ( const mp_int a,
mp_int b 
)
static

Definition at line 780 of file mpi.c.

781 {
782  int olduse, res, pa, ix, iz;
783  mp_digit W[MP_WARRAY], *tmpx;
784  mp_word W1;
785 
786  /* grow the destination as required */
787  pa = a->used + a->used;
788  if (b->alloc < pa) {
789  if ((res = mp_grow (b, pa)) != MP_OKAY) {
790  return res;
791  }
792  }
793 
794  /* number of output digits to produce */
795  W1 = 0;
796  for (ix = 0; ix <= pa; ix++) {
797  int tx, ty, iy;
798  mp_word _W;
799  mp_digit *tmpy;
800 
801  /* clear counter */
802  _W = 0;
803 
804  /* get offsets into the two bignums */
805  ty = MIN(a->used-1, ix);
806  tx = ix - ty;
807 
808  /* setup temp aliases */
809  tmpx = a->dp + tx;
810  tmpy = a->dp + ty;
811 
812  /* This is the number of times the loop will iterate, essentially it's
813  while (tx++ < a->used && ty-- >= 0) { ... }
814  */
815  iy = MIN(a->used-tx, ty+1);
816 
817  /* now for squaring tx can never equal ty
818  * we halve the distance since they approach at a rate of 2x
819  * and we have to round because odd cases need to be executed
820  */
821  iy = MIN(iy, (ty-tx+1)>>1);
822 
823  /* execute loop */
824  for (iz = 0; iz < iy; iz++) {
825  _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
826  }
827 
828  /* double the inner product and add carry */
829  _W = _W + _W + W1;
830 
831  /* even columns have the square term in them */
832  if ((ix&1) == 0) {
833  _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]);
834  }
835 
836  /* store it */
837  W[ix] = _W;
838 
839  /* make next carry */
840  W1 = _W >> ((mp_word)DIGIT_BIT);
841  }
842 
843  /* setup dest */
844  olduse = b->used;
845  b->used = a->used+a->used;
846 
847  {
848  mp_digit *tmpb;
849  tmpb = b->dp;
850  for (ix = 0; ix < pa; ix++) {
851  *tmpb++ = W[ix] & MP_MASK;
852  }
853 
854  /* clear unused digits [that existed in the old copy of c] */
855  for (; ix < olduse; ix++) {
856  *tmpb++ = 0;
857  }
858  }
859  mp_clamp (b);
860  return MP_OKAY;
861 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
#define MP_MASK
Definition: tomcrypt.h:189
int iy
Definition: tritemp.h:491
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
T MIN(T a, T b)
Definition: polytest.cpp:79
Definition: polytest.cpp:35
GLbyte ty
Definition: glext.h:8756
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_WARRAY
Definition: tomcrypt.h:222
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_sqr().

◆ mp_2expt()

static int mp_2expt ( mp_int a,
int  b 
)
static

Definition at line 869 of file mpi.c.

870 {
871  int res;
872 
873  /* zero a as per default */
874  mp_zero (a);
875 
876  /* grow a to accommodate the single bit */
877  if ((res = mp_grow (a, b / DIGIT_BIT + 1)) != MP_OKAY) {
878  return res;
879  }
880 
881  /* set the used count of where the bit will go */
882  a->used = b / DIGIT_BIT + 1;
883 
884  /* put the single bit in its place */
885  a->dp[b / DIGIT_BIT] = ((mp_digit)1) << (b % DIGIT_BIT);
886 
887  return MP_OKAY;
888 }
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
static void mp_zero(mp_int *a)
Definition: mpi.c:278
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_montgomery_calc_normalization(), mp_reduce_2k_setup(), and mp_reduce_setup().

◆ mp_abs()

static int mp_abs ( const mp_int a,
mp_int b 
)
static

Definition at line 290 of file mpi.c.

291 {
292  int res;
293 
294  /* copy a to b */
295  if (a != b) {
296  if ((res = mp_copy (a, b)) != MP_OKAY) {
297  return res;
298  }
299  }
300 
301  /* force the sign of b to positive */
302  b->sign = MP_ZPOS;
303 
304  return MP_OKAY;
305 }
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_ZPOS
Definition: tomcrypt.h:197
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156

Referenced by fast_mp_invmod(), mp_exptmod(), and mp_gcd().

◆ mp_add()

int mp_add ( mp_int a,
mp_int b,
mp_int c 
)

Definition at line 891 of file mpi.c.

892 {
893  int sa, sb, res;
894 
895  /* get sign of both inputs */
896  sa = a->sign;
897  sb = b->sign;
898 
899  /* handle two cases, not four */
900  if (sa == sb) {
901  /* both positive or both negative */
902  /* add their magnitudes, copy the sign */
903  c->sign = sa;
904  res = s_mp_add (a, b, c);
905  } else {
906  /* one positive, the other negative */
907  /* subtract the one with the greater magnitude from */
908  /* the one of the lesser magnitude. The result gets */
909  /* the sign of the one with the greater magnitude. */
910  if (mp_cmp_mag (a, b) == MP_LT) {
911  c->sign = sb;
912  res = s_mp_sub (b, a, c);
913  } else {
914  c->sign = sa;
915  res = s_mp_sub (a, b, c);
916  }
917  }
918  return res;
919 }
superblock * sb
Definition: btrfs.c:3876
static int s_mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:3925
#define MP_LT
Definition: tomcrypt.h:193
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
static int s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:4412
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
static struct sockaddr_in sa
Definition: adnsresfilter.c:69

Referenced by fast_mp_invmod(), mp_div(), mp_invmod_slow(), mp_karatsuba_mul(), mp_karatsuba_sqr(), mp_mod(), mp_reduce(), and rsa_exptmod().

◆ mp_add_d()

static int mp_add_d ( mp_int a,
mp_digit  b,
mp_int c 
)
static

Definition at line 924 of file mpi.c.

925 {
926  int res, ix, oldused;
927  mp_digit *tmpa, *tmpc, mu;
928 
929  /* grow c as required */
930  if (c->alloc < a->used + 1) {
931  if ((res = mp_grow(c, a->used + 1)) != MP_OKAY) {
932  return res;
933  }
934  }
935 
936  /* if a is negative and |a| >= b, call c = |a| - b */
937  if (a->sign == MP_NEG && (a->used > 1 || a->dp[0] >= b)) {
938  /* temporarily fix sign of a */
939  a->sign = MP_ZPOS;
940 
941  /* c = |a| - b */
942  res = mp_sub_d(a, b, c);
943 
944  /* fix sign */
945  a->sign = c->sign = MP_NEG;
946 
947  return res;
948  }
949 
950  /* old number of used digits in c */
951  oldused = c->used;
952 
953  /* sign always positive */
954  c->sign = MP_ZPOS;
955 
956  /* source alias */
957  tmpa = a->dp;
958 
959  /* destination alias */
960  tmpc = c->dp;
961 
962  /* if a is positive */
963  if (a->sign == MP_ZPOS) {
964  /* add digit, after this we're propagating
965  * the carry.
966  */
967  *tmpc = *tmpa++ + b;
968  mu = *tmpc >> DIGIT_BIT;
969  *tmpc++ &= MP_MASK;
970 
971  /* now handle rest of the digits */
972  for (ix = 1; ix < a->used; ix++) {
973  *tmpc = *tmpa++ + mu;
974  mu = *tmpc >> DIGIT_BIT;
975  *tmpc++ &= MP_MASK;
976  }
977  /* set final carry */
978  ix++;
979  *tmpc++ = mu;
980 
981  /* setup size */
982  c->used = a->used + 1;
983  } else {
984  /* a was negative and |a| < b */
985  c->used = 1;
986 
987  /* the result is a single digit */
988  if (a->used == 1) {
989  *tmpc++ = b - a->dp[0];
990  } else {
991  *tmpc++ = b;
992  }
993 
994  /* setup count so the clearing of oldused
995  * can fall through correctly
996  */
997  ix = 1;
998  }
999 
1000  /* now zero to oldused */
1001  while (ix++ < oldused) {
1002  *tmpc++ = 0;
1003  }
1004  mp_clamp(c);
1005 
1006  return MP_OKAY;
1007 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
#define MP_MASK
Definition: tomcrypt.h:189
#define DIGIT_BIT
Definition: tomcrypt.h:186
#define b
Definition: ke_i.h:79
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
#define MP_ZPOS
Definition: tomcrypt.h:197
int mp_sub_d(mp_int *a, mp_digit b, mp_int *c)
Definition: mpi.c:3808
#define MP_OKAY
Definition: tomcrypt.h:200
#define MP_NEG
Definition: tomcrypt.h:198
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_prime_random_ex(), and mp_sub_d().

◆ mp_clamp()

void mp_clamp ( mp_int a)
static

Definition at line 1017 of file mpi.c.

1018 {
1019  /* decrease used while the most significant digit is
1020  * zero.
1021  */
1022  while (a->used > 0 && a->dp[a->used - 1] == 0) {
1023  --(a->used);
1024  }
1025 
1026  /* reset the sign flag if used == 0 */
1027  if (a->used == 0) {
1028  a->sign = MP_ZPOS;
1029  }
1030 }
#define MP_ZPOS
Definition: tomcrypt.h:197
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by fast_mp_montgomery_reduce(), fast_s_mp_mul_digs(), fast_s_mp_mul_high_digs(), fast_s_mp_sqr(), mp_add_d(), mp_div(), mp_div_2(), mp_div_2d(), mp_div_d(), mp_dr_reduce(), mp_karatsuba_mul(), mp_karatsuba_sqr(), mp_mod_2d(), mp_montgomery_reduce(), mp_mul_2d(), mp_mul_d(), mp_read_unsigned_bin(), mp_set_int(), mp_sub_d(), s_mp_add(), s_mp_mul_digs(), s_mp_mul_high_digs(), s_mp_sqr(), and s_mp_sub().

◆ mp_clear()

static void mp_clear ( mp_int a)
static

Definition at line 255 of file mpi.c.

256 {
257  int i;
258 
259  /* only do anything if a hasn't been freed previously */
260  if (a->dp != NULL) {
261  /* first zero the digits */
262  for (i = 0; i < a->used; i++) {
263  a->dp[i] = 0;
264  }
265 
266  /* free ram */
267  HeapFree(GetProcessHeap(), 0, a->dp);
268 
269  /* reset members to make debugging easier */
270  a->dp = NULL;
271  a->alloc = a->used = 0;
272  a->sign = MP_ZPOS;
273  }
274 }
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
smooth NULL
Definition: ftsmooth.c:416
#define GetProcessHeap()
Definition: compat.h:395
#define MP_ZPOS
Definition: tomcrypt.h:197
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
#define HeapFree(x, y, z)
Definition: compat.h:394

Referenced by mp_clear_multi(), mp_div(), mp_div_2d(), mp_div_d(), mp_exptmod(), mp_exptmod_fast(), mp_gcd(), mp_init_multi(), mp_karatsuba_mul(), mp_karatsuba_sqr(), mp_mod(), mp_mulmod(), mp_prime_is_prime(), mp_prime_miller_rabin(), mp_reduce(), mp_reduce_2k(), mp_reduce_2k_setup(), mp_sqrmod(), mp_to_unsigned_bin(), s_mp_exptmod(), s_mp_mul_digs(), s_mp_mul_high_digs(), and s_mp_sqr().

◆ mp_clear_multi()

void mp_clear_multi ( mp_int mp,
  ... 
)

Definition at line 1032 of file mpi.c.

1033 {
1034  mp_int* next_mp = mp;
1035  va_list args;
1036  va_start(args, mp);
1037  while (next_mp != NULL) {
1038  mp_clear(next_mp);
1039  next_mp = va_arg(args, mp_int*);
1040  }
1041  va_end(args);
1042 }
static void mp_clear(mp_int *a)
Definition: mpi.c:255
Definition: match.c:390
#define va_end(ap)
Definition: acmsvcex.h:90
smooth NULL
Definition: ftsmooth.c:416
char * va_list
Definition: acmsvcex.h:78
#define va_arg(ap, T)
Definition: acmsvcex.h:89
#define va_start(ap, A)
Definition: acmsvcex.h:91
#define args
Definition: format.c:66

Referenced by fast_mp_invmod(), mp_exptmod(), mp_invmod_slow(), mp_lcm(), rsa_exptmod(), rsa_free(), and rsa_make_key().

◆ mp_cmp()

int mp_cmp ( const mp_int a,
const mp_int b 
)

Definition at line 1046 of file mpi.c.

1047 {
1048  /* compare based on sign */
1049  if (a->sign != b->sign) {
1050  if (a->sign == MP_NEG) {
1051  return MP_LT;
1052  } else {
1053  return MP_GT;
1054  }
1055  }
1056 
1057  /* compare digits */
1058  if (a->sign == MP_NEG) {
1059  /* if negative compare opposite direction */
1060  return mp_cmp_mag(b, a);
1061  } else {
1062  return mp_cmp_mag(a, b);
1063  }
1064 }
#define MP_LT
Definition: tomcrypt.h:193
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_GT
Definition: tomcrypt.h:195
#define MP_NEG
Definition: tomcrypt.h:198
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by fast_mp_invmod(), mp_div(), mp_invmod_slow(), mp_prime_miller_rabin(), mp_reduce(), and rsa_exptmod().

◆ mp_cmp_d()

int mp_cmp_d ( const mp_int a,
mp_digit  b 
)

Definition at line 1067 of file mpi.c.

1068 {
1069  /* compare based on sign */
1070  if (a->sign == MP_NEG) {
1071  return MP_LT;
1072  }
1073 
1074  /* compare based on magnitude */
1075  if (a->used > 1) {
1076  return MP_GT;
1077  }
1078 
1079  /* compare the only digit of a to b */
1080  if (a->dp[0] > b) {
1081  return MP_GT;
1082  } else if (a->dp[0] < b) {
1083  return MP_LT;
1084  } else {
1085  return MP_EQ;
1086  }
1087 }
#define MP_LT
Definition: tomcrypt.h:193
#define MP_EQ
Definition: tomcrypt.h:194
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_GT
Definition: tomcrypt.h:195
#define MP_NEG
Definition: tomcrypt.h:198
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by fast_mp_invmod(), mp_invmod_slow(), mp_prime_is_prime(), mp_prime_miller_rabin(), mp_reduce(), and rsa_make_key().

◆ mp_cmp_mag()

int mp_cmp_mag ( const mp_int a,
const mp_int b 
)
static

Definition at line 1090 of file mpi.c.

1091 {
1092  int n;
1093  mp_digit *tmpa, *tmpb;
1094 
1095  /* compare based on # of non-zero digits */
1096  if (a->used > b->used) {
1097  return MP_GT;
1098  }
1099 
1100  if (a->used < b->used) {
1101  return MP_LT;
1102  }
1103 
1104  /* alias for a */
1105  tmpa = a->dp + (a->used - 1);
1106 
1107  /* alias for b */
1108  tmpb = b->dp + (a->used - 1);
1109 
1110  /* compare based on digits */
1111  for (n = 0; n < a->used; ++n, --tmpa, --tmpb) {
1112  if (*tmpa > *tmpb) {
1113  return MP_GT;
1114  }
1115 
1116  if (*tmpa < *tmpb) {
1117  return MP_LT;
1118  }
1119  }
1120  return MP_EQ;
1121 }
GLdouble n
Definition: glext.h:7729
#define MP_LT
Definition: tomcrypt.h:193
#define MP_EQ
Definition: tomcrypt.h:194
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_GT
Definition: tomcrypt.h:195
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by fast_mp_montgomery_reduce(), mp_add(), mp_cmp(), mp_div(), mp_dr_reduce(), mp_gcd(), mp_invmod_slow(), mp_lcm(), mp_montgomery_calc_normalization(), mp_montgomery_reduce(), mp_reduce_2k(), and mp_sub().

◆ mp_cnt_lsb()

int mp_cnt_lsb ( const mp_int a)
static

Definition at line 1128 of file mpi.c.

1129 {
1130  int x;
1131  mp_digit q, qq;
1132 
1133  /* easy out */
1134  if (mp_iszero(a) == 1) {
1135  return 0;
1136  }
1137 
1138  /* scan lower digits until non-zero */
1139  for (x = 0; x < a->used && a->dp[x] == 0; x++);
1140  q = a->dp[x];
1141  x *= DIGIT_BIT;
1142 
1143  /* now scan this digit until a 1 is found */
1144  if ((q & 1) == 0) {
1145  do {
1146  qq = q & 15;
1147  x += lnz[qq];
1148  q >>= 4;
1149  } while (qq == 0);
1150  }
1151  return x;
1152 }
static const int lnz[16]
Definition: mpi.c:1123
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define DIGIT_BIT
Definition: tomcrypt.h:186
#define mp_iszero(a)
Definition: tomcrypt.h:248
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_gcd(), and mp_prime_miller_rabin().

◆ mp_copy()

int mp_copy ( const mp_int a,
mp_int b 
)

Definition at line 1156 of file mpi.c.

1157 {
1158  int res, n;
1159 
1160  /* if dst == src do nothing */
1161  if (a == b) {
1162  return MP_OKAY;
1163  }
1164 
1165  /* grow dest */
1166  if (b->alloc < a->used) {
1167  if ((res = mp_grow (b, a->used)) != MP_OKAY) {
1168  return res;
1169  }
1170  }
1171 
1172  /* zero b and copy the parameters over */
1173  {
1174  register mp_digit *tmpa, *tmpb;
1175 
1176  /* pointer aliases */
1177 
1178  /* source */
1179  tmpa = a->dp;
1180 
1181  /* destination */
1182  tmpb = b->dp;
1183 
1184  /* copy all the digits */
1185  for (n = 0; n < a->used; n++) {
1186  *tmpb++ = *tmpa++;
1187  }
1188 
1189  /* clear high digits */
1190  for (; n < b->used; n++) {
1191  *tmpb++ = 0;
1192  }
1193  }
1194 
1195  /* copy used count and sign */
1196  b->used = a->used;
1197  b->sign = a->sign;
1198  return MP_OKAY;
1199 }
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
GLdouble n
Definition: glext.h:7729
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by fast_mp_invmod(), mp_abs(), mp_div(), mp_div_2d(), mp_div_d(), mp_exptmod_fast(), mp_init_copy(), mp_invmod_slow(), mp_mod_2d(), mp_mul_2d(), rsa_make_key(), and s_mp_exptmod().

◆ mp_count_bits()

int mp_count_bits ( const mp_int a)

Definition at line 1203 of file mpi.c.

1204 {
1205  int r;
1206  mp_digit q;
1207 
1208  /* shortcut */
1209  if (a->used == 0) {
1210  return 0;
1211  }
1212 
1213  /* get number of digits and add that */
1214  r = (a->used - 1) * DIGIT_BIT;
1215 
1216  /* take the last digit and count the bits in it */
1217  q = a->dp[a->used - 1];
1218  while (q > 0) {
1219  ++r;
1220  q >>= ((mp_digit) 1);
1221  }
1222  return r;
1223 }
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by encrypt_block_impl(), mp_div(), mp_exptmod_fast(), mp_montgomery_calc_normalization(), mp_reduce_2k(), mp_reduce_2k_setup(), mp_unsigned_bin_size(), and s_mp_exptmod().

◆ mp_div()

static int mp_div ( const mp_int a,
const mp_int b,
mp_int c,
mp_int d 
)
static

Definition at line 1565 of file mpi.c.

1566 {
1567  mp_int q, x, y, t1, t2;
1568  int res, n, t, i, norm, neg;
1569 
1570  /* is divisor zero ? */
1571  if (mp_iszero (b) == 1) {
1572  return MP_VAL;
1573  }
1574 
1575  /* if a < b then q=0, r = a */
1576  if (mp_cmp_mag (a, b) == MP_LT) {
1577  if (d != NULL) {
1578  res = mp_copy (a, d);
1579  } else {
1580  res = MP_OKAY;
1581  }
1582  if (c != NULL) {
1583  mp_zero (c);
1584  }
1585  return res;
1586  }
1587 
1588  if ((res = mp_init_size (&q, a->used + 2)) != MP_OKAY) {
1589  return res;
1590  }
1591  q.used = a->used + 2;
1592 
1593  if ((res = mp_init (&t1)) != MP_OKAY) {
1594  goto __Q;
1595  }
1596 
1597  if ((res = mp_init (&t2)) != MP_OKAY) {
1598  goto __T1;
1599  }
1600 
1601  if ((res = mp_init_copy (&x, a)) != MP_OKAY) {
1602  goto __T2;
1603  }
1604 
1605  if ((res = mp_init_copy (&y, b)) != MP_OKAY) {
1606  goto __X;
1607  }
1608 
1609  /* fix the sign */
1610  neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
1611  x.sign = y.sign = MP_ZPOS;
1612 
1613  /* normalize both x and y, ensure that y >= b/2, [b == 2**DIGIT_BIT] */
1614  norm = mp_count_bits(&y) % DIGIT_BIT;
1615  if (norm < DIGIT_BIT-1) {
1616  norm = (DIGIT_BIT-1) - norm;
1617  if ((res = mp_mul_2d (&x, norm, &x)) != MP_OKAY) {
1618  goto __Y;
1619  }
1620  if ((res = mp_mul_2d (&y, norm, &y)) != MP_OKAY) {
1621  goto __Y;
1622  }
1623  } else {
1624  norm = 0;
1625  }
1626 
1627  /* note hac does 0 based, so if used==5 then it's 0,1,2,3,4, e.g. use 4 */
1628  n = x.used - 1;
1629  t = y.used - 1;
1630 
1631  /* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */
1632  if ((res = mp_lshd (&y, n - t)) != MP_OKAY) { /* y = y*b**{n-t} */
1633  goto __Y;
1634  }
1635 
1636  while (mp_cmp (&x, &y) != MP_LT) {
1637  ++(q.dp[n - t]);
1638  if ((res = mp_sub (&x, &y, &x)) != MP_OKAY) {
1639  goto __Y;
1640  }
1641  }
1642 
1643  /* reset y by shifting it back down */
1644  mp_rshd (&y, n - t);
1645 
1646  /* step 3. for i from n down to (t + 1) */
1647  for (i = n; i >= (t + 1); i--) {
1648  if (i > x.used) {
1649  continue;
1650  }
1651 
1652  /* step 3.1 if xi == yt then set q{i-t-1} to b-1,
1653  * otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */
1654  if (x.dp[i] == y.dp[t]) {
1655  q.dp[i - t - 1] = ((((mp_digit)1) << DIGIT_BIT) - 1);
1656  } else {
1657  mp_word tmp;
1658  tmp = ((mp_word) x.dp[i]) << ((mp_word) DIGIT_BIT);
1659  tmp |= ((mp_word) x.dp[i - 1]);
1660  tmp /= ((mp_word) y.dp[t]);
1661  if (tmp > (mp_word) MP_MASK)
1662  tmp = MP_MASK;
1663  q.dp[i - t - 1] = (mp_digit) (tmp & (mp_word) (MP_MASK));
1664  }
1665 
1666  /* while (q{i-t-1} * (yt * b + y{t-1})) >
1667  xi * b**2 + xi-1 * b + xi-2
1668 
1669  do q{i-t-1} -= 1;
1670  */
1671  q.dp[i - t - 1] = (q.dp[i - t - 1] + 1) & MP_MASK;
1672  do {
1673  q.dp[i - t - 1] = (q.dp[i - t - 1] - 1) & MP_MASK;
1674 
1675  /* find left hand */
1676  mp_zero (&t1);
1677  t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
1678  t1.dp[1] = y.dp[t];
1679  t1.used = 2;
1680  if ((res = mp_mul_d (&t1, q.dp[i - t - 1], &t1)) != MP_OKAY) {
1681  goto __Y;
1682  }
1683 
1684  /* find right hand */
1685  t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
1686  t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
1687  t2.dp[2] = x.dp[i];
1688  t2.used = 3;
1689  } while (mp_cmp_mag(&t1, &t2) == MP_GT);
1690 
1691  /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */
1692  if ((res = mp_mul_d (&y, q.dp[i - t - 1], &t1)) != MP_OKAY) {
1693  goto __Y;
1694  }
1695 
1696  if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) {
1697  goto __Y;
1698  }
1699 
1700  if ((res = mp_sub (&x, &t1, &x)) != MP_OKAY) {
1701  goto __Y;
1702  }
1703 
1704  /* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */
1705  if (x.sign == MP_NEG) {
1706  if ((res = mp_copy (&y, &t1)) != MP_OKAY) {
1707  goto __Y;
1708  }
1709  if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) {
1710  goto __Y;
1711  }
1712  if ((res = mp_add (&x, &t1, &x)) != MP_OKAY) {
1713  goto __Y;
1714  }
1715 
1716  q.dp[i - t - 1] = (q.dp[i - t - 1] - 1UL) & MP_MASK;
1717  }
1718  }
1719 
1720  /* now q is the quotient and x is the remainder
1721  * [which we have to normalize]
1722  */
1723 
1724  /* get sign before writing to c */
1725  x.sign = x.used == 0 ? MP_ZPOS : a->sign;
1726 
1727  if (c != NULL) {
1728  mp_clamp (&q);
1729  mp_exch (&q, c);
1730  c->sign = neg;
1731  }
1732 
1733  if (d != NULL) {
1734  mp_div_2d (&x, norm, &x, NULL);
1735  mp_exch (&x, d);
1736  }
1737 
1738  res = MP_OKAY;
1739 
1740 __Y:mp_clear (&y);
1741 __X:mp_clear (&x);
1742 __T2:mp_clear (&t2);
1743 __T1:mp_clear (&t1);
1744 __Q:mp_clear (&q);
1745  return res;
1746 }
static int mp_div_2d(const mp_int *a, int b, mp_int *c, mp_int *d)
Definition: mpi.c:1310
int mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:891
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define MP_MASK
Definition: tomcrypt.h:189
static void mp_clear(mp_int *a)
Definition: mpi.c:255
GLdouble n
Definition: glext.h:7729
int mp_count_bits(const mp_int *a)
Definition: mpi.c:1203
GLdouble GLdouble t
Definition: gl.h:2047
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
int t
Definition: mpi.c:3369
int mp_cmp(const mp_int *a, const mp_int *b)
Definition: mpi.c:1046
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
static int mp_mul_d(const mp_int *a, mp_digit b, mp_int *c)
Definition: mpi.c:1497
#define MP_LT
Definition: tomcrypt.h:193
static int mp_lshd(mp_int *a, int b)
Definition: mpi.c:1386
smooth NULL
Definition: ftsmooth.c:416
static int mp_init_size(mp_int *a, int size)
Definition: mpi.c:227
static int mp_init(mp_int *a)
Definition: mpi.c:202
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
int mp_init_copy(mp_int *a, const mp_int *b)
Definition: mpi.c:2344
#define d
Definition: ke_i.h:81
if(!(yy_init))
Definition: macro.lex.yy.c:714
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
const GLubyte * c
Definition: glext.h:8905
#define mp_iszero(a)
Definition: tomcrypt.h:248
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
#define MP_GT
Definition: tomcrypt.h:195
static void mp_zero(mp_int *a)
Definition: mpi.c:278
#define MP_VAL
Definition: tomcrypt.h:202
#define MP_ZPOS
Definition: tomcrypt.h:197
#define MP_OKAY
Definition: tomcrypt.h:200
#define MP_NEG
Definition: tomcrypt.h:198
mp_digit * dp
Definition: tomcrypt.h:227
static void mp_rshd(mp_int *a, int b)
Definition: mpi.c:1259
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
static int mp_mul_2d(const mp_int *a, int b, mp_int *c)
Definition: mpi.c:1432
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
int used
Definition: tomcrypt.h:226
int mp_sub(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:3771
#define UL
Definition: tui.h:70
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_lcm(), mp_mod(), and mp_reduce_setup().

◆ mp_div_2()

static int mp_div_2 ( const mp_int a,
mp_int b 
)
static

Definition at line 142 of file mpi.c.

143 {
144  int x, res, oldused;
145 
146  /* copy */
147  if (b->alloc < a->used) {
148  if ((res = mp_grow (b, a->used)) != MP_OKAY) {
149  return res;
150  }
151  }
152 
153  oldused = b->used;
154  b->used = a->used;
155  {
156  register mp_digit r, rr, *tmpa, *tmpb;
157 
158  /* source alias */
159  tmpa = a->dp + b->used - 1;
160 
161  /* dest alias */
162  tmpb = b->dp + b->used - 1;
163 
164  /* carry */
165  r = 0;
166  for (x = b->used - 1; x >= 0; x--) {
167  /* get the carry for the next iteration */
168  rr = *tmpa & 1;
169 
170  /* shift the current digit, add in carry and store */
171  *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
172 
173  /* forward carry to next iteration */
174  r = rr;
175  }
176 
177  /* zero excess digits */
178  tmpb = b->dp + b->used;
179  for (x = b->used; x < oldused; x++) {
180  *tmpb++ = 0;
181  }
182  }
183  b->sign = a->sign;
184  mp_clamp (b);
185  return MP_OKAY;
186 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by fast_mp_invmod(), mp_invmod_slow(), and mp_prime_random_ex().

◆ mp_div_2d()

static int mp_div_2d ( const mp_int a,
int  b,
mp_int c,
mp_int d 
)
static

Definition at line 1310 of file mpi.c.

1311 {
1312  mp_digit D, r, rr;
1313  int x, res;
1314  mp_int t;
1315 
1316 
1317  /* if the shift count is <= 0 then we do no work */
1318  if (b <= 0) {
1319  res = mp_copy (a, c);
1320  if (d != NULL) {
1321  mp_zero (d);
1322  }
1323  return res;
1324  }
1325 
1326  if ((res = mp_init (&t)) != MP_OKAY) {
1327  return res;
1328  }
1329 
1330  /* get the remainder */
1331  if (d != NULL) {
1332  if ((res = mp_mod_2d (a, b, &t)) != MP_OKAY) {
1333  mp_clear (&t);
1334  return res;
1335  }
1336  }
1337 
1338  /* copy */
1339  if ((res = mp_copy (a, c)) != MP_OKAY) {
1340  mp_clear (&t);
1341  return res;
1342  }
1343 
1344  /* shift by as many digits in the bit count */
1345  if (b >= DIGIT_BIT) {
1346  mp_rshd (c, b / DIGIT_BIT);
1347  }
1348 
1349  /* shift any bit count < DIGIT_BIT */
1350  D = (mp_digit) (b % DIGIT_BIT);
1351  if (D != 0) {
1352  register mp_digit *tmpc, mask, shift;
1353 
1354  /* mask */
1355  mask = (((mp_digit)1) << D) - 1;
1356 
1357  /* shift for lsb */
1358  shift = DIGIT_BIT - D;
1359 
1360  /* alias */
1361  tmpc = c->dp + (c->used - 1);
1362 
1363  /* carry */
1364  r = 0;
1365  for (x = c->used - 1; x >= 0; x--) {
1366  /* get the lower bits of this word in a temp */
1367  rr = *tmpc & mask;
1368 
1369  /* shift the current word and mix in the carry bits from the previous word */
1370  *tmpc = (*tmpc >> D) | (r << shift);
1371  --tmpc;
1372 
1373  /* set the carry to the carry bits of the current word found above */
1374  r = rr;
1375  }
1376  }
1377  mp_clamp (c);
1378  if (d != NULL) {
1379  mp_exch (&t, d);
1380  }
1381  mp_clear (&t);
1382  return MP_OKAY;
1383 }
#define shift
Definition: input.c:1668
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
static void mp_clear(mp_int *a)
Definition: mpi.c:255
GLdouble GLdouble t
Definition: gl.h:2047
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
int t
Definition: mpi.c:3369
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLenum GLint GLuint mask
Definition: glext.h:6028
smooth NULL
Definition: ftsmooth.c:416
static int mp_init(mp_int *a)
Definition: mpi.c:202
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define d
Definition: ke_i.h:81
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
const GLubyte * c
Definition: glext.h:8905
static void mp_zero(mp_int *a)
Definition: mpi.c:278
#define MP_OKAY
Definition: tomcrypt.h:200
#define D(name, bit)
static void mp_rshd(mp_int *a, int b)
Definition: mpi.c:1259
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
static int mp_mod_2d(const mp_int *a, int b, mp_int *c)
Definition: mpi.c:1227
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_div(), mp_div_d(), mp_gcd(), mp_prime_miller_rabin(), mp_reduce_2k(), and mp_to_unsigned_bin().

◆ mp_div_d()

static int mp_div_d ( const mp_int a,
mp_digit  b,
mp_int c,
mp_digit d 
)
static

Definition at line 1762 of file mpi.c.

1763 {
1764  mp_int q;
1765  mp_word w;
1766  mp_digit t;
1767  int res, ix;
1768 
1769  /* cannot divide by zero */
1770  if (b == 0) {
1771  return MP_VAL;
1772  }
1773 
1774  /* quick outs */
1775  if (b == 1 || mp_iszero(a) == 1) {
1776  if (d != NULL) {
1777  *d = 0;
1778  }
1779  if (c != NULL) {
1780  return mp_copy(a, c);
1781  }
1782  return MP_OKAY;
1783  }
1784 
1785  /* power of two ? */
1786  if (s_is_power_of_two(b, &ix)) {
1787  if (d != NULL) {
1788  *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
1789  }
1790  if (c != NULL) {
1791  return mp_div_2d(a, ix, c, NULL);
1792  }
1793  return MP_OKAY;
1794  }
1795 
1796  /* no easy answer [c'est la vie]. Just division */
1797  if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
1798  return res;
1799  }
1800 
1801  q.used = a->used;
1802  q.sign = a->sign;
1803  w = 0;
1804  for (ix = a->used - 1; ix >= 0; ix--) {
1805  w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
1806 
1807  if (w >= b) {
1808  t = (mp_digit)(w / b);
1809  w -= ((mp_word)t) * ((mp_word)b);
1810  } else {
1811  t = 0;
1812  }
1813  q.dp[ix] = t;
1814  }
1815 
1816  if (d != NULL) {
1817  *d = (mp_digit)w;
1818  }
1819 
1820  if (c != NULL) {
1821  mp_clamp(&q);
1822  mp_exch(&q, c);
1823  }
1824  mp_clear(&q);
1825 
1826  return res;
1827 }
static int mp_div_2d(const mp_int *a, int b, mp_int *c, mp_int *d)
Definition: mpi.c:1310
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static void mp_clear(mp_int *a)
Definition: mpi.c:255
GLdouble GLdouble t
Definition: gl.h:2047
int t
Definition: mpi.c:3369
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
static BOOL s_is_power_of_two(mp_digit b, int *p)
Definition: mpi.c:1748
smooth NULL
Definition: ftsmooth.c:416
static int mp_init_size(mp_int *a, int size)
Definition: mpi.c:227
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define d
Definition: ke_i.h:81
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
const GLubyte * c
Definition: glext.h:8905
#define mp_iszero(a)
Definition: tomcrypt.h:248
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
#define MP_VAL
Definition: tomcrypt.h:202
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_mod_d().

◆ mp_dr_reduce()

static int mp_dr_reduce ( mp_int x,
const mp_int n,
mp_digit  k 
)
static

Definition at line 1844 of file mpi.c.

1845 {
1846  int err, i, m;
1847  mp_word r;
1848  mp_digit mu, *tmpx1, *tmpx2;
1849 
1850  /* m = digits in modulus */
1851  m = n->used;
1852 
1853  /* ensure that "x" has at least 2m digits */
1854  if (x->alloc < m + m) {
1855  if ((err = mp_grow (x, m + m)) != MP_OKAY) {
1856  return err;
1857  }
1858  }
1859 
1860 /* top of loop, this is where the code resumes if
1861  * another reduction pass is required.
1862  */
1863 top:
1864  /* aliases for digits */
1865  /* alias for lower half of x */
1866  tmpx1 = x->dp;
1867 
1868  /* alias for upper half of x, or x/B**m */
1869  tmpx2 = x->dp + m;
1870 
1871  /* set carry to zero */
1872  mu = 0;
1873 
1874  /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
1875  for (i = 0; i < m; i++) {
1876  r = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu;
1877  *tmpx1++ = (mp_digit)(r & MP_MASK);
1878  mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT));
1879  }
1880 
1881  /* set final carry */
1882  *tmpx1++ = mu;
1883 
1884  /* zero words above m */
1885  for (i = m + 1; i < x->used; i++) {
1886  *tmpx1++ = 0;
1887  }
1888 
1889  /* clamp, sub and return */
1890  mp_clamp (x);
1891 
1892  /* if x >= n then subtract and reduce again
1893  * Each successive "recursion" makes the input smaller and smaller.
1894  */
1895  if (mp_cmp_mag (x, n) != MP_LT) {
1896  s_mp_sub(x, n, x);
1897  goto top;
1898  }
1899  return MP_OKAY;
1900 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define MP_MASK
Definition: tomcrypt.h:189
GLdouble n
Definition: glext.h:7729
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
const GLfloat * m
Definition: glext.h:10848
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define MP_LT
Definition: tomcrypt.h:193
static int s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:4412
#define err(...)
#define MP_OKAY
Definition: tomcrypt.h:200
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
int k
Definition: mpi.c:3369
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_exptmod_fast().

◆ mp_dr_setup()

static void mp_dr_setup ( const mp_int a,
mp_digit d 
)
static

Definition at line 1903 of file mpi.c.

1904 {
1905  /* the casts are required if DIGIT_BIT is one less than
1906  * the number of bits in a mp_digit [e.g. DIGIT_BIT==31]
1907  */
1908  *d = (mp_digit)((((mp_word)1) << ((mp_word)DIGIT_BIT)) -
1909  ((mp_word)a->dp[0]));
1910 }
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
#define d
Definition: ke_i.h:81
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_exptmod_fast().

◆ mp_exch()

static void mp_exch ( mp_int a,
mp_int b 
)
static

Definition at line 192 of file mpi.c.

193 {
194  mp_int t;
195 
196  t = *a;
197  *a = *b;
198  *b = t;
199 }
GLdouble GLdouble t
Definition: gl.h:2047
int t
Definition: mpi.c:3369
#define a
Definition: ke_i.h:78
#define b
Definition: ke_i.h:79
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by fast_mp_invmod(), mp_div(), mp_div_2d(), mp_div_d(), mp_exptmod_fast(), mp_gcd(), mp_invmod_slow(), mp_mod(), s_mp_exptmod(), s_mp_mul_digs(), s_mp_mul_high_digs(), and s_mp_sqr().

◆ mp_exptmod()

int mp_exptmod ( const mp_int G,
const mp_int X,
mp_int P,
mp_int Y 
)

Definition at line 1917 of file mpi.c.

1918 {
1919  int dr;
1920 
1921  /* modulus P must be positive */
1922  if (P->sign == MP_NEG) {
1923  return MP_VAL;
1924  }
1925 
1926  /* if exponent X is negative we have to recurse */
1927  if (X->sign == MP_NEG) {
1928  mp_int tmpG, tmpX;
1929  int err;
1930 
1931  /* first compute 1/G mod P */
1932  if ((err = mp_init(&tmpG)) != MP_OKAY) {
1933  return err;
1934  }
1935  if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
1936  mp_clear(&tmpG);
1937  return err;
1938  }
1939 
1940  /* now get |X| */
1941  if ((err = mp_init(&tmpX)) != MP_OKAY) {
1942  mp_clear(&tmpG);
1943  return err;
1944  }
1945  if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
1946  mp_clear_multi(&tmpG, &tmpX, NULL);
1947  return err;
1948  }
1949 
1950  /* and now compute (1/G)**|X| instead of G**X [X < 0] */
1951  err = mp_exptmod(&tmpG, &tmpX, P, Y);
1952  mp_clear_multi(&tmpG, &tmpX, NULL);
1953  return err;
1954  }
1955 
1956  dr = 0;
1957 
1958  /* if the modulus is odd use the fast method */
1959  if (mp_isodd (P) == 1) {
1960  return mp_exptmod_fast (G, X, P, Y, dr);
1961  } else {
1962  /* otherwise use the generic Barrett reduction technique */
1963  return s_mp_exptmod (G, X, P, Y);
1964  }
1965 }
void mp_clear_multi(mp_int *mp,...)
Definition: mpi.c:1032
#define Y(I)
static int s_mp_exptmod(const mp_int *G, const mp_int *X, mp_int *P, mp_int *Y)
Definition: mpi.c:4011
static void mp_clear(mp_int *a)
Definition: mpi.c:255
static int mp_abs(const mp_int *a, mp_int *b)
Definition: mpi.c:290
smooth NULL
Definition: ftsmooth.c:416
static int mp_init(mp_int *a)
Definition: mpi.c:202
#define mp_isodd(a)
Definition: tomcrypt.h:250
static int mp_exptmod_fast(const mp_int *G, const mp_int *X, mp_int *P, mp_int *Y, int mode)
Definition: mpi.c:1976
#define MP_VAL
Definition: tomcrypt.h:202
#define err(...)
#define P(row, col)
#define MP_OKAY
Definition: tomcrypt.h:200
int mp_exptmod(const mp_int *G, const mp_int *X, mp_int *P, mp_int *Y)
Definition: mpi.c:1917
#define G(x, y, z)
Definition: md5.c:52
#define MP_NEG
Definition: tomcrypt.h:198
int mp_invmod(const mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:2391

Referenced by mp_exptmod(), mp_prime_miller_rabin(), and rsa_exptmod().

◆ mp_exptmod_fast()

int mp_exptmod_fast ( const mp_int G,
const mp_int X,
mp_int P,
mp_int Y,
int  mode 
)
static

Definition at line 1976 of file mpi.c.

1977 {
1978  mp_int M[256], res;
1979  mp_digit buf, mp;
1980  int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
1981 
1982  /* use a pointer to the reduction algorithm. This allows us to use
1983  * one of many reduction algorithms without modding the guts of
1984  * the code with if statements everywhere.
1985  */
1986  int (*redux)(mp_int*,const mp_int*,mp_digit);
1987 
1988  /* find window size */
1989  x = mp_count_bits (X);
1990  if (x <= 7) {
1991  winsize = 2;
1992  } else if (x <= 36) {
1993  winsize = 3;
1994  } else if (x <= 140) {
1995  winsize = 4;
1996  } else if (x <= 450) {
1997  winsize = 5;
1998  } else if (x <= 1303) {
1999  winsize = 6;
2000  } else if (x <= 3529) {
2001  winsize = 7;
2002  } else {
2003  winsize = 8;
2004  }
2005 
2006  /* init M array */
2007  /* init first cell */
2008  if ((err = mp_init(&M[1])) != MP_OKAY) {
2009  return err;
2010  }
2011 
2012  /* now init the second half of the array */
2013  for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
2014  if ((err = mp_init(&M[x])) != MP_OKAY) {
2015  for (y = 1<<(winsize-1); y < x; y++) {
2016  mp_clear (&M[y]);
2017  }
2018  mp_clear(&M[1]);
2019  return err;
2020  }
2021  }
2022 
2023  /* determine and setup reduction code */
2024  if (redmode == 0) {
2025  /* now setup montgomery */
2026  if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) {
2027  goto __M;
2028  }
2029 
2030  /* automatically pick the comba one if available (saves quite a few calls/ifs) */
2031  if (((P->used * 2 + 1) < MP_WARRAY) &&
2032  P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
2033  redux = fast_mp_montgomery_reduce;
2034  } else {
2035  /* use slower baseline Montgomery method */
2036  redux = mp_montgomery_reduce;
2037  }
2038  } else if (redmode == 1) {
2039  /* setup DR reduction for moduli of the form B**k - b */
2040  mp_dr_setup(P, &mp);
2041  redux = mp_dr_reduce;
2042  } else {
2043  /* setup DR reduction for moduli of the form 2**k - b */
2044  if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) {
2045  goto __M;
2046  }
2047  redux = mp_reduce_2k;
2048  }
2049 
2050  /* setup result */
2051  if ((err = mp_init (&res)) != MP_OKAY) {
2052  goto __M;
2053  }
2054 
2055  /* create M table
2056  *
2057 
2058  *
2059  * The first half of the table is not computed though accept for M[0] and M[1]
2060  */
2061 
2062  if (redmode == 0) {
2063  /* now we need R mod m */
2065  goto __RES;
2066  }
2067 
2068  /* now set M[1] to G * R mod m */
2069  if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) {
2070  goto __RES;
2071  }
2072  } else {
2073  mp_set(&res, 1);
2074  if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) {
2075  goto __RES;
2076  }
2077  }
2078 
2079  /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */
2080  if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) {
2081  goto __RES;
2082  }
2083 
2084  for (x = 0; x < (winsize - 1); x++) {
2085  if ((err = mp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)])) != MP_OKAY) {
2086  goto __RES;
2087  }
2088  if ((err = redux (&M[1 << (winsize - 1)], P, mp)) != MP_OKAY) {
2089  goto __RES;
2090  }
2091  }
2092 
2093  /* create upper table */
2094  for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
2095  if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) {
2096  goto __RES;
2097  }
2098  if ((err = redux (&M[x], P, mp)) != MP_OKAY) {
2099  goto __RES;
2100  }
2101  }
2102 
2103  /* set initial mode and bit cnt */
2104  mode = 0;
2105  bitcnt = 1;
2106  buf = 0;
2107  digidx = X->used - 1;
2108  bitcpy = 0;
2109  bitbuf = 0;
2110 
2111  for (;;) {
2112  /* grab next digit as required */
2113  if (--bitcnt == 0) {
2114  /* if digidx == -1 we are out of digits so break */
2115  if (digidx == -1) {
2116  break;
2117  }
2118  /* read next digit and reset bitcnt */
2119  buf = X->dp[digidx--];
2120  bitcnt = DIGIT_BIT;
2121  }
2122 
2123  /* grab the next msb from the exponent */
2124  y = (buf >> (DIGIT_BIT - 1)) & 1;
2125  buf <<= (mp_digit)1;
2126 
2127  /* if the bit is zero and mode == 0 then we ignore it
2128  * These represent the leading zero bits before the first 1 bit
2129  * in the exponent. Technically this opt is not required but it
2130  * does lower the # of trivial squaring/reductions used
2131  */
2132  if (mode == 0 && y == 0) {
2133  continue;
2134  }
2135 
2136  /* if the bit is zero and mode == 1 then we square */
2137  if (mode == 1 && y == 0) {
2138  if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
2139  goto __RES;
2140  }
2141  if ((err = redux (&res, P, mp)) != MP_OKAY) {
2142  goto __RES;
2143  }
2144  continue;
2145  }
2146 
2147  /* else we add it to the window */
2148  bitbuf |= (y << (winsize - ++bitcpy));
2149  mode = 2;
2150 
2151  if (bitcpy == winsize) {
2152  /* ok window is filled so square as required and multiply */
2153  /* square first */
2154  for (x = 0; x < winsize; x++) {
2155  if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
2156  goto __RES;
2157  }
2158  if ((err = redux (&res, P, mp)) != MP_OKAY) {
2159  goto __RES;
2160  }
2161  }
2162 
2163  /* then multiply */
2164  if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) {
2165  goto __RES;
2166  }
2167  if ((err = redux (&res, P, mp)) != MP_OKAY) {
2168  goto __RES;
2169  }
2170 
2171  /* empty window and reset */
2172  bitcpy = 0;
2173  bitbuf = 0;
2174  mode = 1;
2175  }
2176  }
2177 
2178  /* if bits remain then square/multiply */
2179  if (mode == 2 && bitcpy > 0) {
2180  /* square then multiply if the bit is set */
2181  for (x = 0; x < bitcpy; x++) {
2182  if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
2183  goto __RES;
2184  }
2185  if ((err = redux (&res, P, mp)) != MP_OKAY) {
2186  goto __RES;
2187  }
2188 
2189  /* get next bit of the window */
2190  bitbuf <<= 1;
2191  if ((bitbuf & (1 << winsize)) != 0) {
2192  /* then multiply */
2193  if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) {
2194  goto __RES;
2195  }
2196  if ((err = redux (&res, P, mp)) != MP_OKAY) {
2197  goto __RES;
2198  }
2199  }
2200  }
2201  }
2202 
2203  if (redmode == 0) {
2204  /* fixup result if Montgomery reduction is used
2205  * recall that any value in a Montgomery system is
2206  * actually multiplied by R mod n. So we have
2207  * to reduce one more time to cancel out the factor
2208  * of R.
2209  */
2210  if ((err = redux(&res, P, mp)) != MP_OKAY) {
2211  goto __RES;
2212  }
2213  }
2214 
2215  /* swap res with Y */
2216  mp_exch (&res, Y);
2217  err = MP_OKAY;
2218 __RES:mp_clear (&res);
2219 __M:
2220  mp_clear(&M[1]);
2221  for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
2222  mp_clear (&M[x]);
2223  }
2224  return err;
2225 }
static int mp_montgomery_calc_normalization(mp_int *a, const mp_int *b)
Definition: mpi.c:2945
#define Y(I)
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
#define M(row, col)
static void mp_clear(mp_int *a)
Definition: mpi.c:255
int mp_mod(const mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:2847
int mp_count_bits(const mp_int *a)
Definition: mpi.c:1203
static int mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k)
Definition: mpi.c:1844
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define CHAR_BIT
Definition: urlcache.c:57
static void mp_dr_setup(const mp_int *a, mp_digit *d)
Definition: mpi.c:1903
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
static int mp_montgomery_reduce(mp_int *a, const mp_int *m, mp_digit mp)
Definition: mpi.c:2980
static int mp_reduce_2k_setup(const mp_int *a, mp_digit *d)
Definition: mpi.c:3640
static int mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d)
Definition: mpi.c:3600
static int mp_sqr(const mp_int *a, mp_int *b)
Definition: mpi.c:3729
static void mp_set(mp_int *a, mp_digit b)
Definition: mpi.c:3679
int mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:3107
static int mp_init(mp_int *a)
Definition: mpi.c:202
static int fast_mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho)
Definition: mpi.c:444
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
#define MP_WARRAY
Definition: tomcrypt.h:222
#define err(...)
GLenum mode
Definition: glext.h:6217
#define P(row, col)
#define MP_OKAY
Definition: tomcrypt.h:200
#define G(x, y, z)
Definition: md5.c:52
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLuint res
Definition: glext.h:9613
static int mp_montgomery_setup(const mp_int *a, mp_digit *mp)
Definition: mpi.c:3077
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
unsigned long mp_digit
Definition: tomcrypt.h:184
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
int mp_mulmod(const mp_int *a, const mp_int *b, mp_int *c, mp_int *d)
Definition: mpi.c:3138

Referenced by mp_exptmod().

◆ mp_gcd()

int mp_gcd ( const mp_int a,
const mp_int b,
mp_int c 
)

Definition at line 2228 of file mpi.c.

2229 {
2230  mp_int u, v;
2231  int k, u_lsb, v_lsb, res;
2232 
2233  /* either zero than gcd is the largest */
2234  if (mp_iszero (a) == 1 && mp_iszero (b) == 0) {
2235  return mp_abs (b, c);
2236  }
2237  if (mp_iszero (a) == 0 && mp_iszero (b) == 1) {
2238  return mp_abs (a, c);
2239  }
2240 
2241  /* optimized. At this point if a == 0 then
2242  * b must equal zero too
2243  */
2244  if (mp_iszero (a) == 1) {
2245  mp_zero(c);
2246  return MP_OKAY;
2247  }
2248 
2249  /* get copies of a and b we can modify */
2250  if ((res = mp_init_copy (&u, a)) != MP_OKAY) {
2251  return res;
2252  }
2253 
2254  if ((res = mp_init_copy (&v, b)) != MP_OKAY) {
2255  goto __U;
2256  }
2257 
2258  /* must be positive for the remainder of the algorithm */
2259  u.sign = v.sign = MP_ZPOS;
2260 
2261  /* B1. Find the common power of two for u and v */
2262  u_lsb = mp_cnt_lsb(&u);
2263  v_lsb = mp_cnt_lsb(&v);
2264  k = MIN(u_lsb, v_lsb);
2265 
2266  if (k > 0) {
2267  /* divide the power of two out */
2268  if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) {
2269  goto __V;
2270  }
2271 
2272  if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) {
2273  goto __V;
2274  }
2275  }
2276 
2277  /* divide any remaining factors of two out */
2278  if (u_lsb != k) {
2279  if ((res = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) {
2280  goto __V;
2281  }
2282  }
2283 
2284  if (v_lsb != k) {
2285  if ((res = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) {
2286  goto __V;
2287  }
2288  }
2289 
2290  while (mp_iszero(&v) == 0) {
2291  /* make sure v is the largest */
2292  if (mp_cmp_mag(&u, &v) == MP_GT) {
2293  /* swap u and v to make sure v is >= u */
2294  mp_exch(&u, &v);
2295  }
2296 
2297  /* subtract smallest from largest */
2298  if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) {
2299  goto __V;
2300  }
2301 
2302  /* Divide out all factors of two */
2303  if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) {
2304  goto __V;
2305  }
2306  }
2307 
2308  /* multiply by 2**k which we divided out at the beginning */
2309  if ((res = mp_mul_2d (&u, k, c)) != MP_OKAY) {
2310  goto __V;
2311  }
2312  c->sign = MP_ZPOS;
2313  res = MP_OKAY;
2314 __V:mp_clear (&u);
2315 __U:mp_clear (&v);
2316  return res;
2317 }
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
static int mp_div_2d(const mp_int *a, int b, mp_int *c, mp_int *d)
Definition: mpi.c:1310
static int mp_cnt_lsb(const mp_int *a)
Definition: mpi.c:1128
static void mp_clear(mp_int *a)
Definition: mpi.c:255
static int mp_abs(const mp_int *a, mp_int *b)
Definition: mpi.c:290
T MIN(T a, T b)
Definition: polytest.cpp:79
smooth NULL
Definition: ftsmooth.c:416
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
int mp_init_copy(mp_int *a, const mp_int *b)
Definition: mpi.c:2344
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
const GLubyte * c
Definition: glext.h:8905
static int s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:4412
#define mp_iszero(a)
Definition: tomcrypt.h:248
#define MP_GT
Definition: tomcrypt.h:195
static void mp_zero(mp_int *a)
Definition: mpi.c:278
#define MP_ZPOS
Definition: tomcrypt.h:197
#define MP_OKAY
Definition: tomcrypt.h:200
const GLdouble * v
Definition: gl.h:2040
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
static int mp_mul_2d(const mp_int *a, int b, mp_int *c)
Definition: mpi.c:1432
int k
Definition: mpi.c:3369

Referenced by mp_lcm(), and rsa_make_key().

◆ mp_get_int()

unsigned long mp_get_int ( const mp_int a)

Definition at line 2320 of file mpi.c.

2321 {
2322  int i;
2323  unsigned long res;
2324 
2325  if (a->used == 0) {
2326  return 0;
2327  }
2328 
2329  /* get number of digits of the lsb we have to read */
2330  i = MIN(a->used,(int)((sizeof(unsigned long)*CHAR_BIT+DIGIT_BIT-1)/DIGIT_BIT))-1;
2331 
2332  /* get most significant digit of result */
2333  res = DIGIT(a,i);
2334 
2335  while (--i >= 0) {
2336  res = (res << DIGIT_BIT) | DIGIT(a,i);
2337  }
2338 
2339  /* force result to 32-bits always so it is consistent on non 32-bit platforms */
2340  return res & 0xFFFFFFFFUL;
2341 }
#define CHAR_BIT
Definition: urlcache.c:57
#define DIGIT_BIT
Definition: tomcrypt.h:186
T MIN(T a, T b)
Definition: polytest.cpp:79
#define DIGIT(m, k)
Definition: tomcrypt.h:233
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
#define UL
Definition: tui.h:70

Referenced by export_private_key_impl(), and export_public_key_impl().

◆ mp_grow()

static int mp_grow ( mp_int a,
int  size 
)
static

Definition at line 106 of file mpi.c.

107 {
108  int i;
109  mp_digit *tmp;
110 
111  /* if the alloc size is smaller alloc more ram */
112  if (a->alloc < size) {
113  /* ensure there are always at least MP_PREC digits extra on top */
114  size += (MP_PREC * 2) - (size % MP_PREC);
115 
116  /* reallocate the array a->dp
117  *
118  * We store the return in a temporary variable
119  * in case the operation failed we don't want
120  * to overwrite the dp member of a.
121  */
122  tmp = HeapReAlloc(GetProcessHeap(), 0, a->dp, sizeof (mp_digit) * size);
123  if (tmp == NULL) {
124  /* reallocation failed but "a" is still valid [can be freed] */
125  return MP_MEM;
126  }
127 
128  /* reallocation succeeded so set a->dp */
129  a->dp = tmp;
130 
131  /* zero excess digits */
132  i = a->alloc;
133  a->alloc = size;
134  for (; i < a->alloc; i++) {
135  a->dp[i] = 0;
136  }
137  }
138  return MP_OKAY;
139 }
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList
#define MP_PREC
Definition: tomcrypt.h:219
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define MP_MEM
Definition: tomcrypt.h:201
smooth NULL
Definition: ftsmooth.c:416
GLsizeiptr size
Definition: glext.h:5919
#define GetProcessHeap()
Definition: compat.h:395
#define MP_OKAY
Definition: tomcrypt.h:200
#define HeapReAlloc
Definition: compat.h:393
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by fast_mp_montgomery_reduce(), fast_s_mp_mul_digs(), fast_s_mp_mul_high_digs(), fast_s_mp_sqr(), mp_2expt(), mp_add_d(), mp_copy(), mp_div_2(), mp_dr_reduce(), mp_lshd(), mp_montgomery_reduce(), mp_mul_2(), mp_mul_2d(), mp_mul_d(), mp_read_unsigned_bin(), mp_sub_d(), s_mp_add(), and s_mp_sub().

◆ mp_init()

static int mp_init ( mp_int a)
static

Definition at line 202 of file mpi.c.

203 {
204  int i;
205 
206  /* allocate memory required and clear it */
207  a->dp = HeapAlloc(GetProcessHeap(), 0, sizeof (mp_digit) * MP_PREC);
208  if (a->dp == NULL) {
209  return MP_MEM;
210  }
211 
212  /* set the digits to zero */
213  for (i = 0; i < MP_PREC; i++) {
214  a->dp[i] = 0;
215  }
216 
217  /* set the used to zero, allocated digits to the default precision
218  * and sign to positive */
219  a->used = 0;
220  a->alloc = MP_PREC;
221  a->sign = MP_ZPOS;
222 
223  return MP_OKAY;
224 }
#define MP_PREC
Definition: tomcrypt.h:219
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define MP_MEM
Definition: tomcrypt.h:201
smooth NULL
Definition: ftsmooth.c:416
#define GetProcessHeap()
Definition: compat.h:395
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
#define MP_ZPOS
Definition: tomcrypt.h:197
#define MP_OKAY
Definition: tomcrypt.h:200
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_div(), mp_div_2d(), mp_exptmod(), mp_exptmod_fast(), mp_init_copy(), mp_init_multi(), mp_mod(), mp_mulmod(), mp_prime_is_prime(), mp_prime_miller_rabin(), mp_reduce_2k(), mp_reduce_2k_setup(), mp_sqrmod(), and s_mp_exptmod().

◆ mp_init_copy()

int mp_init_copy ( mp_int a,
const mp_int b 
)

Definition at line 2344 of file mpi.c.

2345 {
2346  int res;
2347 
2348  if ((res = mp_init (a)) != MP_OKAY) {
2349  return res;
2350  }
2351  return mp_copy (b, a);
2352 }
static int mp_init(mp_int *a)
Definition: mpi.c:202
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156

Referenced by duplicate_key_impl(), mp_div(), mp_gcd(), mp_prime_miller_rabin(), mp_reduce(), and mp_to_unsigned_bin().

◆ mp_init_multi()

int mp_init_multi ( mp_int mp,
  ... 
)

Definition at line 2354 of file mpi.c.

2355 {
2356  mp_err res = MP_OKAY; /* Assume ok until proven otherwise */
2357  int n = 0; /* Number of ok inits */
2358  mp_int* cur_arg = mp;
2359  va_list args;
2360 
2361  va_start(args, mp); /* init args to next argument from caller */
2362  while (cur_arg != NULL) {
2363  if (mp_init(cur_arg) != MP_OKAY) {
2364  /* Oops - error! Back-track and mp_clear what we already
2365  succeeded in init-ing, then return error.
2366  */
2367  va_list clean_args;
2368 
2369  /* end the current list */
2370  va_end(args);
2371 
2372  /* now start cleaning up */
2373  cur_arg = mp;
2374  va_start(clean_args, mp);
2375  while (n--) {
2376  mp_clear(cur_arg);
2377  cur_arg = va_arg(clean_args, mp_int*);
2378  }
2379  va_end(clean_args);
2380  res = MP_MEM;
2381  break;
2382  }
2383  n++;
2384  cur_arg = va_arg(args, mp_int*);
2385  }
2386  va_end(args);
2387  return res; /* Assumed ok, if error flagged above. */
2388 }
static void mp_clear(mp_int *a)
Definition: mpi.c:255
GLdouble n
Definition: glext.h:7729
Definition: match.c:390
#define va_end(ap)
Definition: acmsvcex.h:90
#define MP_MEM
Definition: tomcrypt.h:201
smooth NULL
Definition: ftsmooth.c:416
char * va_list
Definition: acmsvcex.h:78
static int mp_init(mp_int *a)
Definition: mpi.c:202
#define MP_OKAY
Definition: tomcrypt.h:200
#define va_arg(ap, T)
Definition: acmsvcex.h:89
#define va_start(ap, A)
Definition: acmsvcex.h:91
GLuint res
Definition: glext.h:9613
int mp_err
Definition: tomcrypt.h:214
#define args
Definition: format.c:66

Referenced by fast_mp_invmod(), import_private_key_impl(), import_public_key_impl(), mp_invmod_slow(), mp_lcm(), rsa_exptmod(), and rsa_make_key().

◆ mp_init_size()

static int mp_init_size ( mp_int a,
int  size 
)
static

Definition at line 227 of file mpi.c.

228 {
229  int x;
230 
231  /* pad size so there are always extra digits */
232  size += (MP_PREC * 2) - (size % MP_PREC);
233 
234  /* alloc mem */
235  a->dp = HeapAlloc(GetProcessHeap(), 0, sizeof (mp_digit) * size);
236  if (a->dp == NULL) {
237  return MP_MEM;
238  }
239 
240  /* set the members */
241  a->used = 0;
242  a->alloc = size;
243  a->sign = MP_ZPOS;
244 
245  /* zero the digits */
246  for (x = 0; x < size; x++) {
247  a->dp[x] = 0;
248  }
249 
250  return MP_OKAY;
251 }
#define MP_PREC
Definition: tomcrypt.h:219
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define MP_MEM
Definition: tomcrypt.h:201
smooth NULL
Definition: ftsmooth.c:416
GLsizeiptr size
Definition: glext.h:5919
#define GetProcessHeap()
Definition: compat.h:395
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
#define MP_ZPOS
Definition: tomcrypt.h:197
#define MP_OKAY
Definition: tomcrypt.h:200
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_div(), mp_div_d(), mp_karatsuba_mul(), mp_karatsuba_sqr(), s_mp_mul_digs(), s_mp_mul_high_digs(), and s_mp_sqr().

◆ mp_invmod()

int mp_invmod ( const mp_int a,
mp_int b,
mp_int c 
)

Definition at line 2391 of file mpi.c.

2392 {
2393  /* b cannot be negative */
2394  if (b->sign == MP_NEG || mp_iszero(b) == 1) {
2395  return MP_VAL;
2396  }
2397 
2398  /* if the modulus is odd we can use a faster routine instead */
2399  if (mp_isodd (b) == 1) {
2400  return fast_mp_invmod (a, b, c);
2401  }
2402 
2403  return mp_invmod_slow(a, b, c);
2404 }
static int mp_invmod_slow(const mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:2407
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define mp_isodd(a)
Definition: tomcrypt.h:250
const GLubyte * c
Definition: glext.h:8905
#define mp_iszero(a)
Definition: tomcrypt.h:248
#define MP_VAL
Definition: tomcrypt.h:202
#define MP_NEG
Definition: tomcrypt.h:198
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
static int fast_mp_invmod(const mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:314

Referenced by mp_exptmod(), and rsa_make_key().

◆ mp_invmod_slow()

int mp_invmod_slow ( const mp_int a,
mp_int b,
mp_int c 
)
static

Definition at line 2407 of file mpi.c.

2408 {
2409  mp_int x, y, u, v, A, B, C, D;
2410  int res;
2411 
2412  /* b cannot be negative */
2413  if (b->sign == MP_NEG || mp_iszero(b) == 1) {
2414  return MP_VAL;
2415  }
2416 
2417  /* init temps */
2418  if ((res = mp_init_multi(&x, &y, &u, &v,
2419  &A, &B, &C, &D, NULL)) != MP_OKAY) {
2420  return res;
2421  }
2422 
2423  /* x = a, y = b */
2424  if ((res = mp_copy (a, &x)) != MP_OKAY) {
2425  goto __ERR;
2426  }
2427  if ((res = mp_copy (b, &y)) != MP_OKAY) {
2428  goto __ERR;
2429  }
2430 
2431  /* 2. [modified] if x,y are both even then return an error! */
2432  if (mp_iseven (&x) == 1 && mp_iseven (&y) == 1) {
2433  res = MP_VAL;
2434  goto __ERR;
2435  }
2436 
2437  /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
2438  if ((res = mp_copy (&x, &u)) != MP_OKAY) {
2439  goto __ERR;
2440  }
2441  if ((res = mp_copy (&y, &v)) != MP_OKAY) {
2442  goto __ERR;
2443  }
2444  mp_set (&A, 1);
2445  mp_set (&D, 1);
2446 
2447 top:
2448  /* 4. while u is even do */
2449  while (mp_iseven (&u) == 1) {
2450  /* 4.1 u = u/2 */
2451  if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
2452  goto __ERR;
2453  }
2454  /* 4.2 if A or B is odd then */
2455  if (mp_isodd (&A) == 1 || mp_isodd (&B) == 1) {
2456  /* A = (A+y)/2, B = (B-x)/2 */
2457  if ((res = mp_add (&A, &y, &A)) != MP_OKAY) {
2458  goto __ERR;
2459  }
2460  if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
2461  goto __ERR;
2462  }
2463  }
2464  /* A = A/2, B = B/2 */
2465  if ((res = mp_div_2 (&A, &A)) != MP_OKAY) {
2466  goto __ERR;
2467  }
2468  if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
2469  goto __ERR;
2470  }
2471  }
2472 
2473  /* 5. while v is even do */
2474  while (mp_iseven (&v) == 1) {
2475  /* 5.1 v = v/2 */
2476  if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
2477  goto __ERR;
2478  }
2479  /* 5.2 if C or D is odd then */
2480  if (mp_isodd (&C) == 1 || mp_isodd (&D) == 1) {
2481  /* C = (C+y)/2, D = (D-x)/2 */
2482  if ((res = mp_add (&C, &y, &C)) != MP_OKAY) {
2483  goto __ERR;
2484  }
2485  if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
2486  goto __ERR;
2487  }
2488  }
2489  /* C = C/2, D = D/2 */
2490  if ((res = mp_div_2 (&C, &C)) != MP_OKAY) {
2491  goto __ERR;
2492  }
2493  if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
2494  goto __ERR;
2495  }
2496  }
2497 
2498  /* 6. if u >= v then */
2499  if (mp_cmp (&u, &v) != MP_LT) {
2500  /* u = u - v, A = A - C, B = B - D */
2501  if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
2502  goto __ERR;
2503  }
2504 
2505  if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) {
2506  goto __ERR;
2507  }
2508 
2509  if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
2510  goto __ERR;
2511  }
2512  } else {
2513  /* v - v - u, C = C - A, D = D - B */
2514  if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
2515  goto __ERR;
2516  }
2517 
2518  if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) {
2519  goto __ERR;
2520  }
2521 
2522  if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
2523  goto __ERR;
2524  }
2525  }
2526 
2527  /* if not zero goto step 4 */
2528  if (mp_iszero (&u) == 0)
2529  goto top;
2530 
2531  /* now a = C, b = D, gcd == g*v */
2532 
2533  /* if v != 1 then there is no inverse */
2534  if (mp_cmp_d (&v, 1) != MP_EQ) {
2535  res = MP_VAL;
2536  goto __ERR;
2537  }
2538 
2539  /* if it's too low */
2540  while (mp_cmp_d(&C, 0) == MP_LT) {
2541  if ((res = mp_add(&C, b, &C)) != MP_OKAY) {
2542  goto __ERR;
2543  }
2544  }
2545 
2546  /* too big */
2547  while (mp_cmp_mag(&C, b) != MP_LT) {
2548  if ((res = mp_sub(&C, b, &C)) != MP_OKAY) {
2549  goto __ERR;
2550  }
2551  }
2552 
2553  /* C is now the inverse */
2554  mp_exch (&C, c);
2555  res = MP_OKAY;
2556 __ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
2557  return res;
2558 }
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
int mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:891
#define C(name, bit)
Definition: cpu.h:208
void mp_clear_multi(mp_int *mp,...)
Definition: mpi.c:1032
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
int mp_cmp(const mp_int *a, const mp_int *b)
Definition: mpi.c:1046
#define A(row, col)
#define MP_LT
Definition: tomcrypt.h:193
static void mp_set(mp_int *a, mp_digit b)
Definition: mpi.c:3679
int mp_cmp_d(const mp_int *a, mp_digit b)
Definition: mpi.c:1067
smooth NULL
Definition: ftsmooth.c:416
#define MP_EQ
Definition: tomcrypt.h:194
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define mp_isodd(a)
Definition: tomcrypt.h:250
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
const GLubyte * c
Definition: glext.h:8905
#define mp_iszero(a)
Definition: tomcrypt.h:248
Definition: ttei1.cpp:12
#define MP_VAL
Definition: tomcrypt.h:202
#define MP_OKAY
Definition: tomcrypt.h:200
#define mp_iseven(a)
Definition: tomcrypt.h:249
#define D(name, bit)
const GLdouble * v
Definition: gl.h:2040
#define MP_NEG
Definition: tomcrypt.h:198
Definition: ttei6.cpp:27
#define B(row, col)
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
static int mp_div_2(const mp_int *a, mp_int *b)
Definition: mpi.c:142
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
int mp_sub(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:3771
int mp_init_multi(mp_int *mp,...)
Definition: mpi.c:2354

Referenced by mp_invmod().

◆ mp_karatsuba_mul()

int mp_karatsuba_mul ( const mp_int a,
const mp_int b,
mp_int c 
)
static

Definition at line 2589 of file mpi.c.

2590 {
2591  mp_int x0, x1, y0, y1, t1, x0y0, x1y1;
2592  int B, err;
2593 
2594  /* default the return code to an error */
2595  err = MP_MEM;
2596 
2597  /* min # of digits */
2598  B = MIN (a->used, b->used);
2599 
2600  /* now divide in two */
2601  B = B >> 1;
2602 
2603  /* init copy all the temps */
2604  if (mp_init_size (&x0, B) != MP_OKAY)
2605  goto ERR;
2606  if (mp_init_size (&x1, a->used - B) != MP_OKAY)
2607  goto X0;
2608  if (mp_init_size (&y0, B) != MP_OKAY)
2609  goto X1;
2610  if (mp_init_size (&y1, b->used - B) != MP_OKAY)
2611  goto Y0;
2612 
2613  /* init temps */
2614  if (mp_init_size (&t1, B * 2) != MP_OKAY)
2615  goto Y1;
2616  if (mp_init_size (&x0y0, B * 2) != MP_OKAY)
2617  goto T1;
2618  if (mp_init_size (&x1y1, B * 2) != MP_OKAY)
2619  goto X0Y0;
2620 
2621  /* now shift the digits */
2622  x0.used = y0.used = B;
2623  x1.used = a->used - B;
2624  y1.used = b->used - B;
2625 
2626  {
2627  register int x;
2628  register mp_digit *tmpa, *tmpb, *tmpx, *tmpy;
2629 
2630  /* we copy the digits directly instead of using higher level functions
2631  * since we also need to shift the digits
2632  */
2633  tmpa = a->dp;
2634  tmpb = b->dp;
2635 
2636  tmpx = x0.dp;
2637  tmpy = y0.dp;
2638  for (x = 0; x < B; x++) {
2639  *tmpx++ = *tmpa++;
2640  *tmpy++ = *tmpb++;
2641  }
2642 
2643  tmpx = x1.dp;
2644  for (x = B; x < a->used; x++) {
2645  *tmpx++ = *tmpa++;
2646  }
2647 
2648  tmpy = y1.dp;
2649  for (x = B; x < b->used; x++) {
2650  *tmpy++ = *tmpb++;
2651  }
2652  }
2653 
2654  /* only need to clamp the lower words since by definition the
2655  * upper words x1/y1 must have a known number of digits
2656  */
2657  mp_clamp (&x0);
2658  mp_clamp (&y0);
2659 
2660  /* now calc the products x0y0 and x1y1 */
2661  /* after this x0 is no longer required, free temp [x0==t2]! */
2662  if (mp_mul (&x0, &y0, &x0y0) != MP_OKAY)
2663  goto X1Y1; /* x0y0 = x0*y0 */
2664  if (mp_mul (&x1, &y1, &x1y1) != MP_OKAY)
2665  goto X1Y1; /* x1y1 = x1*y1 */
2666 
2667  /* now calc x1-x0 and y1-y0 */
2668  if (mp_sub (&x1, &x0, &t1) != MP_OKAY)
2669  goto X1Y1; /* t1 = x1 - x0 */
2670  if (mp_sub (&y1, &y0, &x0) != MP_OKAY)
2671  goto X1Y1; /* t2 = y1 - y0 */
2672  if (mp_mul (&t1, &x0, &t1) != MP_OKAY)
2673  goto X1Y1; /* t1 = (x1 - x0) * (y1 - y0) */
2674 
2675  /* add x0y0 */
2676  if (mp_add (&x0y0, &x1y1, &x0) != MP_OKAY)
2677  goto X1Y1; /* t2 = x0y0 + x1y1 */
2678  if (mp_sub (&x0, &t1, &t1) != MP_OKAY)
2679  goto X1Y1; /* t1 = x0y0 + x1y1 - (x1-x0)*(y1-y0) */
2680 
2681  /* shift by B */
2682  if (mp_lshd (&t1, B) != MP_OKAY)
2683  goto X1Y1; /* t1 = (x0y0 + x1y1 - (x1-x0)*(y1-y0))<<B */
2684  if (mp_lshd (&x1y1, B * 2) != MP_OKAY)
2685  goto X1Y1; /* x1y1 = x1y1 << 2*B */
2686 
2687  if (mp_add (&x0y0, &t1, &t1) != MP_OKAY)
2688  goto X1Y1; /* t1 = x0y0 + t1 */
2689  if (mp_add (&t1, &x1y1, c) != MP_OKAY)
2690  goto X1Y1; /* t1 = x0y0 + t1 + x1y1 */
2691 
2692  /* Algorithm succeeded set the return code to MP_OKAY */
2693  err = MP_OKAY;
2694 
2695 X1Y1:mp_clear (&x1y1);
2696 X0Y0:mp_clear (&x0y0);
2697 T1:mp_clear (&t1);
2698 Y1:mp_clear (&y1);
2699 Y0:mp_clear (&y0);
2700 X1:mp_clear (&x1);
2701 X0:mp_clear (&x0);
2702 ERR:
2703  return err;
2704 }
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG y1
Definition: winddi.h:3706
int mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:891
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
GLint x0
Definition: linetemp.h:95
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3706
static void mp_clear(mp_int *a)
Definition: mpi.c:255
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
T MIN(T a, T b)
Definition: polytest.cpp:79
static int mp_lshd(mp_int *a, int b)
Definition: mpi.c:1386
#define MP_MEM
Definition: tomcrypt.h:201
static int mp_init_size(mp_int *a, int size)
Definition: mpi.c:227
int mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:3107
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
#define err(...)
#define MP_OKAY
Definition: tomcrypt.h:200
#define ERR(fmt,...)
Definition: debug.h:109
GLint y0
Definition: linetemp.h:96
#define B(row, col)
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_sub(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:3771
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_mul().

◆ mp_karatsuba_sqr()

int mp_karatsuba_sqr ( const mp_int a,
mp_int b 
)
static

Definition at line 2713 of file mpi.c.

2714 {
2715  mp_int x0, x1, t1, t2, x0x0, x1x1;
2716  int B, err;
2717 
2718  err = MP_MEM;
2719 
2720  /* min # of digits */
2721  B = a->used;
2722 
2723  /* now divide in two */
2724  B = B >> 1;
2725 
2726  /* init copy all the temps */
2727  if (mp_init_size (&x0, B) != MP_OKAY)
2728  goto ERR;
2729  if (mp_init_size (&x1, a->used - B) != MP_OKAY)
2730  goto X0;
2731 
2732  /* init temps */
2733  if (mp_init_size (&t1, a->used * 2) != MP_OKAY)
2734  goto X1;
2735  if (mp_init_size (&t2, a->used * 2) != MP_OKAY)
2736  goto T1;
2737  if (mp_init_size (&x0x0, B * 2) != MP_OKAY)
2738  goto T2;
2739  if (mp_init_size (&x1x1, (a->used - B) * 2) != MP_OKAY)
2740  goto X0X0;
2741 
2742  {
2743  register int x;
2744  register mp_digit *dst, *src;
2745 
2746  src = a->dp;
2747 
2748  /* now shift the digits */
2749  dst = x0.dp;
2750  for (x = 0; x < B; x++) {
2751  *dst++ = *src++;
2752  }
2753 
2754  dst = x1.dp;
2755  for (x = B; x < a->used; x++) {
2756  *dst++ = *src++;
2757  }
2758  }
2759 
2760  x0.used = B;
2761  x1.used = a->used - B;
2762 
2763  mp_clamp (&x0);
2764 
2765  /* now calc the products x0*x0 and x1*x1 */
2766  if (mp_sqr (&x0, &x0x0) != MP_OKAY)
2767  goto X1X1; /* x0x0 = x0*x0 */
2768  if (mp_sqr (&x1, &x1x1) != MP_OKAY)
2769  goto X1X1; /* x1x1 = x1*x1 */
2770 
2771  /* now calc (x1-x0)**2 */
2772  if (mp_sub (&x1, &x0, &t1) != MP_OKAY)
2773  goto X1X1; /* t1 = x1 - x0 */
2774  if (mp_sqr (&t1, &t1) != MP_OKAY)
2775  goto X1X1; /* t1 = (x1 - x0) * (x1 - x0) */
2776 
2777  /* add x0y0 */
2778  if (s_mp_add (&x0x0, &x1x1, &t2) != MP_OKAY)
2779  goto X1X1; /* t2 = x0x0 + x1x1 */
2780  if (mp_sub (&t2, &t1, &t1) != MP_OKAY)
2781  goto X1X1; /* t1 = x0x0 + x1x1 - (x1-x0)*(x1-x0) */
2782 
2783  /* shift by B */
2784  if (mp_lshd (&t1, B) != MP_OKAY)
2785  goto X1X1; /* t1 = (x0x0 + x1x1 - (x1-x0)*(x1-x0))<<B */
2786  if (mp_lshd (&x1x1, B * 2) != MP_OKAY)
2787  goto X1X1; /* x1x1 = x1x1 << 2*B */
2788 
2789  if (mp_add (&x0x0, &t1, &t1) != MP_OKAY)
2790  goto X1X1; /* t1 = x0x0 + t1 */
2791  if (mp_add (&t1, &x1x1, b) != MP_OKAY)
2792  goto X1X1; /* t1 = x0x0 + t1 + x1x1 */
2793 
2794  err = MP_OKAY;
2795 
2796 X1X1:mp_clear (&x1x1);
2797 X0X0:mp_clear (&x0x0);
2798 T2:mp_clear (&t2);
2799 T1:mp_clear (&t1);
2800 X1:mp_clear (&x1);
2801 X0:mp_clear (&x0);
2802 ERR:
2803  return err;
2804 }
int mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:891
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
GLint x0
Definition: linetemp.h:95
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3706
static void mp_clear(mp_int *a)
Definition: mpi.c:255
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
static int s_mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:3925
static int mp_sqr(const mp_int *a, mp_int *b)
Definition: mpi.c:3729
static int mp_lshd(mp_int *a, int b)
Definition: mpi.c:1386
#define MP_MEM
Definition: tomcrypt.h:201
static int mp_init_size(mp_int *a, int size)
Definition: mpi.c:227
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLenum src
Definition: glext.h:6340
#define err(...)
#define MP_OKAY
Definition: tomcrypt.h:200
#define ERR(fmt,...)
Definition: debug.h:109
GLenum GLenum dst
Definition: glext.h:6340
#define B(row, col)
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_sub(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:3771
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_sqr().

◆ mp_lcm()

int mp_lcm ( const mp_int a,
const mp_int b,
mp_int c 
)

Definition at line 2807 of file mpi.c.

2808 {
2809  int res;
2810  mp_int t1, t2;
2811 
2812 
2813  if ((res = mp_init_multi (&t1, &t2, NULL)) != MP_OKAY) {
2814  return res;
2815  }
2816 
2817  /* t1 = get the GCD of the two inputs */
2818  if ((res = mp_gcd (a, b, &t1)) != MP_OKAY) {
2819  goto __T;
2820  }
2821 
2822  /* divide the smallest by the GCD */
2823  if (mp_cmp_mag(a, b) == MP_LT) {
2824  /* store quotient in t2 so that t2 * b is the LCM */
2825  if ((res = mp_div(a, &t1, &t2, NULL)) != MP_OKAY) {
2826  goto __T;
2827  }
2828  res = mp_mul(b, &t2, c);
2829  } else {
2830  /* store quotient in t2 so that t2 * a is the LCM */
2831  if ((res = mp_div(b, &t1, &t2, NULL)) != MP_OKAY) {
2832  goto __T;
2833  }
2834  res = mp_mul(a, &t2, c);
2835  }
2836 
2837  /* fix the sign to positive */
2838  c->sign = MP_ZPOS;
2839 
2840 __T:
2841  mp_clear_multi (&t1, &t2, NULL);
2842  return res;
2843 }
void mp_clear_multi(mp_int *mp,...)
Definition: mpi.c:1032
#define __T(x)
Definition: vfdio.h:17
#define MP_LT
Definition: tomcrypt.h:193
smooth NULL
Definition: ftsmooth.c:416
int mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:3107
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
static int mp_div(const mp_int *a, const mp_int *b, mp_int *c, mp_int *d)
Definition: mpi.c:1565
const GLubyte * c
Definition: glext.h:8905
#define MP_ZPOS
Definition: tomcrypt.h:197
#define MP_OKAY
Definition: tomcrypt.h:200
int mp_gcd(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:2228
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_init_multi(mp_int *mp,...)
Definition: mpi.c:2354

Referenced by rsa_make_key().

◆ mp_lshd()

static int mp_lshd ( mp_int a,
int  b 
)
static

Definition at line 1386 of file mpi.c.

1387 {
1388  int x, res;
1389 
1390  /* if it's less than zero return */
1391  if (b <= 0) {
1392  return MP_OKAY;
1393  }
1394 
1395  /* grow to fit the new digits */
1396  if (a->alloc < a->used + b) {
1397  if ((res = mp_grow (a, a->used + b)) != MP_OKAY) {
1398  return res;
1399  }
1400  }
1401 
1402  {
1403  register mp_digit *top, *bottom;
1404 
1405  /* increment the used by the shift amount then copy upwards */
1406  a->used += b;
1407 
1408  /* top */
1409  top = a->dp + a->used - 1;
1410 
1411  /* base */
1412  bottom = a->dp + a->used - 1 - b;
1413 
1414  /* much like mp_rshd this is implemented using a sliding window
1415  * except the window goes the other way around. Copying from
1416  * the bottom to the top. see bn_mp_rshd.c for more info.
1417  */
1418  for (x = a->used - 1; x >= b; x--) {
1419  *top-- = *bottom--;
1420  }
1421 
1422  /* zero the lower digits */
1423  top = a->dp;
1424  for (x = 0; x < b; x++) {
1425  *top++ = 0;
1426  }
1427  }
1428  return MP_OKAY;
1429 }
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLint GLint bottom
Definition: glext.h:7726
#define b
Definition: ke_i.h:79
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_div(), mp_karatsuba_mul(), mp_karatsuba_sqr(), mp_mul_2d(), and mp_reduce().

◆ mp_mod()

int mp_mod ( const mp_int a,
mp_int b,
mp_int c 
)

Definition at line 2847 of file mpi.c.

2848 {
2849  mp_int t;
2850  int res;
2851 
2852  if ((res = mp_init (&t)) != MP_OKAY) {
2853  return res;
2854  }
2855 
2856  if ((res = mp_div (a, b, NULL, &t)) != MP_OKAY) {
2857  mp_clear (&t);
2858  return res;
2859  }
2860 
2861  if (t.sign != b->sign) {
2862  res = mp_add (b, &t, c);
2863  } else {
2864  res = MP_OKAY;
2865  mp_exch (&t, c);
2866  }
2867 
2868  mp_clear (&t);
2869  return res;
2870 }
int mp_add(mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:891
static void mp_clear(mp_int *a)
Definition: mpi.c:255
GLdouble GLdouble t
Definition: gl.h:2047
int t
Definition: mpi.c:3369
smooth NULL
Definition: ftsmooth.c:416
static int mp_init(mp_int *a)
Definition: mpi.c:202
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
static int mp_div(const mp_int *a, const mp_int *b, mp_int *c, mp_int *d)
Definition: mpi.c:1565
static void mp_exch(mp_int *a, mp_int *b)
Definition: mpi.c:192
const GLubyte * c
Definition: glext.h:8905
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by mp_exptmod_fast(), mp_mulmod(), mp_sqrmod(), rsa_make_key(), and s_mp_exptmod().

◆ mp_mod_2d()

static int mp_mod_2d ( const mp_int a,
int  b,
mp_int c 
)
static

Definition at line 1227 of file mpi.c.

1228 {
1229  int x, res;
1230 
1231  /* if b is <= 0 then zero the int */
1232  if (b <= 0) {
1233  mp_zero (c);
1234  return MP_OKAY;
1235  }
1236 
1237  /* if the modulus is larger than the value than return */
1238  if (b > a->used * DIGIT_BIT) {
1239  res = mp_copy (a, c);
1240  return res;
1241  }
1242 
1243  /* copy */
1244  if ((res = mp_copy (a, c)) != MP_OKAY) {
1245  return res;
1246  }
1247 
1248  /* zero digits above the last digit of the modulus */
1249  for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++) {
1250  c->dp[x] = 0;
1251  }
1252  /* clear the digit that is not completely outside/inside the modulus */
1253  c->dp[b / DIGIT_BIT] &= (1 << ((mp_digit)b % DIGIT_BIT)) - 1;
1254  mp_clamp (c);
1255  return MP_OKAY;
1256 }
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
static void mp_zero(mp_int *a)
Definition: mpi.c:278
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_div_2d(), and mp_reduce().

◆ mp_mod_d()

static int mp_mod_d ( const mp_int a,
mp_digit  b,
mp_digit c 
)
static

Definition at line 2873 of file mpi.c.

2874 {
2875  return mp_div_d(a, b, NULL, c);
2876 }
smooth NULL
Definition: ftsmooth.c:416
static int mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
Definition: mpi.c:1762
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by mp_prime_is_divisible().

◆ mp_montgomery_calc_normalization()

int mp_montgomery_calc_normalization ( mp_int a,
const mp_int b 
)
static

Definition at line 2945 of file mpi.c.

2946 {
2947  int x, bits, res;
2948 
2949  /* how many bits of last digit does b use */
2950  bits = mp_count_bits (b) % DIGIT_BIT;
2951 
2952 
2953  if (b->used > 1) {
2954  if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) {
2955  return res;
2956  }
2957  } else {
2958  mp_set(a, 1);
2959  bits = 1;
2960  }
2961 
2962 
2963  /* now compute C = A * B mod b */
2964  for (x = bits - 1; x < DIGIT_BIT; x++) {
2965  if ((res = mp_mul_2 (a, a)) != MP_OKAY) {
2966  return res;
2967  }
2968  if (mp_cmp_mag (a, b) != MP_LT) {
2969  if ((res = s_mp_sub (a, b, a)) != MP_OKAY) {
2970  return res;
2971  }
2972  }
2973  }
2974 
2975  return MP_OKAY;
2976 }
int mp_count_bits(const mp_int *a)
Definition: mpi.c:1203
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
#define DIGIT_BIT
Definition: tomcrypt.h:186
#define MP_LT
Definition: tomcrypt.h:193
static void mp_set(mp_int *a, mp_digit b)
Definition: mpi.c:3679
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
static int s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:4412
static int mp_2expt(mp_int *a, int b)
Definition: mpi.c:869
#define MP_OKAY
Definition: tomcrypt.h:200
static int mp_mul_2(const mp_int *a, mp_int *b)
Definition: mpi.c:2879
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by mp_exptmod_fast().

◆ mp_montgomery_reduce()

int mp_montgomery_reduce ( mp_int a,
const mp_int m,
mp_digit  mp 
)
static

Definition at line 2980 of file mpi.c.

2981 {
2982  int ix, res, digs;
2983  mp_digit mu;
2984 
2985  /* can the fast reduction [comba] method be used?
2986  *
2987  * Note that unlike in mul you're safely allowed *less*
2988  * than the available columns [255 per default] since carries
2989  * are fixed up in the inner loop.
2990  */
2991  digs = n->used * 2 + 1;
2992  if ((digs < MP_WARRAY) &&
2993  n->used <
2994  (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
2995  return fast_mp_montgomery_reduce (x, n, rho);
2996  }
2997 
2998  /* grow the input as required */
2999  if (x->alloc < digs) {
3000  if ((res = mp_grow (x, digs)) != MP_OKAY) {
3001  return res;
3002  }
3003  }
3004  x->used = digs;
3005 
3006  for (ix = 0; ix < n->used; ix++) {
3007  /* mu = ai * rho mod b
3008  *
3009  * The value of rho must be precalculated via
3010  * montgomery_setup() such that
3011  * it equals -1/n0 mod b this allows the
3012  * following inner loop to reduce the
3013  * input one digit at a time
3014  */
3015  mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK);
3016 
3017  /* a = a + mu * m * b**i */
3018  {
3019  register int iy;
3020  register mp_digit *tmpn, *tmpx, u;
3021  register mp_word r;
3022 
3023  /* alias for digits of the modulus */
3024  tmpn = n->dp;
3025 
3026  /* alias for the digits of x [the input] */
3027  tmpx = x->dp + ix;
3028 
3029  /* set the carry to zero */
3030  u = 0;
3031 
3032  /* Multiply and add in place */
3033  for (iy = 0; iy < n->used; iy++) {
3034  /* compute product and sum */
3035  r = ((mp_word)mu) * ((mp_word)*tmpn++) +
3036  ((mp_word) u) + ((mp_word) * tmpx);
3037 
3038  /* get carry */
3039  u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
3040 
3041  /* fix digit */
3042  *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK));
3043  }
3044  /* At this point the ix'th digit of x should be zero */
3045 
3046 
3047  /* propagate carries upwards as required*/
3048  while (u) {
3049  *tmpx += u;
3050  u = *tmpx >> DIGIT_BIT;
3051  *tmpx++ &= MP_MASK;
3052  }
3053  }
3054  }
3055 
3056  /* at this point the n.used'th least
3057  * significant digits of x are all zero
3058  * which means we can shift x to the
3059  * right by n.used digits and the
3060  * residue is unchanged.
3061  */
3062 
3063  /* x = x/b**n.used */
3064  mp_clamp(x);
3065  mp_rshd (x, n->used);
3066 
3067  /* if x >= n then x = x - n */
3068  if (mp_cmp_mag (x, n) != MP_LT) {
3069  return s_mp_sub (x, n, x);
3070  }
3071 
3072  return MP_OKAY;
3073 }
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define MP_MASK
Definition: tomcrypt.h:189
GLdouble n
Definition: glext.h:7729
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define CHAR_BIT
Definition: urlcache.c:57
int iy
Definition: tritemp.h:491
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
#define MP_LT
Definition: tomcrypt.h:193
static int fast_mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho)
Definition: mpi.c:444
static int s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:4412
#define MP_WARRAY
Definition: tomcrypt.h:222
#define MP_OKAY
Definition: tomcrypt.h:200
static void mp_rshd(mp_int *a, int b)
Definition: mpi.c:1259
static int mp_cmp_mag(const mp_int *a, const mp_int *b)
Definition: mpi.c:1090
GLuint res
Definition: glext.h:9613
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_exptmod_fast().

◆ mp_montgomery_setup()

int mp_montgomery_setup ( const mp_int a,
mp_digit mp 
)
static

Definition at line 3077 of file mpi.c.

3078 {
3079  mp_digit x, b;
3080 
3081 /* fast inversion mod 2**k
3082  *
3083  * Based on the fact that
3084  *
3085  * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
3086  * => 2*X*A - X*X*A*A = 1
3087  * => 2*(1) - (1) = 1
3088  */
3089  b = n->dp[0];
3090 
3091  if ((b & 1) == 0) {
3092  return MP_VAL;
3093  }
3094 
3095  x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
3096  x *= 2 - b * x; /* here x*a==1 mod 2**8 */
3097  x *= 2 - b * x; /* here x*a==1 mod 2**16 */
3098  x *= 2 - b * x; /* here x*a==1 mod 2**32 */
3099 
3100  /* rho = -1/m mod b */
3101  *rho = (((mp_word)1 << ((mp_word) DIGIT_BIT)) - x) & MP_MASK;
3102 
3103  return MP_OKAY;
3104 }
#define MP_MASK
Definition: tomcrypt.h:189
GLdouble n
Definition: glext.h:7729
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
#define b
Definition: ke_i.h:79
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_VAL
Definition: tomcrypt.h:202
#define MP_OKAY
Definition: tomcrypt.h:200
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_exptmod_fast().

◆ mp_mul()

int mp_mul ( const mp_int a,
const mp_int b,
mp_int c 
)

Definition at line 3107 of file mpi.c.

3108 {
3109  int res, neg;
3110  neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
3111 
3112  /* use Karatsuba? */
3113  if (MIN (a->used, b->used) >= KARATSUBA_MUL_CUTOFF) {
3114  res = mp_karatsuba_mul (a, b, c);
3115  } else
3116  {
3117  /* can we use the fast multiplier?
3118  *
3119  * The fast multiplier can be used if the output will
3120  * have less than MP_WARRAY digits and the number of
3121  * digits won't affect carry propagation
3122  */
3123  int digs = a->used + b->used + 1;
3124 
3125  if ((digs < MP_WARRAY) &&
3126  MIN(a->used, b->used) <=
3127  (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
3128  res = fast_s_mp_mul_digs (a, b, c, digs);
3129  } else
3130  res = s_mp_mul (a, b, c); /* uses s_mp_mul_digs */
3131  }
3132  c->sign = (c->used > 0) ? neg : MP_ZPOS;
3133  return res;
3134 }
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList
#define CHAR_BIT
Definition: urlcache.c:57
static int mp_karatsuba_mul(const mp_int *a, const mp_int *b, mp_int *c)
Definition: mpi.c:2589
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
T MIN(T a, T b)
Definition: polytest.cpp:79
static int fast_s_mp_mul_digs(const mp_int *a, const mp_int *b, mp_int *c, int digs)
Definition: mpi.c:604
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define s_mp_mul(a, b, c)
Definition: mpi.c:95
const GLubyte * c
Definition: glext.h:8905
#define MP_WARRAY
Definition: tomcrypt.h:222
static const int KARATSUBA_MUL_CUTOFF
Definition: mpi.c:42
#define MP_ZPOS
Definition: tomcrypt.h:197
#define MP_NEG
Definition: tomcrypt.h:198
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by mp_exptmod_fast(), mp_karatsuba_mul(), mp_lcm(), mp_mulmod(), mp_reduce(), rsa_exptmod(), rsa_make_key(), and s_mp_exptmod().

◆ mp_mul_2()

static int mp_mul_2 ( const mp_int a,
mp_int b 
)
static

Definition at line 2879 of file mpi.c.

2880 {
2881  int x, res, oldused;
2882 
2883  /* grow to accommodate result */
2884  if (b->alloc < a->used + 1) {
2885  if ((res = mp_grow (b, a->used + 1)) != MP_OKAY) {
2886  return res;
2887  }
2888  }
2889 
2890  oldused = b->used;
2891  b->used = a->used;
2892 
2893  {
2894  register mp_digit r, rr, *tmpa, *tmpb;
2895 
2896  /* alias for source */
2897  tmpa = a->dp;
2898 
2899  /* alias for dest */
2900  tmpb = b->dp;
2901 
2902  /* carry */
2903  r = 0;
2904  for (x = 0; x < a->used; x++) {
2905 
2906  /* get what will be the *next* carry bit from the
2907  * MSB of the current digit
2908  */
2909  rr = *tmpa >> ((mp_digit)(DIGIT_BIT - 1));
2910 
2911  /* now shift up this digit, add in the carry [from the previous] */
2912  *tmpb++ = ((*tmpa++ << ((mp_digit)1)) | r) & MP_MASK;
2913 
2914  /* copy the carry that would be from the source
2915  * digit into the next iteration
2916  */
2917  r = rr;
2918  }
2919 
2920  /* new leading digit? */
2921  if (r != 0) {
2922  /* add a MSB which is always 1 at this point */
2923  *tmpb = 1;
2924  ++(b->used);
2925  }
2926 
2927  /* now zero any excess digits on the destination
2928  * that we didn't write to
2929  */
2930  tmpb = b->dp + b->used;
2931  for (x = b->used; x < oldused; x++) {
2932  *tmpb++ = 0;
2933  }
2934  }
2935  b->sign = a->sign;
2936  return MP_OKAY;
2937 }
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define MP_MASK
Definition: tomcrypt.h:189
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_montgomery_calc_normalization(), and mp_prime_random_ex().

◆ mp_mul_2d()

static int mp_mul_2d ( const mp_int a,
int  b,
mp_int c 
)
static

Definition at line 1432 of file mpi.c.

1433 {
1434  mp_digit d;
1435  int res;
1436 
1437  /* copy */
1438  if (a != c) {
1439  if ((res = mp_copy (a, c)) != MP_OKAY) {
1440  return res;
1441  }
1442  }
1443 
1444  if (c->alloc < c->used + b/DIGIT_BIT + 1) {
1445  if ((res = mp_grow (c, c->used + b / DIGIT_BIT + 1)) != MP_OKAY) {
1446  return res;
1447  }
1448  }
1449 
1450  /* shift by as many digits in the bit count */
1451  if (b >= DIGIT_BIT) {
1452  if ((res = mp_lshd (c, b / DIGIT_BIT)) != MP_OKAY) {
1453  return res;
1454  }
1455  }
1456 
1457  /* shift any bit count < DIGIT_BIT */
1458  d = (mp_digit) (b % DIGIT_BIT);
1459  if (d != 0) {
1460  register mp_digit *tmpc, shift, mask, r, rr;
1461  register int x;
1462 
1463  /* bitmask for carries */
1464  mask = (((mp_digit)1) << d) - 1;
1465 
1466  /* shift for msbs */
1467  shift = DIGIT_BIT - d;
1468 
1469  /* alias */
1470  tmpc = c->dp;
1471 
1472  /* carry */
1473  r = 0;
1474  for (x = 0; x < c->used; x++) {
1475  /* get the higher bits of the current word */
1476  rr = (*tmpc >> shift) & mask;
1477 
1478  /* shift the current word and OR in the carry */
1479  *tmpc = ((*tmpc << d) | r) & MP_MASK;
1480  ++tmpc;
1481 
1482  /* set the carry to the carry bits of the current word */
1483  r = rr;
1484  }
1485 
1486  /* set final carry */
1487  if (r != 0) {
1488  c->dp[(c->used)++] = r;
1489  }
1490  }
1491  mp_clamp (c);
1492  return MP_OKAY;
1493 }
#define shift
Definition: input.c:1668
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define MP_MASK
Definition: tomcrypt.h:189
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLenum GLint GLuint mask
Definition: glext.h:6028
static int mp_lshd(mp_int *a, int b)
Definition: mpi.c:1386
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define d
Definition: ke_i.h:81
const GLubyte * c
Definition: glext.h:8905
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
int mp_copy(const mp_int *a, mp_int *b)
Definition: mpi.c:1156
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_div(), mp_gcd(), mp_read_unsigned_bin(), and mp_set_int().

◆ mp_mul_d()

static int mp_mul_d ( const mp_int a,
mp_digit  b,
mp_int c 
)
static

Definition at line 1497 of file mpi.c.

1498 {
1499  mp_digit u, *tmpa, *tmpc;
1500  mp_word r;
1501  int ix, res, olduse;
1502 
1503  /* make sure c is big enough to hold a*b */
1504  if (c->alloc < a->used + 1) {
1505  if ((res = mp_grow (c, a->used + 1)) != MP_OKAY) {
1506  return res;
1507  }
1508  }
1509 
1510  /* get the original destinations used count */
1511  olduse = c->used;
1512 
1513  /* set the sign */
1514  c->sign = a->sign;
1515 
1516  /* alias for a->dp [source] */
1517  tmpa = a->dp;
1518 
1519  /* alias for c->dp [dest] */
1520  tmpc = c->dp;
1521 
1522  /* zero carry */
1523  u = 0;
1524 
1525  /* compute columns */
1526  for (ix = 0; ix < a->used; ix++) {
1527  /* compute product and carry sum for this term */
1528  r = ((mp_word) u) + ((mp_word)*tmpa++) * ((mp_word)b);
1529 
1530  /* mask off higher bits to get a single digit */
1531  *tmpc++ = (mp_digit) (r & ((mp_word) MP_MASK));
1532 
1533  /* send carry into next iteration */
1534  u = (mp_digit) (r >> ((mp_word) DIGIT_BIT));
1535  }
1536 
1537  /* store final carry [if any] */
1538  *tmpc++ = u;
1539 
1540  /* now zero digits above the top */
1541  while (ix++ < olduse) {
1542  *tmpc++ = 0;
1543  }
1544 
1545  /* set used count */
1546  c->used = a->used + 1;
1547  mp_clamp(c);
1548 
1549  return MP_OKAY;
1550 }
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
static void mp_clamp(mp_int *a)
Definition: mpi.c:1017
static int mp_grow(mp_int *a, int size)
Definition: mpi.c:106
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define MP_MASK
Definition: tomcrypt.h:189
ulong64 mp_word
Definition: tomcrypt.h:185
#define DIGIT_BIT
Definition: tomcrypt.h:186
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLubyte * c
Definition: glext.h:8905
#define MP_OKAY
Definition: tomcrypt.h:200
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
unsigned long mp_digit
Definition: tomcrypt.h:184

Referenced by mp_div(), and mp_reduce_2k().

◆ mp_mulmod()

int mp_mulmod ( const mp_int a,
const mp_int b,
mp_int c,
mp_int d 
)

Definition at line 3138 of file mpi.c.

3139 {
3140  int res;
3141  mp_int t;
3142 
3143  if ((res = mp_init (&t)) != MP_OKAY) {
3144  return res;
3145  }
3146 
3147  if ((res = mp_mul (a, b, &t)) != MP_OKAY) {
3148  mp_clear (&t);
3149  return res;
3150  }
3151  res = mp_mod (&t, c, d);
3152  mp_clear (&t);
3153  return res;
3154 }
static void mp_clear(mp_int *a)
Definition: mpi.c:255
int mp_mod(const mp_int *a, mp_int *b, mp_int *c)
Definition: mpi.c:2847