Implementazione di RSA senza allocazione dinamica

Question

Una tipica implementazione RSA incorpora una libreria di numeri interi a più precisione. Una tipica libreria di interi a più precisione utilizza l'allocazione dinamica per rappresentare interi di grandi dimensioni come array di parole di macchina della giusta dimensione.

Mi aspetto che ci debba essere un limite sugli interi matematici che si possono incontrare quando si utilizzano gli interi multi-precision solo per crittografare o decrittografare messaggi di lunghezza nota (tipicamente, chiavi di crittografia simmetriche) con, ad esempio, RSA-2048, e che sarebbe possibile implementare l'algoritmo allocando lo spazio per tutti i risultati intermedi necessari sia staticamente che in pila.

Ho trovato this forum thread suggerendo che ciò è possibile. Non indica le dimensioni massime integer. Forse è ovvio ("hai bisogno di 2048 bit per tutti gli interi, duh!"). In ogni caso, sarei più interessato a un'implementazione già esistente, se ce n'è una.

Come una domanda secondaria che non merita il proprio ingresso, le implementazioni tipiche della crittografia a curva ellittica richiedono allocazione dinamica?

Answer 1

E 'possibile implementare una classe intero multi-precisione, senza l'allocazione dinamica

Sì.

Sono a conoscenza di un'implementazione simile in C# BigInteger Class. (E non regge ciò che fa il runtime di clr sottostante).

Non sono a conoscenza di alcun buffer di dimensioni statiche in C/C++. Ma conosco solo Botan, Crypto ++ e OpenSSL.

Da quello che ho visto delle implementazioni, l'esponente pubblico e a volte ottiene un'ottimizzazione che lo rende un int o long. Ma n e d sono multi-precisione. (E mi piacerebbe vedere come questo scoppi un giorno).

Infine, i router e altri dispositivi a bassa potenza spesso sfruttano questa ottimizzazione per inviare e ricevere buffer (lavoro con un ragazzo che era un ingegnere elettrico e progettava router). Si riservano semplicemente un blocco di memoria e il software utilizza un indice per accedere al buffer statico. Quindi non è difficile credere che abbiano preso l'ottimizzazione di cui parli.

---

RSA-2048 e che sarebbe possibile implementare l'algoritmo allocando spazio per tutti i necessari risultati intermedi staticamente o in pila.

Sì, è possibile farlo con uno schema di magnitudine del segno utilizzando buffer di dimensioni fisse se si accetta di limitare la dimensione massima del modulo RSA o la dimensione del campo primo CE.

Una chiave pubblica RSA è (e, n). Nonostante l'avviso sui piccoli e, sono necessari due buffer di 2048/8 = 256 byte o ottetti.

Una chiave privata RSA senza trucchi precomputazione è semplicemente (e, d, n). Quindi avresti bisogno di tre buffer di 256 byte o ottetti.

Se si stava lavorando su un PDP-8 con byte da 12 bit, sarebbero necessari meno byte.

---

Non indica le dimensioni massime interi.

Il diavolo nel dettaglio è probabilmente una moltiplicazione. Quindi avresti bisogno di un buffer scratch per eseguire la moltiplicazione. Ciò significa che avrai bisogno di un buffer di dimensioni 2 ~ 2048 bit (moltiplicando 2 buffer m crea un risultato della dimensione 2m -1). Il risultato della moltiplicazione dovrebbe quindi essere ridotto. Potrebbero essere ulteriori ottimizzazioni, ma di solito non mi occupo di quei dettagli.

Correlate, la dimensione massima del messaggio e la dimensione massima del testo cifrato sono relative a n. In Crpyto ++, possono essere recuperati con MaxPreImageSize (per il testo normale) e MaxImageSize (per il testo cifrato). MaxPreImageSize e MaxImageSize restituiscono n - 1.

---

Come un lato, domanda che non merita la propria voce, non implementazioni tipiche della crittografia a curva ellittica richiedono l'allocazione dinamica?

Dipende dall'implementazione sottostante. Una curva su un campo primo è definito dai parametri di dominio (da Certicom di SEC1, Elliptic Curve Domain Parameters, sezione 3, pagina 16):

Elliptic curve domain parameters over F_p are a sextuple: 

    T = (p, a, b, G, n, h) 

• p è un grande primo e ha bisogno di un intero multi-precisione

• a e b sono i coefficienti che definiscono la curva. Solitamente sono "piccoli" (ad esempio, a = 3), ma potrebbero richiedere numeri interi multi-precisione per curve non standard. Ad esempio, la curva ed25519 di DJB è y^2 = x^3 - 102314837768112 x + 398341948620716521344.

• G è il punto base, quindi è davvero un elemento (o punto) sulla curva. Ciò significa che è una coordinata (X, Y) e probabilmente richiede un numero intero a più precisione.

• n è un numero primo ordine G che significa che è nealry grande come n

• h è il cofattore e il suo solito molto piccola: 4 o 2, o 1.

Quando si crea una coppia di chiavi per la curva, è necessario un esponente privato casuale d (o x) e che crea un elemento (punto sulla curva) dopo l'esponenziazione. Cioè, chiave pubblica (X, Y) = G^x. Quindi hai altri tre numeri interi multi-precisione.

Una curva su un file binario richiede un modo per esprimere il polinomio. Quindi probabilmente avresti ancora bisogno del numero multi-precision (usato per p nel campo principale).

Quindi, la maggior parte delle "cose" su una curva ellittica necessitano di un numero multi-precisione.

È possibile visualizzare esempi dei parametri del dominio, ad esempio, Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation.

Answer 2

Questo RSA implementation, all'interno di BearSSL, di Thomas Pornin, ha esattamente le proprietà che stavo chiedendo. Dalla pagina web di BearSSL:

Nessuna allocazione dinamica di sorta. Non c'è una sola chiamata malloc() in tutta la libreria.

...

sul grande desktop e sistema operativo per server, questa funzionalità offre ancora una caratteristica interessante: l'immunità per le perdite di memoria e attacchi DoS basati sulla memoria. Gli utenti esterni non possono rendere BearSSL allocare megabyte di RAM poiché BearSSL in realtà non sa come allocare la RAM.