[otbn] unify montmul routines in modexp
This unfiies the three Montgomery multiplication
subroutine montmul_sqr, montmul_exp and montmul
in a single one.
This is related to #3776.
Signed-off-by: Felix Miller <felix.miller@gi-de.com>
diff --git a/sw/otbn/code-snippets/modexp.s b/sw/otbn/code-snippets/modexp.s
index 7e66f88..b33cf0b 100644
--- a/sw/otbn/code-snippets/modexp.s
+++ b/sw/otbn/code-snippets/modexp.s
@@ -561,76 +561,6 @@
/**
- * Constant-time Montgomery Modular Multiplication
- *
- * Returns: C = montmul(A,B) = A*B*R^(-1) mod M
- *
- * This implements the limb-by-limb interleadved Montgomory Modular
- * Multiplication Algorithm. This is only a wrapper around the main loop body.
- * For algorithmic implementation details see the mont_loop subroutine.
- *
- * Flags: The states of both FG0 and FG1 depend on intermediate values and are
- * not usable after return.
- *
- * @param[in] x16 dptr_M: dmem pointer to first limb of modulus M
- * @param[in] x17 dptr_m0d: dmem pointer to Montgomery Constant m0'
- * @param[in] x19 dptr_a: dmem pointer to first limb of operand A
- * @param[in] x20 dptr_b: dmem pointer to first limb of operand B
- * @param[in] x21 dptr_c: dmem pointer to first limb of result C
- * @param[in] w31 all-zero
- * @param[in] x30 N: number of limbs
- * @param[in] x31 N-1: number of limbs minus one
- * @param[in] x9: pointer to temp reg, must be set to 3
- * @param[in] x10: pointer to temp reg, must be set to 4
- * @param[in] x11: pointer to temp reg, must be set to 2
- * @param[out] [dmem[dptr_c+N*32-1]:dmem[dptr_c]]: result C
- *
- * clobbered registers: x3, x4, x5, x6, x8 to x13, x16 to x31
- * w1 to w3, w24 to w30
- * w4 to w[4+N-1]
- * clobbered Flag Groups: FG0, FG1
- */
-montmul:
- /* load Montgomery constant: w3 = dmem[x17] = dmem[dptr_m0d] = m0'*/
- bn.lid x9, 0(x17)
-
- /* init regfile bigint buffer with zeros */
- bn.mov w2, w31
- loop x30, 1
- bn.movr x10++, x11
-
- /* iterate over limbs of operand B */
- loop x30, 8
-
- /* load limb of operand b */
- bn.lid x11, 0(x20++)
-
- /* save some regs */
- add x4, x16, x0
- add x5, x19, x0
- add x6, x20, x0
-
- /* Main loop body of Montgomory Multiplication algorithm */
- jal x1, mont_loop
-
- /* restore regs */
- add x16, x4, x0
- add x19, x5, x0
- add x20, x6, x0
-
- /* Store result in dmem starting at dmem[dptr_c] */
- loop x30, 2
- bn.sid x8, 0(x21++)
- addi x8, x8, 1
-
- /* restore pointer */
- li x8, 4
- li x10, 4
-
- ret
-
-
-/**
* Constant time conditional bigint subtraction
*
* Returns C = A-x*B
@@ -790,82 +720,6 @@
* Multiplication Algorithm. This is only a wrapper around the main loop body.
* For algorithmic implementation details see the mont_loop subroutine.
*
- * This variant loads the 3rd descriptor (dmem cell 2) and stores the result
- * in dmem. It is intended to be used as squaring primitive in a
- * square and multiply implementation.
- *
- * Flags: The states of both FG0 and FG1 depend on intermediate values and are
- * not usable after return.
- *
- * @param[in] x16 dptr_M: dmem pointer to first limb of modulus M
- * @param[in] x17 dptr_m0d: dmem pointer to Montgomery Constant m0'
- * @param[in] x19 dptr_a: dmem pointer to first limb of operand A
- * @param[in] x20 dptr_b: dmem pointer to first limb of operand B
- * @param[in] x21 dptr_c: dmem pointer to first limb of result C
- * @param[in] w31 all-zero
- * @param[in] x30 N: number of limbs
- * @param[in] x31 N-1: number of limbs minus one
- * @param[in] x9: pointer to temp reg, must be set to 3
- * @param[in] x10: pointer to temp reg, must be set to 4
- * @param[in] x11: pointer to temp reg, must be set to 2
- *
- * clobbered registers: x5, x6, x7, x8, x10, x12, x13, x16, x17, x19, x20, x21
- * w2, w3, w24 to w30, w4 to w[4+N-1]
- * clobbered Flag Groups: FG0, FG1
- */
-montmul_sqr:
- /* load Montgomery constant: w3 = dmem[x17] = dmem[dptr_m0d] = m0' */
- bn.lid x9, 0(x17)
-
- /* init regfile bigint buffer with zeros */
- bn.mov w2, w31
- loop x30, 1
- bn.movr x10++, x11
-
- /* iterate over limbs of operand B */
- loop x30, 8
-
- /* load limb of operand b */
- bn.lid x11, 0(x20++)
-
- /* save some regs */
- addi x5, x20, 0
- addi x6, x16, 0
- addi x7, x19, 0
-
- /* Main loop body of Montgomory Multiplication algorithm */
- jal x1, mont_loop
-
- /* restore regs */
- addi x20, x5, 0
- addi x16, x6, 0
- addi x19, x7, 0
-
- /* Store result in dmem starting at dmem[dptr_c] */
- loop x30, 2
- bn.sid x8, 0(x21++)
- addi x8, x8, 1
-
- /* restore pointers */
- li x8, 4
- li x10, 4
-
- ret
-
-
-/**
- * Constant-time Montgomery Modular Multiplication
- *
- * Returns: C = montmul(A,B) = A*B*R^(-1) mod M
- *
- * This implements the limb-by-limb interleadved Montgomory Modular
- * Multiplication Algorithm. This is only a wrapper around the main loop body.
- * For algorithmic implementation details see the mont_loop subroutine.
- *
- * This variant loads the 2nd descriptor (dmem cell 1) and stores the result
- * in the regfile. It is intended to be used as multiplication primitive in a
- * square and multiply implementation.
- *
* Flags: The states of both FG0 and FG1 depend on intermediate values and are
* not usable after return.
*
@@ -885,7 +739,7 @@
* w2, w3, w24 to w30, w4 to w[4+N-1]
* clobbered Flag Groups: FG0, FG1
*/
-montmul_mul:
+montmul:
/* load Montgomery constant: w3 = dmem[x17] = dmem[dptr_m0d] = m0' */
bn.lid x9, 0(x17)
@@ -969,8 +823,8 @@
* This implements the square and multiply algorithm, i.e. for each bit of the
* exponent both the squared only and the squared with multiply results are
* computed but one result is discarded.
- * Computation is carried out in the Montgomery domain, by using the primitives
- * montmul, montmul_sqr, montmul_mul and montmul_mul1.
+ * Computation is carried out in the Montgomery domain, by using the montmul
+ * primitive.
* The squared Montgomery modulus RR and the Montgomery constant m0' have to
* be precomputed and provided at the appropriate locations in dmem.
*
@@ -1019,6 +873,10 @@
lw x20, 12(x0)
lw x21, 20(x0)
jal x1, montmul
+ /* Store result in dmem starting at dmem[dptr_c] */
+ loop x30, 2
+ bn.sid x8, 0(x21++)
+ addi x8, x8, 1
/* zeroize w2 and reset flags */
bn.sub w2, w2, w2
@@ -1043,18 +901,22 @@
slli x24, x30, 8
/* iterate over all bits of bigint */
- loop x24, 17
+ loop x24, 20
/* square: out = montmul(out,out) */
lw x19, 28(x0)
lw x20, 28(x0)
lw x21, 28(x0)
- jal x1, montmul_sqr
+ jal x1, montmul
+ /* Store result in dmem starting at dmem[dptr_c] */
+ loop x30, 2
+ bn.sid x8, 0(x21++)
+ addi x8, x8, 1
/* multiply: out = montmul(in,out) */
lw x19, 20(x0)
lw x20, 28(x0)
lw x21, 28(x0)
- jal x1, montmul_mul
+ jal x1, montmul
/* w2 <= w2 << 1 */
bn.add w2, w2, w2
@@ -1139,6 +1001,10 @@
lw x20, 12(x0)
lw x21, 20(x0)
jal x1, montmul
+ /* Store result in dmem starting at dmem[dptr_c] */
+ loop x30, 2
+ bn.sid x8, 0(x21++)
+ addi x8, x8, 1
/* pointer to out buffer */
lw x21, 28(x0)
@@ -1166,13 +1032,17 @@
lw x19, 28(x0)
lw x20, 28(x0)
lw x21, 28(x0)
- jal x1, montmul_sqr
+ jal x1, montmul
+ /* Store result in dmem starting at dmem[dptr_c] */
+ loop x30, 2
+ bn.sid x8, 0(x21++)
+ addi x8, x8, 1
/* out = montmul(in,out) */
lw x19, 20(x0)
lw x20, 28(x0)
lw x20, 28(x0)
- jal x1, montmul_mul
+ jal x1, montmul
/* store multiplication result in output buffer */
lw x21, 28(x0)
@@ -1184,13 +1054,16 @@
/* 65537 = 0b10000000000000001
^<< 16 x sqr >>^ */
- loopi 16, 5
+ loopi 16, 7
/* square: out = montmul(out, out) */
lw x19, 28(x0)
lw x20, 28(x0)
lw x21, 28(x0)
- jal x1, montmul_sqr
- nop
+ jal x1, montmul
+ /* Store result in dmem starting at dmem[dptr_c] */
+ loop x30, 2
+ bn.sid x8, 0(x21++)
+ addi x8, x8, 1
/* 65537 = 0b10000000000000001
mult ^
@@ -1198,7 +1071,7 @@
lw x19, 20(x0)
lw x20, 28(x0)
lw x21, 28(x0)
- jal x1, montmul_mul
+ jal x1, montmul
/* store multiplication result in output buffer */
lw x21, 28(x0)
