Metodo Kasiski

Da Wikipedia, l'enciclopedia libera.

Il metodo Kasiski è un metodo crittoanalitico per l'attacco del cifrario di Vigénère e dei cifrari ad esso simili. Prende il nome dal maggiore prussiano Friedrich Kasiski, che nel 1863 pubblicò un metodo di decifratura della tavola di Vigénère.[1]

Il maggiore Kasiski notò che spesso in un crittogramma di Vigénère si possono notare sequenze di caratteri identiche, poste ad una certa distanza fra di loro; questa distanza può, con una certa probabilità, corrispondere alla lunghezza della chiave, o a un suo multiplo.

In genere la stessa lettera con il cifrario di Vigénère viene cifrata in modo diverso nelle sue varie occorrenze, come si confà ai cifrari polialfabetici, ma se due lettere del testo in chiaro sono poste ad una distanza pari alla lunghezza della chiave (od un suo multiplo), questo fa sì che vengano cifrate nello stesso modo.

Individuando tutte le sequenze ripetute (cosa che avviene frequentemente in un testo lungo), si può dedurre quasi certamente che la lunghezza della chiave è il massimo comun divisore tra le distanze tra sequenze ripetute, o al più un suo multiplo.

Conoscere la lunghezza n della chiave permette di ricondurre il messaggio cifrato ad n messaggi intercalati cifrati con un cifrario di Cesare facilmente decifrabile.


Esempio di uso del metodo Kasiski[modifica | modifica sorgente]

Quando una stessa porzione di chiave è usata per cifrare una ripetizione contenuta nel testo da cifrare, essa genera una ripetizione corrispondente nel testo cifrato. Questo equivale a dire che l'intervallo fra due gruppi di lettere cifrate uguali è un multiplo della lunghezza della chiave. L'analisi di questi intervalli può quindi fornire la lunghezza della chiave, cioè il numero di alfabeti usati per cifrare. È però necessario individuare e scartare le eventuali ripetizioni che siano semplicemente dovute al caso e non alla ripetizione della chiave (di solito, gruppi di lettere non più lunghi di due o tre caratteri). In sintesi si deve:

  1. Individuare i gruppi di lettere ripetuti ed elencarli indicando le posizioni in cui le loro lettere iniziali si trovano nel crittogramma
  2. Calcolare gli intervalli fra le ripetizioni eseguendo la differenza fra i due numeri
  3. Scomporre questi intervalli in tutti i loro sottomultipli
  4. Individuare i fattori maggiormente ricorrenti, dando più peso a quelli relativi ai gruppi di lettere più lunghi, i quali più difficilmente saranno casuali.

Crittogramma di cui si vuol trovare il periodo:

         10        20        30        40
____.____|____.____|____.____|____.____|
MHSFXQEWYAQSFPCAZUMBXLOEGMDXLAHMRPJNYUWU

         50        60        70        80
____.____|____.____|____.____|____.____|
EXCYKVBVEMMQWLRBWHLQSPBANZAAACAOKNBQJZTE

         90        100       110       120
____.____|____.____|____.____|____.____|
MBPQAPESXGXTJOGQUKMWZKMBXLMVWROGMWKGMULQ

         130
____.____|
FOYJIZ

Tabulazione

__________________________________________________________________________________
|Stringa|Prima |Secon.|Distanza|                Sottomultipli                    |
|       |posiz.|posiz.|        |                dell’intervallo                  |
+-------|------|------|--------|---+---+---+---+---+----+----+----+----+----+----+
|  CA   |   15 |   70 |   55   |   | 5 |   |   |   |    | 11 |    |    |    |    |
|  EM   |   49 |   80 |   31   |   |   |   |   |   |    |    |    |    |    | 31 |
|  GM   |   25 |  112 |   87   |   |   |   |   |   |    |    |    |    |    | 29 |
|  GM   |   25 |  116 |   91   |   |   |   | 7 |   |    |    |    | 13 |    |    |
|  GM   |  112 |  116 |    4   | 4 |   |   |   |   |    |    |    |    |    |    |
|  KM   |   98 |  102 |    4   | 4 |   |   |   |   |    |    |    |    |    |    |
|  LQ   |   59 |  119 |   60   | 4 | 5 | 6 |   |   | 10 |    | 12 |    |    | 15 |
|  MB   |   19 |   81 |   62   |   |   |   |   |   |    |    |    |    |    | 31 |
|  MB   |   81 |  103 |   22   |   |   |   |   |   |    | 11 |    |    |    |    |
|  MBXL |   19 |  103 |   84   | 4 |   | 6 | 7 |   |    |    | 12 |    | 14 | 21 |
|  MW   |   99 |  113 |   14   |   |   |   | 7 |   |    |    |    |    |    |    |
|  OG   |   94 |  111 |   17   |   |   |   |   |   |    |    |    |    |    | 17 |
|  QS   |   11 |   60 |   49   |   |   |   | 7 |   |    |    |    |    |    |    |
|  SF   |    3 |   12 |    9   |   |   |   |   | 9 |    |    |    |    |    |    |
|  XL   |   21 |   28 |    7   |   |   |   | 7 |   |    |    |    |    |    |    |
|  XL   |   28 |  105 |   77   |   |   |   | 7 |   |    | 11 |    |    |    |    |
----------------------------------------------------------------------------------

Fra tutti i sottomultipli si sceglie il periodo 7 perché è originato da un gruppo di lettere lungo, è rappresentato 6 volte e dà un valore ponderato maggiore (7x6=42, 11x3=33, 12x2=24, 4x4=16). È escluso il periodo 31 perché troppo lungo.

Si tratta qui di una cifratura Beaufort, in lingua inglese. Le prime parole del testo decifrato sono: statistics indicate.

Il predecessore di Kasiski[modifica | modifica sorgente]

In realtà già nel 1854 l'eclettico scienziato inglese Charles Babbage aveva individuato un criterio di decifrazione del tutto analogo a quello successivamente elaborato dal Kasiski. Babbage non pubblicò mai questo lavoro, come fece, o meglio "non fece", per molti altri, ma la sua scoperta emerge da un lungo epistolario [2] ed il metodo di decrittazione viene spesso chiamato Babbage-Kasiski.

Bibliografia[modifica | modifica sorgente]

  • David Kahn, The Codebreakers - The Story of Secret Writing, Macmillan, 1967; seconda edizione: Scribner, 1996. pp. 207-213; tradotto in italiano in edizione ridotta come La Guerra dei Codici. La storia dei codici segreti, Mondadori, 1969, pp. 162-166.

Note[modifica | modifica sorgente]

  1. ^ Die Geheimschriften und die Dechiffrir-kunst (Le scritture segrete e l'arte della decifrazione)
  2. ^ Simon Singh, Codici & segreti, Rizzoli Editore, 1999, Milano, ISBN 88-17-86213-4, pagg. 67-79