2
$\begingroup$

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$.

$\endgroup$
4
  • 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$ Mar 12, 2015 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$ Mar 12, 2015 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, 2015 at 21:57
  • $\begingroup$ Yes, you are right. The API enables the user to perform modular additions, multiplications and reductions. $\endgroup$
    – maral
    Mar 17, 2015 at 9:10

0

Browse other questions tagged or ask your own question.