1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #include <libecc/nn/nn_rand.h>
17 #include <libecc/nn/nn_add.h>
18 #include <libecc/nn/nn_logical.h>
19 /* Include the "internal" header as we use non public API here */
20 #include "../nn/nn_div.h"
21
22
23 #include <libecc/external_deps/rand.h>
24
25 /*
26 * The function initializes nn structure pointed by 'out' to a random value of
27 * byte length 'len'. The resulting nn will have a uniformly random value in
28 * [0, 2^(8 * len)[. Provided length 'len' parameter must be less than or equal
29 * to NN_MAX_BYTE_LEN. The function returns -1 on error and 0 on success.
30 */
nn_get_random_len(nn_t out,u16 len)31 int nn_get_random_len(nn_t out, u16 len)
32 {
33 int ret;
34
35 MUST_HAVE((len <= NN_MAX_BYTE_LEN), ret, err);
36
37 ret = nn_init(out, len); EG(ret, err);
38 ret = get_random((u8*) out->val, len);
39
40 err:
41 return ret;
42 }
43
44 /*
45 * The function initializes nn structure pointed by 'out' to a random value of
46 * *random* byte length less than or equal to 'max_len'. Unlike the function
47 * above (nn_get_random_len()), the resulting nn will have a uniformly random
48 * value in in [0, 2^(8 * len)[ *with* length selected at random in
49 * [0, max_len]. The function returns -1 on error and 0 on success.
50 *
51 * !! NOTE !!: think twice before using this function for anything other than
52 * testing purposes. Its main goal is to generate nn with random length, not
53 * random numbers. For instance, for a given value of max_len, the function
54 * returns a nn with a value of 0 w/ probability 1/max_len.
55 */
nn_get_random_maxlen(nn_t out,u16 max_len)56 int nn_get_random_maxlen(nn_t out, u16 max_len)
57 {
58 u16 len;
59 int ret;
60
61 MUST_HAVE((max_len <= NN_MAX_BYTE_LEN), ret, err);
62
63 ret = get_random((u8 *)&len, 2); EG(ret, err);
64
65 len = (u16)(len % (max_len + 1));
66
67 ret = nn_get_random_len(out, len);
68
69 err:
70 return ret;
71 }
72
73 /*
74 * On success, the return value of the function is 0 and 'out' parameter
75 * is initialized to an unbiased random value in ]0,q[. On error, the
76 * function returns -1. Due to the generation process described below,
77 * the size of q is limited by NN_MAX_BYTE_LEN / 2. Aliasing is supported.
78 *
79 * Generating a random value in ]0,q[ is done by reducing a large random
80 * value modulo q. The random value is taken with a length twice the one
81 * of q to ensure the reduction does not produce a biased value.
82 *
83 * Even if this is unlikely to happen, the reduction can produce a null
84 * result; this specific case would require to repeat the whole process.
85 * For that reason, the algorithm we implement works in the following
86 * way:
87 *
88 * 1) compute q' = q - 1 (note: q is neither 0 nor 1)
89 * 2) generate a random value tmp_rand twice the size of q
90 * 3) compute out = tmp_rand mod q' (note: out is in [0, q-2])
91 * 4) compute out += 1 (note: out is in [1, q-1])
92 *
93 * Aliasing is supported.
94 */
nn_get_random_mod(nn_t out,nn_src_t q)95 int nn_get_random_mod(nn_t out, nn_src_t q)
96 {
97 nn tmp_rand, qprime;
98 bitcnt_t q_bit_len, q_len;
99 int ret, isone;
100 qprime.magic = tmp_rand.magic = WORD(0);
101
102 /* Check q is initialized and get its bit length */
103 ret = nn_check_initialized(q); EG(ret, err);
104 ret = nn_bitlen(q, &q_bit_len); EG(ret, err);
105 q_len = (bitcnt_t)BYTECEIL(q_bit_len);
106
107 /* Check q is neither 0, nor 1 and its size is ok */
108 MUST_HAVE((q_len) && (q_len <= (NN_MAX_BYTE_LEN / 2)), ret, err);
109 MUST_HAVE((!nn_isone(q, &isone)) && (!isone), ret, err);
110
111 /* 1) compute q' = q - 1 */
112 ret = nn_copy(&qprime, q); EG(ret, err);
113 ret = nn_dec(&qprime, &qprime); EG(ret, err);
114
115 /* 2) generate a random value tmp_rand twice the size of q */
116 ret = nn_init(&tmp_rand, (u16)(2 * q_len)); EG(ret, err);
117 ret = get_random((u8 *)tmp_rand.val, (u16)(2 * q_len)); EG(ret, err);
118
119 /* 3) compute out = tmp_rand mod q' */
120 ret = nn_init(out, (u16)q_len); EG(ret, err);
121
122 /* Use nn_mod_notrim to avoid exposing the generated random length */
123 ret = nn_mod_notrim(out, &tmp_rand, &qprime); EG(ret, err);
124
125 /* 4) compute out += 1 */
126 ret = nn_inc(out, out);
127
128 err:
129 nn_uninit(&qprime);
130 nn_uninit(&tmp_rand);
131
132 return ret;
133 }
134