Wie mit massiven Zahlen in C

Question

umgehen

Ich schreibe einen RSA-Verschlüsselungsalgorithmus in C. Ich plane nicht, es überall in Produktion zu bringen, es ist hauptsächlich nur so, dass ich mein Verständnis von Verschlüsselung erweitern kann.

Wie gehe ich mit den riesigen Zahlen um, die RSA generiert? Selbst wenn die Entschlüsselung mit einem relativ kleinen privaten Schlüsseln wie 103 durchgeführt wird, ich habe immer noch das Problem mit Dingen wie dies zu tun:

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

Was ist der beste Weg, um eine Nummer dieser Größe zu speichern? Gibt es eine Möglichkeit, dies mit Standardbibliotheken zu tun? .

Answer 1

Falsche Annäherung. 67^103 mod 143 muss nicht zuerst 67^103 berechnen.

Berechnen Sie die modulo in einer Schleife, 1 Bit des Exponenten zu einem Zeitpunkt.

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)); 
} 

Ausgabe

89