program Atk;

const MAX_KEY = 30;		{lunghezza massima delle chiavi considerate}
const MAX_TEXT = 2048;	{lunghezza massima del testo}
const MAX_TESTS = 10;	{numero massimo di parole accettate dal programma}
const TOP_CS = 3;		{numero di caratteri più frequenti considerati}
	
{ Somma, sottrazione e inverso di caratteri a-z
 Visti come elementi 0-25 implementa operazioni modulo 26
 'c' + 'x' = 3 + 23 = 26 mod 26 = 0  = 'a' = 97
 'c' - 'x' = 3 - 23 = 20 mod 26 = 20 = 'u' = 117
 -'c' = -3 = 0-3 mod 26 = 23 = 'x' =  120
 Il tutto è allineato all'intervallo 97-122 del codice ASCII}	
function plus(a,b : char):char;
begin
	plus := chr((ord(a) + ord(b) - 194) mod 26 + 97)
end;

function minus(a,b : char):char;
begin
	minus := chr((ord(a) - ord(b) + 26) mod 26 + 97)
end;

function inv(a : char):char;
begin
	inv := minus('a',a)
end;
		
{ Restituisce False se il carattere deve esser ingorato, True altrimenti }
function filter_char(VAR c:char):boolean;
begin
	if c in ['A' .. 'Z'] then
	begin
		{ Lettera maiuscola, viene ridotta}
		c := chr((ord(c)) + 32);
		filter_char := true;
	end
	else if c in ['a' .. 'z'] then
		{ Lettera minuscola, ok}
		filter_char := true
	else
		{ Carattere da ignorare}
		filter_char := false
end;	

procedure help_and_exit(msg : string);
begin
	writeln(StdErr,msg);
	writeln(StdErr,'Utilizzo: atk [Opzioni] [Parole]');
	writeln(StdErr,'   [parole] è una lista di parole da ricercarsi nel testo forzato al fine');
	writeln(StdErr,'    di automatizzare il riconoscimento dei casi positivi.');
	writeln(StdErr,'    Le parole devono essere in minuscolo e separate da spazi.');
	writeln(StdErr,'Opzioni:');
	writeln(StdErr,'-i <file>  File di input, se omesso utilizza stdin');	
	writeln(StdErr,'-o <file>  File di output, se omesso utilizza stdout');
	writeln(StdErr,'-m <char>  Ipotesi sul carattere più pribabile. Italiano: ''e''');
	writeln(StdErr,'-h         Visualizza questo messaggio');
	exit(program)
end;

{ Funzione ausiliaria per i parametri che richiedono un argomento
  Dato un indice controlla che questo sia seguito da un ulteriore parametro.
  Restituisce l'indice dell'argomento
  In caso contrario notifica l'errore e termina il programma }
function check_next_param(VAR i : integer) : integer;
begin
	if(paramCount > i) then
	begin
		i := i + 1;
		check_next_param := i;
	end
	else
		help_and_exit(paramStr(i) + ' richiede un argomento.')
end;

{ Testo in ingresso e area di lavoro per la decrittazione }
var in_text, out_text : array[1 .. MAX_TEXT] of char;
{ Per ogni posizione della chiave, top_cs caratteri più probabili }
var hints : array[1 .. MAX_KEY] of array [1 .. TOP_CS] of char;
{ Lunghezza del vettore delle parole da cercare nei testi decrittati,
  del testo cifrato e della chiave (ottenuta mediante miglior allineamento) }
var test_str_len, text_len, key_len : integer;
{ Vettore di parole da ricercarsi nelle decrittazioni del testo per riconoscere 
  quelle di successo }
var test_str : array[1 .. MAX_TESTS] of string[20];
{ Chiave}
var key : array[1 .. MAX_KEY] of char;
{ Carattere più frequente nei testi in chiaro 
  Nel caso di testi in italiano, la 'e' è quella più probabile}
var EXP_C : char = 'e';	

{ Genera ricorsivamente e prova le chiavi combinando le lettere contenute in hints 
  i rappresenta la porzione di chiave già generata e corrisponde alla profondità
  delle chiamate ricorsive.
  key viene utilizzato come una pila.
  Il valore di ritorno serve per interrompere la ricerca non appena viene trovata 
  una decrittazione contenente almeno un elemento di test_str.}
function try_keys(i: integer) : boolean;
begin
	var j,k,l : integer;
	{ La decodifica avviene codificando con l'inversa della chiave }
	var rev_key : array[1 .. MAX_KEY] of char;
	var r : boolean;
	r := false;
	if i <= key_len then
	begin
		{ La chiave è stata generata fino alla posizione i -1.
		  Per ogni carattere in hints[i] completa ricorsivamente la chiave.
		  Se viene trovata una soluzione la chiamata corrispondente restituirà True
		  rendendo vera r e facendo terminare la ricerca }
		j := 1;
		while (j <= TOP_CS) and (not r) do
		begin
			key[i] := hints[i][j];
			if try_keys(i+1) then
				r := true;
			j := j + 1;
		end
	end
	else
	begin
		{ key contiene una chiave completa.
		  calcola l'inversa della chiave e decritta il testo}
		for j := 1 to key_len do
			rev_key[j] := inv(key[j]);
		j := 1;
		k := 1;
		while in_text[j] <> #0 do
		begin
			out_text[j] := plus(in_text[j],rev_key[k]);
			j:=j+1;
			if k = key_len then
				k := 1
			else
				k := k + 1;
		end;
		if test_str_len > 0 then
		begin
			{ test_str non è vuoto, ne ricerca gli elementi nel testo decifrato}
			j:=1; 
			while (j <= test_str_len) and (not r) do
			begin
				if pos(test_str[j], out_text) > 0 then
				begin
					write('KEY ');writeln(key);	writeln(out_text);
					r := true;
				end;
				j := j + 1;
			end
		end
		else
		begin
			{ non vi sono parole da cerccare per automatizzare la ricerca, 
			  stampa tutte le soluzioni}
			write('KEY ');writeln(key);	writeln(out_text);
		end;
	end;
	try_keys := r;
end;
	
begin
	{ un contatore delle corrispondenze per ogni scostamento da 1 fino a max_key. 
	  è usato nel calcolo del miglio allineamento.
	  La tecnica del miglior allineamento consente di ottenere informazioni 
	  sulla lunghezza della chiave.
	   
	  for i := 0 to lunghezza_testo - scostamento
	  	 if testo[i] = testo[i + scostamento] then
	         corrispondenze := corrispondenze + 1
	 
	  La dimensione della chiave è un sottomultiplo del minor scostamento che
	  massimizza il numero di corrispondenze tra testo originale e scostato }
	var matches : array[1 .. MAX_KEY] of integer;
	{ un contatore per ogni carattere dell'alfabeto. è usato durante il calcolo di hints }
	var freq : array['a' .. 'z'] of integer;
	var i, j, k : integer;
	var c, d : char;
	
	test_str_len := 0;
	{ Lettura dei parametri del programma}
	i := 1;
	while (i <= paramcount) do
	begin
		if paramStr(i) = '-i' then
			reset(input, paramStr(check_next_param(i)))
		else if paramStr(i) = '-o' then
			rewrite(output, paramStr(check_next_param(i)))			
		else if paramStr(i) = '-m' then
		begin
			exp_c := paramStr(check_next_param(i))[1];
			if not (exp_c in ['a' .. 'z']) then
				help_and_exit('L''argomento di -m deve essere una lettera minuscola.')
		end
		else if paramStr(i) = '-h' then
			help_and_exit('')
		else
		begin
			if (paramcount - i) < MAX_TESTS then
				test_str_len := paramcount - i + 1
			else
				test_str_len := MAX_TESTS;			
			for j := 1 to test_str_len do
			begin
				test_str[j] := paramstr(i);
				i := i + 1;
			end
		end;
		i := i + 1;
	end;
		
	text_len := 1;
	for i:= 1 to MAX_KEY do
		matches[i] := 0;
		
	{ legge e filtra il testo in ingresso calcolando il miglior allineamento }
	while (not eof) and (text_len < MAX_TEXT) do
	begin
		read(c);
		{ i caratteri non alfabetici sono ignorati e quelli maiuscoli ridotti }
		if filter_char(c) then
		begin
			{ copia il carattere letto }
			in_text[text_len] := c;
			{ Controlla rispetto a quali scostamenti il carattere appena letto
			  comporti una corrispondenza e incrementa il contatore relativo a
			  tale scostamento 
			  durante la lettura dei primi max_key caratteri non è possibile
			  controlalre tutti gli scostamenti da 1 a max_key, ma solo
			  quelli da 1 a text_len
			  j è il minimo tra max_key e text_len } 
			if text_len > MAX_KEY then
				j := MAX_KEY
			else
				j := text_len-1;
			for i := 1 to j do
			begin
				if in_text[text_len - i] = c then
					matches[i] := matches[i] + 1;
			end;
			text_len := text_len + 1;
		end;
	end;
	in_text[text_len] := #0;
	{ L'indice di matches contenente il valore massimo è lo scostamento migliore }
	key_len := 1;
	for i:=2 to MAX_KEY do
		if matches[key_len] < matches[i] then
			key_len := i;
	{ Determinata la possibile (le possibili) lunghezza della chiave si procede
	  considerando separatamente i vari cifrari mono-alfabetici utilizzati.
	  Questi non sono forzati singolarmente per forza bruta, ma si utilizza la
	  statistica linguistica per ridurre il numero di chiavi da provare.
	  Tale tecnica si basa sull'assunto che nel testo in chiaro vi siano 
	  dei caratteri più frequenti di altri.
	  La cifratura mono alfabetica, cambia il simbolo, ma mantiene le frequenze
	  Se la 'i' è la più frequente nel testo in chiaro e viene cifrata in 'z',
	  allora 'z' sarà la più frequente nel testo cifrato.
      L'osservazione coinvolge il testo in chiaro, ma è generalmente valida:
	  si utilizzano le probabilità dei vari caratteri rispetto alla lingua in 
	  cui sospettiamo sia scritto il testo.
	  Trattandosi di un metodo statistico la corrispondenza tra carattere più
	  probabile nella lingua e la sua frequenza nel caso particolare di un singolo
	  testo non è esatta.
	  Tuttavia, è molto probabile che tale carattere sia tra i più frequenti.
	  Pertanto si considerano un certo numero di caratteri più frequenti nel 
	  testo ottenendo più di una chiave da provare, ma sicuramente meno di 
	  tutte quelle possibili.
	  Il numero di caratteri più frequenti da considerare è specificato da top_cs,
	  mentre exp_c contiene il carattere atteso.
	  La matrice hints conterrà, per ogni cifrario mono alfabetico (ovvero key_len)
	  top_cs suggerimenti per la decodifica.}
	for i := 1 to key_len do
	begin
		{ azzera i contatori }
		for c in ['a' .. 'z'] do
			freq[c] := 0;
		j := i;
		{ conta le occorrenze dei caratteri nelle posizioni j = i+n*key_len }
		while j < text_len do
		begin
			c := in_text[j];
			freq[c] := freq[c] + 1;
			j := j + key_len
		end;
		{ determina i massimi }
		for j:=1 to TOP_CS do
		begin
			d := 'a';
			for c in ['a' .. 'z'] do
				if freq[c] > freq[d] then
					d := c;
			{ calcola il carattere che servirebbe per cifrare exp_c in hints[i][j]
			  se exp_c = 'e' = 101 e hints[i][j] = 'g' = 103 allora 'e' + 'c' = 'g'
			  e hints[i][j] diventa 'c' = 99 s}
			hints[i][j] := minus(d,EXP_C);
			freq[d] := -1;
		end
	end;
	{ Prova ricorsivamente le combinazioni dei suggerimenti contenuti in hints.
	  Per ogni chiave generata tenta la decifrazione del testo.
	  Se sono specificate delle parole da ricercare nel testo decifrato produce
	  in output solo quelli che ne contengono almeno una.}
	if try_keys(1) then
		i := i;
	close(input);
	close(output);	
end.