Working Precision and Time-constant Arithmetic with ECC?

Question

I am interested in Elliptic Curve Cryptography and found algorithms for constant-time multiplication. Within these algorithms arithmetic operations must be performed (like addition and multiplication).

I have two questions about these 'internal' arithmetic operations:

• these 'internal' operations must be performed in constant-time, too, right? Then I guess the precision of all intermediate variables must be the same. But what precision is necessary here (e.g. if I multiply two 256 bit numbers, I need 512 bits for the result, I guess).

• What are good algorithms for performing these 'internal' arithmetic operations in constant time?

Answer 1

You can have additions and multiplications take constant time on a hardware level; however, the multiply units generally take 4 cycles due to the array multiplier design for a 32-bit width, at 64-bit on Intel, it's 6 cycles. The division will always be iterative, which is the problem.

Here's an example of a routine that I have for adding two 256 numbers in constant time on my i7 (note, these times will be different for different cores):

add256:
        xorl      %r9d, %r9d         # 1 cycle                             
        movq      (%rsi), %rax       # 1 cycle                          
        addq      %rax, (%rdi)       # 1 cycle                        
        movq      8(%rsi), %rdx      # 1 cycle                         
        adcq      %rdx, 8(%rdi)      # 1 cycle                           
        movq      16(%rsi), %rcx     # 1 cycle                           
        adcq      %rcx, 16(%rdi)     # 1 cycle                         
        movq      24(%rsi), %r8      # 1 cycle                          
        adcq      %r8, 24(%rdi)      # 1 cycle
        setb      %r9b               # 1 cycle                           
        ret                          # 1 cycle

You are not going to get true constant time unless you are in assembly. I believe that the best way to get constant time would be to just figure out the maximum it time it takes to do a calculation, and then pad intermediate cycles with junk because the ADD and MUL will take different times.

The thing that will hurt you the most is the division that is iterative, as that takes an arbitrary amount of cycles.