1 /* Microsoft Reference Implementation for TPM 2.0 2 * 3 * The copyright in this software is being made available under the BSD License, 4 * included below. This software may be subject to other third party and 5 * contributor rights, including patent rights, and no such rights are granted 6 * under this license. 7 * 8 * Copyright (c) Microsoft Corporation 9 * 10 * All rights reserved. 11 * 12 * BSD License 13 * 14 * Redistribution and use in source and binary forms, with or without modification, 15 * are permitted provided that the following conditions are met: 16 * 17 * Redistributions of source code must retain the above copyright notice, this list 18 * of conditions and the following disclaimer. 19 * 20 * Redistributions in binary form must reproduce the above copyright notice, this 21 * list of conditions and the following disclaimer in the documentation and/or 22 * other materials provided with the distribution. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ""AS IS"" 25 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 27 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR 28 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 31 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35 /*(Auto-generated) 36 * Created by TpmPrototypes; Version 3.0 July 18, 2017 37 * Date: Aug 30, 2019 Time: 02:11:54PM 38 */ 39 40 #ifndef _CRYPT_PRIME_SIEVE_FP_H_ 41 #define _CRYPT_PRIME_SIEVE_FP_H_ 42 43 #if RSA_KEY_SIEVE 44 45 //*** RsaAdjustPrimeLimit() 46 // This used during the sieve process. The iterator for getting the 47 // next prime (RsaNextPrime()) will return primes until it hits the 48 // limit (primeLimit) set up by this function. This causes the sieve 49 // process to stop when an appropriate number of primes have been 50 // sieved. 51 LIB_EXPORT void 52 RsaAdjustPrimeLimit( 53 uint32_t requestedPrimes 54 ); 55 56 //*** RsaNextPrime() 57 // This the iterator used during the sieve process. The input is the 58 // last prime returned (or any starting point) and the output is the 59 // next higher prime. The function returns 0 when the primeLimit is 60 // reached. 61 LIB_EXPORT uint32_t 62 RsaNextPrime( 63 uint32_t lastPrime 64 ); 65 66 //*** FindNthSetBit() 67 // This function finds the nth SET bit in a bit array. The 'n' parameter is 68 // between 1 and the number of bits in the array (always a multiple of 8). 69 // If called when the array does not have n bits set, it will return -1 70 // Return Type: unsigned int 71 // <0 no bit is set or no bit with the requested number is set 72 // >=0 the number of the bit in the array that is the nth set 73 LIB_EXPORT int 74 FindNthSetBit( 75 const UINT16 aSize, // IN: the size of the array to check 76 const BYTE *a, // IN: the array to check 77 const UINT32 n // IN, the number of the SET bit 78 ); 79 80 //*** PrimeSieve() 81 // This function does a prime sieve over the input 'field' which has as its 82 // starting address the value in bnN. Since this initializes the Sieve 83 // using a precomputed field with the bits associated with 3, 5 and 7 already 84 // turned off, the value of pnN may need to be adjusted by a few counts to allow 85 // the precomputed field to be used without modification. 86 // 87 // To get better performance, one could address the issue of developing the 88 // composite numbers. When the size of the prime gets large, the time for doing 89 // the divisions goes up, noticeably. It could be better to develop larger composite 90 // numbers even if they need to be bigNum's themselves. The object would be to 91 // reduce the number of times that the large prime is divided into a few large 92 // divides and then use smaller divides to get to the final 16 bit (or smaller) 93 // remainders. 94 LIB_EXPORT UINT32 95 PrimeSieve( 96 bigNum bnN, // IN/OUT: number to sieve 97 UINT32 fieldSize, // IN: size of the field area in bytes 98 BYTE *field // IN: field 99 ); 100 #ifdef SIEVE_DEBUG 101 102 //***SetFieldSize() 103 // Function to set the field size used for prime generation. Used for tuning. 104 LIB_EXPORT uint32_t 105 SetFieldSize( 106 uint32_t newFieldSize 107 ); 108 #endif // SIEVE_DEBUG 109 110 //*** PrimeSelectWithSieve() 111 // This function will sieve the field around the input prime candidate. If the 112 // sieve field is not empty, one of the one bits in the field is chosen for testing 113 // with Miller-Rabin. If the value is prime, 'pnP' is updated with this value 114 // and the function returns success. If this value is not prime, another 115 // pseudo-random candidate is chosen and tested. This process repeats until 116 // all values in the field have been checked. If all bits in the field have 117 // been checked and none is prime, the function returns FALSE and a new random 118 // value needs to be chosen. 119 // Return Type: TPM_RC 120 // TPM_RC_FAILURE TPM in failure mode, probably due to entropy source 121 // TPM_RC_SUCCESS candidate is probably prime 122 // TPM_RC_NO_RESULT candidate is not prime and couldn't find and alternative 123 // in the field 124 LIB_EXPORT TPM_RC 125 PrimeSelectWithSieve( 126 bigNum candidate, // IN/OUT: The candidate to filter 127 UINT32 e, // IN: the exponent 128 RAND_STATE *rand // IN: the random number generator state 129 ); 130 #if RSA_INSTRUMENT 131 132 //*** PrintTuple() 133 char * 134 PrintTuple( 135 UINT32 *i 136 ); 137 138 //*** RsaSimulationEnd() 139 void 140 RsaSimulationEnd( 141 void 142 ); 143 144 //*** GetSieveStats() 145 LIB_EXPORT void 146 GetSieveStats( 147 uint32_t *trials, 148 uint32_t *emptyFields, 149 uint32_t *averageBits 150 ); 151 #endif 152 #endif // RSA_KEY_SIEVE 153 #if !RSA_INSTRUMENT 154 155 //*** RsaSimulationEnd() 156 // Stub for call when not doing instrumentation. 157 void 158 RsaSimulationEnd( 159 void 160 ); 161 #endif 162 163 #endif // _CRYPT_PRIME_SIEVE_FP_H_ 164