Tell me more ×
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.
up vote 0 down vote favorite

I am working on 224-bit elliptic curve cryptography. In this 224-bit * 224-bit multiplication results 448-bit output. I am reducing 448-bit into prime field range( prime number $2^{224}-2^{96}+1$) using modulus operation. Can any tell me efficient modulus operation for remainder calculation? I am working on VHDL.

share|improve this question

1 Answer

up vote 3 down vote

See section D.2.2 of FIPS 186-3. The modular reduction can be expressed as two additions and two subtractions of values which are assembled by concatenating selected 32-bit words of the 448-bit value which is to be reduced. Note that these additions and subtractions are modular, so you may have to mind some carries.

share|improve this answer
yes. i know that procedure. It is recommended by NIST standard Elliptic Curve. But if the prime number changes that formula won't work. Is any alternative way? In FIPS 186-3 , how can he able to computed the value, could you explain mathematics behind in that method? – venkat Mar 18 at 11:13
1  
@venkat Primes in ECC are often specifically chosen so they allow more efficient reductions. – CodesInChaos Mar 18 at 11:42
Aninteger c = (c13,..., c2, c1, c0) in base 2^32 with 0 ≤ c < 224-bit*224-bit OUTPUT: c mod p(224-bit) z1 = (c6, c5, c4, c3, c2, c1, c0), z2 = (c10, c9, c8, c7, 0, 0, 0), z3 = (0, c13, c12, c11, 0, 0, 0), z5 = (0, 0, 0, 0, c13, c12, c11), z4 = (c13, c12, c11, c10, c9, c8, c7),= Return(z1 + z2 + z3 − z4 − z5mod p224).this is algorithm what i supposed to explain. after 224-bit * 224-bit multiplication gives 448 -bit output. it will reduce into field range using prime number (2^224-2^96+1) using above algorithm. can you explain mathematical concept behind in this efficient reduction technique? – venkat Mar 19 at 10:53

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.