Come gestire massicci numeri in C

Question

Sto scrivendo un algoritmo di crittografia RSA in C. Non sto pianificando di metterlo in produzione da nessuna parte, è principalmente solo così posso ampliare la mia comprensione della crittografia.

Come si gestiscono i numeri massicci generati da RSA? Anche durante l'esecuzione di decrittazione con un relativamente piccolo chiave privata come 103, ho ancora il problema di affrontare le cose in questo modo:

67^103 mod 143 = (1,21816096336830017301951805581 x 10^188) mod 143

Qual è il modo migliore per memorizzare un numero di tale dimensione? C'è un modo per farlo usando le librerie standard? .

Answer 1

Approccio errato. 67^103 mod 143 non ha bisogno di calcolare prima 67^103.

Calcolare il modulo in un ciclo, 1 bit di esponente alla volta.

uint32_t powmod(uint32_t base, uint32_t expo, uint32_t mod) { 

    // % mod need only for the cases expo==0, mod<=1 
    uint32_t y = 1u % mod; 

    while (expo) { 
    if (expo & 1u) { 
     y = ((uint64_t) base * y) % mod; 
    } 
    expo >>= 1u; 
    base = ((uint64_t) base * base) % mod; 
    } 

    return y; 
} 

int main(void) { 
    printf("%lu",(unsigned long) powmod(67, 103, 143)); 
} 

uscita

89