Fast asymmetric cypher for C++ application

Question

Hello.

I'm looking for a fast asymmetric cypher algorithm to be used in C++ program. Our application accesses read-only data stored in archive (custom format, somewhat similar to tar), and I would like to prevent any modifications of that archive by asymmetrically encrypting archive index (I'm aware that this isn't a perfect solution and data can still be extracted and repacked using certain techniques).

Some individual files within archive are encrypted with symmetric cypher and encryption keys for them are stored within archive index(header). Which is why I want to encrypt archive header asymmetrically.

Cypher requirements:
1) Algorithm implementation should be platform-independent.
2) Algorithm should be either easy to implement myself or it should be available in library (with source code) that allows static linking with proprietary application, which means that GPL/LGPL/viral licenses cannot be used. MIT/BSD-licensed code, or public domain code is acceptable.
3) If cypher is available in library, ideally it should have small memory footprint, and implementation should be compact. I would prefer to use a C/C++ library that implements only one cipher instead of full-blown all-purpose cipher collection.

Originally I wanted to use RSA, but it looks like it is simply too slow to be useful, and there aren't many alternatives.

So, any advice on what can I use?

Answer 1

OpenSSL should do the job for you. It's open-source (apache license, so meets your license requirements).

It's widely used and well tested.

Answer 2

Use a custom RSA to sign the archive. Store the public key in the application and keep the private key in house. Now anyone could modify the read only archive, but your application would refuse to load the modified archive.

Answer 3

How about MD5?

Yes I am aware that MD5 has been 'broken; - but most practical applications this is irrelevant.
Especially if the modified data would also have to be valid in the particular data format as well as have the correct MD5

EDIT:
MD5 is appropriate if you want to just ensure that data stored can't be changed (or at least you can detect it) but it doesn't hide the data. Note that if you after have the key in your app alongside the data it can always be extracted.

Answer 4

Check out Curve25519, which is elliptic curve crytpography implemented efficiently, and around patent problems.

It meets all of your requirements. See Here.

You can use it to encrypt, or to simply sign.

As a side note:

For integrity checking, a MAC should suffice unless you really need assymetric encryption.

Answer 5

Okay, I've found what I've been looking for, and I think it is better than OpenSSL (for my purposes, at least).

There are two libraries:
libtomcrypt, which implements several cyphers (including RSA), and libtommath, that implements bignum arithmetics. Both libraries are in public domain, easy to hack/modify and have simpler programming interface than OpenSSL, and (much) better documentation than OpenSSL.
Unlike older public domain rsa code I found before, libtomcrypt can generate new keys very quickly, can import OpenSSL-generated keys, and supports padding. Another good thing about libtomcrypt is that it doesn't have extra dependencies (OpenSSL for windows wants gdi32, for example) and is smaller than OpenSSL.

I've decided to use RSA for encryption, after all, because (to me it looks like) there are no truly asymmetric alternatives. It looks like most of the other ciphers (elgamal, elliptic curves) are more suitable for symmetric encryption where session key is being encrypted asymmetrically. Which isn't suitable for me. Such ciphers are suitable for network communications/session keys, but it wouldn't be good to use that for static unchanging data on disk.

As for "RSA being slow", I've changed archive format a bit, so now only small chunk of data is being asymmetrically encrypted. Failure to decrypt this chunk will make reading archive index completely very difficult if not impossible. Also, I must admit that slowness of RSA was partially a wrong impression given by older code I've tried to use before.

Which means, question solved. Solution is RSA + libtomcrypt. RSA - because there aren't many alternatives to RSA, and libtomcrypt - because it is small and in public domain.