Post by crashedmind
I have a general purpose 32-bit CPU that has an onboard hardware
- Modulo exponentiation
- Montgomery Multiplication
- Montgomery modulo exponentiation
The onboard hardware crypto block supports maximum 2048 bit operations
only e.g. it can support an RSA public key operation (signature
verification) with 2048 bit public modulus n and exponent e =3D 65537.
I want to know if it is possible to use the crypto h/w (with
associated 2048 bit limit) to do a 4096 bit public key operations
(n of 4096 bit, e =3D 65537) and how.
I know all the input parameters in advance (n, e, signature) and can
do whatever pre-computations are required.
I don't have the specification for the crypto block e.g. what model #
is etc... but this is a general question as to what if any techniques
can be used to solve this problem.
Assuming that when you wrote "Montgomery Multiplication" you meant
"Montgomery modular multiplication", I see no way to make good use
of the three primitives that you mention. However many crypto blocks
do support additional primitives that can be put to good use.
One thing to consider: there may be no need to use the crypto block
in the first place. In particular, there is no security-related
reason to use the crypto block to perform the public-key operation
for the purpose of integrity verification (that would be slightly
different if the public-key operation was used for encryption).
And the 32-bit CPU is likely fast enough for the the RSA public-key
operation: with n of 4096 bit and e =3D 65537, it is typically faster
than the private-key operation is on same hardware, by a factor of
80 to 1000 (depending on if the private-key operation uses CRT and
The fact that signature verification is fast with RSA is one of the
excellent reason to prefer RSA (or other schemes based on
Integer Factorisation) to ECC in many applications.
For a view on the state of the art in this field, see