Guide

Appendice 5: Cenni di implementazione efficiente di algoritmi

Molte cifratura a chiave pubblica e schemi di firma digitale, e alcune funzioni hash, richiedono calcoli in Zm, gli interi modulo m (m è un numero intero positivo molto grande che può essere primo o meno)., e anche su altre strutture algebriche come anelli polinomiali, campi finiti e gruppi ciclici finiti. L’efficienza di questi schemi dipenderà da un certo numero di fattori come la grandezza dei parametri, compromessi tempo-memoria, potenza di calcolo disponibile, ottimizzazione di hardware e software ed altro ancora; ad esempio la tecnologia dei chip su carte di credito e affini preferisce algoritmi meno efficienti nel tempo ma più efficienti nella richiesta di memoria. Questi algoritmi hanno avuto una considerevole attenzione in letteratura, a cui si invita per un approfondimento maggiore, partendo dai testi citati nella bibliografia.

Aritmetica multi precisione: i numeri interi positivi sono rappresentabili su base, o radice, b in questo modo: con e (ai sono le cifre). Se an e diverso da zero, l’ordine, o lunghezza, è n+1. Se n=0 l’intero è a precisione singola, altrimenti è a multi precisione. I problemi sorgono quando, con la rappresentazione in base 2, gli interi sono, ad esempio, a 512bit, o cifre binarie, visto che i normali computer hanno registri di una parola di 32bit (64 bit nel caso di doppia parola), e hanno difficoltà a maneggiare tali numeri. Qui entrano in gioco librerie particolari che lavorano su numeri multiparola, operando sulle cifre di rappresentazione anziché sul numero intero. Ecco un esempio di algoritmo per la riduzione a modulo veloce ad opera di Chivers (1984):

dato un intero dove la base b è la più conveniente lunghezza di parola. Quindi questo implica che il Massimo Comun Divisore (MCD) può essere rimosso, il suo resto modulo m aggiunto alle cifre rimanenti risulterà essere un numero che è congruente modulo m all’originale. L’implementazione Pascal è la seguente:

Prima si costruisce un array R=(bd, 2bd, …, (b-1)bd)(mod m), poi

FOR i = n-1 to d do Dove A[i] è l’i-esima cifra del numero A

WHILE A[i] != 0 do R[j] è il j-esimo intero residuo dal vettore R

j = A[i]; R[j] è il j-esimo intero residuo dal vettore R

A[i] = 0; n è il numero di cifre in A

A = A + bi-d.R[j]; d è il numero di cifre nel modulo

END WHILE

END FOR

Un altro esempio è l’algoritmo di moltiplicazione intera di Schonhage-Strassen, utile per la velocizzazione del RSA; infatti la moltiplicazione convenzionale prende O(n2) operazioni su bit, questo algoritmo solo O(n log n). Prima spezza ogni intero in blocchi e li usa come coefficienti di polinomi (uno per ogni numero), dunque valuta questi polinomi in punti opportuni e moltiplica i valori risultanti. Il polinomio prodotto è ricostruito con l’interpolazione di questi valori (tramite trasformata discreta di Fourier e il teorema della convoluzione) e si recupera dai suoi coefficienti il prodotto degli interi originali. Purtroppo ha bisogno di hardware specializzato perché le unità aritmetiche convenzionali non si ingrandiscono a causa dei ritardi di propagazione del riporto, per cui usa riporti serie-parallelo con O(n) porte per moltiplicare in O(n) operazioni su bit, oppure usa tecniche serie-parallelo con O(n2) porte per moltiplicare in O(log n) operazioni.

Un altro modo per velocizzare l’RSA sfrutta il teorema del resto Cinese (vedi appendice 1), basandosi anziché sul modulo n, su due moduli distinti p e q (tali che n=pq), molto più piccoli e quindi assai più semplici.

Decifratura con RSA classico (con M messaggio, C crittogramma, d chiave privata):

M = Cd mod n

Sfruttando il CRT invece ho una coppia di equazioni la cui soluzione è nota:

M1 = M mod p= (C mod p)d mod (p-1)

M2 = M mod q= (C mod q)d mod (q-1)

Le due equazioni da risolvere sono dunque:

M = M1 mod p

M = M2 mod q

Questo sistema ha un’unica soluzione data dal CRT

M = [(M2 + q – M1)U mod q] p + m1 (dove p U mod q = 1)