57 views

Skip to first unread message

Oct 17, 2009, 12:10:12 AM10/17/09

to

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...

Oct 20, 2009, 4:49:04 AM10/20/09

to

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).

Oct 20, 2009, 4:50:23 AM10/20/09

to

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu