BREAKING THE VIGENERE CYPHER
Questo esercizio fa parte del corso di crittografia di Coursera – University of Maryland.
Consegna:
- L’obiettivo è, dato un testo cifrato, ottenere il testo in chiaro.
- Viene data una spiegazione generale del metodo di cifratura Vigenere
- Vengono forniti alcuni dettagli su questa particolare implementazione (usa codice Ascii e uno shift di tipo Add + Modulo)
- Sono forniti consigli su come sia possibile rompere questo sistema crittografico con l’analisi di frequenza
- Viene fornito il codice in C dell’algoritmo di encryption
- E’ disponibile un testo cifrato che occorre decrittare
Esecuzione:
- La prima fase consiste nel trovare la lunghezza della chiave. Si analizza la frequenza dei caratteri nel testo cifrato, “saltando” i caratteri intermedi ad intervalli regolari. Se il salto avviene con il periodo corretto, la frequenza dei caratteri apparirà differente da una distribuzione casuale uniforme.
- Una volta trovata la lunghezza della chiave occorre testare – per ciascuna posizione, o text stream – le varie possibili chiavi ed escludere quelle che danno un risultato incompatibile.
- Si tenta di decrittare i caratteri di uno stream con una chiave. Se risultano appartenere a regioni Ascii incompatibili con il testo, la chiave è scartata e se ne tenta un’altra.
- Sulle le chiavi che restituiscono caratteri leggibili e utili si opera un’analisi di frequenza. La frequenza delle lettere dovrebbe corrispondere a quella che si ritrova nella lingua inglese. Quando ciò avviene, è stata trovata la chiave che decritta tutti i caratteri che si trovano ad una certa distanza fra loro
- Trovate tutte le chiavi è possibile decrittare il testo e scriverlo nella sequenza corretta
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 | #include <stdio.h> #define MAX_KEY_LENGTH 13 #define BYTE_LENGTH 256 #define A_CHAR 97 #include <math.h> /* This code breaks a Vigenere Cipher. The first step determines the length of the key. The second step finds the key values. This code was not meant to be particularly efficient :).*/ double find_length(int n, FILE *fpIn); float do_stream(int i, int stride, unsigned char key, FILE *fpIn); void decipher(unsigned char key[], int key_length, FILE *fpIn); // Frequencies of letters in english language, in alphabetical order double eng_frequencies[] = {.082, .015, .028, .043, .127, .022, .002, .061, .07, .002, .008, .004, .024, .067, .015, .019, .001, .06, .063, .091, .028, .01, .024, .002, .02, .001}; long int txt_length = 0; void main() { FILE *fpIn; int stride = 0; // Length of the key unsigned char keys[MAX_KEY_LENGTH];// Array for storing up to 13 keys {186,31,145,178,83,205,62}; unsigned char ch; // Read cipher text fpIn = fopen("../ctext.txt", "r"); //GET THE CIPHER TEXT LENGTH while (fscanf(fpIn, "%c", &ch) != EOF) txt_length++; txt_length = txt_length/2; printf("TEXT LENGTH: %d\n",txt_length); /* STEP 1: DETERMINE THE KEY LENGTH */ // Tries different lengths of the cypher text, 1-13 double temp_max_freq = 0; double freq = 0; for(int i = 1; i < 14; i++) { // Looks for the maximum sum of squared frequencies for different key lengths. // The highest one should be the not-random one freq = find_length(i, fpIn); if (freq>temp_max_freq) { temp_max_freq = freq; stride = i; } printf("Best key length: %d\n\n\n", stride); } // LENGTH IS 7 /* STEP 2: FIND A KEY FOR EACH TEXT STREAM */ // Manage each stream int h = 0; float temp_ratio = 0; float max_ratio = 0; for(h = 0; h < stride; h++) // For each text stream { max_ratio = 0; for (unsigned char key=0; key<BYTE_LENGTH-1; key++) //Test a different byte for the xor operation { temp_ratio = do_stream(h, stride, key, fpIn); if (temp_ratio>max_ratio) { max_ratio = temp_ratio; keys[h] = key; } } printf("\nKEY: %d\n", keys[h]); } // DECRYPT AND PRINT AS PLAIN TEXT decipher(keys,stride, fpIn); fclose(fpIn); return; } void decipher(unsigned char keys[], int key_length, FILE *fpIn) { /* Prints frequencies. Look where the highest ones are */ unsigned char ch[4]= {0,0}; int nFound = 0; // Every n character, increment its byte counter rewind(fpIn); for (int i=0; i<txt_length; i++) { fscanf(fpIn, "%02X", &ch); printf("%c", ch[0] ^ keys[i % (key_length)],i); // Add, mod 2 cypher }; } float do_stream(int n, int stride, unsigned char key, FILE *fpIn) { unsigned char ch[4]; double hifreq = 0; unsigned int n_lowercase = 0; float ratio; int i = 0; // Discard sequences where at least one // is out of the ascii enghlish text boundaries rewind(fpIn); while (fscanf(fpIn, "%02X", &ch) != EOF) { ch[0] = ch[0] ^ key; if ((i%stride == n) && (ch[0]<=31 || ch[0]>=128)) return 0; i++; } printf("FOUND"); printf("\nstream %d, stride %d, key %d\n", n, stride, key); i=0; rewind(fpIn); while (fscanf(fpIn, "%02X", &ch) != EOF) { ch[0] = ch[0] ^ key; // Decrypt // If the character is a lowercase letter or a space, increment and print if ((i%stride == n) &&((ch[0]>96 && ch[0]<123)||(ch[0]==32))) { printf("%c", ch[0]); n_lowercase++; } //Assign proper weight to each character, according to frequency tables hifreq+= eng_frequencies[ch[0]-A_CHAR]; i++; } // Discard the key, if too few of the characters are lowercase letters if (n_lowercase<(txt_length/(stride+1))) { printf(" >n_lower:%d\n", n_lowercase); return 0; } // Find relative frequencies hifreq = hifreq/i;//n_lowercase; printf("\nhigh: %f; low: %d ", hifreq, i); return hifreq; } double find_length(int n, FILE *fpIn) { /* Prints frequencies. Look where the highest ones are */ unsigned int ch[2]; // Allow more space to prevent overflow unsigned char all_ascii[BYTE_LENGTH] = {0}; double all_freqs[BYTE_LENGTH] = {0}; double all_f_add=0; int nFound = 0; double midvar=0; int i=0; // Every n characters, increment its byte counter rewind(fpIn); while (fscanf(fpIn, "%02X", &ch) != EOF) { if (i%n == 0) { all_ascii[ch[0]] +=1; nFound ++; } i++; } // Compute relative frequency and square it, them add all together for(int l = 0; l < BYTE_LENGTH; l++) { midvar = ((double)all_ascii[l])/nFound; all_f_add += pow(midvar,2); } // Print frequency printf(">%d: %f ", n, all_f_add); return all_f_add; } |
I commenti sono chiusi, ma riferimenti e pingbacks sono aperti.