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 have to implement a 256*256 bit Montgomery multiplier for pairing computations. The straightforward approach is to use a bit-serial version, but I would like to utilize the built-in 64*64 bits multipliers on soft cores of modern FPGA devices, therefore I need a blockwise implementation (64 bits each). Two choices for implementation are:

  1. Get a 512-bit product and then apply Montgomery reduction.
  2. Reduce the intermediate products (128 bits) in each step using Montgomery reduction.

Which strategy is faster? If intermediate results are reduced in each step, then what should be the value of $R$: is it $2^{256}$ or $2^{64}$?

share|improve this question
    
This question is about implementation of Montgomery multiplier, which is commonly a component used for implementation of asymmetric cryptography. However, such components do not usually belong to this site. I propose migrating question to appropriate generic programming discussion, such as stackoverflow.com. –  user4982 Oct 14 '13 at 15:15
5  
@user4982 This is an algorithm question rather than a coding question. While not about cryptography specifically, it is about a subject (bignums) for which cryptography is one of the main use cases. Therefore I think the question is fine here. –  Gilles Oct 14 '13 at 17:53
add comment

1 Answer

As I said above, I feel the question is bit off-topic here. However, there does not seem to be too good a place in SE for questions that combine mathematics and programming on VHDL, where target is obviously something cryptography related. Most questions regarding FPGA are seen in electronics.stackexchange.com.

Montgomery reduction in Wikipedia is useful description of Montgomery reduction. The value of R you usually use is the same than word size used in processing. In your case, it could be $2^{256}$ or $2^{64}$ depending on how you implement the montgomery multiplier. If you have multiple $64*64$ bit multiplier units, you may want to use them in parallel, to perform large multiplications and/or montgomery reductions at once.

Assuming you had two multipliers available, one way around this would be using one multiplier for 64*64 multiply and another for montgomery reduction of previous 64*64 multiply, and thus R would be $2^{64}$. Then you would need to build 256*256 from e.g. 16 executions of 64*64 multiply. But, the algorithm, approach and processing pattern somewhat depends on how many multiplier you have available. Notice that you do not need to use rectangular size: you may build 128*64 montgomery step (from e.g. 4 multipliers) and you can use it to build 256*256.

The speed of different implementation decisions in the end depend on your target platform. Likely you need to design and implement appropriate benchmarks yourself.

Coming back to the original question. Overall, it is often most efficient to work locally i.e. inside one 64 bit / 128 bit word, i.e. to try to constrain each handling path to process word at time. (I.e. choice 2.) Note: you cannot restrict all operations to work in 128-bits, but occasionally need to handle carries etc. concerns.

Advice

Or how to proceed in practice.

In case you are experienced with "ordinary" programming languages in addition to the HDL language you use (often verilog or VHDL), I would propose first trying to make functional model of the multiplier in one of usual programming languages and comparing the results against some existing big number multiplier code, because it may appear that it is not always completely straight forward to build correctly functioning processing step.

There may be inexpensive already existing design for your FPGA, available for licensing with reasonable cost. It may be superior option compared to doing it your self. (For SW implementations I also recommend using one of existing libraries, and in fact for HW this same choice usually exists as well.)

If side-channel attacks (such as timing) are considerable threat in your use, you'll need to carefully consider the side channels during the implementation. Standard "basic" implementation of montgomery reduction is not side channel free.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.