RSA 4096 public key operation on crypto block that natively supports 2048 bit only?
crashedmind
I have a general purpose 32-bit CPU that has an onboard hardware
crypto block that supports low level crypto primitives like:
=95 Modulo exponentiation
=95 Montgomery Multiplication
=95 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 =91n=92 and exponent =91e=92 of
value 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 (=91n=92
=3D 4096 bit, =91e=92 =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.
Apologies if this is a dumb question...
mike clark
On Oct 16, 10:10=A0pm, crashedmind <chris.mad...@crashedmind.com> wrote:
> I have a general purpose 32-bit CPU that has an onboard hardware
> crypto block that supports low level crypto primitives like:
> =3D95 =A0 =A0 Modulo exponentiation
> =3D95 =A0 =A0 Montgomery Multiplication
> =3D95 =A0 =A0 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 =3D91n=3D92 and exponent =3D91e=3D92 of
> value 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 (=3D91n=3D92
> =3D3D 4096 bit, =3D91e=3D92 =3D3D 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.
>
> Apologies if this is a dumb question...
If you know the factorization of n, I would think you could use the
Chinese Remainder Theorem to do your modular exponentiation using the
factors of n. Then combine the 2 results to get the answer (mod n).
Francois Grieu
crashedmind wrote :
> I have a general purpose 32-bit CPU that has an onboard hardware
> crypto block that supports low level crypto primitives like:
> - 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
security countermeasures).
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
http://cr.yp.to/papers.html#rwsota
Fran=E7ois Grieu