Large exponentials and 8-bit PIC processors

Question

Does anyone know if 8-bit (PIC) processors could typically handle large exponentials, e.g., 5^15 mod 23, with a reasonable speed? Does doing so result in more cycles than on 16-bit processors?

I'm hoping to implement Diffie-Hellman Key Exchange on one, but the thought of computing large exponentials seems daunting.

Are large exponentials commonly done on 8-bit processors? Is DH key exchange commonly implemented on such low-end devices?

Answer 1

Any math can be done on any processor. The only question is how many operations, and therefore how much time it will take.

5¹⁵ = 2^34.8, so requires at least 35 bits to express. Bits come in bytes of 8 each on a PIC 18, so you'd use 40 bits or 5 bytes to represent this value.

So all you have to write is a routine that multiplies a 1 byte number by a 5 byte number into the 5 byte number. This is actually pretty easy since the PIC 18 has a hardware 8x8 into 16 bit multiplier. Basically, you multiply the one input byte by each of the wide number bytes separately and add up the results. I'd probably write this as a unrolled loop, so the guts would be 5 sets of a multiply and two adds, or 15 instructions.

Added

As Dan D correctly pointed out in a comment, I forgot to address the modulo part. That is significantly more complicated than computing 5¹⁵. Basically, you do a divide by 23 and keep only the remainder. You may be able to save a few instructions because you don't need the quotient at the end, but mostly you still have to write a 5-byte divided by 1-byte with 1-byte remainder algorithm.

Again, this can all be done on a PIC 18 or other small processors, but will take many more instructions than on a processor that can manipulate 40 bit numbers natively.

Answer 2

As crasic pointed out in the comments, you don't actually need to compute the actual exponential. You can use modular arithmetic to reduce the max value you need to store:

\begin{gather} (a b) ~\textrm{mod}~ m = ((a ~\textrm{mod}~ m) (b ~\textrm{mod}~ m)) ~\textrm{mod}~ m \end{gather}

For \$(a b)~\textrm{mod}~m\$, the maximum value you will ever need to store is \$(m-1)^2\$, which for m=23 means you must be able to store 484. This is outside the range of 8 bit numbers but fits into 16-bits. However, as Olin pointed out some 8-bit micros can manipulate 16-bit values efficient so this isn't a huge issue.

A general implementation in C might look like:

uint16_t exp_mod(uint16_t base, uint16_t power, uint16_t m)
{
    uint16_t res = 1;
    while(power)
    {
        if(power & 1)
        {
            res = (res * base) % m;
        }
        res = (res*res) % m;
        power >>= 1;
    }
    return  res;
}

If your uC has an efficient modulo instruction, this is usually good enough. However, if you don't and know that n will always be a certain value, there is an efficient division (and thus modulo) implementation by T. Granlun and P.L. Montomery. Agner Fog also has a description of how this works.

Here's a hacked implementation for m=23.

uint16_t mod23(uint16_t m)
{
    // note: I didn't actually figure out what n and the error correction term is suppose
    // to be, I just guessed a value for n which produces a simple function
    // only checked to be correct for m <= 484
    // 
    // n = 11
    uint16_t res = a - 23*((m*89)>>11);
    return (res == 23) ? 0 : res;
}

The only required 16-bit operations then are:

• addition/subtraction
• multiplication
• bitwise shifting
• bitwise and
• equality comparison

I'm not familiar with the PIC instruction set, but here's roughly a worst-case instructions count:

• 4*log2(power) comparisons
• 4*log2(power) jumps
• 2*log2(power) subtractions
• 3*log2(power) bitwise shift
• 6*log2(power) multiplications

For power=15, this is roughly 76 instructions. Note that this can go down if you have access to multiply-add instructions or other special instructions. I would consider this quite reasonable.

note: This implementation has variable timings for how long exp_mod takes depending on the input parameter, so is vulnerable to timing-based cracks (though for a 16-bit key, can just be brute-force cracked, too). It's relatively easy to modify this code to be resilient to this by injecting dummy instructions, which in theory should only hurt average performance and worst-case performance is unchanged.

Answer 3

Disclaimer: If you want to do it for educational purpose, go ahead. If you want to use it to actually protect communication, go an get a copy of "Handbook of Applied Cryptography".

As already stated, the problem is not the exponentiation but the modulo operation (if done naively). Montgomery multiplication is an efficient way to solve this. In short, the problem is mapped onto a different group that has the property that the modulo operation can be replaced by bit shifting (and/or memory copy)

I don't know about DH implementations on 8-Bit chips, but I know for sure that there are RSA implementations for 8-Bit microprocessors.