source: rtems/c/src/lib/libbsp/arm/nds/tools/ndstool/source/bigint.cpp @ 9a12c7e5

/*
        big integer class for RSA calculation
        Numbers stored in big endian order.
*/

/*
 * Includes
 */
#include <stdio.h>
#include <string.h>
#include "bigint.h"

/*
 * Sub
 * Subtract (shifted) b from a.
 */
int BigInt::Sub(BigInt &a, BigInt &b, int b_shift)
{
        unsigned int b_byte = sizeof(data) - 1 + (b_shift / 8);
        int b_bit = (b_shift % 8);
        int carry = 0;
        for (int ia=sizeof(data)-1; ia>=0; ia--)
        {
                unsigned char b_data_shifted = 0;
                if (b_byte + 1 < sizeof(b.data)) b_data_shifted |= b.data[b_byte + 1] >> (8 - b_bit);
                if (b_byte + 0 < sizeof(b.data)) b_data_shifted |= b.data[b_byte + 0] << b_bit;
                b_byte--;
                int r = a.data[ia] - b_data_shifted + carry;
                data[ia] = r;
                carry = r>>8;
        }
        return carry;
}

/*
 * MulMod
 * Multiply two numbers and perform modulo.
 */
void BigInt::MulMod(BigInt &a, BigInt &b, BigInt &m)
{
        memset(this, 0, sizeof(*this));
        for (unsigned int ia=sizeof(data) - 1; ia>=sizeof(data)/2; ia--)
        {
                int carry = 0;
                for (unsigned int ib=sizeof(data) - 1; ib>=sizeof(data)/2; ib--)
                {
                        int iab = ia + ib - sizeof(data) + 1;
                        unsigned int r = a.data[ia] * b.data[ib] + carry + data[iab];
                        data[iab] = r;
                        carry = r>>8;
                }
        }

        for (int shift=sizeof(data)/2*8; shift>=0; shift--)
        {
                BigInt subbed;
                if (!subbed.Sub(*this, m, shift))       // positive?
                {
                        memcpy(this, &subbed, sizeof(*this));
                }
        }
}

/*
 * PowMod
 * Raise to power 65537 and perform modulo.
 */
void BigInt::PowMod(BigInt &n, BigInt &m)
{
        BigInt n65536;
        memcpy(&n65536, &n, sizeof(n));
        for (int i=0; i<16; i++)        // 16 times n^2 = n^65536
        {
                BigInt tmp;
                tmp.MulMod(n65536, n65536, m);
                memcpy(&n65536, &tmp, sizeof(n));
        }
        MulMod(n, n65536, m);   // final result: n^1 * n^65536
}

/*
 * print
 */
void BigInt::print()
{
        printf("0x");
        bool show = false;
        for (unsigned int i=0; i<sizeof(data); i++)
        {
                if (data[i]) show = true;
                if (show) printf("%02X", data[i]);
        }
        printf(show ? "\n" : "0\n");
}

/*
 * Set
 */
void BigInt::Set(unsigned char *data, unsigned int length)
{
        memset(this, 0, sizeof(*this));
        memcpy(this->data + sizeof(this->data) - length, data, length);
}

/*
 * Get
 */
void BigInt::Get(unsigned char *data, unsigned int length)
{
        memcpy(data, this->data + sizeof(this->data) - length, length);
}