1198092Srdivacky/* $NetBSD: bn_mp_prime_random_ex.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */ 2198092Srdivacky 3198092Srdivacky#include <tommath.h> 4198092Srdivacky#ifdef BN_MP_PRIME_RANDOM_EX_C 5198092Srdivacky/* LibTomMath, multiple-precision integer library -- Tom St Denis 6198092Srdivacky * 7198092Srdivacky * LibTomMath is a library that provides multiple-precision 8198092Srdivacky * integer arithmetic as well as number theoretic functionality. 9198092Srdivacky * 10198092Srdivacky * The library was designed directly after the MPI library by 11198092Srdivacky * Michael Fromberger but has been written from scratch with 12198092Srdivacky * additional optimizations in place. 13198092Srdivacky * 14212904Sdim * The library is free for all purposes without any express 15276479Sdim * guarantee it works. 16198092Srdivacky * 17198092Srdivacky * Tom St Denis, tomstdenis@gmail.com, http://libtom.org 18198092Srdivacky */ 19206084Srdivacky 20203955Srdivacky/* makes a truly random prime of a given size (bits), 21203955Srdivacky * 22198092Srdivacky * Flags are as follows: 23234353Sdim * 24198092Srdivacky * LTM_PRIME_BBS - make prime congruent to 3 mod 4 25198092Srdivacky * LTM_PRIME_SAFE - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS) 26198092Srdivacky * LTM_PRIME_2MSB_OFF - make the 2nd highest bit zero 27198092Srdivacky * LTM_PRIME_2MSB_ON - make the 2nd highest bit one 28198092Srdivacky * 29198092Srdivacky * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can 30198092Srdivacky * have passed to the callback (e.g. a state or something). This function doesn't use "dat" itself 31198092Srdivacky * so it can be NULL 32198092Srdivacky * 33198092Srdivacky */ 34198092Srdivacky 35198092Srdivacky/* This is possibly the mother of all prime generation functions, muahahahahaha! */ 36198092Srdivackyint mp_prime_random_ex(mp_int *a, int t, int size, int flags, ltm_prime_callback cb, void *dat) 37198092Srdivacky{ 38280031Sdim unsigned char *tmp, maskAND, maskOR_msb, maskOR_lsb; 39280031Sdim int res, err, bsize, maskOR_msb_offset; 40280031Sdim 41280031Sdim /* sanity check the input */ 42280031Sdim if (size <= 1 || t <= 0) { 43280031Sdim return MP_VAL; 44280031Sdim } 45280031Sdim 46280031Sdim /* LTM_PRIME_SAFE implies LTM_PRIME_BBS */ 47280031Sdim if (flags & LTM_PRIME_SAFE) { 48280031Sdim flags |= LTM_PRIME_BBS; 49280031Sdim } 50280031Sdim 51280031Sdim /* calc the byte size */ 52280031Sdim bsize = (size>>3) + ((size&7)?1:0); 53280031Sdim 54280031Sdim /* we need a buffer of bsize bytes */ 55280031Sdim tmp = OPT_CAST(unsigned char) XMALLOC(bsize); 56280031Sdim if (tmp == NULL) { 57280031Sdim return MP_MEM; 58280031Sdim } 59280031Sdim 60280031Sdim /* calc the maskAND value for the MSbyte*/ 61280031Sdim maskAND = ((size&7) == 0) ? 0xFF : (0xFF >> (8 - (size & 7))); 62280031Sdim 63280031Sdim /* calc the maskOR_msb */ 64280031Sdim maskOR_msb = 0; 65198092Srdivacky maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0; 66198092Srdivacky if (flags & LTM_PRIME_2MSB_ON) { 67198092Srdivacky maskOR_msb |= 0x80 >> ((9 - size) & 7); 68249423Sdim } 69249423Sdim 70249423Sdim /* get the maskOR_lsb */ 71249423Sdim maskOR_lsb = 1; 72249423Sdim if (flags & LTM_PRIME_BBS) { 73249423Sdim maskOR_lsb |= 3; 74249423Sdim } 75249423Sdim 76249423Sdim do { 77249423Sdim /* read the bytes */ 78249423Sdim if (cb(tmp, bsize, dat) != bsize) { 79249423Sdim err = MP_VAL; 80249423Sdim goto error; 81249423Sdim } 82198092Srdivacky 83249423Sdim /* work over the MSbyte */ 84249423Sdim tmp[0] &= maskAND; 85249423Sdim tmp[0] |= 1 << ((size - 1) & 7); 86249423Sdim 87249423Sdim /* mix in the maskORs */ 88198092Srdivacky tmp[maskOR_msb_offset] |= maskOR_msb; 89249423Sdim tmp[bsize-1] |= maskOR_lsb; 90249423Sdim 91249423Sdim /* read it in */ 92249423Sdim if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY) { goto error; } 93249423Sdim 94249423Sdim /* is it prime? */ 95249423Sdim if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; } 96198092Srdivacky if (res == MP_NO) { 97249423Sdim continue; 98249423Sdim } 99249423Sdim 100249423Sdim if (flags & LTM_PRIME_SAFE) { 101249423Sdim /* see if (a-1)/2 is prime */ 102249423Sdim if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { goto error; } 103249423Sdim if ((err = mp_div_2(a, a)) != MP_OKAY) { goto error; } 104249423Sdim 105249423Sdim /* is it prime? */ 106249423Sdim if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; } 107249423Sdim } 108249423Sdim } while (res == MP_NO); 109249423Sdim 110249423Sdim if (flags & LTM_PRIME_SAFE) { 111249423Sdim /* restore a to the original value */ 112249423Sdim if ((err = mp_mul_2(a, a)) != MP_OKAY) { goto error; } 113249423Sdim if ((err = mp_add_d(a, 1, a)) != MP_OKAY) { goto error; } 114249423Sdim } 115249423Sdim 116249423Sdim err = MP_OKAY; 117198092Srdivackyerror: 118198092Srdivacky XFREE(tmp); 119198092Srdivacky return err; 120198092Srdivacky} 121198092Srdivacky 122198092Srdivacky 123198092Srdivacky#endif 124198092Srdivacky 125198092Srdivacky/* Source: /cvs/libtom/libtommath/bn_mp_prime_random_ex.c,v */ 126198092Srdivacky/* Revision: 1.5 */ 127198092Srdivacky/* Date: 2006/12/28 01:25:13 */ 128198092Srdivacky