La generazione della chiave privata nell'algoritmo RSA

Nel documento viene descritto il metodo per ottenere la CHIAVE PRIVATA nell’algoritmo RSA a chiave pubblica con l’utilizzo delle congruenze lineari, in quanto queste ultime vengono impiegate, oltre che nel suddetto algoritmo, anche in diversi altri metodi crittografici, come ad esempio nell’algoritmo DSA e nell’algoritmo di El Gamal per la generazione e la verifica della firma digitale. Dopo una introduzione al concetto di frazione continua, a quello di congruenza lineare e di equazioni alle congruenze, si passa ad illustrare un algoritmo per la risoluzione della congruenza lineare Ax ≡ C (mod B) o dell’equazione lineare diofantea
A ⋅ x − B ⋅ y = C dove A, B e C sono numeri interi qualsiasi positivi o negativi. Come caso particolare si prende in considerazione la congruenza del tipo Ax≡1 (mod B) per il calcolo della Chiave Privata. Dopo una breve premessa viene descritto lo sviluppo di un numero razionale in frazione continua arrivando al calcolo del MCD di due numeri. Si passa quindi ad introdurre l’algoritmo riguardante la risoluzione di questo tipo di equazioni o congruenze attraverso i seguenti passi: calcolo delle ridotte; condizioni di risolvibilità dell’equazione; risoluzione delle equazione A⋅ x − B ⋅ y = ±1 e quindi dell'equazione più generale
A ⋅ x − B ⋅ y = C . Viene data poi una concisa panoramica dell’impiego negli algoritmi crittografi citati di questo tipo di congruenza, illustrando poi in dettaglio una sua applicazione riguardante il calcolo della Chiave Privata nell’algoritmo RSA .
Al termine del documento, negli allegati 1 e 2 vengono presentati due programmi in linguaggio Qbasic relativi il primo alla risoluzione di congruenze lineari, il secondo al calcolo della chiave privata nell’algoritmo RSA.

br]