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_FP_H_ 41 #define _CRYPT_PRIME_FP_H_ 42 43 //*** IsPrimeInt() 44 // This will do a test of a word of up to 32-bits in size. 45 BOOL 46 IsPrimeInt( 47 uint32_t n 48 ); 49 50 //*** BnIsProbablyPrime() 51 // This function is used when the key sieve is not implemented. This function 52 // Will try to eliminate some of the obvious things before going on 53 // to perform MillerRabin as a final verification of primeness. 54 BOOL 55 BnIsProbablyPrime( 56 bigNum prime, // IN: 57 RAND_STATE *rand // IN: the random state just 58 // in case Miller-Rabin is required 59 ); 60 61 //*** MillerRabinRounds() 62 // Function returns the number of Miller-Rabin rounds necessary to give an 63 // error probability equal to the security strength of the prime. These values 64 // are from FIPS 186-3. 65 UINT32 66 MillerRabinRounds( 67 UINT32 bits // IN: Number of bits in the RSA prime 68 ); 69 70 //*** MillerRabin() 71 // This function performs a Miller-Rabin test from FIPS 186-3. It does 72 // 'iterations' trials on the number. In all likelihood, if the number 73 // is not prime, the first test fails. 74 // Return Type: BOOL 75 // TRUE(1) probably prime 76 // FALSE(0) composite 77 BOOL 78 MillerRabin( 79 bigNum bnW, 80 RAND_STATE *rand 81 ); 82 #if ALG_RSA 83 84 //*** RsaCheckPrime() 85 // This will check to see if a number is prime and appropriate for an 86 // RSA prime. 87 // 88 // This has different functionality based on whether we are using key 89 // sieving or not. If not, the number checked to see if it is divisible by 90 // the public exponent, then the number is adjusted either up or down 91 // in order to make it a better candidate. It is then checked for being 92 // probably prime. 93 // 94 // If sieving is used, the number is used to root a sieving process. 95 // 96 TPM_RC 97 RsaCheckPrime( 98 bigNum prime, 99 UINT32 exponent, 100 RAND_STATE *rand 101 ); 102 103 //*** RsaAdjustPrimeCandiate() 104 // For this math, we assume that the RSA numbers are fixed-point numbers with 105 // the decimal point to the "left" of the most significant bit. This approach helps 106 // make it clear what is happening with the MSb of the values. 107 // The two RSA primes have to be large enough so that their product will be a number 108 // with the necessary number of significant bits. For example, we want to be able 109 // to multiply two 1024-bit numbers to produce a number with 2028 significant bits. If 110 // we accept any 1024-bit prime that has its MSb set, then it is possible to produce a 111 // product that does not have the MSb SET. For example, if we use tiny keys of 16 bits 112 // and have two 8-bit 'primes' of 0x80, then the public key would be 0x4000 which is 113 // only 15-bits. So, what we need to do is made sure that each of the primes is large 114 // enough so that the product of the primes is twice as large as each prime. A little 115 // arithmetic will show that the only way to do this is to make sure that each of the 116 // primes is no less than root(2)/2. That's what this functions does. 117 // This function adjusts the candidate prime so that it is odd and >= root(2)/2. 118 // This allows the product of these two numbers to be .5, which, in fixed point 119 // notation means that the most significant bit is 1. 120 // For this routine, the root(2)/2 (0.7071067811865475) approximated with 0xB505 121 // which is, in fixed point, 0.7071075439453125 or an error of 0.000108%. Just setting 122 // the upper two bits would give a value > 0.75 which is an error of > 6%. Given the 123 // amount of time all the other computations take, reducing the error is not much of 124 // a cost, but it isn't totally required either. 125 // 126 // This function can be replaced with a function that just sets the two most 127 // significant bits of each prime candidate without introducing any computational 128 // issues. 129 // 130 LIB_EXPORT void 131 RsaAdjustPrimeCandidate( 132 bigNum prime 133 ); 134 135 //***BnGeneratePrimeForRSA() 136 // Function to generate a prime of the desired size with the proper attributes 137 // for an RSA prime. 138 TPM_RC 139 BnGeneratePrimeForRSA( 140 bigNum prime, // IN/OUT: points to the BN that will get the 141 // random value 142 UINT32 bits, // IN: number of bits to get 143 UINT32 exponent, // IN: the exponent 144 RAND_STATE *rand // IN: the random state 145 ); 146 #endif // ALG_RSA 147 148 #endif // _CRYPT_PRIME_FP_H_ 149