CODEWITHSUNDEEP
rsapublic-keyexponentiationmodular-arithmeticdsa
Ziad Abdelkarim elsayed
Ziad Abdelkarim elsayed

Reputation: 1

modular exponentiation of 2048 bit operands using multiple 256 bit operations

I am implementing RSA digital signature algorithm and one of the operations needed is modular exponentiation of 2048 bit strings. and the hardware i am using provides me an accelerated 256 bit modular exponentiation operation. so, my question here is there an optimized way to compute the 2048 bit operation using multiple 256 bit operations.

thanks in advance !!

Upvotes: 0

Views: 171

Answers (1)

fgrieu
fgrieu

Reputation: 2912

I second this comment that hardware restricted to computing Ab mod n for 256-bit parameters is useless for RSA with 2048-bit modulus N.

  • We can't use a RSA Multiprime strategy (where N is the product of more than 2 primes, and the compute-intensive operations are made modulo these smaller primes), because a product of eight or nine primes each fitting 256 bits would be vulnerable to the Elliptic Curve factoring method. Also that would only work for the private key operation (signature generation, or decryption).
  • We can't use the thing as a general multiplier, because there's a single input.
  • By setting n to 2256-1 and b=2 we could use the thing to compute squares of any 128-bit argument, but that represents only a small fraction of the arithmetic work in RSA, and is most certainly not worth the hassle.

Upvotes: 0

Related Questions