To prevent various forms of timing side-channel attacks, it's strongly advisable to implementing public-key cryptography in constant time. Or at least, without secret-dependent timing variations. However, as far as I'm aware, such implementations rely on a constant-cycle hardware multiplier. Sometimes it's also possible to replace some multiplications with shifts and adds, still, a constant-time implementation requires a barrel shifter.
Hypothetically, if I want to implement public-key cryptography (either elliptic curve or discrete log) on the cheapest microcontrollers without either a hardware multiplier or barrel shifter, what are my options for a constant-time multiplication algorithm in pure software? Constant-time multiplication in pure software sounds like a basic enough problem and many researchers must already have investigated it, but I don't know where to look. What algorithms are available, and how do they perform comparing to their non-constant time counterpart? 10x slower? 100x slower?
An obvious solution I can imagine is using a 16-bit lookup table for 8x8 multiplication, then pretending that we have a 8-bit multiplier and proceeding from here. On an embedded system without cache, on ROM, there will be no timing variation. But are there any alternative approaches (or a variation of the LUT approach that performs better in time/space)?
To clarify my motivation, I know this is impractical in real applications (even if one is stubborn enough to do it, a crypto coprocessor would be the solution), I ask it mostly due to theoretical interests.