Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

closed as unclear what you're asking by Ilmari Karonen, poncho, yyyyyyy, DrLecter, K.G. Mar 16 at 10:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

1  
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. –  Robert NACIRI Mar 12 at 15:34
    
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. –  Ilmari Karonen Mar 12 at 20:06
1  
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? –  poncho Mar 15 at 21:57
    
Yes, you are right. The API enables the user to perform modular additions, multiplications and reductions. –  maral Mar 17 at 9:10

Browse other questions tagged or ask your own question.