RSA Encryption for Embedded Devices
A simple RSA-based encryption engine and guide on generating a public/private key pairs.
Two commonly used methods of encrypting data are DES and RSA. While both have their strengths and weaknesses, RSA is easier to implement in software, requiring only a couple dozen lines of code. But while impementing RSA in software is relatively easy, generating valid public and private keys to make the system work poses more of a problem.
We've put together this tutorial to show you how to add simple RSA encryption to your embedded systems, including how to calculate your own public and private keys. The RSA implementation provided here is based on the examples in the book Mastering Algorithms With C by Kyle Loudon. The supplied code is aimed at providing basic encryption to enable you to more securely transmit data over a wireless sensor network, for example. The encryption engine supplied is limited to 64-bit integers (unsigned long long), meaning that it doesn't provide the same level of security that much larger key pairs would provide, but it does still significantly raise the bar compared to unencrypted data while keeping a relatively small code footprint (since you aren't implementing support for massive integers). The current code uses around 1.6kB flash when compiled in release mode for a Cortex M3 processor.
NOTE: Many instances of libc that are used for embedded systems do not include support for 64-bit integers in printf by default (%lld, etc.). You may need to modify stdio.c (printf), change the way you display the 64-bit variables, or avoid printf altogether. This example has been tested successfully in the
LPC1343 Code Base removing the printf output, for example.
rsa.h
/**************************************************************************/
/*!
\file rsa.h
\author Kyle Loudon
modified: microBuilder.eu
\date 4 January, 2010
\version 1.0
Basic RSA-encryption using 64-bit math (32-bit keys).
Based on the examples from "Mastering Algorithms with C" by
Kyle Loudon (O'Reilly, 1999).
*/
/**************************************************************************/
#ifndef _RSA_H_
#define _RSA_H_
/* In a secure implementation, huge_t should be at least 400 decimal digits, *
* instead of the 20 provided by a 64-bit value. This means that key values *
* can be no longer than 10 digits in length in the current implementation. */
typedef uint64_t huge_t;
/* Structure for RSA public keys. */
typedef struct rsaPubKey_s
{
huge_t e;
huge_t n;
}
rsaPubKey_t;
/* Define a structure for RSA private keys. */
typedef struct rsaPriKey_s
{
huge_t d;
huge_t n;
}
rsaPriKey_t;
void rsaTest();
void rsaEncrypt(huge_t plaintext, huge_t *ciphertext, rsaPubKey_t pubkey);
void rsaDecrypt(huge_t ciphertext, huge_t *plaintext, rsaPriKey_t prikey);
#endif rsa.c
/**************************************************************************/
/*!
\file rsa.c
\author Kyle Loudon
modified: microBuilder.eu
\date 4 January, 2010
\version 1.0
Basic RSA-encryption using 64-bit math (32-bit keys).
Based on the examples from "Mastering Algorithms with C" by
Kyle Loudon (O'Reilly, 1999).
Note: The rsaTest function uses debug_printf in Rowley Associate's
Crossworks for ARM. If you wish to use an alternative means to
display the test results, cross_studio_io.h can be removed from the
include list, and debug_printf can be renamed to a different
output method.
*/
/**************************************************************************/
#include <cross_studio_io.h>
#include "rsa.h"
static huge_t modexp(huge_t a, huge_t b, huge_t n)
{
huge_t y;
y = 1;
/* Compute pow(a, b) % n using the binary square and multiply method. */
while (b != 0)
{
/* For each 1 in b, accumulate y. */
if (b & 1)
{
y = (y * a) % n;
}
/* Square a for each bit in b. */
a = (a * a) % n;
/* Prepare for the next bit in b. */
b = b >> 1;
}
return y;
}
void rsaTest()
{
huge_t rsaOrig, rsaDecrypted, rsaEncrypted;
rsaPubKey_t publicKey;
rsaPriKey_t privateKey;
int i;
debug_printf("Encrypting with RSA\n");
// Values based on 64-bit math (huge_t = unsigned long long)
// which will result in more secure encryption, but also
// increases the size of the encrypted text
publicKey.e = 21;
publicKey.n = 16484947;
privateKey.d = 15689981;
privateKey.n = 16484947;
// Alternative values with 32-bit math (huge_t = unsigned long)
// or when smaller encrypted text is desired
// publicKey.e = 17;
// publicKey.n = 209;
// privateKey.d = 53;
// privateKey.n = 209;
debug_printf("d=%lld, e=%lld, n=%lld\n",
privateKey.d, publicKey.e, publicKey.n);
for (i = 0; i < 128; i++)
{
rsaOrig = i;
rsaEncrypt(rsaOrig, &rsaEncrypted, publicKey);
rsaDecrypt(rsaEncrypted, &rsaDecrypted, privateKey);
if (rsaOrig == rsaDecrypted)
{
debug_printf("In=%5lld, Encrypted=%10lld, Out=%5lld (OK)\n",
rsaOrig, rsaEncrypted, rsaDecrypted);
}
else
{
debug_printf("In=%5lld, Encrypted=%10lld, Out=%5lld (ERROR)\n",
rsaOrig, rsaEncrypted, rsaDecrypted);
}
}
}
void rsaEncrypt(huge_t plaintext, huge_t *ciphertext, rsaPubKey_t pubkey)
{
*ciphertext = modexp(plaintext, pubkey.e, pubkey.n);
return;
}
void rsaDecrypt(huge_t ciphertext, huge_t *plaintext, rsaPriKey_t prikey)
{
*plaintext = modexp(ciphertext, prikey.d, prikey.n);
return;
} Generating the Public and Private Keys
RSA encryption is assymetric and requires both a public and private key. To come up with a set of keys that are compatible with each other, you will first need to perform a handful of basic calculations which we've detailed below.
The first step is to find two large prime numbers. The maximum size of the numbers you use will depend on your own software implementation, but in our own case we are using unsigned long long (64-bit) numbers as the largest possible value (0 to 18,446,744,073,709,551,615). That means that the largest prime numbers that we can use need to be less than 32-bits (0-4,294,967,295), since one 32-bit value multiplied by one 32-bit value can't possibly exceed the upper 64-bit limit.
You start by determining the modulus value of 'N' which will be common to both the public and private keys, with the following formula: N = pq. As an example we've taken the prime numbers 1931 and 8537:
N = pq
N = 1931 * 8537 = 16,484,947
To come up with a prime number, you can use one of the following links (found via Google):
The next step is to find an odd-value integer with no factors in common with the result of "(p-1)(q-1)" ... which we've calculated below:
r = (p-1)(q-1)
r = 1930 * 8536 = 16,474,480
Given that this is the most complicated part of generating the keys, we were glad to come across the following tool which will propose some candidate values for you (which saves us from having to make something similar ourselves): RSA Calculator
To use the tool, simply enter your two prime numbers (1931 and 8537 in this example) into the textboxes for 'p' and 'q' and click 'set p, q & check for primality'. If the supplied numbers are indeed both primes, the tool will propose a list of odd-valued candidate integers with no factors in common with r. To continue with the numbers used here, we've selected 329489601.
The values of 'e' (for the public key) and 'd' (for the private key) can be calulated using the same RSA Calculator. Take the candidate value ('K'), enter it in the appropriate textbox and click "Factor K". This should populate two text boxes with the factored values. The value K (329489601) can be represented as:
K = 3 * 7 * 15689981
But since for 'e' and 'd' we need to have two values (not three) this must be simplified to:
21 * 15689981
Which gives us our values for 'e' and 'd' to complete the public and private keys. You can confirm these values using a scientific calculator and the formula e*d mod r = 1:
e*d mod r = 1
21 * 15689981 mod 16474480 = 1
329489601 mod 16474480 = 1
That means that, using the example numbers provided here, we would end up with the following values for our keys:
Public Key
e = 21
n = 16484947
Private Key
d = 15689981
n = 16484947