I'm implementing a public key cryptosystem in a proprietary System On Chip that only allows modular reductions by $n$.

However, that cryptosystem requires ($n^2$) modular reductions. Perhaps someone knows a strategy for performing those reductions relying on a modular reducer by $n$? The Montgomery reduction requires a value $R > n$ that makes ill-suited my approach.

I can perform any modular arithmetic operation mod $n$ but nothing $n^2$.

  • 1
    $\begingroup$ What is your operative environment(8, 16, 32 ... bits) and the available tools. Are you coding in native assembler languager, some libraries are available otherwise if you program in Assembly, you need at least Multiply and other arithmetic operators. $\endgroup$ – Robert NACIRI Mar 12 '15 at 15:34
  • $\begingroup$ Reduce modulo $n$, subtract remainder from input, divide by $n$, reduce again? You now effectively have the last two base-$n$ digits of the input. $\endgroup$ – Ilmari Karonen Mar 12 '15 at 20:06
  • 1
    $\begingroup$ Are you attempting to implement Paillier? I assume that you need to implement (say) a 2048 bit $n$, and the chip is unable to perform modular reductions on 4096 bit numbers, correct? $\endgroup$ – poncho Mar 15 '15 at 21:57
  • $\begingroup$ Yes, you are right. The API enables the user to perform modular additions, multiplications and reductions. $\endgroup$ – maral Mar 17 '15 at 9:10