RSA encrypt only on MSP430

Hello,

We have a need to implement a PKI scheme in our embedded system which uses a MSP430 controller. Ideally we want to use RSA with 512 or 1024 bit keys. The public key will be in the flash, we need only encryption with the public key of a 256 bit block.

Couple of questions.

1. Is this even possible on a MSP430 with 4K SRAM and 32K Flash ?

2. Any pointers where I can find implementations of this in C (have looked at polarssl and openssl, don't think they were written with embedded systems in view) A search on the TI forums also drew a blank

3. If RSA is a impossibility any pointers for a PKI scheme that is implementable on a 430 based system ?

Thanks in advance.

Best,
Rama

Sorry
I am posting this because I also want to be updated about replies to this post
Please don't mind and I'm sorry I couldn't be more helpful

(1) I have no experience with the MSP430, but memory should not be a problem. I've seen implementations that only require working space equal to the size of the block (so between input, output, modulus and working memory would be ~1K in your case). Speed on the other hand may but that depends on your requirements.

(2) RSA is a rather simple algorithm. Most crypto libraries you'll find will implement a lot of other features that are typically used with RSA. You might have better luck looking for a big-number library--all you really need is an exponent-modulus function. (Stick any of those keywords into your search engine of choice and you'll get decent explanations/algorithms/libraries.)

Though I'd check your requirements. RSA is usually used in conjunction with other algorithms (such has SHA to mask the encrypted data, or a symmetric algorithm like DES or AES to encrypt larger blocks of data than RSA can easily handle).

(3) If you do run into the physical limits of your processor, you might look into the Rabin algorithm. It's similar to RSA but using an exponent of 2 which simplifies the math somewhat.

The embedded forum is a bit slow. You might have better luck asking in the Cryptography forum (for further questions about RSA) or in the C/whatever language you're using (for problems with your implementation) (letting people know you're cross-posting of course).