RSA on 8bit micro

I'm working with a Cypress PSoC micro with an M8C core (CY8C29666).  I have 
32K ROM and 1K RAM.  I need to implement 1024 bit RSA encryption in as 
small a footprint as possible.  I do not need to do any key generation in 
the micro itself.

I know that RSA is common on Smart Card micros and secure micros with 
similar resorces, but I can't find any good examples.  All I find is tons 
of Mathamatical and Therotical discussions on RSA, or implementations for a 
full PC. 

Anyone have any pointers to some source code that I can port over to this 
micro.  Preferebly in C or Assembly.

Thanks,

W

On Jan 24, 4:32 pm, W Trembyle <nore...@nowhere.com> wrote:
> I'm working with a Cypress PSoC micro with an M8C core (CY8C29666).  I have
> 32K ROM and 1K RAM.  I need to implement 1024 bit RSA encryption in as
> small a footprint as possible.  I do not need to do any key generation in
> the micro itself.
>
> I know that RSA is common on Smart Card micros and secure micros with
> similar resorces, but I can't find any good examples.  All I find is tons
> of Mathamatical and Therotical discussions on RSA, or implementations for a
> full PC.
>
> Anyone have any pointers to some source code that I can port over to this
> micro.  Preferebly in C or Assembly.
>
> Thanks,
>
> W

Hi there,
I don't have ready answers to your questions, sorry. But always
interested in questions like this ;-)

1) I've googled for CY8C29666 and all the links I've had a quick look
at quote 2K RAM. Are you sure you've got only 1K?

2) Assuming you have 1K - can you dedicate all this memory to RSA
function. If not - how much can you dedicate? My rough estimate is: for
1024bit (128 byte) RSA you'll need at least ~520 bytes...

3) Do you have any particular performance (speed) requirements for the
RSA operation? It might turn out that you simply can't achive it on a
given CPU, no matter how smart you are.


4) There's plenty of open source implementations of RSA (mostly in C)
to start with (search for openssl, libtomcrypt, or just google). I have
a gut feeling that you won't achieve your goal unless you switch to asm
but you can always use the C compiler output and improve it.

In case you're not going to give up, I think that this document might
be helpful:
http://www.cypress.com/portal/server.pt?space=CommunityPage&control=SetCommunity&CommunityID=285&PageID=552&r_folder=Application%20Notes&r_title=AN2032&ref=prt

as multiplication is the heart of RSA.


You mention smart cards, I'm not an expert in this area
but from what I've heard those chips tend to use crypto-accelerating
hardware.

[Posting through Google, they changed their design again and where the
hell is the Preview button? Sorry if my post looks absolutely
awkward...]

W Trembyle wrote:

> I'm working with a Cypress PSoC micro with an M8C core (CY8C29666).  I have 
> 32K ROM and 1K RAM.  I need to implement 1024 bit RSA encryption in as 
> small a footprint as possible.  I do not need to do any key generation in 
> the micro itself.
> 
> I know that RSA is common on Smart Card micros and secure micros with 
> similar resorces, but I can't find any good examples.  All I find is tons 
> of Mathamatical and Therotical discussions on RSA, or implementations for a 
> full PC. 
> 
> Anyone have any pointers to some source code that I can port over to this 
> micro.  Preferebly in C or Assembly.

RSA implementation is straightforward and dead simple. All you need are 
the integer arithmetic operations with the multibit numbers. The 1k of 
RAM should be sufficient to do that, although it is going to be rather 
slow on the shamefull M8C.


Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

tum_,

Thanks for the response.

Your correct.  I have 2K RAM and not just 1K. I think I can devote 90% of 
this or so to RSA.  I can store the key in Flash so no problems there.  
Assembly is the only way to go else you kill yourself in code size.

You are also correct in saying that most SmartCards use a cryptographic 
coprocessor.  But I know some do not.  I have read about implementations 
on 8051 processors and other 8bit micros.  I was hopping that someone 
might know an implementation like this.  

Speed is no issue, as this is used only for Key exchange of symetric keys 
(very infrequently) and firmware update signatures (even more 
infrequently - hopfully :)

I have done my time in digging through openSSL but have not looked yet at 
libtomcrypt.  I will check that as well.  My problem with these libraries 
is that they are designed for PC's with unlimited RAM.  Some of there 
structures are larger than my entire RAM.  I need some very optomized 
code to make this work.

I still have hope though and will keep trying to find something to make 
the development faster.

later,

W

"tum_" <atoumantsev_spam@mail.ru> wrote in
news:1169666257.053198.212110@a75g2000cwd.googlegroups.com: 

> Hi there,
> I don't have ready answers to your questions, sorry. But always
> interested in questions like this ;-)
> 
> 1) I've googled for CY8C29666 and all the links I've had a quick look
> at quote 2K RAM. Are you sure you've got only 1K?
> 
> 2) Assuming you have 1K - can you dedicate all this memory to RSA
> function. If not - how much can you dedicate? My rough estimate is:
> for 1024bit (128 byte) RSA you'll need at least ~520 bytes...
> 
> 3) Do you have any particular performance (speed) requirements for the
> RSA operation? It might turn out that you simply can't achive it on a
> given CPU, no matter how smart you are.
> 
> 
> 4) There's plenty of open source implementations of RSA (mostly in C)
> to start with (search for openssl, libtomcrypt, or just google). I
> have a gut feeling that you won't achieve your goal unless you switch
> to asm but you can always use the C compiler output and improve it.
> 
> In case you're not going to give up, I think that this document might
> be helpful:
> http://www.cypress.com/portal/server.pt?space=CommunityPage&control=Set
> Community&CommunityID=285&PageID=552&r_folder=Application%20Notes&r_tit
> le=AN2032&ref=prt 
> 
> as multiplication is the heart of RSA.
> 
> 
> You mention smart cards, I'm not an expert in this area
> but from what I've heard those chips tend to use crypto-accelerating
> hardware.
> 
> [Posting through Google, they changed their design again and where the
> hell is the Preview button? Sorry if my post looks absolutely
> awkward...]
> 

W Trembyle wrote:

>
> I still have hope though and will keep trying to find something to make 
> the development faster.
> 

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

http://www.abvolt.com

> Your correct.  I have 2K RAM and not just 1K. I think I can devote 90% of
> this or so to RSA.  I can store the key in Flash so no problems there.  
> Assembly is the only way to go else you kill yourself in code size.

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.

> You are also correct in saying that most SmartCards use a cryptographic
> coprocessor.  But I know some do not.  I have read about implementations
> on 8051 processors and other 8bit micros.  I was hopping that someone
> might know an implementation like this.  
>
> Speed is no issue, as this is used only for Key exchange of symetric keys
> (very infrequently) and firmware update signatures (even more
> infrequently - hopfully :)

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.


> I have done my time in digging through openSSL but have not looked yet at
> libtomcrypt.  I will check that as well.  My problem with these libraries
> is that they are designed for PC's with unlimited RAM.  Some of there
> structures are larger than my entire RAM.  I need some very optomized
> code to make this work.
> I still have hope though and will keep trying to find something to make
> the development faster.

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 <<<commercial at>>> mail.ru) - I
couldn't figure out your email address from your posts.

> I have read about implementations
> on 8051 processors and other 8bit micros.  I was hopping that someone
> might know an implementation like this.

I think for the AVR there is one here
  http://www.iaik.tugraz.at/research/krypto/AES/old/~rijmen/rijndael/
Called there "Atmal", don�t know if it works. 

MfG JRD

On Jan 25, 8:32 am, Rafael Deliano
<Rafael_DelianoENTFER...@t-online.de> wrote:
> > I have read about implementations
> > on 8051 processors and other 8bit micros.  I was hopping that someone
> > might know an implementation like this.I think for the AVR there is one=
 here
>  http://www.iaik.tugraz.at/research/krypto/AES/old/~rijmen/rijndael/
> Called there "Atmal", don=B4t know if it works.

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

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

>> You mention smart cards, ...
>> but from what I've heard those chips tend to use crypto-accelerating
>> hardware.

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

On Jan 25, 10:57 am, Rafael Deliano
<Rafael_DelianoENTFER...@t-online.de> wrote:
> > 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:
>
> >> You mention smart cards, ...
> >> but from what I've heard those chips tend to use crypto-accelerating
> >> hardware.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.  

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?