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/sha.h> 10 #include "Log.h" 11 #include "Crypto.h" 12 #include "Ed25519.h" 13 14 namespace i2p 15 { 16 namespace crypto 17 { Ed25519()18 Ed25519::Ed25519 () 19 { 20 BN_CTX * ctx = BN_CTX_new (); 21 BIGNUM * tmp = BN_new (); 22 23 q = BN_new (); 24 // 2^255-19 25 BN_set_bit (q, 255); // 2^255 26 BN_sub_word (q, 19); 27 28 l = BN_new (); 29 // 2^252 + 27742317777372353535851937790883648493 30 BN_set_bit (l, 252); 31 two_252_2 = BN_dup (l); 32 BN_dec2bn (&tmp, "27742317777372353535851937790883648493"); 33 BN_add (l, l, tmp); 34 BN_sub_word (two_252_2, 2); // 2^252 - 2 35 36 // -121665*inv(121666) 37 d = BN_new (); 38 BN_set_word (tmp, 121666); 39 BN_mod_inverse (tmp, tmp, q, ctx); 40 BN_set_word (d, 121665); 41 BN_set_negative (d, 1); 42 BN_mod_mul (d, d, tmp, q, ctx); 43 44 // 2^((q-1)/4) 45 I = BN_new (); 46 BN_free (tmp); 47 tmp = BN_dup (q); 48 BN_sub_word (tmp, 1); 49 BN_div_word (tmp, 4); 50 BN_set_word (I, 2); 51 BN_mod_exp (I, I, tmp, q, ctx); 52 BN_free (tmp); 53 54 // 4*inv(5) 55 BIGNUM * By = BN_new (); 56 BN_set_word (By, 5); 57 BN_mod_inverse (By, By, q, ctx); 58 BN_mul_word (By, 4); 59 BIGNUM * Bx = RecoverX (By, ctx); 60 BN_mod (Bx, Bx, q, ctx); // % q 61 BN_mod (By, By, q, ctx); // % q 62 63 // precalculate Bi256 table 64 Bi256Carry = { Bx, By }; // B 65 for (int i = 0; i < 32; i++) 66 { 67 Bi256[i][0] = Bi256Carry; // first point 68 for (int j = 1; j < 128; j++) 69 Bi256[i][j] = Sum (Bi256[i][j-1], Bi256[i][0], ctx); // (256+j+1)^i*B 70 Bi256Carry = Bi256[i][127]; 71 for (int j = 0; j < 128; j++) // add first point 128 more times 72 Bi256Carry = Sum (Bi256Carry, Bi256[i][0], ctx); 73 } 74 75 BN_CTX_free (ctx); 76 } 77 Ed25519(const Ed25519 & other)78 Ed25519::Ed25519 (const Ed25519& other): q (BN_dup (other.q)), l (BN_dup (other.l)), 79 d (BN_dup (other.d)), I (BN_dup (other.I)), two_252_2 (BN_dup (other.two_252_2)), 80 Bi256Carry (other.Bi256Carry) 81 { 82 for (int i = 0; i < 32; i++) 83 for (int j = 0; j < 128; j++) 84 Bi256[i][j] = other.Bi256[i][j]; 85 } 86 ~Ed25519()87 Ed25519::~Ed25519 () 88 { 89 BN_free (q); 90 BN_free (l); 91 BN_free (d); 92 BN_free (I); 93 BN_free (two_252_2); 94 } 95 96 GeneratePublicKey(const uint8_t * expandedPrivateKey,BN_CTX * ctx) const97 EDDSAPoint Ed25519::GeneratePublicKey (const uint8_t * expandedPrivateKey, BN_CTX * ctx) const 98 { 99 return MulB (expandedPrivateKey, ctx); // left half of expanded key, considered as Little Endian 100 } 101 DecodePublicKey(const uint8_t * buf,BN_CTX * ctx) const102 EDDSAPoint Ed25519::DecodePublicKey (const uint8_t * buf, BN_CTX * ctx) const 103 { 104 return DecodePoint (buf, ctx); 105 } 106 EncodePublicKey(const EDDSAPoint & publicKey,uint8_t * buf,BN_CTX * ctx) const107 void Ed25519::EncodePublicKey (const EDDSAPoint& publicKey, uint8_t * buf, BN_CTX * ctx) const 108 { 109 EncodePoint (Normalize (publicKey, ctx), buf); 110 } 111 Verify(const EDDSAPoint & publicKey,const uint8_t * digest,const uint8_t * signature) const112 bool Ed25519::Verify (const EDDSAPoint& publicKey, const uint8_t * digest, const uint8_t * signature) const 113 { 114 BN_CTX * ctx = BN_CTX_new (); 115 BIGNUM * h = DecodeBN<64> (digest); 116 // signature 0..31 - R, 32..63 - S 117 // B*S = R + PK*h => R = B*S - PK*h 118 // we don't decode R, but encode (B*S - PK*h) 119 auto Bs = MulB (signature + EDDSA25519_SIGNATURE_LENGTH/2, ctx); // B*S; 120 BN_mod (h, h, l, ctx); // public key is multiple of B, but B%l = 0 121 auto PKh = Mul (publicKey, h, ctx); // PK*h 122 uint8_t diff[32]; 123 EncodePoint (Normalize (Sum (Bs, -PKh, ctx), ctx), diff); // Bs - PKh encoded 124 bool passed = !memcmp (signature, diff, 32); // R 125 BN_free (h); 126 BN_CTX_free (ctx); 127 if (!passed) 128 LogPrint (eLogError, "25519 signature verification failed"); 129 return passed; 130 } 131 Sign(const uint8_t * expandedPrivateKey,const uint8_t * publicKeyEncoded,const uint8_t * buf,size_t len,uint8_t * signature) const132 void Ed25519::Sign (const uint8_t * expandedPrivateKey, const uint8_t * publicKeyEncoded, 133 const uint8_t * buf, size_t len, uint8_t * signature) const 134 { 135 BN_CTX * bnCtx = BN_CTX_new (); 136 // calculate r 137 SHA512_CTX ctx; 138 SHA512_Init (&ctx); 139 SHA512_Update (&ctx, expandedPrivateKey + EDDSA25519_PRIVATE_KEY_LENGTH, EDDSA25519_PRIVATE_KEY_LENGTH); // right half of expanded key 140 SHA512_Update (&ctx, buf, len); // data 141 uint8_t digest[64]; 142 SHA512_Final (digest, &ctx); 143 BIGNUM * r = DecodeBN<32> (digest); // DecodeBN<64> (digest); // for test vectors 144 // calculate R 145 uint8_t R[EDDSA25519_SIGNATURE_LENGTH/2]; // we must use separate buffer because signature might be inside buf 146 EncodePoint (Normalize (MulB (digest, bnCtx), bnCtx), R); // EncodePoint (Mul (B, r, bnCtx), R); // for test vectors 147 // calculate S 148 SHA512_Init (&ctx); 149 SHA512_Update (&ctx, R, EDDSA25519_SIGNATURE_LENGTH/2); // R 150 SHA512_Update (&ctx, publicKeyEncoded, EDDSA25519_PUBLIC_KEY_LENGTH); // public key 151 SHA512_Update (&ctx, buf, len); // data 152 SHA512_Final (digest, &ctx); 153 BIGNUM * h = DecodeBN<64> (digest); 154 // S = (r + h*a) % l 155 BIGNUM * a = DecodeBN<EDDSA25519_PRIVATE_KEY_LENGTH> (expandedPrivateKey); // left half of expanded key 156 BN_mod_mul (h, h, a, l, bnCtx); // %l 157 BN_mod_add (h, h, r, l, bnCtx); // %l 158 memcpy (signature, R, EDDSA25519_SIGNATURE_LENGTH/2); 159 EncodeBN (h, signature + EDDSA25519_SIGNATURE_LENGTH/2, EDDSA25519_SIGNATURE_LENGTH/2); // S 160 BN_free (r); BN_free (h); BN_free (a); 161 BN_CTX_free (bnCtx); 162 } 163 SignRedDSA(const uint8_t * privateKey,const uint8_t * publicKeyEncoded,const uint8_t * buf,size_t len,uint8_t * signature) const164 void Ed25519::SignRedDSA (const uint8_t * privateKey, const uint8_t * publicKeyEncoded, 165 const uint8_t * buf, size_t len, uint8_t * signature) const 166 { 167 BN_CTX * bnCtx = BN_CTX_new (); 168 // T = 80 random bytes 169 uint8_t T[80]; 170 RAND_bytes (T, 80); 171 // calculate r = H*(T || publickey || data) 172 SHA512_CTX ctx; 173 SHA512_Init (&ctx); 174 SHA512_Update (&ctx, T, 80); 175 SHA512_Update (&ctx, publicKeyEncoded, 32); 176 SHA512_Update (&ctx, buf, len); // data 177 uint8_t digest[64]; 178 SHA512_Final (digest, &ctx); 179 BIGNUM * r = DecodeBN<64> (digest); 180 BN_mod (r, r, l, bnCtx); // % l 181 EncodeBN (r, digest, 32); 182 // calculate R 183 uint8_t R[EDDSA25519_SIGNATURE_LENGTH/2]; // we must use separate buffer because signature might be inside buf 184 EncodePoint (Normalize (MulB (digest, bnCtx), bnCtx), R); 185 // calculate S 186 SHA512_Init (&ctx); 187 SHA512_Update (&ctx, R, EDDSA25519_SIGNATURE_LENGTH/2); // R 188 SHA512_Update (&ctx, publicKeyEncoded, EDDSA25519_PUBLIC_KEY_LENGTH); // public key 189 SHA512_Update (&ctx, buf, len); // data 190 SHA512_Final (digest, &ctx); 191 BIGNUM * h = DecodeBN<64> (digest); 192 // S = (r + h*a) % l 193 BIGNUM * a = DecodeBN<EDDSA25519_PRIVATE_KEY_LENGTH> (privateKey); 194 BN_mod_mul (h, h, a, l, bnCtx); // %l 195 BN_mod_add (h, h, r, l, bnCtx); // %l 196 memcpy (signature, R, EDDSA25519_SIGNATURE_LENGTH/2); 197 EncodeBN (h, signature + EDDSA25519_SIGNATURE_LENGTH/2, EDDSA25519_SIGNATURE_LENGTH/2); // S 198 BN_free (r); BN_free (h); BN_free (a); 199 BN_CTX_free (bnCtx); 200 } 201 Sum(const EDDSAPoint & p1,const EDDSAPoint & p2,BN_CTX * ctx) const202 EDDSAPoint Ed25519::Sum (const EDDSAPoint& p1, const EDDSAPoint& p2, BN_CTX * ctx) const 203 { 204 // x3 = (x1*y2+y1*x2)*(z1*z2-d*t1*t2) 205 // y3 = (y1*y2+x1*x2)*(z1*z2+d*t1*t2) 206 // z3 = (z1*z2-d*t1*t2)*(z1*z2+d*t1*t2) 207 // t3 = (y1*y2+x1*x2)*(x1*y2+y1*x2) 208 BIGNUM * x3 = BN_new (), * y3 = BN_new (), * z3 = BN_new (), * t3 = BN_new (); 209 210 BN_mul (x3, p1.x, p2.x, ctx); // A = x1*x2 211 BN_mul (y3, p1.y, p2.y, ctx); // B = y1*y2 212 213 BN_CTX_start (ctx); 214 BIGNUM * t1 = p1.t, * t2 = p2.t; 215 if (!t1) { t1 = BN_CTX_get (ctx); BN_mul (t1, p1.x, p1.y, ctx); } 216 if (!t2) { t2 = BN_CTX_get (ctx); BN_mul (t2, p2.x, p2.y, ctx); } 217 BN_mul (t3, t1, t2, ctx); 218 BN_mul (t3, t3, d, ctx); // C = d*t1*t2 219 220 if (p1.z) 221 { 222 if (p2.z) 223 BN_mul (z3, p1.z, p2.z, ctx); // D = z1*z2 224 else 225 BN_copy (z3, p1.z); // D = z1 226 } 227 else 228 { 229 if (p2.z) 230 BN_copy (z3, p2.z); // D = z2 231 else 232 BN_one (z3); // D = 1 233 } 234 235 BIGNUM * E = BN_CTX_get (ctx), * F = BN_CTX_get (ctx), * G = BN_CTX_get (ctx), * H = BN_CTX_get (ctx); 236 BN_add (E, p1.x, p1.y); 237 BN_add (F, p2.x, p2.y); 238 BN_mul (E, E, F, ctx); // (x1 + y1)*(x2 + y2) 239 BN_sub (E, E, x3); 240 BN_sub (E, E, y3); // E = (x1 + y1)*(x2 + y2) - A - B 241 BN_sub (F, z3, t3); // F = D - C 242 BN_add (G, z3, t3); // G = D + C 243 BN_add (H, y3, x3); // H = B + A 244 245 BN_mod_mul (x3, E, F, q, ctx); // x3 = E*F 246 BN_mod_mul (y3, G, H, q, ctx); // y3 = G*H 247 BN_mod_mul (z3, F, G, q, ctx); // z3 = F*G 248 BN_mod_mul (t3, E, H, q, ctx); // t3 = E*H 249 250 BN_CTX_end (ctx); 251 252 return EDDSAPoint {x3, y3, z3, t3}; 253 } 254 Double(EDDSAPoint & p,BN_CTX * ctx) const255 void Ed25519::Double (EDDSAPoint& p, BN_CTX * ctx) const 256 { 257 BN_CTX_start (ctx); 258 BIGNUM * x2 = BN_CTX_get (ctx), * y2 = BN_CTX_get (ctx), * z2 = BN_CTX_get (ctx), * t2 = BN_CTX_get (ctx); 259 260 BN_sqr (x2, p.x, ctx); // x2 = A = x^2 261 BN_sqr (y2, p.y, ctx); // y2 = B = y^2 262 if (p.t) 263 BN_sqr (t2, p.t, ctx); // t2 = t^2 264 else 265 { 266 BN_mul (t2, p.x, p.y, ctx); // t = x*y 267 BN_sqr (t2, t2, ctx); // t2 = t^2 268 } 269 BN_mul (t2, t2, d, ctx); // t2 = C = d*t^2 270 if (p.z) 271 BN_sqr (z2, p.z, ctx); // z2 = D = z^2 272 else 273 BN_one (z2); // z2 = 1 274 275 BIGNUM * E = BN_CTX_get (ctx), * F = BN_CTX_get (ctx), * G = BN_CTX_get (ctx), * H = BN_CTX_get (ctx); 276 // E = (x+y)*(x+y)-A-B = x^2+y^2+2xy-A-B = 2xy 277 BN_mul (E, p.x, p.y, ctx); 278 BN_lshift1 (E, E); // E =2*x*y 279 BN_sub (F, z2, t2); // F = D - C 280 BN_add (G, z2, t2); // G = D + C 281 BN_add (H, y2, x2); // H = B + A 282 283 BN_mod_mul (p.x, E, F, q, ctx); // x2 = E*F 284 BN_mod_mul (p.y, G, H, q, ctx); // y2 = G*H 285 if (!p.z) p.z = BN_new (); 286 BN_mod_mul (p.z, F, G, q, ctx); // z2 = F*G 287 if (!p.t) p.t = BN_new (); 288 BN_mod_mul (p.t, E, H, q, ctx); // t2 = E*H 289 290 BN_CTX_end (ctx); 291 } 292 Mul(const EDDSAPoint & p,const BIGNUM * e,BN_CTX * ctx) const293 EDDSAPoint Ed25519::Mul (const EDDSAPoint& p, const BIGNUM * e, BN_CTX * ctx) const 294 { 295 BIGNUM * zero = BN_new (), * one = BN_new (); 296 BN_zero (zero); BN_one (one); 297 EDDSAPoint res {zero, one}; 298 if (!BN_is_zero (e)) 299 { 300 int bitCount = BN_num_bits (e); 301 for (int i = bitCount - 1; i >= 0; i--) 302 { 303 Double (res, ctx); 304 if (BN_is_bit_set (e, i)) res = Sum (res, p, ctx); 305 } 306 } 307 return res; 308 } 309 MulB(const uint8_t * e,BN_CTX * ctx) const310 EDDSAPoint Ed25519::MulB (const uint8_t * e, BN_CTX * ctx) const // B*e, e is 32 bytes Little Endian 311 { 312 BIGNUM * zero = BN_new (), * one = BN_new (); 313 BN_zero (zero); BN_one (one); 314 EDDSAPoint res {zero, one}; 315 bool carry = false; 316 for (int i = 0; i < 32; i++) 317 { 318 uint8_t x = e[i]; 319 if (carry) 320 { 321 if (x < 255) 322 { 323 x++; 324 carry = false; 325 } 326 else 327 x = 0; 328 } 329 if (x > 0) 330 { 331 if (x <= 128) 332 res = Sum (res, Bi256[i][x-1], ctx); 333 else 334 { 335 res = Sum (res, -Bi256[i][255-x], ctx); // -Bi[256-x] 336 carry = true; 337 } 338 } 339 } 340 if (carry) res = Sum (res, Bi256Carry, ctx); 341 return res; 342 } 343 Normalize(const EDDSAPoint & p,BN_CTX * ctx) const344 EDDSAPoint Ed25519::Normalize (const EDDSAPoint& p, BN_CTX * ctx) const 345 { 346 if (p.z) 347 { 348 BIGNUM * x = BN_new (), * y = BN_new (); 349 BN_mod_inverse (y, p.z, q, ctx); 350 BN_mod_mul (x, p.x, y, q, ctx); // x = x/z 351 BN_mod_mul (y, p.y, y, q, ctx); // y = y/z 352 return EDDSAPoint{x, y}; 353 } 354 else 355 return EDDSAPoint{BN_dup (p.x), BN_dup (p.y)}; 356 } 357 IsOnCurve(const EDDSAPoint & p,BN_CTX * ctx) const358 bool Ed25519::IsOnCurve (const EDDSAPoint& p, BN_CTX * ctx) const 359 { 360 BN_CTX_start (ctx); 361 BIGNUM * x2 = BN_CTX_get (ctx), * y2 = BN_CTX_get (ctx), * tmp = BN_CTX_get (ctx); 362 BN_sqr (x2, p.x, ctx); // x^2 363 BN_sqr (y2, p.y, ctx); // y^2 364 // y^2 - x^2 - 1 - d*x^2*y^2 365 BN_mul (tmp, d, x2, ctx); 366 BN_mul (tmp, tmp, y2, ctx); 367 BN_sub (tmp, y2, tmp); 368 BN_sub (tmp, tmp, x2); 369 BN_sub_word (tmp, 1); 370 BN_mod (tmp, tmp, q, ctx); // % q 371 bool ret = BN_is_zero (tmp); 372 BN_CTX_end (ctx); 373 return ret; 374 } 375 RecoverX(const BIGNUM * y,BN_CTX * ctx) const376 BIGNUM * Ed25519::RecoverX (const BIGNUM * y, BN_CTX * ctx) const 377 { 378 BN_CTX_start (ctx); 379 BIGNUM * y2 = BN_CTX_get (ctx), * xx = BN_CTX_get (ctx); 380 BN_sqr (y2, y, ctx); // y^2 381 // xx = (y^2 -1)*inv(d*y^2 +1) 382 BN_mul (xx, d, y2, ctx); 383 BN_add_word (xx, 1); 384 BN_mod_inverse (xx, xx, q, ctx); 385 BN_sub_word (y2, 1); 386 BN_mul (xx, y2, xx, ctx); 387 // x = srqt(xx) = xx^(2^252-2) 388 BIGNUM * x = BN_new (); 389 BN_mod_exp (x, xx, two_252_2, q, ctx); 390 // check (x^2 -xx) % q 391 BN_sqr (y2, x, ctx); 392 BN_mod_sub (y2, y2, xx, q, ctx); 393 if (!BN_is_zero (y2)) 394 BN_mod_mul (x, x, I, q, ctx); 395 if (BN_is_odd (x)) 396 BN_sub (x, q, x); 397 BN_CTX_end (ctx); 398 return x; 399 } 400 DecodePoint(const uint8_t * buf,BN_CTX * ctx) const401 EDDSAPoint Ed25519::DecodePoint (const uint8_t * buf, BN_CTX * ctx) const 402 { 403 // buf is 32 bytes Little Endian, convert it to Big Endian 404 uint8_t buf1[EDDSA25519_PUBLIC_KEY_LENGTH]; 405 for (size_t i = 0; i < EDDSA25519_PUBLIC_KEY_LENGTH/2; i++) // invert bytes 406 { 407 buf1[i] = buf[EDDSA25519_PUBLIC_KEY_LENGTH -1 - i]; 408 buf1[EDDSA25519_PUBLIC_KEY_LENGTH -1 - i] = buf[i]; 409 } 410 bool isHighestBitSet = buf1[0] & 0x80; 411 if (isHighestBitSet) 412 buf1[0] &= 0x7f; // clear highest bit 413 BIGNUM * y = BN_new (); 414 BN_bin2bn (buf1, EDDSA25519_PUBLIC_KEY_LENGTH, y); 415 BIGNUM * x = RecoverX (y, ctx); 416 if (BN_is_bit_set (x, 0) != isHighestBitSet) 417 BN_sub (x, q, x); // x = q - x 418 BIGNUM * z = BN_new (), * t = BN_new (); 419 BN_one (z); BN_mod_mul (t, x, y, q, ctx); // pre-calculate t 420 EDDSAPoint p {x, y, z, t}; 421 if (!IsOnCurve (p, ctx)) 422 LogPrint (eLogError, "Decoded point is not on 25519"); 423 return p; 424 } 425 EncodePoint(const EDDSAPoint & p,uint8_t * buf) const426 void Ed25519::EncodePoint (const EDDSAPoint& p, uint8_t * buf) const 427 { 428 EncodeBN (p.y, buf,EDDSA25519_PUBLIC_KEY_LENGTH); 429 if (BN_is_bit_set (p.x, 0)) // highest bit 430 buf[EDDSA25519_PUBLIC_KEY_LENGTH - 1] |= 0x80; // set highest bit 431 } 432 433 template<int len> DecodeBN(const uint8_t * buf) const434 BIGNUM * Ed25519::DecodeBN (const uint8_t * buf) const 435 { 436 // buf is Little Endian convert it to Big Endian 437 uint8_t buf1[len]; 438 for (size_t i = 0; i < len/2; i++) // invert bytes 439 { 440 buf1[i] = buf[len -1 - i]; 441 buf1[len -1 - i] = buf[i]; 442 } 443 BIGNUM * res = BN_new (); 444 BN_bin2bn (buf1, len, res); 445 return res; 446 } 447 EncodeBN(const BIGNUM * bn,uint8_t * buf,size_t len) const448 void Ed25519::EncodeBN (const BIGNUM * bn, uint8_t * buf, size_t len) const 449 { 450 bn2buf (bn, buf, len); 451 // To Little Endian 452 for (size_t i = 0; i < len/2; i++) // invert bytes 453 { 454 uint8_t tmp = buf[i]; 455 buf[i] = buf[len -1 - i]; 456 buf[len -1 - i] = tmp; 457 } 458 } 459 460 #if !OPENSSL_X25519 ScalarMul(const BIGNUM * u,const BIGNUM * k,BN_CTX * ctx) const461 BIGNUM * Ed25519::ScalarMul (const BIGNUM * u, const BIGNUM * k, BN_CTX * ctx) const 462 { 463 BN_CTX_start (ctx); 464 auto x1 = BN_CTX_get (ctx); BN_copy (x1, u); 465 auto x2 = BN_CTX_get (ctx); BN_one (x2); 466 auto z2 = BN_CTX_get (ctx); BN_zero (z2); 467 auto x3 = BN_CTX_get (ctx); BN_copy (x3, u); 468 auto z3 = BN_CTX_get (ctx); BN_one (z3); 469 auto c121666 = BN_CTX_get (ctx); BN_set_word (c121666, 121666); 470 auto tmp0 = BN_CTX_get (ctx); auto tmp1 = BN_CTX_get (ctx); 471 unsigned int swap = 0; 472 auto bits = BN_num_bits (k); 473 while(bits) 474 { 475 --bits; 476 auto k_t = BN_is_bit_set(k, bits) ? 1 : 0; 477 swap ^= k_t; 478 if (swap) 479 { 480 std::swap (x2, x3); 481 std::swap (z2, z3); 482 } 483 swap = k_t; 484 BN_mod_sub(tmp0, x3, z3, q, ctx); 485 BN_mod_sub(tmp1, x2, z2, q, ctx); 486 BN_mod_add(x2, x2, z2, q, ctx); 487 BN_mod_add(z2, x3, z3, q, ctx); 488 BN_mod_mul(z3, tmp0, x2, q, ctx); 489 BN_mod_mul(z2, z2, tmp1, q, ctx); 490 BN_mod_sqr(tmp0, tmp1, q, ctx); 491 BN_mod_sqr(tmp1, x2, q, ctx); 492 BN_mod_add(x3, z3, z2, q, ctx); 493 BN_mod_sub(z2, z3, z2, q, ctx); 494 BN_mod_mul(x2, tmp1, tmp0, q, ctx); 495 BN_mod_sub(tmp1, tmp1, tmp0, q, ctx); 496 BN_mod_sqr(z2, z2, q, ctx); 497 BN_mod_mul(z3, tmp1, c121666, q, ctx); 498 BN_mod_sqr(x3, x3, q, ctx); 499 BN_mod_add(tmp0, tmp0, z3, q, ctx); 500 BN_mod_mul(z3, x1, z2, q, ctx); 501 BN_mod_mul(z2, tmp1, tmp0, q, ctx); 502 } 503 if (swap) 504 { 505 std::swap (x2, x3); 506 std::swap (z2, z3); 507 } 508 BN_mod_inverse (z2, z2, q, ctx); 509 BIGNUM * res = BN_new (); // not from ctx 510 BN_mod_mul(res, x2, z2, q, ctx); 511 BN_CTX_end (ctx); 512 return res; 513 } 514 ScalarMul(const uint8_t * p,const uint8_t * e,uint8_t * buf,BN_CTX * ctx) const515 void Ed25519::ScalarMul (const uint8_t * p, const uint8_t * e, uint8_t * buf, BN_CTX * ctx) const 516 { 517 BIGNUM * p1 = DecodeBN<32> (p); 518 uint8_t k[32]; 519 memcpy (k, e, 32); 520 k[0] &= 248; k[31] &= 127; k[31] |= 64; 521 BIGNUM * n = DecodeBN<32> (k); 522 BIGNUM * q1 = ScalarMul (p1, n, ctx); 523 EncodeBN (q1, buf, 32); 524 BN_free (p1); BN_free (n); BN_free (q1); 525 } 526 ScalarMulB(const uint8_t * e,uint8_t * buf,BN_CTX * ctx) const527 void Ed25519::ScalarMulB (const uint8_t * e, uint8_t * buf, BN_CTX * ctx) const 528 { 529 BIGNUM *p1 = BN_new (); BN_set_word (p1, 9); 530 uint8_t k[32]; 531 memcpy (k, e, 32); 532 k[0] &= 248; k[31] &= 127; k[31] |= 64; 533 BIGNUM * n = DecodeBN<32> (k); 534 BIGNUM * q1 = ScalarMul (p1, n, ctx); 535 EncodeBN (q1, buf, 32); 536 BN_free (p1); BN_free (n); BN_free (q1); 537 } 538 #endif 539 BlindPublicKey(const uint8_t * pub,const uint8_t * seed,uint8_t * blinded)540 void Ed25519::BlindPublicKey (const uint8_t * pub, const uint8_t * seed, uint8_t * blinded) 541 { 542 BN_CTX * ctx = BN_CTX_new (); 543 // calculate alpha = seed mod l 544 BIGNUM * alpha = DecodeBN<64> (seed); // seed is in Little Endian 545 BN_mod (alpha, alpha, l, ctx); // % l 546 uint8_t priv[32]; 547 EncodeBN (alpha, priv, 32); // back to Little Endian 548 BN_free (alpha); 549 // A' = BLIND_PUBKEY(A, alpha) = A + DERIVE_PUBLIC(alpha) 550 auto A1 = Sum (DecodePublicKey (pub, ctx), MulB (priv, ctx), ctx); // pub + B*alpha 551 EncodePublicKey (A1, blinded, ctx); 552 BN_CTX_free (ctx); 553 } 554 BlindPrivateKey(const uint8_t * priv,const uint8_t * seed,uint8_t * blindedPriv,uint8_t * blindedPub)555 void Ed25519::BlindPrivateKey (const uint8_t * priv, const uint8_t * seed, uint8_t * blindedPriv, uint8_t * blindedPub) 556 { 557 BN_CTX * ctx = BN_CTX_new (); 558 // calculate alpha = seed mod l 559 BIGNUM * alpha = DecodeBN<64> (seed); // seed is in Little Endian 560 BN_mod (alpha, alpha, l, ctx); // % l 561 BIGNUM * p = DecodeBN<32> (priv); // priv is in Little Endian 562 BN_add (alpha, alpha, p); // alpha = alpha + priv 563 // a' = BLIND_PRIVKEY(a, alpha) = (a + alpha) mod L 564 BN_mod (alpha, alpha, l, ctx); // % l 565 EncodeBN (alpha, blindedPriv, 32); 566 // A' = DERIVE_PUBLIC(a') 567 auto A1 = MulB (blindedPriv, ctx); 568 EncodePublicKey (A1, blindedPub, ctx); 569 BN_free (alpha); BN_free (p); 570 BN_CTX_free (ctx); 571 } 572 ExpandPrivateKey(const uint8_t * key,uint8_t * expandedKey)573 void Ed25519::ExpandPrivateKey (const uint8_t * key, uint8_t * expandedKey) 574 { 575 SHA512 (key, EDDSA25519_PRIVATE_KEY_LENGTH, expandedKey); 576 expandedKey[0] &= 0xF8; // drop last 3 bits 577 expandedKey[EDDSA25519_PRIVATE_KEY_LENGTH - 1] &= 0x3F; // drop first 2 bits 578 expandedKey[EDDSA25519_PRIVATE_KEY_LENGTH - 1] |= 0x40; // set second bit 579 } 580 CreateRedDSAPrivateKey(uint8_t * priv)581 void Ed25519::CreateRedDSAPrivateKey (uint8_t * priv) 582 { 583 uint8_t seed[32]; 584 RAND_bytes (seed, 32); 585 BIGNUM * p = DecodeBN<32> (seed); 586 BN_CTX * ctx = BN_CTX_new (); 587 BN_mod (p, p, l, ctx); // % l 588 EncodeBN (p, priv, 32); 589 BN_CTX_free (ctx); 590 BN_free (p); 591 } 592 593 static std::unique_ptr<Ed25519> g_Ed25519; GetEd25519()594 std::unique_ptr<Ed25519>& GetEd25519 () 595 { 596 if (!g_Ed25519) 597 { 598 auto c = new Ed25519(); 599 if (!g_Ed25519) // make sure it was not created already 600 g_Ed25519.reset (c); 601 else 602 delete c; 603 } 604 return g_Ed25519; 605 } 606 } 607 } 608