/src/cryptofuzz/expmod.cpp

Source (jump to first uncovered line)
#include "expmod.h"
#include <boost/random.hpp>
#include <fuzzing/datasource/id.hpp>
#include <cryptofuzz/util.h>
#include <cryptofuzz/repository.h>
#include "repository_tbl.h"
#include "config.h"

uint32_t PRNG(void);
std::string getBignum(bool mustBePositive = false);
std::string getPrime(void);

namespace cryptofuzz {
namespace mutator {
namespace ExpModGenerator {
    using namespace boost::multiprecision;
    using namespace boost::random;

    static mt19937 mt;

    inline bool is_even(const cpp_int& v) {
        return (v & 1) == 0;
    }

    inline bool is_odd(const cpp_int& v) {
        return (v & 1) == 1;
    }

    inline nlohmann::json to_json(const cpp_int& B, const cpp_int& E, const cpp_int& M) {
        nlohmann::json ret;

        ret["modifier"] = "";
        ret["calcOp"] = CF_CALCOP("ExpMod(A,B,C)");
        ret["bn1"] = B.str();
        ret["bn2"] = E.str();
        ret["bn3"] = M.str();
        ret["bn4"] = "";

        return ret;
    }

    inline const cpp_int& max(void) {
        static const cpp_int max(std::string(cryptofuzz::config::kMaxBignumSize, '9'));
        return max;
    }

    inline cpp_int max_multiplier(const cpp_int& v, const cpp_int& m) {
        return v == 0 ? cpp_int(0) : m / v;
    }

    inline cpp_int max_multiplier(const cpp_int& v) {
        return max_multiplier(v, max());
    }

    /* Multiply 'v' by a random positive integer m such that v * m < max() */
    /* If that is not possible, return false, else return true.
     */
    inline bool multiply_random(cpp_int& v, const bool odd = false) {
        const cpp_int max_mul = max_multiplier(v);

        if ( max_mul == 0 ) {
            return false;
        }

        cpp_int mul = uniform_int_distribution<cpp_int>(1, max_mul)(mt);

        if ( odd && is_even(mul) ) {
            mul--;
            //assert(mul > 0);
        }

        v *= mul;

        return true;
    }

    /* If 'a' and 'b' are such that a * b < max(), then
     * perform the multiplication on 'a' and return true.
     * Return false otherwise.
     */
    inline bool multiply(cpp_int& a, const cpp_int& b) {
        /* XXX return a <= max() / b; */
        const cpp_int max_mul = max_multiplier(a);

        if ( max_mul < b ) {
            return false;
        }

        a *= b;

        return true;
    }

    inline cpp_int get_prime(void) {
        const cpp_int p(getPrime());

        if ( p > 0 ) {
            return p;
        }

        /* Prime pool is empty, fall back to regular number */
        return cpp_int(getBignum(true));
    }

    inline std::vector<size_t> prime_factors(const cpp_int& v) noexcept {
        static const std::vector<size_t> primes{2, 3, 5, 7, 11, 13, 17, 19};

        std::vector<size_t> ret;

        for (const auto& p : primes) {
            if ( v % p == 0 ) {
                ret.push_back(p);
            }
        }

        return ret;
    }

    /* Compute max E such that base^E <= v */
    inline size_t log(const cpp_int& v, const cpp_int& base) {
        size_t i = 0;
        auto x = base;
        while ( x <= v ) {
            x *= base;
            i++;
        }
        return i;
    }

    /* This is slightly faster than native boost::multiprecision::pow */
    inline cpp_int pow(const cpp_int& v, const size_t exponent) {
        if ( exponent == 0 ) {
            static const cpp_int one(1);
            return one;
        } else if ( exponent == 1 ) {
            return v;
        } else {
            return boost::multiprecision::pow(v, exponent);
        }
    }

    /* Create an ExpMod operation where base, exp and mod are of size 'bits'
     * and base^exp%mod == 0.
     *
     * To find certain modexp reduction bugs such as:
     * https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315
     * https://boringssl.googlesource.com/boringssl/+/801a801024febe1a33add5ddaa719e257d97aba5
     */
    static std::optional<nlohmann::json> generate_exp_mod_is_0(const size_t bits)
    {
        CF_ASSERT(bits > 0, "Bits must be non-zero");

        /* For some reason this crashes with high optimization */
        /*
        const auto min = cpp_int(1) << (bits - 1);
        const auto max = (cpp_int(1) << bits) - 1;
        */

        auto min = cpp_int(1);
        min <<= (bits - 1);

        auto max = cpp_int(1);
        max <<= bits;
        max--;

        /* Create random base/exponent */
        const cpp_int BE = uniform_int_distribution<cpp_int>(min, max)(mt);

        /* Compute some prime factors of base/exponent */
        const auto factors = prime_factors(BE);
        if ( factors.empty() ) {
            return std::nullopt;
        }

        /* Pick two random prime factors */
        const auto P1 = cpp_int(factors[mt() % factors.size()]);
        const auto P2 = factors[mt() % factors.size()];

        /* I = P1^[0..P2] */
        const cpp_int I = pow(P1, mt() % (P2+1));

        /* Any J = P2^[0..I] would yield a valid modulus.
         *
         * However, we want I*J to not exceed the bitsize.
         * Therefore, compute the max J.
         */
        const cpp_int maxJ = max / I;

        //assert(I * maxJ <= max);

        /* Compute the max exponent such that
         * J = P2^exp does not exceed the bitsize.
         */
        const size_t maxJExp = log(maxJ, P2);

        const cpp_int J = pow(cpp_int(P2), maxJExp);

        const cpp_int M = I * J;

        //assert(M <= max);
        //assert(powm(BE, BE, M) == 0);

        return to_json(BE, BE, M);
    }

    /* For all odd values base, pow(base, base*mul, be+1) == base) where mul is any odd value. */
    static std::optional<nlohmann::json> generate_exp_mod_is_odd_base_1(const cpp_int& B) {
        if ( !is_odd(B) ) {
            return std::nullopt;
        }

        cpp_int E = B;
        if ( !multiply_random(E, true) ) {
            return std::nullopt;
        }

        const cpp_int M = B + 1;

        //assert(powm(B, E, M) == B);

        return to_json(B, E, M);
    }

    /* For all odd values base, pow(base, base*mul, base*2) == base) where mul is any positive integer. */
    static std::optional<nlohmann::json> generate_exp_mod_is_odd_base_2(const cpp_int& B) {
        if ( !is_odd(B) ) {
            return std::nullopt;
        }

        cpp_int E = B;
        if ( !multiply_random(E) ) {
            return std::nullopt;
        }

        const cpp_int M = B * 2;

        //assert(powm(B, E, M) == B);

        return to_json(B, E, M);
    }

    /* For all even values base >= 4, pow(base, base*mul, base*2-2) == base) where mul is any positive integer. */
    static std::optional<nlohmann::json> generate_exp_mod_is_even_base_1(const cpp_int& B) {
        if ( !is_even(B) ) {
            return std::nullopt;
        }
        if ( B < 4 ) {
            return std::nullopt;
        }

        cpp_int E = B;
        if ( !multiply_random(E) ) {
            return std::nullopt;
        }

        const cpp_int M = B * 2 - 2;

        //assert(powm(B, E, M) == B);

        return to_json(B, E, M);
    }

    /* For all prime values me > base, pow(base, me, me) == base). */
    static std::optional<nlohmann::json> generate_exp_mod_is_base_1(const cpp_int& B) {
        const cpp_int p = get_prime();

        if ( B <= p ) {
            return std::nullopt;
        }

        const cpp_int E = p;
        const cpp_int M = p;

        /* This only holds for prime p */
        //assert(powm(B, E, M) == B);

        return to_json(B, E, M);
    }

    /* For all prime values p and any positive e, pow(p+1, e, (p+1)*p) == p+1. */
    static std::optional<nlohmann::json> generate_exp_mod_is_base_2(void) {
        const cpp_int p = get_prime();

        if ( p < 3 ) {
            return std::nullopt;
        }

        const cpp_int B = p + 1;
        cpp_int E = 1;
        if ( !multiply_random(E) ) {
            return std::nullopt;
        }
        cpp_int M = p + 1;
        if ( !multiply(M, p) ) {
            return std::nullopt;
        }

        /* This only holds for prime p */
        //assert(powm(B, E, M) == B);

        return to_json(B, E, M);
    }

    /* For all odd values exp, pow(exp*mul, exp, exp*2) == exp) where mul is any odd integer. */
    static std::optional<nlohmann::json> generate_exp_mod_is_odd_exp_1(const cpp_int& E) {
        if ( !is_odd(E) ) {
            return std::nullopt;
        }

        cpp_int B = E;
        if ( !multiply_random(B, true) ) {
            return std::nullopt;
        }
        const cpp_int M = E * 2;

        //assert(powm(B, E, M) == E);

        return to_json(B, E, M);
    }

    /* 1. Let p be a prime such that p*2-1 >= v.
     * 2. Let exp = p*2-1.
     * 3. Let base = exp + (exp * (exp - v)).
     * 4. Let mod = exp + 1.
     * 5. Let k be any positive integer.
     *
     * Now pow(base, exp**k, mod) == v.
     */
    static std::optional<nlohmann::json> generate_exp_mod_is_v_1(const cpp_int& v) {
        /* Step 1 */
        const cpp_int p = get_prime();
        if ( p < 1 ) {
            return std::nullopt;
        }

        /* Step 2 */
        const cpp_int E = 2 * p - 1;
        if ( E > max() || E < v ) {
            return std::nullopt;
        }

        /* Step 3 */
        cpp_int B = E;
        {
            const cpp_int delta = E - v + 1;
            /* B *= delta */
            if ( !multiply(B, delta) ) {
                return std::nullopt;
            }
        }

        /* Step 4 */
        const cpp_int M = E + 1;

        /* TODO exponentiate exp */

        /* This only holds for prime p */
        //assert(powm(B, E, M) == v);

        return to_json(B, E, M);
    }

    /* 1. Let p be a prime such that p-1 >= v.
     * 2. Let exp = p-1.
     * 3. Let base = exp + (exp * (exp - v)).
     * 4. Let mod = exp + 1.
     * 5. Let k be any positive integer.
     *
     * Now pow(base, (exp*k)+1, mod) == v.
     */
    static std::optional<nlohmann::json> generate_exp_mod_is_v_2(const cpp_int& v) {
        /* Step 1 */
        const cpp_int p = get_prime();
        if ( p < 1 ) {
            return std::nullopt;
        }

        /* Step 2 */
        cpp_int E = p - 1;
        if ( E > max() || E < v ) {
            return std::nullopt;
        }

        /* Step 3 */
        cpp_int B = E;
        {
            const cpp_int delta = E - v + 1;
            /* B *= delta */
            if ( !multiply(B, delta) ) {
                return std::nullopt;
            }
        }

        /* Step 4 */
        const cpp_int M = E + 1;

        /* E = E*K+1 */
        if ( !multiply_random(E) ) {
            return std::nullopt;
        }
        E++;

        /* This only holds for prime p */
        //assert(powm(B, E, M) == v);

        return to_json(B, E, M);
    }

    std::optional<nlohmann::json> generate_exp_mod(const std::string& _result) {
        const uint8_t which = PRNG() % 3;
        if ( which == 0 ) {
            static const std::array<size_t, 6> bitsizes{256, 512, 1024, 2048, 4096, 8192};

            return generate_exp_mod_is_0(bitsizes[PRNG() % bitsizes.size()]);
        } else if ( which == 1 ) {
            const cpp_int result = cpp_int(_result);

            const uint8_t which = PRNG() % 2;

            if ( which == 0 ) {
                return generate_exp_mod_is_v_1(result);
            } else if ( which == 1 ) {
                return generate_exp_mod_is_v_2(result);
            } else {
                CF_UNREACHABLE();
            }
        } else if ( which == 2 ) {
            const cpp_int result = cpp_int(_result);

            if ( is_odd(result) ) {
                const uint8_t which = PRNG() % 5;

                if ( which == 0 ) {
                    return generate_exp_mod_is_odd_base_1(result);
                } else if ( which == 1 ) {
                    return generate_exp_mod_is_odd_base_2(result);
                } else if ( which == 2 ) {
                    return generate_exp_mod_is_odd_exp_1(result);
                } else if ( which == 3 ) {
                    return generate_exp_mod_is_base_1(result);
                } else if ( which == 4 ) {
                    return generate_exp_mod_is_base_2();
                } else {
                    CF_UNREACHABLE();
                }
            } else {
                const uint8_t which = PRNG() % 3;

                if ( which == 0 ) {
                    return generate_exp_mod_is_even_base_1(result);
                } else if ( which == 1 ) {
                    return generate_exp_mod_is_base_1(result);
                } else if ( which == 2 ) {
                    return generate_exp_mod_is_base_2();
                } else {
                    CF_UNREACHABLE();
                }
            }
        } else {
            CF_UNREACHABLE();
        }
    }
} /* ExpModGenerator */
} /* mutator */
} /* cryptofuzz */

Coverage Report

Created: 2022-08-24 06:31

Line	Count	Source (jump to first uncovered line)
1		#include "expmod.h"
2		#include <boost/random.hpp>
3		#include <fuzzing/datasource/id.hpp>
4		#include <cryptofuzz/util.h>
5		#include <cryptofuzz/repository.h>
6		#include "repository_tbl.h"
7		#include "config.h"
8
9		uint32_t PRNG(void);
10		std::string getBignum(bool mustBePositive = false);
11		std::string getPrime(void);
12
13		namespace cryptofuzz {
14		namespace mutator {
15		namespace ExpModGenerator {
16		using namespace boost::multiprecision;
17		using namespace boost::random;
18
19		static mt19937 mt;
20
21	0	inline bool is_even(const cpp_int& v) {
22	0	return (v & 1) == 0;
23	0	}
24
25	0	inline bool is_odd(const cpp_int& v) {
26	0	return (v & 1) == 1;
27	0	}
28
29	0	inline nlohmann::json to_json(const cpp_int& B, const cpp_int& E, const cpp_int& M) {
30	0	nlohmann::json ret;
31
32	0	ret["modifier"] = "";
33	0	ret["calcOp"] = CF_CALCOP("ExpMod(A,B,C)");
34	0	ret["bn1"] = B.str();
35	0	ret["bn2"] = E.str();
36	0	ret["bn3"] = M.str();
37	0	ret["bn4"] = "";
38
39	0	return ret;
40	0	}
41
42	0	inline const cpp_int& max(void) {
43	0	static const cpp_int max(std::string(cryptofuzz::config::kMaxBignumSize, '9'));
44	0	return max;
45	0	}
46
47	0	inline cpp_int max_multiplier(const cpp_int& v, const cpp_int& m) {
48	0	return v == 0 ? cpp_int(0) : m / v;
49	0	}
50
51	0	inline cpp_int max_multiplier(const cpp_int& v) {
52	0	return max_multiplier(v, max());
53	0	}
54
55		/* Multiply 'v' by a random positive integer m such that v * m < max() */
56		/* If that is not possible, return false, else return true.
57		*/
58	0	inline bool multiply_random(cpp_int& v, const bool odd = false) {
59	0	const cpp_int max_mul = max_multiplier(v);
60
61	0	if ( max_mul == 0 ) {
62	0	return false;
63	0	}
64
65	0	cpp_int mul = uniform_int_distribution<cpp_int>(1, max_mul)(mt);
66
67	0	if ( odd && is_even(mul) ) {
68	0	mul--;
69		//assert(mul > 0);
70	0	}
71
72	0	v *= mul;
73
74	0	return true;
75	0	}
76
77		/* If 'a' and 'b' are such that a * b < max(), then
78		* perform the multiplication on 'a' and return true.
79		* Return false otherwise.
80		*/
81	0	inline bool multiply(cpp_int& a, const cpp_int& b) {
82		/* XXX return a <= max() / b; */
83	0	const cpp_int max_mul = max_multiplier(a);
84
85	0	if ( max_mul < b ) {
86	0	return false;
87	0	}
88
89	0	a *= b;
90
91	0	return true;
92	0	}
93
94	0	inline cpp_int get_prime(void) {
95	0	const cpp_int p(getPrime());
96
97	0	if ( p > 0 ) {
98	0	return p;
99	0	}
100
101		/* Prime pool is empty, fall back to regular number */
102	0	return cpp_int(getBignum(true));
103	0	}
104
105	0	inline std::vector<size_t> prime_factors(const cpp_int& v) noexcept {
106	0	static const std::vector<size_t> primes{2, 3, 5, 7, 11, 13, 17, 19};
107
108	0	std::vector<size_t> ret;
109
110	0	for (const auto& p : primes) {
111	0	if ( v % p == 0 ) {
112	0	ret.push_back(p);
113	0	}
114	0	}
115
116	0	return ret;
117	0	}
118
119		/* Compute max E such that base^E <= v */
120	0	inline size_t log(const cpp_int& v, const cpp_int& base) {
121	0	size_t i = 0;
122	0	auto x = base;
123	0	while ( x <= v ) {
124	0	x *= base;
125	0	i++;
126	0	}
127	0	return i;
128	0	}
129
130		/* This is slightly faster than native boost::multiprecision::pow */
131	0	inline cpp_int pow(const cpp_int& v, const size_t exponent) {
132	0	if ( exponent == 0 ) {
133	0	static const cpp_int one(1);
134	0	return one;
135	0	} else if ( exponent == 1 ) {
136	0	return v;
137	0	} else {
138	0	return boost::multiprecision::pow(v, exponent);
139	0	}
140	0	}
141
142		/* Create an ExpMod operation where base, exp and mod are of size 'bits'
143		* and base^exp%mod == 0.
144		*
145		* To find certain modexp reduction bugs such as:
146		* https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315
147		* https://boringssl.googlesource.com/boringssl/+/801a801024febe1a33add5ddaa719e257d97aba5
148		*/
149		static std::optional<nlohmann::json> generate_exp_mod_is_0(const size_t bits)
150	0	{
151	0	CF_ASSERT(bits > 0, "Bits must be non-zero");
152
153		/* For some reason this crashes with high optimization */
154		/*
155		const auto min = cpp_int(1) << (bits - 1);
156		const auto max = (cpp_int(1) << bits) - 1;
157		*/
158
159	0	auto min = cpp_int(1);
160	0	min <<= (bits - 1);
161
162	0	auto max = cpp_int(1);
163	0	max <<= bits;
164	0	max--;
165
166		/* Create random base/exponent */
167	0	const cpp_int BE = uniform_int_distribution<cpp_int>(min, max)(mt);
168
169		/* Compute some prime factors of base/exponent */
170	0	const auto factors = prime_factors(BE);
171	0	if ( factors.empty() ) {
172	0	return std::nullopt;
173	0	}
174
175		/* Pick two random prime factors */
176	0	const auto P1 = cpp_int(factors[mt() % factors.size()]);
177	0	const auto P2 = factors[mt() % factors.size()];
178
179		/* I = P1^[0..P2] */
180	0	const cpp_int I = pow(P1, mt() % (P2+1));
181
182		/* Any J = P2^[0..I] would yield a valid modulus.
183		*
184		* However, we want I*J to not exceed the bitsize.
185		* Therefore, compute the max J.
186		*/
187	0	const cpp_int maxJ = max / I;
188
189		//assert(I * maxJ <= max);
190
191		/* Compute the max exponent such that
192		* J = P2^exp does not exceed the bitsize.
193		*/
194	0	const size_t maxJExp = log(maxJ, P2);
195
196	0	const cpp_int J = pow(cpp_int(P2), maxJExp);
197
198	0	const cpp_int M = I * J;
199
200		//assert(M <= max);
201		//assert(powm(BE, BE, M) == 0);
202
203	0	return to_json(BE, BE, M);
204	0	}
205
206		/* For all odd values base, pow(base, basemul, be+1) == base) where mul is any odd value. /
207	0	static std::optional<nlohmann::json> generate_exp_mod_is_odd_base_1(const cpp_int& B) {
208	0	if ( !is_odd(B) ) {
209	0	return std::nullopt;
210	0	}
211
212	0	cpp_int E = B;
213	0	if ( !multiply_random(E, true) ) {
214	0	return std::nullopt;
215	0	}
216
217	0	const cpp_int M = B + 1;
218
219		//assert(powm(B, E, M) == B);
220
221	0	return to_json(B, E, M);
222	0	}
223
224		/* For all odd values base, pow(base, basemul, base2) == base) where mul is any positive integer. */
225	0	static std::optional<nlohmann::json> generate_exp_mod_is_odd_base_2(const cpp_int& B) {
226	0	if ( !is_odd(B) ) {
227	0	return std::nullopt;
228	0	}
229
230	0	cpp_int E = B;
231	0	if ( !multiply_random(E) ) {
232	0	return std::nullopt;
233	0	}
234
235	0	const cpp_int M = B * 2;
236
237		//assert(powm(B, E, M) == B);
238
239	0	return to_json(B, E, M);
240	0	}
241
242		/* For all even values base >= 4, pow(base, basemul, base2-2) == base) where mul is any positive integer. */
243	0	static std::optional<nlohmann::json> generate_exp_mod_is_even_base_1(const cpp_int& B) {
244	0	if ( !is_even(B) ) {
245	0	return std::nullopt;
246	0	}
247	0	if ( B < 4 ) {
248	0	return std::nullopt;
249	0	}
250
251	0	cpp_int E = B;
252	0	if ( !multiply_random(E) ) {
253	0	return std::nullopt;
254	0	}
255
256	0	const cpp_int M = B * 2 - 2;
257
258		//assert(powm(B, E, M) == B);
259
260	0	return to_json(B, E, M);
261	0	}
262
263		/* For all prime values me > base, pow(base, me, me) == base). */
264	0	static std::optional<nlohmann::json> generate_exp_mod_is_base_1(const cpp_int& B) {
265	0	const cpp_int p = get_prime();
266
267	0	if ( B <= p ) {
268	0	return std::nullopt;
269	0	}
270
271	0	const cpp_int E = p;
272	0	const cpp_int M = p;
273
274		/* This only holds for prime p */
275		//assert(powm(B, E, M) == B);
276
277	0	return to_json(B, E, M);
278	0	}
279
280		/* For all prime values p and any positive e, pow(p+1, e, (p+1)p) == p+1. /
281	0	static std::optional<nlohmann::json> generate_exp_mod_is_base_2(void) {
282	0	const cpp_int p = get_prime();
283
284	0	if ( p < 3 ) {
285	0	return std::nullopt;
286	0	}
287
288	0	const cpp_int B = p + 1;
289	0	cpp_int E = 1;
290	0	if ( !multiply_random(E) ) {
291	0	return std::nullopt;
292	0	}
293	0	cpp_int M = p + 1;
294	0	if ( !multiply(M, p) ) {
295	0	return std::nullopt;
296	0	}
297
298		/* This only holds for prime p */
299		//assert(powm(B, E, M) == B);
300
301	0	return to_json(B, E, M);
302	0	}
303
304		/* For all odd values exp, pow(expmul, exp, exp2) == exp) where mul is any odd integer. */
305	0	static std::optional<nlohmann::json> generate_exp_mod_is_odd_exp_1(const cpp_int& E) {
306	0	if ( !is_odd(E) ) {
307	0	return std::nullopt;
308	0	}
309
310	0	cpp_int B = E;
311	0	if ( !multiply_random(B, true) ) {
312	0	return std::nullopt;
313	0	}
314	0	const cpp_int M = E * 2;
315
316		//assert(powm(B, E, M) == E);
317
318	0	return to_json(B, E, M);
319	0	}
320
321		/* 1. Let p be a prime such that p*2-1 >= v.
322		* 2. Let exp = p*2-1.
323		* 3. Let base = exp + (exp * (exp - v)).
324		* 4. Let mod = exp + 1.
325		* 5. Let k be any positive integer.
326		*
327		* Now pow(base, exp**k, mod) == v.
328		*/
329	0	static std::optional<nlohmann::json> generate_exp_mod_is_v_1(const cpp_int& v) {
330		/* Step 1 */
331	0	const cpp_int p = get_prime();
332	0	if ( p < 1 ) {
333	0	return std::nullopt;
334	0	}
335
336		/* Step 2 */
337	0	const cpp_int E = 2 * p - 1;
338	0	if ( E > max() \|\| E < v ) {
339	0	return std::nullopt;
340	0	}
341
342		/* Step 3 */
343	0	cpp_int B = E;
344	0	{
345	0	const cpp_int delta = E - v + 1;
346		/* B = delta /
347	0	if ( !multiply(B, delta) ) {
348	0	return std::nullopt;
349	0	}
350	0	}
351
352		/* Step 4 */
353	0	const cpp_int M = E + 1;
354
355		/* TODO exponentiate exp */
356
357		/* This only holds for prime p */
358		//assert(powm(B, E, M) == v);
359
360	0	return to_json(B, E, M);
361	0	}
362
363		/* 1. Let p be a prime such that p-1 >= v.
364		* 2. Let exp = p-1.
365		* 3. Let base = exp + (exp * (exp - v)).
366		* 4. Let mod = exp + 1.
367		* 5. Let k be any positive integer.
368		*
369		* Now pow(base, (exp*k)+1, mod) == v.
370		*/
371	0	static std::optional<nlohmann::json> generate_exp_mod_is_v_2(const cpp_int& v) {
372		/* Step 1 */
373	0	const cpp_int p = get_prime();
374	0	if ( p < 1 ) {
375	0	return std::nullopt;
376	0	}
377
378		/* Step 2 */
379	0	cpp_int E = p - 1;
380	0	if ( E > max() \|\| E < v ) {
381	0	return std::nullopt;
382	0	}
383
384		/* Step 3 */
385	0	cpp_int B = E;
386	0	{
387	0	const cpp_int delta = E - v + 1;
388		/* B = delta /
389	0	if ( !multiply(B, delta) ) {
390	0	return std::nullopt;
391	0	}
392	0	}
393
394		/* Step 4 */
395	0	const cpp_int M = E + 1;
396
397		/* E = EK+1 /
398	0	if ( !multiply_random(E) ) {
399	0	return std::nullopt;
400	0	}
401	0	E++;
402
403		/* This only holds for prime p */
404		//assert(powm(B, E, M) == v);
405
406	0	return to_json(B, E, M);
407	0	}
408
409	0	std::optional<nlohmann::json> generate_exp_mod(const std::string& _result) {
410	0	const uint8_t which = PRNG() % 3;
411	0	if ( which == 0 ) {
412	0	static const std::array<size_t, 6> bitsizes{256, 512, 1024, 2048, 4096, 8192};
413
414	0	return generate_exp_mod_is_0(bitsizes[PRNG() % bitsizes.size()]);
415	0	} else if ( which == 1 ) {
416	0	const cpp_int result = cpp_int(_result);
417
418	0	const uint8_t which = PRNG() % 2;
419
420	0	if ( which == 0 ) {
421	0	return generate_exp_mod_is_v_1(result);
422	0	} else if ( which == 1 ) {
423	0	return generate_exp_mod_is_v_2(result);
424	0	} else {
425	0	CF_UNREACHABLE();
426	0	}
427	0	} else if ( which == 2 ) {
428	0	const cpp_int result = cpp_int(_result);
429
430	0	if ( is_odd(result) ) {
431	0	const uint8_t which = PRNG() % 5;
432
433	0	if ( which == 0 ) {
434	0	return generate_exp_mod_is_odd_base_1(result);
435	0	} else if ( which == 1 ) {
436	0	return generate_exp_mod_is_odd_base_2(result);
437	0	} else if ( which == 2 ) {
438	0	return generate_exp_mod_is_odd_exp_1(result);
439	0	} else if ( which == 3 ) {
440	0	return generate_exp_mod_is_base_1(result);
441	0	} else if ( which == 4 ) {
442	0	return generate_exp_mod_is_base_2();
443	0	} else {
444	0	CF_UNREACHABLE();
445	0	}
446	0	} else {
447	0	const uint8_t which = PRNG() % 3;
448
449	0	if ( which == 0 ) {
450	0	return generate_exp_mod_is_even_base_1(result);
451	0	} else if ( which == 1 ) {
452	0	return generate_exp_mod_is_base_1(result);
453	0	} else if ( which == 2 ) {
454	0	return generate_exp_mod_is_base_2();
455	0	} else {
456	0	CF_UNREACHABLE();
457	0	}
458	0	}
459	0	} else {
460	0	CF_UNREACHABLE();
461	0	}
462	0	}
463		} /* ExpModGenerator */
464		} /* mutator */
465		} /* cryptofuzz */