Crittografia
Indice
Software
Link
Errata

Software Crittografico

Introduzione alla Crittografia, Alessandro Languasco & Alessandro Zaccagnini, Ulrico Hoepli Editore, Milano, 2004.

In questa pagina raccogliamo qualche programma in C/C++ o PARI/GP: naturalmente non abbiamo alcuna pretesa di completezza, né abbiamo velleità stilistiche. Si tratta semplicemente di un servizio ai nostri Lettori che potranno utilizzare il nostro codice sorgente come base per fare di meglio. Per esempio, come esercizio consigliamo di riscrivere tutto il codice C/C++ utilizzando la libreria CLN (Class Library for Numbers) per trattare interi arbitrari.

Script PARI/GP

Questi sono gli script dati nel Capitolo 9, nell'ordine in cui compaiono nel testo. Si riferiscono alla versione 2.1.4 di PARI/GP.

  1. Verifica di congetture
  2. Codifica e decodifica con RSA §9.6.2, pagina 271; vedi anche il §5.9
  3. Criteri di primalità
  4. Algoritmi di fattorizzazione

Alcuni degli script precedenti possono essere un po' migliorati usando delle caratteristiche di versioni piú recenti di PARI/GP. In particolare i seguenti possono essere usati a partire dalla versione 2.2.9.

  1. Codifica e decodifica con RSA §9.6.2, pagina 271; vedi anche il §5.9
Inseriamo anche altri script non riportati nel testo e che si riferiscono alla versione 2.2.9 e seguenti di PARI/GP.
  1. Legge di gruppo
  2. Algoritmo di Euclide e formula di Bezout
  3. Crittografia Classica
  4. Crittosistema di ElGamal
  5. Tabelle di Primi
  6. Algoritmi di fattorizzazione
  7. Metodo dei quadrati ripetuti

Programmi in C/C++

Questi programmi illustrano gli algoritmi descritti nel libro: per semplicità sono scritti in C++ standard, e per la maggior parte non richiedono l'uso di librerie esterne per i calcoli con interi a lunghezza arbitraria. Questo significa che, dal punto di vista delle applicazioni alla crittografia, questi programmi non sono molto realistici.

N. B. Avvertiamo che alcuni compilatori non accettano dichiarazioni di long long integer (o le trasformano tacitamente in long integer), e di conseguenza, in questo caso, i risultati ottenuti compilando i nostri programmi potrebbero discostarsi in modo anche rilevante da quelli indicati nel libro.
Inoltre, i valori assegnati staticamente ad alcune variabili potrebbero creare problemi di allocazione di memoria su alcuni computer. In questo caso consigliamo di diminuire i valori indicati nei nostri programmi.
Questi programmi sono stati provati con
g++ (GCC) 3.4.2
Copyright (C) 2004 Free Software Foundation, Inc.

  1. Aritmetica di base Questa piccola libreria contiene le operazioni aritmetiche di base, e deve essere inclusa negli altri programmi.
    • Algoritmo di Euclide, §6.2
    • Algoritmo di Euclide esteso, §6.2
    • Moltiplicazione veloce modulo n, §6.9.1
    • Esponenziazione veloce modulo n, §6.9.2
    • Divisione con resto, §6.9.4
  2. Ricerca di pattern in un testo Vedi la didascalia della Figura 5.3, §5.3
  3. Codifica-decodifica RSA §5.9
  4. Crivello di Eratostene §6.3
  5. Algoritmi di fattorizzazione
  6. Ricerca di un generatore modulo p: Algoritmo di Gauss §6.7
  7. Calcolo del logaritmo discreto modulo p: Algoritmo di Shanks §6.8.1
N. B. Abbiamo testato questi programmi anche con un secondo compilatore e con una diversa libreria per l'aritmetica intera a lunghezza arbitraria. In particolare utilizzando
c++ (GCC) 3.3 20030304 (Apple Computer, Inc. build 1666)
Copyright (C) 2002 Free Software Foundation, Inc.
e la libreria NTL di V. Shoup NTL (Number Theory Library) è necessario sostituire i seguenti files ai corrispondenti predecentemente elencati.
  1. Crivello di Eratostene
  2. metodo ρ di Pollard (N.B.: Questo programma ha bisogno della libreria NTL).

Ultimo aggiornamento: 15.12.2010: 12:55:01.

Crittografia Indice Software Link Errata
© Alessandro Languasco & Alessandro Zaccagnini 2010