2

I'm developing a library for RSA cryptography to be used on small devices like microcontrollers. I want to know if someone already had experience doing this kind of thing.

What I've tried so far:

The first thing I tried was taking some code from this library http://axtls.sourceforge.net/. I don't want any of TLS idiosyncrasies because it's too complex (and big). I’m having problems loading the bytes from memory, perhaps I should use the loader routine that came from them, DER is boring to read, ASN1 is binary XML, I'm done with XML and I don't have space to decode XML too.

Perhaps I shouldn't take bytes by using openssl dump tool because of interoperability problems I don't know.

The second try was using code from library https://github.com/wernerd/ZRTPCPP/blob/master/bnlib/bn16.c. The problem was that the CRT algorithm is too big to fit, even though it gave some performance boost, I don’t need it because I have small data packets and I will not use longer keys. I can't have longer keys because I don’t have enough RAM memory.

I prefer to have some small library. Also this library does too much pointer indirection. Reading more from Stackoverflow I found this code, but I got division by zero from it, I am not sure if I have endianes problem when loading the big number. https://github.com/Coder-666/uRSAlib/blob/master/uRSA/BN.c

These libraries looks promising, but I didn’t have time to test them: http://cryptopp.com/#download. https://github.com/jedisct1/libsodium/tree/master/src/libsodium

This is it, i need to finish this soon because I'm almost out of time, If someone knows some small RSA library that really works on little things with 8bits, it would be appreciated, otherwise I will just use something like AES and a fixed key, but this is suboptimal to security. (update: now I'm exploring using ECC curves because they use fixed amounts of memory and need less memory too, as per this paper http://eprint.iacr.org/2013/375.pdf)

The question:

Is it possible to implement a RSA cryptography in less than 15Kb of PIC hex code, or is there some known library that does it?

References:

encryption : RSA algorithm

How to encrypt a string using public key cryptography

Library for RSA implementation in pure C

Are there any very simple RSA implementation in C++

Implementation of RSA without dynamic allocation

implementing a bignum library for rsa encryption

http://en.wikipedia.org/wiki/RSA

http://www.di-mgt.com.au/rsa_alg.html#encryption I also looked at this library from PGP project, but it was too complex.

http://fossies.org/dox/pgpsrc658unix-gnu/dir_d8387bb0a43f1d00e085a9a2c8a94120.html

http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/phi4.html

http://cacr.uwaterloo.ca/hac/ (Applied Cryptology, this one looks very promising, I’m reading just now).

ftp://ftp.cs.pdx.edu/smn/ipsec/skip/ Something worth looking.

http://www.codeproject.com/Articles/14462/Build-your-own-cryptographically-safe-server-clien

http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=8536

http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=5266

http://www.codeproject.com/Articles/60108/BigInteger-Library

Community
  • 1
  • 1
Luiz Felipe
  • 1,123
  • 8
  • 14
  • So do you have a concrete question in here anywhere? I can't figure out what you're after... – Ross Oct 20 '14 at 22:07
  • I just wanted some directions. Perhaps I should post in another place. – Luiz Felipe Oct 21 '14 at 13:29
  • Honestly, and with no offense intended, it sounds like you're in a bit over your head. Also, you may have some technological prejudices that are holding you back; DER parsing should *not* be too painful, and while there are plenty of reasons to dislike ASN.1, it's *not* "binary XML" in any real sense (other than in the extremely loose figurative sense of being a method for storing structured data in a binary string). – Ilmari Karonen Oct 29 '14 at 12:39
  • If ECC is acceptable, I'd go with Curve25519 plus Salsa20Poly1305 for the actual encryption. Libsodium is one implementation, though you'll probably need to rip out the parts you don't need for encryption to reduce the code size. As a minimal code base there is also [TweetNaCl](http://tweetnacl.cr.yp.to/software.html), but I'm not too fond of the minification. – CodesInChaos Oct 30 '14 at 11:01
  • That's what I did, I'll use Curve25519, I will look at TweetNaCl, thanks. – Luiz Felipe Oct 30 '14 at 13:08

1 Answers1

2

The BigDigits library + Wikipedia worked for me. The BigDigit library is very small (I am using only 1 header and 1 source file from them), but very fast and already implements the "exponentiation and modulus" function so encoding and decoding is straight-forward. I am not generating the keys on the micro-controller though.

My code size (on an ARMv7) was between 38 and 27 KB depending on the optimization.

GChabot
  • 143
  • 2
  • 9