lib/nanohub/rsa.c

/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <nanohub/rsa.h>


static bool biModIterative(uint32_t *num, const uint32_t *denum, uint32_t *tmp, uint32_t *state1, uint32_t *state2, uint32_t step)
//num %= denum where num is RSA_LEN * 2 and denum is RSA_LEN and tmp is RSA_LEN + limb_sz
//will need to be called till it returns true (up to RSA_LEN * 2 + 2 times)
{
    uint32_t bitsh = *state1, limbsh = *state2;
    bool ret = false;
    int64_t t;
    int32_t i;

    //first step is init
    if (!step) {
        //initially set it up left shifted as far as possible
        memcpy(tmp + 1, denum, RSA_BYTES);
        tmp[0] = 0;
        bitsh = 32;
        limbsh = RSA_LIMBS - 1;
        goto out;
    }

    //second is shifting denum
    if (step == 1) {
        while (!(tmp[RSA_LIMBS] & 0x80000000)) {
            for (i = RSA_LIMBS; i > 0; i--) {
                tmp[i] <<= 1;
                if (tmp[i - 1] & 0x80000000)
                    tmp[i]++;
            }
            //no need to adjust tmp[0] as it is still zero
            bitsh++;
        }
        goto out;
    }

    //all future steps do the division

    //check if we should subtract (uses less space than subtracting and unroling it later)
    for (i = RSA_LIMBS; i >= 0; i--) {
        if (num[limbsh + i] < tmp[i])
            goto dont_subtract;
        if (num[limbsh + i] > tmp[i])
            break;
    }

    //subtract
    t = 0;
    for (i = 0; i <= RSA_LIMBS; i++) {
        t += (uint64_t)num[limbsh + i];
        t -= (uint64_t)tmp[i];
        num[limbsh + i] = t;
        t >>= 32;
    }

    //carry the subtraction's carry to the end
    for (i = RSA_LIMBS + limbsh + 1; i < RSA_LIMBS * 2; i++) {
        t += (uint64_t)num[i];
        num[i] = t;
        t >>= 32;
    }

dont_subtract:
    //handle bitshifts/refills
    if (!bitsh) {                          // tmp = denum << 32
        if (!limbsh) {
            ret = true;
            goto out;
        }

        memcpy(tmp + 1, denum, RSA_BYTES);
        tmp[0] = 0;
        bitsh = 32;
        limbsh--;
    }
    else {                                 // tmp >>= 1
        for (i = 0; i < RSA_LIMBS; i++) {
            tmp[i] >>= 1;
            if (tmp[i + 1] & 1)
                tmp[i] += 0x80000000;
        }
        tmp[i] >>= 1;
        bitsh--;
    }


out:
    *state1 = bitsh;
    *state2 = limbsh;
    return ret;
}

static void biMulIterative(uint32_t *ret, const uint32_t *a, const uint32_t *b, uint32_t step) //ret = a * b, call with step = [0..RSA_LIMBS)
{
    uint32_t j, c;
    uint64_t r;

    //zero the result on first call
    if (!step)
        memset(ret, 0, RSA_BYTES * 2);

    //produce a partial sum & add it in
    c = 0;
    for (j = 0; j < RSA_LIMBS; j++) {
        r = (uint64_t)a[step] * b[j] + c + ret[step + j];
        ret[step + j] = r;
        c = r >> 32;
    }

    //carry the carry to the end
    for (j = step + RSA_LIMBS; j < RSA_LIMBS * 2; j++) {
        r = (uint64_t)ret[j] + c;
        ret[j] = r;
        c = r >> 32;
    }
}

/*
 * Piecewise RSA:
 * normal RSA public op with 65537 exponent does 34 operations. 17 muls and 17 mods, as follows:
 * 16x {mul, mod} to calculate a ^ 65536 mod c
 * 1x {mul, mod} to calculate a ^ 65537 mod c
 * we break up each mul and mod itself into more steps. mul needs RSA_LIMBS steps, and mod needs up to RSA_LEN * 2 + 2 steps
 * so if we allocate RSA_LEN * 3 step values to mod, each mul-mod pair will use <= RSA_LEN * 4 step values
 * and the whole opetaion will need <= RSA_LEN * 4 * 34 step values, which fits into a uint32. cool. In fact
 * some values will be skipped, but this makes life easier, really. Call this func with *stepP = 0, and keep calling till
 * output stepP is zero. We'll call each of the RSA_LEN * 4 pieces a gigastep, and have 17 of them as seen above. Each
 * will be logically separated into 4 megasteps. First will contain the MUL, last 3 the MOD and maybe the memcpy.
 * In the first 16 gigasteps, the very last step of the gigastep will be used for the memcpy call.
 *
 * The initial non-iterative RSA logic looks as follows, shown here for clarity:
 *
 *   memcpy(state->tmpB, a, RSA_BYTES);
 *   for (i = 0; i < 16; i++) {
 *       biMul(state->tmpA, state->tmpB, state->tmpB);
 *       biMod(state->tmpA, c, state->tmpB);
 *       memcpy(state->tmpB, state->tmpA, RSA_BYTES);
 *   }
 *
 *   //calculate a ^ 65537 mod c into state->tmpA [ at this point this means do state->tmpA = (state->tmpB * a) % c ]
 *   biMul(state->tmpA, state->tmpB, a);
 *   biMod(state->tmpA, c, state->tmpB);
 *
 *   //return result
 *   return state->tmpA;
 *
 */

const uint32_t* rsaPubOpIterative(struct RsaState* state, const uint32_t *a, const uint32_t *c, uint32_t *state1, uint32_t *state2, uint32_t *stepP)
{
    uint32_t step = *stepP, gigastep, gigastepBase, gigastepSubstep, megaSubstep;

    //step 0: copy a -> tmpB
    if (!step) {
        memcpy(state->tmpB, a, RSA_BYTES);
        step = 1;
    }
    else { //subsequent steps: do real work


        gigastep = (step - 1) / (RSA_LEN * 4);
        gigastepSubstep = (step - 1) % (RSA_LEN * 4);
        gigastepBase = gigastep * (RSA_LEN * 4);
        megaSubstep = gigastepSubstep / RSA_LEN;

        if (!megaSubstep) { // first megastep of the gigastep - MUL
            biMulIterative(state->tmpA, state->tmpB, gigastep == 16 ? a : state->tmpB, gigastepSubstep);
            if (gigastepSubstep == RSA_LIMBS - 1) //MUL is done - do mod next
                step = gigastepBase + RSA_LEN + 1;
            else                                  //More of MUL is left to do
                step++;
        }
        else if (gigastepSubstep != RSA_LEN * 4 - 1){   // second part of gigastep - MOD
            if (biModIterative(state->tmpA, c, state->tmpB, state1, state2, gigastepSubstep - RSA_LEN)) { //MOD is done
                if (gigastep == 16) // we're done
                    step = 0;
                else              // last part of the gigastep is a copy
                    step = gigastepBase + RSA_LEN * 4 - 1 + 1;
            }
            else
                step++;
        }
        else {   //last part - memcpy
            memcpy(state->tmpB, state->tmpA, RSA_BYTES);
            step++;
        }
    }

    *stepP = step;
    return state->tmpA;
}

#if defined(RSA_SUPPORT_PRIV_OP_LOWRAM) || defined (RSA_SUPPORT_PRIV_OP_BIGRAM)
#include <stdio.h>
const uint32_t* rsaPubOp(struct RsaState* state, const uint32_t *a, const uint32_t *c)
{
    const uint32_t *ret;
    uint32_t state1 = 0, state2 = 0, step = 0, ns = 0;

    do {
        ret = rsaPubOpIterative(state, a, c, &state1, &state2, &step);
        ns++;
    } while(step);

fprintf(stderr, "steps: %u\n", ns);

    return ret;
}

static void biMod(uint32_t *num, const uint32_t *denum, uint32_t *tmp)
{
    uint32_t state1 = 0, state2 = 0, step;

    for (step = 0; !biModIterative(num, denum, tmp, &state1, &state2, step); step++);
}

static void biMul(uint32_t *ret, const uint32_t *a, const uint32_t *b)
{
    uint32_t step;

    for (step = 0; step < RSA_LIMBS; step++)
        biMulIterative(ret, a, b, step);
}

const uint32_t* rsaPrivOp(struct RsaState* state, const uint32_t *a, const uint32_t *b, const uint32_t *c)
{
    uint32_t i;

    memcpy(state->tmpC, a, RSA_BYTES);  //tC will hold our powers of a

    memset(state->tmpA, 0, RSA_BYTES * 2); //tA will hold result
    state->tmpA[0] = 1;

    for (i = 0; i < RSA_LEN; i++) {
        //if the bit is set, multiply the current power of A into result
        if (b[i / 32] & (1 << (i % 32))) {
            memcpy(state->tmpB, state->tmpA, RSA_BYTES);
            biMul(state->tmpA, state->tmpB, state->tmpC);
            biMod(state->tmpA, c, state->tmpB);
        }

        //calculate the next power of a and modulus it
#if defined(RSA_SUPPORT_PRIV_OP_LOWRAM)
        memcpy(state->tmpB, state->tmpA, RSA_BYTES); //save tA
        biMul(state->tmpA, state->tmpC, state->tmpC);
        biMod(state->tmpA, c, state->tmpC);
        memcpy(state->tmpC, state->tmpA, RSA_BYTES);
        memcpy(state->tmpA, state->tmpB, RSA_BYTES); //restore tA
#elif defined (RSA_SUPPORT_PRIV_OP_BIGRAM)
        memcpy(state->tmpB, state->tmpC, RSA_BYTES);
        biMul(state->tmpC, state->tmpB, state->tmpB);
        biMod(state->tmpC, c, state->tmpB);
#endif
    }

    return state->tmpA;
}
#endif