Here's a second pass, 348 bytes, runs in 280811106 cycles for 2048 bit and exp of 0x10001:
Code: #ifndef POWMOD_H
#define POWMOD_H
#include <stdint.h>
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
/// Computes \c{base = base ** exp % mod}.
/// \p base and \p mod may not overlap.
/// Leaks size and exp but not the contents of exp or mod via timing,
/// with the assumption that \p base and \c sp point to normal ram.
/// @param size size in bytes of \p base and \p mod, 0 means 2**8, must not be 1
/// @param base the base stored MSB first, must be less than \p mod
/// the result is also written here MSB first
/// @param exp the exponent, must be non-zero
/// @param mod the modulus stored MSB first, must be odd
void powmod(uint8_t size, uint8_t *restrict base, uint24_t exp, const uint8_t *restrict mod);
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /* POWMOD_H */
Code: public _powmod
_powmod:
push ix
ld ix, 0
lea bc, ix
add ix, sp
.ret := ix + long
.size := .ret + long
.base := .size + long
.exp := .base + long
.mod := .exp + long
.acc := ix - long
.tmp := .acc - long
.end := .tmp - byte
ld c, (.size)
dec c
ld hl, .end - ix
add hl, sp
push hl
; scf
sbc hl, bc
push hl
; or a, a
sbc hl, bc
ld sp, hl
ld hl, (.mod)
add hl, bc
ld (.mod), hl
ld b, bsr 8
ld e, b
; ld e, 1
.nmi.loop:
ld a, e
ld d, (hl)
mlt de
inc de
inc de
ld d, a
mlt de
djnz .nmi.loop ; leaks size
ld a, e
ld (.nmi), a
ld hl, (.base)
add hl, bc
ld (.base), hl
ld c, 8
.mod.outer:
ld b, (.size)
.mod.inner:
push bc, hl
ld b, (.size)
; or a, a
.shift:
rl (hl)
dec hl
djnz .shift ; leaks size
pop hl
push hl
call .reduce
pop hl, bc
djnz .mod.inner ; leaks size
dec c
jq nz, .mod.outer ; leaks constant
ld c, (.size)
dec c
inc bc
ld de, (.acc)
lddr ; leaks size
ld hl, (.exp)
scf
.normalize:
adc hl, hl
jq nc, .normalize ; leaks exp
xor a, a
.loop:
push hl, af
ld hl, (.acc)
call nz, .mul ; leaks exp
pop af
ld hl, (.base)
call c, .mul ; leaks exp
pop hl
; or a, a
adc hl, hl
jq nz, .loop ; leaks exp
ld de, (.tmp)
add hl, de
dec de
; ld bc, 0
ld c, (.size)
dec c
ld (hl), b
push hl
lddr ; leaks size
pop hl
inc (hl)
ld iy, (.base)
call .mul.alt
ld sp, ix
pop ix
ret
; vi(acc) = vi(acc) * vi(hl) % vi(mod)
; assumes bc = 0
; destroys vi(tmp)
; returns bc = 0, cf = 0
.mul:
ld iy, (.tmp)
.mul.alt:
push hl
lea hl, iy - 0
lea de, iy - 1
ld c, (.size)
dec c
ld (hl), b
lddr ; leaks size
ld de, (.acc)
ld (.acc), iy
ld (.tmp), de
pop hl
ld c, (.size)
or a, a
.mul.outer:
ld a, (de)
ld (.cur), a
dec de
push de, hl, ix, iy, af
ld e, (hl)
ld d, a
mlt de
push hl
ld l, (iy)
ld h, 0
add hl, de
ld e, l
ld d, 0
.nmi := $ - byte
mlt de
ld a, e
ld (.adj), a
ld b, (.size)
dec b
ld ix, (.mod)
ld d, (ix)
mlt de
add.s hl, de
ld e, h
ld d, l
; ld d, 0
rl d
pop hl
.mul.inner:
dec hl
push hl
ld l, (hl)
ld h, 0
.cur := $ - byte
mlt hl
adc hl, de
dec ix
ld e, (ix)
ld d, 0
.adj := $ - byte
mlt de
add.s hl, de
ld e, h
ld d, 0
rl d
ld a, l
dec iy
add a, (iy)
ld (iy + 1), a
pop hl
djnz .mul.inner ; leaks size
ld l, b
rl l
ld h, b
pop af
adc hl, de
ld (iy + 0), l
sra h
pop iy, ix, hl, de
dec c
jq nz, .mul.outer ; leaks size
lea hl, iy
; if (cf:vi(hl) >= vi(mod)) cf:vi(hl) -= vi(mod)
; assumes bcu = 0
; destroys vi(tmp)
; returns bc = 0, cf = 0
.reduce:
ccf
sbc a, a
ld c, a
ld b, (.size)
ld de, (.tmp)
ld iy, (.mod)
or a, a
push hl, de
.reduce.sub:
ld a, (hl)
dec hl
sbc a, (iy)
dec iy
ld (de), a
dec de
djnz .reduce.sub ; leaks size
sbc a, a
and a, c
and a, long
sbc hl, hl
ld l, a
add hl, sp
ld hl, (hl)
pop de, de
ld c, (.size)
dec c
inc bc
lddr ; leaks size, assuming that base and stack are in normal ram
ret
