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