1 /*

2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>

3 *

4 * Permission is hereby granted, free of charge, to any person obtaining

5 * a copy of this software and associated documentation files (the

6 * "Software"), to deal in the Software without restriction, including

7 * without limitation the rights to use, copy, modify, merge, publish,

8 * distribute, sublicense, and/or sell copies of the Software, and to

9 * permit persons to whom the Software is furnished to do so, subject to

10 * the following conditions:

11 *

12 * The above copyright notice and this permission notice shall be

13 * included in all copies or substantial portions of the Software.

14 *

15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS

19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN

20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

22 * SOFTWARE.

23 */

27 #define U (1 + ((BR_MAX_RSA_FACTOR + 30) / 31))

29 /* see bearssl_rsa.h */

30 uint32_t

32 {

40 /*

41 * All our temporary buffers are from the tmp[] array.

42 *

43 * The mp, mq, s1, s2, t1 and t2 buffers are large enough to

44 * contain a RSA factor. The t3 buffer can contain a complete

45 * RSA modulus. t3 shares its storage space with s2, s1 and t1,

46 * in that order (this is important, see below).

47 */

56 /*

57 * Compute the actual lengths (in bytes) of p and q, and check

58 * that they fit within our stack buffers.

59 */

63 p ++;

64 plen --;

65 }

69 q ++;

70 qlen --;

71 }

74 {

76 }

78 /*

79 * Decode p and q.

80 */

84 /*

85 * Compute signature length (in bytes).

86 */

89 /*

90 * Compute s1 = x^dp mod p.

91 */

96 /*

97 * Compute s2 = x^dq mod q.

98 */

103 /*

104 * Compute:

105 * h = (s1 - s2)*(1/q) mod p

106 * s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is

107 * unclear about whether p may be lower than q (some existing,

108 * widely deployed implementations of RSA don't tolerate p < q),

109 * but we want to support that occurrence, so we need to use the

110 * reduction function.

111 *

112 * Since we use br_i31_decode_reduce() for iq (purportedly, the

113 * inverse of q modulo p), we also tolerate improperly large

114 * values for this parameter.

115 */

122 /*

123 * h is now in t2. We compute the final result:

124 * s = s2 + q*h

125 * All these operations are non-modular.

126 *

127 * We need mq, s2 and t2. We use the t3 buffer as destination.

128 * The buffers mp, s1 and t1 are no longer needed. Moreover,

129 * the first step is to copy s2 into the destination buffer t3.

130 * We thus arranged for t3 to actually share space with s2, and

131 * to be followed by the space formerly used by s1 and t1.

132 */

135 /*

136 * Encode the result. Since we already checked the value of xlen,

137 * we can just use it right away.

138 */

141 /*

142 * The only error conditions remaining at that point are invalid

143 * values for p and q (even integers).

144 */

146 }