What's the use of storing R^2 with a public key?

Question

I think I have successfully reverse engineered a Samsung RSA public key here. However, the public key mainly seems to consist of the modulus, but it also contains a 32 bit integer -1 / n[0] mod 2^32, i.e. the inverse of the first 32-bit word of the modulus as well as R^2 (possibly mod n?).

Can anybody explain why these values are included with the RSA public key? What could these values do? I first thought about maybe protection against side channel attacks, but that doesn't make sense for the public key.

---

Found out a bit more information in the source code:

/* montgomery c[] += a * b[] / R % mod */
static void montMulAdd(const RSAPublicKey *key,
                       uint32_t* c,
                       const uint32_t a,
                       const uint32_t* b) {
    uint64_t A = (uint64_t)a * b[0] + c[0];
    uint32_t d0 = (uint32_t)A * key->n0inv;                      // <--- HERE
    uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
    int i;


    for (i = 1; i < key->len; ++i) {
        A = (A >> 32) + (uint64_t)a * b[i] + c[i];
        B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
        c[i - 1] = (uint32_t)B;
    }


    A = (A >> 32) + (B >> 32);


    c[i - 1] = (uint32_t)A;


    if (A >> 32) {
        subM(key, c);
    }
}

and

/* In-place public exponentiation.
** Input and output big-endian byte array in inout.
*/
static void modpow3(const RSAPublicKey *key,
                    uint8_t* inout) {
    uint32_t a[RSANUMWORDS];
    uint32_t aR[RSANUMWORDS];
    uint32_t aaR[RSANUMWORDS];
    uint32_t *aaa = aR;  /* Re-use location. */
    int i;


    /* Convert from big endian byte array to little endian word array. */
    for (i = 0; i < key->len; ++i) {
        uint32_t tmp =
            (inout[((key->len - 1 - i) * 4) + 0] << 24) |
            (inout[((key->len - 1 - i) * 4) + 1] << 16) |
            (inout[((key->len - 1 - i) * 4) + 2] << 8) |
            (inout[((key->len - 1 - i) * 4) + 3] << 0);
        a[i] = tmp;
    }


    montMul(key, aR, a, key->rr);  /* aR = a * RR / R mod M   */ // <-- HERE
    montMul(key, aaR, aR, aR);     /* aaR = aR * aR / R mod M */
    montMul(key, aaa, aaR, a);     /* aaa = aaR * a / R mod M */


    /* Make sure aaa < mod; aaa is at most 1x mod too large. */
    if (geM(key, aaa)) {
        subM(key, aaa);
    }


    /* Convert to bigendian byte array */
    for (i = key->len - 1; i >= 0; --i) {
        uint32_t tmp = aaa[i];
        *inout++ = tmp >> 24;
        *inout++ = tmp >> 16;
        *inout++ = tmp >> 8;
        *inout++ = tmp >> 0;
    }
}

So I presume both are used to speedup modular exponentiation for when using public exponent 3? If so, can anybody indicate the algorithm(s) used?

Answer 1

The simplest possibility is that those values are included to make the implementation as simple as possible. Namely, the only primitive needed for the exponentiation is Montgomery multiplication.

The core mechanism of Montgomery multiplication is the modular reduction, which consists essentially of Hensel's division method preserving solely the remainder. If you have an odd modulus $n < 2^b$, and some value $x < n^2$, Montgomery reduction computes $$ \frac{x + n\left(xn' \bmod 2^b\right)}{2^b}\,, $$ with $n' = -n^{-1} \bmod 2^b$ (the implementation above uses the truncated value $n' = -n^{-1} \bmod 2^{32}$, which is enough for simple quadratic implementations.). This ensures that a) the result is $x2^{-b} \bmod n$, b) the division by $2^b$ is trivial, since $x + n\left(xn' \bmod 2^b\right)$ is a multiple of $2^b$ by design, and c) the result is size-reduced to at most $2n$.

When composing several operations modulo $n$, such as in an exponentiation, it is convenient to put the operands into "Montgomery form", that is $x \mapsto x2^b \bmod n$. This is because Montgomery multiplication will multiply the operands and reduce them using the above trick. So, $$ \text{MontMul}(x2^b, y2^b) = \frac{x2^b\cdot y2^b}{2^b} \bmod n = xy2^b \bmod n\,, $$ thus preserving the Montgomery form for the next operation.

There are several ways to convert arguments into Montgomery form. One of them is to compute $x\cdot 2^b \bmod n$ manually, using long division. This is unfortunate, because it will require extra complicated code to perform said division. The alternative is to use Montgomery multiplication itself to compute $$ \text{MontMul}(x, 2^{2b}) = \frac{x\cdot 2^{2b}}{2^b} \bmod n = x2^b \bmod n\,. $$ This, however, requires precomputing $2^{2b} \bmod n$ somewhere, which is exactly what the public key format above does.

To convert a value $x2^b \bmod n$ back to normal form, it suffices to multiply it by $1$ using Montgomery multiplication. Or, alternatively, as this implementation does, multiply $x^22^b$ by $x$ to obtain $\frac{x^32^b}{2^b} \bmod n = x^3 \bmod n$.