Re: RSA on 8bit micro

RSA is dead simple. All you have to do is compute pow(A,B)%C where A, B, C are the very long integer variables. You may have to develop the multiprecision integer arithmetics, but this should not be a problem either.

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

Depends on the quality of your compiler, actually. I'm not familiar with M8C at all, a quick look at the datasheet tells me that the CPU is quite unusual (I only have Z80 & ARM experience), no idea if there exist a good C compiler for it.

If the speed is not an issue, then the task is definitely doable. "RSA is dead simple' as Vladimir says, it's just 'x^e mod n' operation and the only trouble with it is that 'x' & 'n' are big numbers, so if you have any performance concerns it becomes tricky.

Well, it's only a few hours since you've posted your request, so you can still hope . My feeling is that you will hardly find a ready solution for your particular CPU. They probably exist but they are not open.

In openssl, libtomcrypt and similar libs you'll find the solutions "optimised for speed" and I perfectly agree that they are hardly applicable to an 8-bitter with limited memory. You need to search for a simplistic, straightforward implementation of RSA, I guess.

Do you have assembly experience on the given CPU?

PS: Drop me a mail (atoumantsev_spam mail.ru) - I couldn't figure out your email address from your posts.

I think for the AVR there is one here

Called there "Atmal", don´t know if it works.

MfG JRD

here

No, it's AES (Rijndael). This thread is about RSA.

You are right: today i am sleeping with open eyes. But RSA will be even less fun:

Philips claimed in 1993 for the P83C852 an 8051 with simple additional "calculation-unit A+a*X", 6k ROM, 256 Byte RAM ,

2k EEPROM about 0,5 ... 1 sec. But 160 sec if one would do it on a 8051 without ( but on the smartcard the clock may have been 4 MHz instead of 12 MHz ). And 4sec for a 32 bit CPU of that time. Not for 1024 but 512 bit it seems.

MfG JRD

sleeping with open eyes.

The big question here is whether they were referring to a public key (short exponent) or a private key operation. I believe 4 sec for a 32bit CPU is for the private key one.

To the OP: are you supposed to do public key only?

Is the application encryption, or signature verification (like in insuring integrity of code or data)? In the former case, you may need protection against a variety of attacks (timing, DPA, SPA..), when in the later you do not.

If your application is DEcryption, or signature GENERATION, you are out of luck with an 8-bit micro, unless you have lots of time; and you likely need protections as suggested above.

My company sells optimized assembly code that performs modexp as needed for RSA/Rabin signature verification, including on very low-end micros; and more generally security-related code and counselling. We mostly work on 8051, ST7, 68HC11, PIC18,

680x0, and ARM, but are open to other micros.

From the spec of our modexp library:

Computes a^e mod n, with 0

For the multi-precision arithmetics, the GMP source code gives (the treatment of natural numbers) some good examples. The algorithms you'll want to use are right out TAOCP, Volume II.

--
David T. Ashley              (dta@e3ft.com)
http://www.e3ft.com          (Consulting Home Page)
http://www.dtashley.com      (Personal Home Page)
http://gpl.e3ft.com          (GPL Publications and Projects)

of

keys

at

libraries

The most understandable implementation I came across was the ancient RSAref. It is written in very portable C

For performance you have to write only 2 - 4 functions in assembler, mainly : multiply long integer with word.