1e71b7053SJung-uk Kim /*
25ac766abSJung-uk Kim * Copyright 1995-2022 The OpenSSL Project Authors. All Rights Reserved.
3ddd58736SKris Kennaway *
4b077aed3SPierre Pronchery * Licensed under the Apache License 2.0 (the "License"). You may not use
5e71b7053SJung-uk Kim * this file except in compliance with the License. You can obtain a copy
6e71b7053SJung-uk Kim * in the file LICENSE in the source distribution or at
7e71b7053SJung-uk Kim * https://www.openssl.org/source/license.html
8ddd58736SKris Kennaway */
9ddd58736SKris Kennaway
1074664626SKris Kennaway #include <stdio.h>
11e71b7053SJung-uk Kim #include "internal/cryptlib.h"
1217f01e99SJung-uk Kim #include "bn_local.h"
1374664626SKris Kennaway
14ddd58736SKris Kennaway #define TABLE_SIZE 32
1574664626SKris Kennaway
BN_mod_exp2_mont(BIGNUM * rr,const BIGNUM * a1,const BIGNUM * p1,const BIGNUM * a2,const BIGNUM * p2,const BIGNUM * m,BN_CTX * ctx,BN_MONT_CTX * in_mont)165c87c606SMark Murray int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,
175c87c606SMark Murray const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m,
185c87c606SMark Murray BN_CTX *ctx, BN_MONT_CTX *in_mont)
1974664626SKris Kennaway {
206f9291ceSJung-uk Kim int i, j, bits, b, bits1, bits2, ret =
216f9291ceSJung-uk Kim 0, wpos1, wpos2, window1, window2, wvalue1, wvalue2;
223b4e3dcbSSimon L. B. Nielsen int r_is_one = 1;
23ddd58736SKris Kennaway BIGNUM *d, *r;
245c87c606SMark Murray const BIGNUM *a_mod_m;
253b4e3dcbSSimon L. B. Nielsen /* Tables of variables obtained from 'ctx' */
263b4e3dcbSSimon L. B. Nielsen BIGNUM *val1[TABLE_SIZE], *val2[TABLE_SIZE];
2774664626SKris Kennaway BN_MONT_CTX *mont = NULL;
2874664626SKris Kennaway
2974664626SKris Kennaway bn_check_top(a1);
3074664626SKris Kennaway bn_check_top(p1);
3174664626SKris Kennaway bn_check_top(a2);
3274664626SKris Kennaway bn_check_top(p2);
3374664626SKris Kennaway bn_check_top(m);
3474664626SKris Kennaway
355ac766abSJung-uk Kim if (!BN_is_odd(m)) {
36b077aed3SPierre Pronchery ERR_raise(ERR_LIB_BN, BN_R_CALLED_WITH_EVEN_MODULUS);
37e71b7053SJung-uk Kim return 0;
3874664626SKris Kennaway }
3974664626SKris Kennaway bits1 = BN_num_bits(p1);
4074664626SKris Kennaway bits2 = BN_num_bits(p2);
416f9291ceSJung-uk Kim if ((bits1 == 0) && (bits2 == 0)) {
425c87c606SMark Murray ret = BN_one(rr);
435c87c606SMark Murray return ret;
4474664626SKris Kennaway }
455c87c606SMark Murray
46ddd58736SKris Kennaway bits = (bits1 > bits2) ? bits1 : bits2;
47f579bf8eSKris Kennaway
48f579bf8eSKris Kennaway BN_CTX_start(ctx);
49f579bf8eSKris Kennaway d = BN_CTX_get(ctx);
50f579bf8eSKris Kennaway r = BN_CTX_get(ctx);
513b4e3dcbSSimon L. B. Nielsen val1[0] = BN_CTX_get(ctx);
523b4e3dcbSSimon L. B. Nielsen val2[0] = BN_CTX_get(ctx);
53e71b7053SJung-uk Kim if (val2[0] == NULL)
546f9291ceSJung-uk Kim goto err;
55f579bf8eSKris Kennaway
5674664626SKris Kennaway if (in_mont != NULL)
5774664626SKris Kennaway mont = in_mont;
586f9291ceSJung-uk Kim else {
596f9291ceSJung-uk Kim if ((mont = BN_MONT_CTX_new()) == NULL)
606f9291ceSJung-uk Kim goto err;
616f9291ceSJung-uk Kim if (!BN_MONT_CTX_set(mont, m, ctx))
626f9291ceSJung-uk Kim goto err;
6374664626SKris Kennaway }
6474664626SKris Kennaway
65ddd58736SKris Kennaway window1 = BN_window_bits_for_exponent_size(bits1);
66ddd58736SKris Kennaway window2 = BN_window_bits_for_exponent_size(bits2);
67ddd58736SKris Kennaway
68ddd58736SKris Kennaway /*
69ddd58736SKris Kennaway * Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 2^(window1-1)
70ddd58736SKris Kennaway */
716f9291ceSJung-uk Kim if (a1->neg || BN_ucmp(a1, m) >= 0) {
723b4e3dcbSSimon L. B. Nielsen if (!BN_mod(val1[0], a1, m, ctx))
73ddd58736SKris Kennaway goto err;
743b4e3dcbSSimon L. B. Nielsen a_mod_m = val1[0];
756f9291ceSJung-uk Kim } else
76ddd58736SKris Kennaway a_mod_m = a1;
776f9291ceSJung-uk Kim if (BN_is_zero(a_mod_m)) {
783b4e3dcbSSimon L. B. Nielsen BN_zero(rr);
793b4e3dcbSSimon L. B. Nielsen ret = 1;
805c87c606SMark Murray goto err;
815c87c606SMark Murray }
825c87c606SMark Murray
836f9291ceSJung-uk Kim if (!BN_to_montgomery(val1[0], a_mod_m, mont, ctx))
846f9291ceSJung-uk Kim goto err;
856f9291ceSJung-uk Kim if (window1 > 1) {
866f9291ceSJung-uk Kim if (!BN_mod_mul_montgomery(d, val1[0], val1[0], mont, ctx))
876f9291ceSJung-uk Kim goto err;
88ddd58736SKris Kennaway
89ddd58736SKris Kennaway j = 1 << (window1 - 1);
906f9291ceSJung-uk Kim for (i = 1; i < j; i++) {
913b4e3dcbSSimon L. B. Nielsen if (((val1[i] = BN_CTX_get(ctx)) == NULL) ||
926f9291ceSJung-uk Kim !BN_mod_mul_montgomery(val1[i], val1[i - 1], d, mont, ctx))
93ddd58736SKris Kennaway goto err;
94ddd58736SKris Kennaway }
95ddd58736SKris Kennaway }
96ddd58736SKris Kennaway
97ddd58736SKris Kennaway /*
98ddd58736SKris Kennaway * Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 2^(window2-1)
99ddd58736SKris Kennaway */
1006f9291ceSJung-uk Kim if (a2->neg || BN_ucmp(a2, m) >= 0) {
1013b4e3dcbSSimon L. B. Nielsen if (!BN_mod(val2[0], a2, m, ctx))
102ddd58736SKris Kennaway goto err;
1033b4e3dcbSSimon L. B. Nielsen a_mod_m = val2[0];
1046f9291ceSJung-uk Kim } else
105ddd58736SKris Kennaway a_mod_m = a2;
1066f9291ceSJung-uk Kim if (BN_is_zero(a_mod_m)) {
1073b4e3dcbSSimon L. B. Nielsen BN_zero(rr);
1083b4e3dcbSSimon L. B. Nielsen ret = 1;
1095c87c606SMark Murray goto err;
1105c87c606SMark Murray }
1116f9291ceSJung-uk Kim if (!BN_to_montgomery(val2[0], a_mod_m, mont, ctx))
1126f9291ceSJung-uk Kim goto err;
1136f9291ceSJung-uk Kim if (window2 > 1) {
1146f9291ceSJung-uk Kim if (!BN_mod_mul_montgomery(d, val2[0], val2[0], mont, ctx))
1156f9291ceSJung-uk Kim goto err;
11674664626SKris Kennaway
117ddd58736SKris Kennaway j = 1 << (window2 - 1);
1186f9291ceSJung-uk Kim for (i = 1; i < j; i++) {
1193b4e3dcbSSimon L. B. Nielsen if (((val2[i] = BN_CTX_get(ctx)) == NULL) ||
1206f9291ceSJung-uk Kim !BN_mod_mul_montgomery(val2[i], val2[i - 1], d, mont, ctx))
12174664626SKris Kennaway goto err;
12274664626SKris Kennaway }
12374664626SKris Kennaway }
12474664626SKris Kennaway
125ddd58736SKris Kennaway /* Now compute the power product, using independent windows. */
126ddd58736SKris Kennaway r_is_one = 1;
127ddd58736SKris Kennaway wvalue1 = 0; /* The 'value' of the first window */
128ddd58736SKris Kennaway wvalue2 = 0; /* The 'value' of the second window */
1296f9291ceSJung-uk Kim wpos1 = 0; /* If wvalue1 > 0, the bottom bit of the
1306f9291ceSJung-uk Kim * first window */
1316f9291ceSJung-uk Kim wpos2 = 0; /* If wvalue2 > 0, the bottom bit of the
1326f9291ceSJung-uk Kim * second window */
13374664626SKris Kennaway
1346f9291ceSJung-uk Kim if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
1356f9291ceSJung-uk Kim goto err;
1366f9291ceSJung-uk Kim for (b = bits - 1; b >= 0; b--) {
1376f9291ceSJung-uk Kim if (!r_is_one) {
13874664626SKris Kennaway if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
13974664626SKris Kennaway goto err;
14074664626SKris Kennaway }
14174664626SKris Kennaway
142ddd58736SKris Kennaway if (!wvalue1)
1436f9291ceSJung-uk Kim if (BN_is_bit_set(p1, b)) {
1446f9291ceSJung-uk Kim /*
1456f9291ceSJung-uk Kim * consider bits b-window1+1 .. b for this window
1466f9291ceSJung-uk Kim */
147ddd58736SKris Kennaway i = b - window1 + 1;
148ddd58736SKris Kennaway while (!BN_is_bit_set(p1, i)) /* works for i<0 */
149ddd58736SKris Kennaway i++;
150ddd58736SKris Kennaway wpos1 = i;
151ddd58736SKris Kennaway wvalue1 = 1;
1526f9291ceSJung-uk Kim for (i = b - 1; i >= wpos1; i--) {
153ddd58736SKris Kennaway wvalue1 <<= 1;
154ddd58736SKris Kennaway if (BN_is_bit_set(p1, i))
155ddd58736SKris Kennaway wvalue1++;
156ddd58736SKris Kennaway }
15774664626SKris Kennaway }
15874664626SKris Kennaway
159ddd58736SKris Kennaway if (!wvalue2)
1606f9291ceSJung-uk Kim if (BN_is_bit_set(p2, b)) {
1616f9291ceSJung-uk Kim /*
1626f9291ceSJung-uk Kim * consider bits b-window2+1 .. b for this window
1636f9291ceSJung-uk Kim */
164ddd58736SKris Kennaway i = b - window2 + 1;
165ddd58736SKris Kennaway while (!BN_is_bit_set(p2, i))
166ddd58736SKris Kennaway i++;
167ddd58736SKris Kennaway wpos2 = i;
168ddd58736SKris Kennaway wvalue2 = 1;
1696f9291ceSJung-uk Kim for (i = b - 1; i >= wpos2; i--) {
170ddd58736SKris Kennaway wvalue2 <<= 1;
171ddd58736SKris Kennaway if (BN_is_bit_set(p2, i))
172ddd58736SKris Kennaway wvalue2++;
173ddd58736SKris Kennaway }
174ddd58736SKris Kennaway }
175ddd58736SKris Kennaway
1766f9291ceSJung-uk Kim if (wvalue1 && b == wpos1) {
177ddd58736SKris Kennaway /* wvalue1 is odd and < 2^window1 */
1783b4e3dcbSSimon L. B. Nielsen if (!BN_mod_mul_montgomery(r, r, val1[wvalue1 >> 1], mont, ctx))
179ddd58736SKris Kennaway goto err;
180ddd58736SKris Kennaway wvalue1 = 0;
181ddd58736SKris Kennaway r_is_one = 0;
182ddd58736SKris Kennaway }
183ddd58736SKris Kennaway
1846f9291ceSJung-uk Kim if (wvalue2 && b == wpos2) {
185ddd58736SKris Kennaway /* wvalue2 is odd and < 2^window2 */
1863b4e3dcbSSimon L. B. Nielsen if (!BN_mod_mul_montgomery(r, r, val2[wvalue2 >> 1], mont, ctx))
187ddd58736SKris Kennaway goto err;
188ddd58736SKris Kennaway wvalue2 = 0;
189ddd58736SKris Kennaway r_is_one = 0;
190ddd58736SKris Kennaway }
19174664626SKris Kennaway }
192a3ddd25aSSimon L. B. Nielsen if (!BN_from_montgomery(rr, r, mont, ctx))
193a3ddd25aSSimon L. B. Nielsen goto err;
19474664626SKris Kennaway ret = 1;
19574664626SKris Kennaway err:
196e71b7053SJung-uk Kim if (in_mont == NULL)
1976f9291ceSJung-uk Kim BN_MONT_CTX_free(mont);
198f579bf8eSKris Kennaway BN_CTX_end(ctx);
1993b4e3dcbSSimon L. B. Nielsen bn_check_top(rr);
200e71b7053SJung-uk Kim return ret;
20174664626SKris Kennaway }
202