1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_PRIME_RANDOM_EX_C 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* LibTomMath, multiple-precision integer library -- Tom St Denis 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LibTomMath is a library that provides multiple-precision 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * integer arithmetic as well as number theoretic functionality. 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library was designed directly after the MPI library by 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Michael Fromberger but has been written from scratch with 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * additional optimizations in place. 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library is free for all purposes without any express 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * guarantee it works. 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* makes a truly random prime of a given size (bits), 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Flags are as follows: 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LTM_PRIME_BBS - make prime congruent to 3 mod 4 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LTM_PRIME_SAFE - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS) 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LTM_PRIME_2MSB_OFF - make the 2nd highest bit zero 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LTM_PRIME_2MSB_ON - make the 2nd highest bit one 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * have passed to the callback (e.g. a state or something). This function doesn't use "dat" itself 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * so it can be NULL 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* This is possibly the mother of all prime generation functions, muahahahahaha! */ 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_random_ex(mp_int *a, int t, int size, int flags, ltm_prime_callback cb, void *dat) 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project unsigned char *tmp, maskAND, maskOR_msb, maskOR_lsb; 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int res, err, bsize, maskOR_msb_offset; 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* sanity check the input */ 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (size <= 1 || t <= 0) { 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_VAL; 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* LTM_PRIME_SAFE implies LTM_PRIME_BBS */ 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (flags & LTM_PRIME_SAFE) { 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project flags |= LTM_PRIME_BBS; 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* calc the byte size */ 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bsize = (size>>3) + ((size&7)?1:0); 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we need a buffer of bsize bytes */ 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp = OPT_CAST(unsigned char) XMALLOC(bsize); 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (tmp == NULL) { 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_MEM; 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* calc the maskAND value for the MSbyte*/ 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project maskAND = ((size&7) == 0) ? 0xFF : (0xFF >> (8 - (size & 7))); 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* calc the maskOR_msb */ 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project maskOR_msb = 0; 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0; 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (flags & LTM_PRIME_2MSB_ON) { 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project maskOR_msb |= 0x80 >> ((9 - size) & 7); 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get the maskOR_lsb */ 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project maskOR_lsb = 1; 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (flags & LTM_PRIME_BBS) { 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project maskOR_lsb |= 3; 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project do { 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* read the bytes */ 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (cb(tmp, bsize, dat) != bsize) { 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = MP_VAL; 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto error; 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* work over the MSbyte */ 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp[0] &= maskAND; 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp[0] |= 1 << ((size - 1) & 7); 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* mix in the maskORs */ 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp[maskOR_msb_offset] |= maskOR_msb; 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp[bsize-1] |= maskOR_lsb; 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* read it in */ 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY) { goto error; } 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* is it prime? */ 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; } 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (res == MP_NO) { 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (flags & LTM_PRIME_SAFE) { 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* see if (a-1)/2 is prime */ 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { goto error; } 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_div_2(a, a)) != MP_OKAY) { goto error; } 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* is it prime? */ 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; } 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } while (res == MP_NO); 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (flags & LTM_PRIME_SAFE) { 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* restore a to the original value */ 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul_2(a, a)) != MP_OKAY) { goto error; } 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_add_d(a, 1, a)) != MP_OKAY) { goto error; } 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = MP_OKAY; 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecterror: 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project XFREE(tmp); 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_mp_prime_random_ex.c,v $ */ 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.4 $ */ 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 126