GCC Code Coverage Report

Directory: src/
File: src/mpq-rsa.c
Date: 2026-10-06 13:47:41
Exec Total Coverage
Lines: 184 192 95.8%
Functions: 12 12 100.0%
Branches: 87 102 85.3%
Line Branch Exec Source
1 /*
2 * mpq-rsa.c -- private fixed-width legacy RSA arithmetic.
3 *
4 * Copyright (c) 2003-2026 Maik Broemme <mbroemme@libmpq.org>
5 *
6 * This file is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as published by
8 * the Free Software Foundation; either version 2.1 of the License, or
9 * (at your option) any later version.
10 *
11 * This file is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public License
17 * along with this file; if not, see <https://www.gnu.org/licenses/>.
18 */
19
20 #include "mpq-rsa.h"
21 #include "mpq-endian.h"
22 #include <libmpq/mpq.h>
23 #include <string.h>
24
25 /*
26 * Little-endian base-256 limbs avoid native word size and alignment assumptions.
27 * Weak RSA-512 and strong RSA-2048 private operations use fixed iterations and
28 * mask selection. Strong RSA-2048 public operation skips leading zero exponent
29 * bits for efficiency. This legacy implementation is not a modern cryptographic API.
30 */
31 static void
32 38793216 add_mod(uint8_t *out, const uint8_t *a, const uint8_t *b, const uint8_t *n, size_t size)
33 {
34 uint8_t sum[LIBMPQ_RSA_MAX_SIZE];
35 uint8_t reduced[LIBMPQ_RSA_MAX_SIZE];
36 38793216 uint32_t carry = 0;
37 38793216 uint32_t borrow = 0;
38 uint32_t mask;
39 size_t i;
40
2/2
✓ Branch 0 taken 2884632576 times.
✓ Branch 1 taken 38793216 times.
 2923425792 for (i = 0; i < size; ++i) {
41 2884632576 uint32_t value = (uint32_t)a[i] + b[i] + carry;
42 2884632576 sum[i] = (uint8_t)value;
43 2884632576 carry = value >> 8;
44 }
45
2/2
✓ Branch 0 taken 2884632576 times.
✓ Branch 1 taken 38793216 times.
 2923425792 for (i = 0; i < size; ++i) {
46 2884632576 uint32_t value = (uint32_t)sum[i] - n[i] - borrow;
47 2884632576 reduced[i] = (uint8_t)value;
48 2884632576 borrow = value >> 31;
49 }
50 38793216 mask = 0u - (carry | (borrow ^ 1u));
51
2/2
✓ Branch 0 taken 2884632576 times.
✓ Branch 1 taken 38793216 times.
 2923425792 for (i = 0; i < size; ++i)
52 2884632576 out[i] = (uint8_t)((reduced[i] & mask) | (sum[i] & ~mask));
53 38793216 libmpq__rsa_clear(sum, sizeof(sum));
54 38793216 libmpq__rsa_clear(reduced, sizeof(reduced));
55 38793216 }
56
57 static void
58 36345 multiply(uint8_t *out, const uint8_t *a, const uint8_t *b, const uint8_t *n, size_t size)
59 {
60 36345 uint8_t result[LIBMPQ_RSA_MAX_SIZE] = { 0 };
61 uint8_t sum[LIBMPQ_RSA_MAX_SIZE];
62 size_t bit;
63 size_t i;
64
2/2
✓ Branch 0 taken 19384320 times.
✓ Branch 1 taken 36345 times.
 19420665 for (bit = (size * 8); bit-- > 0;) {
65 19384320 uint32_t mask = 0u - ((b[bit / 8] >> (bit % 8)) & 1u);
66 19384320 add_mod(result, result, result, n, size);
67 19384320 add_mod(sum, result, a, n, size);
68
2/2
✓ Branch 0 taken 1439170560 times.
✓ Branch 1 taken 19384320 times.
 1458554880 for (i = 0; i < size; ++i)
69 1439170560 result[i] = (uint8_t)((sum[i] & mask) | (result[i] & ~mask));
70 }
71 36345 memcpy(out, result, size);
72 36345 libmpq__rsa_clear(result, sizeof(result));
73 36345 libmpq__rsa_clear(sum, sizeof(sum));
74 36345 }
75
76 #define LIBMPQ_RSA_MAX_WORDS (LIBMPQ_RSA_MAX_SIZE / 4u)
77
78 /*
79 * Montgomery multiplication with base 2^32. The inputs and output have the
80 * same fixed width; the caller supplies values in Montgomery representation.
81 */
82 static void
83 24594 montgomery_multiply(
84 uint32_t *output, const uint32_t *left, const uint32_t *right, const uint32_t *modulus,
85 uint32_t inverse, size_t words
86 )
87 {
88 24594 uint32_t temporary[LIBMPQ_RSA_MAX_WORDS + 2u] = { 0 };
89 uint32_t reduced[LIBMPQ_RSA_MAX_WORDS];
90 uint64_t carry;
91 uint64_t value;
92 24594 uint32_t borrow = 0;
93 uint32_t select;
94 size_t i;
95 size_t j;
96
97
2/2
✓ Branch 0 taken 1574016 times.
✓ Branch 1 taken 24594 times.
 1598610 for (i = 0; i < words; ++i) {
98 1574016 carry = 0;
99
2/2
✓ Branch 0 taken 100737024 times.
✓ Branch 1 taken 1574016 times.
 102311040 for (j = 0; j < words; ++j) {
100 100737024 value = (uint64_t)temporary[j] + (uint64_t)left[j] * right[i] + carry;
101 100737024 temporary[j] = (uint32_t)value;
102 100737024 carry = value >> 32;
103 }
104 1574016 value = (uint64_t)temporary[words] + carry;
105 1574016 temporary[words] = (uint32_t)value;
106 1574016 temporary[words + 1u] = (uint32_t)(value >> 32);
107
108 1574016 carry = 0;
109 1574016 value = (uint32_t)((uint64_t)temporary[0] * inverse);
110
2/2
✓ Branch 0 taken 100737024 times.
✓ Branch 1 taken 1574016 times.
 102311040 for (j = 0; j < words; ++j) {
111 100737024 uint64_t sum = (uint64_t)temporary[j] + value * modulus[j] + carry;
112
2/2
✓ Branch 0 taken 99163008 times.
✓ Branch 1 taken 1574016 times.
 100737024 if (j != 0)
113 99163008 temporary[j - 1u] = (uint32_t)sum;
114 100737024 carry = sum >> 32;
115 }
116 1574016 value = (uint64_t)temporary[words] + carry;
117 1574016 temporary[words - 1u] = (uint32_t)value;
118 1574016 carry = (uint64_t)temporary[words + 1u] + (value >> 32);
119 1574016 temporary[words] = (uint32_t)carry;
120 1574016 temporary[words + 1u] = (uint32_t)(carry >> 32);
121 }
122
2/2
✓ Branch 0 taken 1574016 times.
✓ Branch 1 taken 24594 times.
 1598610 for (i = 0; i < words; ++i) {
123 1574016 uint64_t difference = (uint64_t)temporary[i] - modulus[i] - borrow;
124 1574016 reduced[i] = (uint32_t)difference;
125 1574016 borrow = (uint32_t)(difference >> 63);
126 }
127 24594 select = 0u - ((temporary[words] != 0u) | (borrow ^ 1u));
128
2/2
✓ Branch 0 taken 1574016 times.
✓ Branch 1 taken 24594 times.
 1598610 for (i = 0; i < words; ++i)
129 1574016 output[i] = (reduced[i] & select) | (temporary[i] & ~select);
130 24594 libmpq__rsa_clear(temporary, sizeof(temporary));
131 24594 libmpq__rsa_clear(reduced, sizeof(reduced));
132 24594 }
133
134 static void
135 6 montgomery_r_squared(uint32_t *output, const uint32_t *modulus, size_t words)
136 {
137 6 uint8_t value[LIBMPQ_RSA_MAX_SIZE] = { 1 };
138 uint8_t doubled[LIBMPQ_RSA_MAX_SIZE];
139 uint8_t bytes[LIBMPQ_RSA_MAX_SIZE];
140 size_t i;
141 size_t bit;
142
143
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 6 times.
 390 for (i = 0; i < words; ++i) {
144 384 libmpq__store_le32(bytes + 4u * i, modulus[i]);
145 }
146
2/2
✓ Branch 0 taken 24576 times.
✓ Branch 1 taken 6 times.
 24582 for (bit = 0; bit < words * 64u; ++bit) {
147 24576 add_mod(doubled, value, value, bytes, words * 4u);
148 24576 memcpy(value, doubled, words * 4u);
149 }
150
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 6 times.
 390 for (i = 0; i < words; ++i) {
151 384 output[i] = libmpq__load_le32(value + 4u * i);
152 }
153 6 libmpq__rsa_clear(value, sizeof(value));
154 6 libmpq__rsa_clear(doubled, sizeof(doubled));
155 6 libmpq__rsa_clear(bytes, sizeof(bytes));
156 6 }
157
158 /*
159 * A raw key is equal-width big-endian n || exponent components. A full-width
160 * odd modulus and an odd exponent in [3,n) are required.
161 */
162 static int32_t
163 135 rsa_key_validate(const uint8_t *key, size_t key_size, size_t modulus_size)
164 {
165 135 uint8_t small = 0;
166 size_t i;
167
4/6
✓ Branch 0 taken 133 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 133 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 133 times.
✗ Branch 5 not taken.
 135 if (key == NULL || modulus_size == 0 || modulus_size > LIBMPQ_RSA_MAX_SIZE ||
168
6/6
✓ Branch 0 taken 123 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 122 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 113 times.
✓ Branch 5 taken 9 times.
 133 key_size != 2u * modulus_size || !(key[0] & 0x80) || !(key[modulus_size - 1] & 1) ||
169
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 111 times.
 113 !(key[key_size - 1] & 1))
170 24 return LIBMPQ_ERROR_FORMAT;
171
2/2
✓ Branch 0 taken 20625 times.
✓ Branch 1 taken 111 times.
 20736 for (i = modulus_size; i < key_size - 1; ++i)
172 20625 small |= key[i];
173
2/6
✗ Branch 0 not taken.
✓ Branch 1 taken 111 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 111 times.
 111 if ((small == 0 && key[key_size - 1] < 3) || memcmp(key + modulus_size, key, modulus_size) >= 0)
174 ✗ return LIBMPQ_ERROR_FORMAT;
175 111 return 0;
176 }
177
178 int32_t
179 50 libmpq__rsa_weak_key_validate(const uint8_t *key, size_t key_size)
180 {
181 50 return rsa_key_validate(key, key_size, LIBMPQ_RSA_SIZE);
182 }
183
184 int32_t
185 85 libmpq__rsa_strong_key_validate(const uint8_t *key, size_t key_size)
186 {
187 85 return rsa_key_validate(key, key_size, LIBMPQ_RSA_STRONG_SIZE);
188 }
189
190 int32_t
191 6 libmpq__rsa_strong_private_operation(
192 const uint8_t key[LIBMPQ_RSA_STRONG_KEY_SIZE], const uint8_t input[LIBMPQ_RSA_STRONG_SIZE],
193 uint8_t output[LIBMPQ_RSA_STRONG_SIZE]
194 )
195 {
196 uint32_t modulus[LIBMPQ_RSA_MAX_WORDS];
197 uint32_t base[LIBMPQ_RSA_MAX_WORDS];
198 uint32_t result[LIBMPQ_RSA_MAX_WORDS];
199 uint32_t product[LIBMPQ_RSA_MAX_WORDS];
200 uint32_t squared[LIBMPQ_RSA_MAX_WORDS];
201 uint32_t r_squared[LIBMPQ_RSA_MAX_WORDS];
202 6 uint32_t one[LIBMPQ_RSA_MAX_WORDS] = { 0 };
203 6 uint32_t inverse = 1;
204 size_t i;
205 size_t bit;
206
3/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 6 if (libmpq__rsa_strong_key_validate(key, LIBMPQ_RSA_STRONG_KEY_SIZE) != 0 || input == NULL ||
207
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 output == NULL || memcmp(input, key, LIBMPQ_RSA_STRONG_SIZE) >= 0)
208 ✗ return LIBMPQ_ERROR_FORMAT;
209
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 6 times.
 390 for (i = 0; i < LIBMPQ_RSA_MAX_WORDS; ++i) {
210 384 modulus[i] = libmpq__load_be32(key + LIBMPQ_RSA_STRONG_SIZE - 4u * (i + 1u));
211 384 base[i] = libmpq__load_be32(input + LIBMPQ_RSA_STRONG_SIZE - 4u * (i + 1u));
212 }
213
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 6 times.
 36 for (i = 0; i < 5; ++i)
214 30 inverse *= 2u - modulus[0] * inverse;
215 6 inverse = 0u - inverse;
216 6 one[0] = 1;
217 6 montgomery_r_squared(r_squared, modulus, LIBMPQ_RSA_MAX_WORDS);
218 6 montgomery_multiply(base, base, r_squared, modulus, inverse, LIBMPQ_RSA_MAX_WORDS);
219 6 montgomery_multiply(result, one, r_squared, modulus, inverse, LIBMPQ_RSA_MAX_WORDS);
220
2/2
✓ Branch 0 taken 12288 times.
✓ Branch 1 taken 6 times.
 12294 for (bit = 0; bit < (LIBMPQ_RSA_STRONG_SIZE * 8); ++bit) {
221 12288 uint32_t mask = 0u - ((key[LIBMPQ_RSA_STRONG_SIZE + bit / 8] >> (7 - bit % 8)) & 1u);
222 12288 montgomery_multiply(squared, result, result, modulus, inverse, LIBMPQ_RSA_MAX_WORDS);
223 12288 montgomery_multiply(product, squared, base, modulus, inverse, LIBMPQ_RSA_MAX_WORDS);
224
2/2
✓ Branch 0 taken 786432 times.
✓ Branch 1 taken 12288 times.
 798720 for (i = 0; i < LIBMPQ_RSA_MAX_WORDS; ++i)
225 786432 result[i] = (product[i] & mask) | (squared[i] & ~mask);
226 }
227 6 montgomery_multiply(result, result, one, modulus, inverse, LIBMPQ_RSA_MAX_WORDS);
228
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 6 times.
 390 for (i = 0; i < LIBMPQ_RSA_MAX_WORDS; ++i)
229 384 libmpq__store_be32(output + 4u * (LIBMPQ_RSA_MAX_WORDS - i - 1u), result[i]);
230 6 libmpq__rsa_clear(modulus, sizeof(modulus));
231 6 libmpq__rsa_clear(base, sizeof(base));
232 6 libmpq__rsa_clear(result, sizeof(result));
233 6 libmpq__rsa_clear(product, sizeof(product));
234 6 libmpq__rsa_clear(squared, sizeof(squared));
235 6 libmpq__rsa_clear(r_squared, sizeof(r_squared));
236 6 libmpq__rsa_clear(one, sizeof(one));
237 6 return 0;
238 }
239
240 int32_t
241 35 libmpq__rsa_weak_operation(
242 const uint8_t key[LIBMPQ_RSA_KEY_SIZE], const uint8_t input[LIBMPQ_RSA_SIZE],
243 uint8_t output[LIBMPQ_RSA_SIZE]
244 )
245 {
246 uint8_t n[LIBMPQ_RSA_SIZE];
247 uint8_t base[LIBMPQ_RSA_SIZE];
248 35 uint8_t result[LIBMPQ_RSA_SIZE] = { 1 };
249 uint8_t product[LIBMPQ_RSA_SIZE];
250 size_t i;
251 size_t bit;
252
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 35 times.
 35 if (memcmp(input, key, LIBMPQ_RSA_SIZE) >= 0)
253 ✗ return LIBMPQ_ERROR_FORMAT;
254
2/2
✓ Branch 0 taken 2240 times.
✓ Branch 1 taken 35 times.
 2275 for (i = 0; i < LIBMPQ_RSA_SIZE; ++i) {
255 2240 n[i] = key[(LIBMPQ_RSA_SIZE - 1) - i];
256 2240 base[i] = input[(LIBMPQ_RSA_SIZE - 1) - i];
257 }
258
2/2
✓ Branch 0 taken 17920 times.
✓ Branch 1 taken 35 times.
 17955 for (bit = 0; bit < (LIBMPQ_RSA_SIZE * 8); ++bit) {
259 17920 uint32_t mask = 0u - ((key[LIBMPQ_RSA_SIZE + bit / 8] >> (7 - bit % 8)) & 1u);
260 17920 multiply(result, result, result, n, LIBMPQ_RSA_SIZE);
261 17920 multiply(product, result, base, n, LIBMPQ_RSA_SIZE);
262
2/2
✓ Branch 0 taken 1146880 times.
✓ Branch 1 taken 17920 times.
 1164800 for (i = 0; i < LIBMPQ_RSA_SIZE; ++i)
263 1146880 result[i] = (uint8_t)((product[i] & mask) | (result[i] & ~mask));
264 }
265
2/2
✓ Branch 0 taken 2240 times.
✓ Branch 1 taken 35 times.
 2275 for (i = 0; i < LIBMPQ_RSA_SIZE; ++i)
266 2240 output[i] = result[(LIBMPQ_RSA_SIZE - 1) - i];
267 35 libmpq__rsa_clear(n, sizeof(n));
268 35 libmpq__rsa_clear(base, sizeof(base));
269 35 libmpq__rsa_clear(result, sizeof(result));
270 35 libmpq__rsa_clear(product, sizeof(product));
271 35 return 0;
272 }
273
274 /*
275 * Public exponents are normally short (for example 65537), so begin at the
276 * first set bit instead of needlessly processing every padded exponent bit.
277 */
278 int32_t
279 30 libmpq__rsa_strong_public_operation(
280 const uint8_t key[LIBMPQ_RSA_STRONG_KEY_SIZE], const uint8_t input[LIBMPQ_RSA_STRONG_SIZE],
281 uint8_t output[LIBMPQ_RSA_STRONG_SIZE]
282 )
283 {
284 uint8_t n[LIBMPQ_RSA_MAX_SIZE];
285 uint8_t base[LIBMPQ_RSA_MAX_SIZE];
286 30 uint8_t result[LIBMPQ_RSA_MAX_SIZE] = { 0 };
287 uint8_t product[LIBMPQ_RSA_MAX_SIZE];
288 size_t i;
289 size_t bit;
290 30 int started = 0;
291
3/6
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 30 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 30 times.
✗ Branch 6 not taken.
 30 if (libmpq__rsa_strong_key_validate(key, LIBMPQ_RSA_STRONG_KEY_SIZE) != 0 || input == NULL ||
292
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 28 times.
 30 output == NULL || memcmp(input, key, LIBMPQ_RSA_STRONG_SIZE) >= 0)
293 2 return LIBMPQ_ERROR_FORMAT;
294
2/2
✓ Branch 0 taken 7168 times.
✓ Branch 1 taken 28 times.
 7196 for (i = 0; i < LIBMPQ_RSA_STRONG_SIZE; ++i) {
295 7168 n[i] = key[LIBMPQ_RSA_STRONG_SIZE - 1 - i];
296 7168 base[i] = input[LIBMPQ_RSA_STRONG_SIZE - 1 - i];
297 }
298 28 result[0] = 1;
299
2/2
✓ Branch 0 taken 57344 times.
✓ Branch 1 taken 28 times.
 57372 for (bit = 0; bit < LIBMPQ_RSA_STRONG_SIZE * 8u; ++bit) {
300 57344 uint8_t set = (uint8_t)((key[LIBMPQ_RSA_STRONG_SIZE + bit / 8u] >> (7u - bit % 8u)) & 1u);
301
2/2
✓ Branch 0 taken 56896 times.
✓ Branch 1 taken 448 times.
 57344 if (!started) {
302
2/2
✓ Branch 0 taken 56868 times.
✓ Branch 1 taken 28 times.
 56896 if (!set)
303 56868 continue;
304 28 started = 1;
305 28 multiply(result, result, base, n, LIBMPQ_RSA_STRONG_SIZE);
306 28 continue;
307 }
308 448 multiply(result, result, result, n, LIBMPQ_RSA_STRONG_SIZE);
309
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 419 times.
 448 if (set) {
310 29 multiply(product, result, base, n, LIBMPQ_RSA_STRONG_SIZE);
311 29 memcpy(result, product, LIBMPQ_RSA_STRONG_SIZE);
312 }
313 }
314
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (!started) {
315 ✗ libmpq__rsa_clear(n, sizeof(n));
316 ✗ libmpq__rsa_clear(base, sizeof(base));
317 ✗ libmpq__rsa_clear(result, sizeof(result));
318 ✗ libmpq__rsa_clear(product, sizeof(product));
319 ✗ return LIBMPQ_ERROR_FORMAT;
320 }
321
2/2
✓ Branch 0 taken 7168 times.
✓ Branch 1 taken 28 times.
 7196 for (i = 0; i < LIBMPQ_RSA_STRONG_SIZE; ++i)
322 7168 output[i] = result[LIBMPQ_RSA_STRONG_SIZE - 1 - i];
323 28 libmpq__rsa_clear(n, sizeof(n));
324 28 libmpq__rsa_clear(base, sizeof(base));
325 28 libmpq__rsa_clear(result, sizeof(result));
326 28 libmpq__rsa_clear(product, sizeof(product));
327 28 return 0;
328 }
329
330 /* RFC 8017 EMSA-PKCS1-v1_5: 00 01 FF...FF 00 DigestInfo(MD5). */
331 void
332 34 libmpq__rsa_md5_encode(const uint8_t digest[LIBMPQ_MD5_SIZE], uint8_t encoded[LIBMPQ_RSA_SIZE])
333 {
334 static const uint8_t prefix[18] = { 0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86, 0x48,
335 0x86, 0xf7, 0x0d, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10 };
336 34 memset(encoded, 0xff, LIBMPQ_RSA_SIZE);
337 34 encoded[0] = 0;
338 34 encoded[1] = 1;
339 34 encoded[29] = 0;
340 34 memcpy(encoded + 30, prefix, sizeof(prefix));
341 34 memcpy(encoded + 48, digest, LIBMPQ_MD5_SIZE);
342 34 }
343
344 void
345 77711719 libmpq__rsa_clear(void *data, size_t size)
346 {
347 77711719 volatile uint8_t *bytes = data;
348
2/2
✓ Branch 0 taken 19894135696 times.
✓ Branch 1 taken 77711719 times.
 19971847415 while (size-- != 0)
349 19894135696 *bytes++ = 0;
350 77711719 }
351