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 */ 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 */ 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 */ 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