Elligator.cpp
1 /* 2 * Copyright (c) 2013-2020, The PurpleI2P Project 3 * 4 * This file is part of Purple i2pd project and licensed under BSD3 5 * 6 * See full license text in LICENSE file at top of project tree 7 */ 8 9 #include <openssl/rand.h> 10 #include "Crypto.h" 11 #include "Elligator.h" 12 13 namespace i2p 14 { 15 namespace crypto 16 { 17 18 Elligator2::Elligator2 () 19 { 20 // TODO: share with Ed22519 21 p = BN_new (); 22 // 2^255-19 23 BN_set_bit (p, 255); // 2^255 24 BN_sub_word (p, 19); 25 p38 = BN_dup (p); BN_add_word (p38, 3); BN_div_word (p38, 8); // (p+3)/8 26 p12 = BN_dup (p); BN_sub_word (p12, 1); BN_div_word (p12, 2); // (p-1)/2 27 p14 = BN_dup (p); BN_sub_word (p14, 1); BN_div_word (p14, 4); // (p-1)/4 28 29 A = BN_new (); BN_set_word (A, 486662); 30 nA = BN_new (); BN_sub (nA, p, A); 31 32 BN_CTX * ctx = BN_CTX_new (); 33 // calculate sqrt(-1) 34 sqrtn1 = BN_new (); 35 BN_set_word (sqrtn1, 2); 36 BN_mod_exp (sqrtn1, sqrtn1, p14, p, ctx); // 2^((p-1)/4 37 38 u = BN_new (); BN_set_word (u, 2); 39 iu = BN_new (); BN_mod_inverse (iu, u, p, ctx); 40 41 BN_CTX_free (ctx); 42 } 43 44 Elligator2::~Elligator2 () 45 { 46 BN_free (p); BN_free (p38); BN_free (p12); BN_free (p14); 47 BN_free (sqrtn1); BN_free (A); BN_free (nA); 48 BN_free (u); BN_free (iu); 49 } 50 51 bool Elligator2::Encode (const uint8_t * key, uint8_t * encoded, bool highY, bool random) const 52 { 53 bool ret = true; 54 BN_CTX * ctx = BN_CTX_new (); 55 BN_CTX_start (ctx); 56 57 uint8_t key1[32]; 58 for (size_t i = 0; i < 16; i++) // from Little Endian 59 { 60 key1[i] = key[31 - i]; 61 key1[31 - i] = key[i]; 62 } 63 64 BIGNUM * x = BN_CTX_get (ctx); BN_bin2bn (key1, 32, x); 65 BIGNUM * xA = BN_CTX_get (ctx); BN_add (xA, x, A); // x + A 66 BN_sub (xA, p, xA); // p - (x + A) 67 68 BIGNUM * uxxA = BN_CTX_get (ctx); // u*x*xA 69 BN_mod_mul (uxxA, u, x, p, ctx); 70 BN_mod_mul (uxxA, uxxA, xA, p, ctx); 71 72 if (Legendre (uxxA, ctx) != -1) 73 { 74 uint8_t randByte = 0; // random highest bits and high y 75 if (random) 76 { 77 RAND_bytes (&randByte, 1); 78 highY = randByte & 0x01; 79 } 80 81 BIGNUM * r = BN_CTX_get (ctx); 82 if (highY) 83 { 84 BN_mod_inverse (r, x, p, ctx); 85 BN_mod_mul (r, r, xA, p, ctx); 86 } 87 else 88 { 89 BN_mod_inverse (r, xA, p, ctx); 90 BN_mod_mul (r, r, x, p, ctx); 91 } 92 BN_mod_mul (r, r, iu, p, ctx); 93 94 SquareRoot (r, r, ctx); 95 bn2buf (r, encoded, 32); 96 97 if (random) 98 encoded[0] |= (randByte & 0xC0); // copy two highest bits from randByte 99 for (size_t i = 0; i < 16; i++) // To Little Endian 100 { 101 uint8_t tmp = encoded[i]; 102 encoded[i] = encoded[31 - i]; 103 encoded[31 - i] = tmp; 104 } 105 } 106 else 107 ret = false; 108 109 BN_CTX_end (ctx); 110 BN_CTX_free (ctx); 111 return ret; 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 } 172 173 void Elligator2::SquareRoot (const BIGNUM * x, BIGNUM * r, BN_CTX * ctx) const 174 { 175 BIGNUM * t = BN_CTX_get (ctx); 176 BN_mod_exp (t, x, p14, p, ctx); // t = x^((p-1)/4) 177 BN_mod_exp (r, x, p38, p, ctx); // r = x^((p+3)/8) 178 BN_add_word (t, 1); 179 180 if (!BN_cmp (t, p)) 181 BN_mod_mul (r, r, sqrtn1, p, ctx); 182 183 if (BN_cmp (r, p12) > 0) // r > (p-1)/2 184 BN_sub (r, p, r); 185 } 186 187 int Elligator2::Legendre (const BIGNUM * a, BN_CTX * ctx) const 188 { 189 // assume a < p, so don't check for a % p = 0, but a = 0 only 190 if (BN_is_zero(a)) return 0; 191 BIGNUM * r = BN_CTX_get (ctx); 192 BN_mod_exp (r, a, p12, p, ctx); // r = a^((p-1)/2) mod p 193 if (BN_is_word(r, 1)) 194 return 1; 195 else if (BN_is_zero(r)) 196 return 0; 197 return -1; 198 } 199 200 static std::unique_ptr<Elligator2> g_Elligator; 201 std::unique_ptr<Elligator2>& GetElligator () 202 { 203 if (!g_Elligator) 204 { 205 auto el = new Elligator2(); 206 if (!g_Elligator) // make sure it was not created already 207 g_Elligator.reset (el); 208 else 209 delete el; 210 } 211 return g_Elligator; 212 } 213 } 214 }