înregistrare Logare
Puncte:2
Maarten Bodewes avatar Crypto

La ce folosește stocarea R^2 cu o cheie publică?

drapel in
Maarten Bodewes

Cred că am realizat cu succes o inginerie inversă a unei chei publice Samsung RSA Aici. Cu toate acestea, cheia publică pare să fie formată în principal din modul, dar conține și un număr întreg de 32 de biți -1 / n[0] mod 2^32, adică inversul primului cuvânt de 32 de biți al modulului, precum și R^2 (posibil mod n?).

Poate cineva să explice de ce aceste valori sunt incluse cu cheia publică RSA? Ce ar putea face aceste valori? M-am gândit mai întâi la protecția împotriva atacurilor pe canale secundare, dar asta nu are sens pentru cheia publică.

Aflați puțin mai multe informații în codul sursă:

/* 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 * cheie->n0inv; // <--- AICI
    uint64_t B = (uint64_t)d0 * cheie->n[0] + (uint32_t)A;
    int i;


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


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


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


    dacă (A >> 32) {
        subM(cheie, c);
    }
}

și

/* Exponentiație publică pe loc.
** Intrare și ieșire matrice de octeți big-endian în 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; /* Reutilizați locația. */
    int i;


    /* Convertiți din matrice de octeți big endian în matrice de cuvinte little endian. */
    pentru (i = 0; i < cheie->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 */ // <-- AICI
    montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
    montMul(key, aaa, aaR, a); /* aaa = aaR * a / R mod M */


    /* Asigurați-vă că aaa < mod; aaa este cel mult 1x mod prea mare. */
    dacă (geM(cheie, aaa)) {
        subM(cheie, aaa);
    }


    /* Convertiți în matrice de octeți bipendian */
    pentru (i = cheie->len - 1; i >= 0; --i) {
        uint32_t tmp = aaa[i];
        *inout++ = tmp >> 24;
        *inout++ = tmp >> 16;
        *inout++ = tmp >> 8;
        *inout++ = tmp >> 0;
    }
}

Deci presupun că ambele sunt folosite pentru a accelera exponentiația modulară atunci când se utilizează exponentul public 3? Dacă da, poate cineva să indice algoritmul (algoritmii) folosit(i)?

91
1 + 1
Maarten Bodewes avatar
drapel in
Maarten Bodewes
OK, așa că am găsit o postare veche a lui Thomas Pornin, ursul nostru prietenos [pe SO](https://stackoverflow.com/a/5377967/589259). Deci, presupun că `R^2` accelerează `pătrat și înmulțire` pentru a implementa exponentiația modulară și că inversul lui `n[0]` ajută la accelerarea adunării modulare Montgomery (utilizată pentru înmulțire) în interiorul? Înseamnă asta că R^2 este semnătura pătratul mod N?
1
Răspunde
Puncte:2
avatar Crypto
drapel pe
Samuel Neves

Cea mai simplă posibilitate este ca acele valori să fie incluse pentru a face implementarea cât mai simplă. Și anume, singura primitivă necesară pentru exponențiere este înmulțirea Montgomery.

Mecanismul de bază al înmulțirii Montgomery este reducerea modulară, care constă în principal din metoda diviziunii lui Hensel care păstrează doar restul. Dacă aveți un modul impar $n < 2^b$, și ceva valoare $x < n^2$, Reducerea Montgomery calculează $$ \frac{x + n\left(xn' \bmod 2^b\right)}{2^b}\,, $$ cu $n' = -n^{-1} \bmod 2^b$ (implementarea de mai sus folosește valoarea trunchiată $n' = -n^{-1} \bmod 2^{32}$, ceea ce este suficient pentru implementări pătratice simple.). Acest lucru asigură că a) rezultatul este $x2^{-b} \bmod n$, b) împărțirea la $2^b$ este banal, din moment ce $x + n\left(xn' \bmod 2^b\right)$ este un multiplu al $2^b$ prin proiectare și c) rezultatul este redus în dimensiune la cel mult 2n$.

La alcătuirea mai multor operații modulo $n$, cum ar fi într-o exponențiere, este convenabil să puneți operanzii în „forma Montgomery”, adică $x \mapsto x2^b \bmod n$. Acest lucru se datorează faptului că înmulțirea Montgomery va înmulți operanzii și îi va reduce folosind trucul de mai sus. Asa de, $$ \text{MontMul}(x2^b, y2^b) = \frac{x2^b\cdot y2^b}{2^b} \bmod n = xy2^b \bmod n\,, $$ păstrând astfel forma Montgomery pentru următoarea operațiune.

Există mai multe moduri de a converti argumentele în formă Montgomery. Una dintre ele este să calculezi $x\cdot 2^b \bmod n$ manual, folosind diviziunea lungă. Acest lucru este regretabil, deoarece va necesita un cod foarte complicat pentru a efectua respectiva împărțire. Alternativa este să folosiți înmulțirea Montgomery în sine pentru a calcula $$ \text{MontMul}(x, 2^{2b}) = \frac{x\cdot 2^{2b}}{2^b} \bmod n = x2^b \bmod n\,. $$ Totuși, acest lucru necesită precalculare $2^{2b} \bmod n$ undeva, care este exact ceea ce face formatul cheii publice de mai sus.

Pentru a converti o valoare $x2^b \bmod n$ înapoi la forma normală, este suficient să o înmulțim cu $1$ folosind înmulțirea Montgomery. Sau, alternativ, așa cum face această implementare, înmulțiți $x^22^b$ de $x$ a obtine $\frac{x^32^b}{2^b} \bmod n = x^3 \bmod n$.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.