Join Log in
Score:2
Maarten Bodewes avatar Crypto

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

in flag
Maarten Bodewes

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?

91
1 + 1
rsa
Maarten Bodewes avatar
in flag
Maarten Bodewes
OK, so I found an old post by Thomas Pornin, our friendly bear [on SO](https://stackoverflow.com/a/5377967/589259). So I guess that `R^2` speeds up `square and multiply` to implement modular exponentiation and that the inverse of `n[0]` helps up speed up the Montgomery modular addition (used for multiplication) within? Does that mean that R^2 is the signature squared mod N?
1
Reply
Score:2
avatar Crypto
pe flag
Samuel Neves

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$.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.