could you also share your (presumably light) rsa code?:-)
Not a problem :-) Thanks for asking; hope it helps.
{Edited to point out that there was a bug in here - see later discussion. I've fixed the bug.} ////////////////////////////////////////////////////////////////////////////
//
static void modexp( hex_bignum_t *a_ptr, hex_bignum_t *b_ptr, hex_bignum_t *n_ptr, hex_bignum_t *result_ptr )
{
static hex_bignum_t zero;
static hex_bignum_t b;
static hex_bignum_t n;
static hex_bignum_t a;
// Make copies, we don't want to stomp on the passed parameters.
a = *a_ptr;
b = *b_ptr;
n = *n_ptr;
HB_int_to_hex_bignum( 1, result_ptr );
HB_int_to_hex_bignum( 0, &zero );
// Compute pow(a, b) % n using the binary square and multiply method.
while ( HB_compare( &b, &zero ) != 0 )
{
// For each 1 in b, accumulate result.
if ( HB_is_low_bit_set( &b ) )
{
//////////////////////////////////////
// result = (result * a) % n;
// result = ( result * a );
HB_multiply( result_ptr, &a, result_ptr );
// result = result % n
HB_modulo( result_ptr, &n, result_ptr );
//////////////////////////////////////
}
// Square a for each bit in b.
//////////////////////////////////////
// a = (a * a) % n;
// a = a * a;
HB_multiply( &a, &a, &a );
// a = a % n;
HB_modulo( &a, &n, &a );
//////////////////////////////////////
// Prepare for the next bit in b.
// b = b >> 1;
HB_rshift( &b );
}
}
////////////////////////////////////////////////////////////////////////////
//
void rsaEncrypt( hex_bignum_t *plaintext_ptr, hex_bignum_t *ciphertext_ptr, rsaKey_t *pubkey_ptr )
{
modexp( ciphertext_ptr, &(pubkey_ptr->e), &(pubkey_ptr->n), plaintext_ptr );
}
H0wdy..
This post really caught my attention - as I've been dreaming of implementing RSA into my boost killer library for sometime, without depending on openssl or any libs of any kind -
Do you have a final source for your hex bignum code included with the rsa code code ? Thank you by the way
MK
I'm not sure what's on this page is the latest I have, but I'll check and see. I am using it, and the RSA stuff works, but it is painfully slow. Since the public exponent is usually really short, encrypt and decrypt with the public key is usable, but with most private keys, these same functions can literally take hours with 2048-bit keys. Just a heads-up; use OpenSSL if you can, it's hairy but really powerful and fast.
How much faster ? - If it takes possibly hours for 2048 bit keys , how long would it take with openSsl ? ( minutes ? seconds ? ) - Personally I'm interested in getting the most minimal rsa working , regardless of speed, and then work towards optimizing.. while maintaining a minimal framework.. - Although, my first language is 80x86 asm, I want to completely stay away from machine language, and see what is possible with carefully thought out C code.. In any case, I'm very excited by your post - I've literally been looking for something like this for years.. -
{Edited to point out that there was a bug in here - see later discussion. I've fixed the bug.} My bad - I meant to include it. Here 'tis : ////////////////////////////////////////////////////////////////////////////
//
void rsaDecrypt( hex_bignum_t *ciphertext_ptr, hex_bignum_t *plaintext_ptr, rsaKey_t *prikey_ptr )
{
modexp( plaintext_ptr, &(prikey_ptr->e), &(prikey_ptr->n), ciphertext_ptr );
}
Thank you for your decrypt, but I think it is not going to work. You need something like:
where, (d * e) % ((p-1)*(q-1)) = 1, p*q = n. ////////////////////////////////////////////////////////////////////////////
//
void rsaDecrypt( hex_bignum_t *ciphertext_ptr, hex_bignum_t *plaintext_ptr, rsaSecKey_t *privkey_ptr )
{
HB_modexp( ciphertext_ptr, &(privkey_ptr->d), &(privkey_ptr->n), plaintext_ptr );
}
It goes without saying (or maybe it doesn't!) that you must use valid p and q values when calculating your RSA keys. You don't say here what HB_modexp() looks like. Did you simply rename it, perhaps? The reason I didn't name it so in the first place, is because mod_exp() is not a public function. As a 'static', it is meant to be local, and only called from the encrypt/decrypt functions.
Here's some sample data and test code to try running through it - if I've made some mistake, I'd be happy to have it pointed out. // This example is from : http://www.di-mgt.com.au/rsa_alg.html#simpleexample
#define TEST_PUBLIC_KEY_EXP "010001" #define TEST_PUBLIC_KEY_MOD "A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F" \
"BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9" \
"3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C" \
"FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB" #define TEST_CRYPTOGRAM "0002257F48FD1F1793B7E5E02306F2D3228F5C95ADF5F31566729F132AA12009" \
"E3FC9B2B475CD6944EF191E3F59545E671E474B555799FE3756099F044964038" \
"B16B2148E9A2F9C6F44BB5C52E3C6C8061CF694145FAFDB24402AD1819EACEDF" \
"4A36C6E4D2CD8FC1D62E5A1268F496004E636AF98E40F3ADCFCCB698F4E80B9F" #define TEST_RESULT "3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5" \
"8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621" \
"EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E" \
"609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B" HB_hex_string_to_hex_bignum( TEST_PUBLIC_KEY_EXP, &(publicKey.e) );
HB_hex_string_to_hex_bignum( TEST_PUBLIC_KEY_MOD, &(publicKey.n) );
HB_int_to_hex_bignum( 0, &privateKey.e );
HB_int_to_hex_bignum( 0, &privateKey.n );
HB_hex_string_to_hex_bignum( TEST_CRYPTOGRAM, &rsaOrig );
rsaDecrypt( &rsaOrig, &rsaDecrypted, &publicKey );
HB_hex_string_to_hex_bignum( TEST_RESULT, &rsaEncrypted );
if ( HB_compare( &rsaEncrypted, &rsaDecrypted ) == 0 )
{
printf( "Passed!\n" );
}
else
{
printf( "Failed!\n" );
}
Sorry about the expmod function. As you said, I have just renamed it. This decrypt function works only for data encrypted with the private key (d,n). Thus, it is useful for checking signatures not for decrypting actual data. if you try the code below you will see it will fail: HB_hex_string_to_hex_bignum( TEST_PUBLIC_KEY_EXP, &(publicKey.e) );
HB_hex_string_to_hex_bignum( TEST_PUBLIC_KEY_MOD, &(publicKey.n) );
HB_int_to_hex_bignum( 0, &privateKey.e );
HB_int_to_hex_bignum( 0, &privateKey.n );
HB_hex_string_to_hex_bignum( TEST_RESULT, &rsaOrig );
rsaEncrypt( &rsaOrig, &rsaEncrypted, &publicKey );
rsaDecrypt( &rsaEncrypted, &rsaDecrypted, &publicKey );
if ( HB_compare( &rsaOrig, &rsaDecrypted ) == 0 )
{
printf( "Passed!\n" );
}
else
{
printf( "Failed!\n" );
}
If you encrypt data with the public key, you must decrypt it with the private key, not the public key.