| 112 | } |
| 113 | |
| 114 | bool Elligator2::Decode (const uint8_t * encoded, uint8_t * key) const |
| 115 | { |
| 116 | bool ret = true; |
| 117 | BN_CTX * ctx = BN_CTX_new (); |
| 118 | BN_CTX_start (ctx); |
| 119 | |
| 120 | uint8_t encoded1[32]; |
| 121 | for (size_t i = 0; i < 16; i++) // from Little Endian |
| 122 | { |
| 123 | encoded1[i] = encoded[31 - i]; |
| 124 | encoded1[31 - i] = encoded[i]; |
| 125 | } |
| 126 | encoded1[0] &= 0x3F; // drop two highest bits |
| 127 | |
| 128 | BIGNUM * r = BN_CTX_get (ctx); BN_bin2bn (encoded1, 32, r); |
| 129 | |
| 130 | if (BN_cmp (r, p12) <= 0) // r < (p-1)/2 |
| 131 | { |
| 132 | // v = -A/(1+u*r^2) |
| 133 | BIGNUM * v = BN_CTX_get (ctx); BN_mod_sqr (v, r, p, ctx); |
| 134 | BN_mod_mul (v, v, u, p, ctx); |
| 135 | BN_add_word (v, 1); |
| 136 | BN_mod_inverse (v, v, p, ctx); |
| 137 | BN_mod_mul (v, v, nA, p, ctx); |
| 138 | |
| 139 | BIGNUM * vpA = BN_CTX_get (ctx); |
| 140 | BN_add (vpA, v, A); // v + A |
| 141 | // t = v^3+A*v^2+v = v^2*(v+A)+v |
| 142 | BIGNUM * t = BN_CTX_get (ctx); BN_mod_sqr (t, v, p, ctx); |
| 143 | BN_mod_mul (t, t, vpA, p, ctx); |
| 144 | BN_mod_add (t, t, v, p, ctx); |
| 145 | |
| 146 | int legendre = Legendre (t, ctx); |
| 147 | BIGNUM * x = BN_CTX_get (ctx); |
| 148 | if (legendre == 1) |
| 149 | BN_copy (x, v); |
| 150 | else |
| 151 | { |
| 152 | BN_sub (x, p, v); |
| 153 | BN_mod_sub (x, x, A, p, ctx); |
| 154 | } |
| 155 | |
| 156 | bn2buf (x, key, 32); |
| 157 | for (size_t i = 0; i < 16; i++) // To Little Endian |
| 158 | { |
| 159 | uint8_t tmp = key[i]; |
| 160 | key[i] = key[31 - i]; |
| 161 | key[31 - i] = tmp; |
| 162 | } |
| 163 | } |
| 164 | else |
| 165 | ret = false; |
| 166 | |
| 167 | BN_CTX_end (ctx); |
| 168 | BN_CTX_free (ctx); |
| 169 | |
| 170 | return ret; |
| 171 | } |