1
2 /* Calculates nQ where Q is the x-coordinate of a point on the curve
3 *
4 * mypublic: the packed little endian x coordinate of the resulting curve point
5 * n: a little endian, 32-byte number
6 * basepoint: a packed little endian point of the curve
7 */
8 static void
curve25519_scalarmult_donna(curve25519_key mypublic,const curve25519_key n,const curve25519_key basepoint)9 curve25519_scalarmult_donna(curve25519_key mypublic, const curve25519_key n, const curve25519_key basepoint) {
10 bignum25519 ALIGN(16) nqx = {1}, nqpqz = {1}, nqz = {0}, nqpqx, zmone;
11 packed32bignum25519 qx, qz, pqz, pqx;
12 packed64bignum25519 nq, sq, sqscalar, prime, primex, primez, nqpq;
13 bignum25519mulprecomp preq;
14 uint32_t bit, lastbit, i;
15
16 curve25519_expand(nqpqx, basepoint);
17 curve25519_mul_precompute(&preq, nqpqx);
18
19 /* do bits 254..3 */
20 for (i = 254, lastbit = 0; i >= 3; i--) {
21 bit = (n[i/8] >> (i & 7)) & 1;
22 curve25519_swap_conditional(nqx, nqpqx, bit ^ lastbit);
23 curve25519_swap_conditional(nqz, nqpqz, bit ^ lastbit);
24 lastbit = bit;
25
26 curve25519_tangle32(qx, nqx, nqpqx); /* qx = [nqx,nqpqx] */
27 curve25519_tangle32(qz, nqz, nqpqz); /* qz = [nqz,nqpqz] */
28
29 curve25519_add_packed32(pqx, qx, qz); /* pqx = [nqx+nqz,nqpqx+nqpqz] */
30 curve25519_sub_packed32(pqz, qx, qz); /* pqz = [nqx-nqz,nqpqx-nqpqz] */
31
32 curve25519_make_nqpq(primex, primez, pqx, pqz); /* primex = [nqx+nqz,nqpqx+nqpqz], primez = [nqpqx-nqpqz,nqx-nqz] */
33 curve25519_mul_packed64(prime, primex, primez); /* prime = [nqx+nqz,nqpqx+nqpqz] * [nqpqx-nqpqz,nqx-nqz] */
34 curve25519_addsub_packed64(prime); /* prime = [prime.x+prime.z,prime.x-prime.z] */
35 curve25519_square_packed64(nqpq, prime); /* nqpq = prime^2 */
36 curve25519_untangle64(nqpqx, nqpqz, nqpq);
37 curve25519_mul_precomputed(nqpqz, nqpqz, &preq); /* nqpqz = nqpqz * q */
38
39 /* (((sq.x-sq.z)*121665)+sq.x) * (sq.x-sq.z) is equivalent to (sq.x*121666-sq.z*121665) * (sq.x-sq.z) */
40 curve25519_make_nq(nq, pqx, pqz); /* nq = [nqx+nqz,nqx-nqz] */
41 curve25519_square_packed64(sq, nq); /* sq = nq^2 */
42 curve25519_121665_packed64(sqscalar, sq); /* sqscalar = sq * [121666,121665] */
43 curve25519_final_nq(nq, sq, sqscalar); /* nq = [sq.x,sqscalar.x-sqscalar.z] * [sq.z,sq.x-sq.z] */
44 curve25519_untangle64(nqx, nqz, nq);
45 };
46
47 /* it's possible to get rid of this swap with the swap in the above loop
48 at the bottom instead of the top, but compilers seem to optimize better this way */
49 curve25519_swap_conditional(nqx, nqpqx, bit);
50 curve25519_swap_conditional(nqz, nqpqz, bit);
51
52 /* do bits 2..0 */
53 for (i = 0; i < 3; i++) {
54 curve25519_compute_nq(nq, nqx, nqz);
55 curve25519_square_packed64(sq, nq); /* sq = nq^2 */
56 curve25519_121665_packed64(sqscalar, sq); /* sqscalar = sq * [121666,121665] */
57 curve25519_final_nq(nq, sq, sqscalar); /* nq = [sq.x,sqscalar.x-sqscalar.z] * [sq.z,sq.x-sq.z] */
58 curve25519_untangle64(nqx, nqz, nq);
59 }
60
61 curve25519_recip(zmone, nqz);
62 curve25519_mul(nqz, nqx, zmone);
63 curve25519_contract(mypublic, nqz);
64 }
65
66