---------
                |       |
  messaggio --> | 1-way | --> messaggiocryptato   ????     
                |       |
                ---------


                ---------                            ------------------
                |       |                            |                |
  messaggio --> | 2-way | --> messaggiocryptato  --> | 2-way-reverse  | --> messaggio
                |       |                            |                |
                ---------                            ------------------

Se l'algoritmo e' una funzione 2-way possiamo costruire un filtro inverso in grado di restituire il messaggio originale. 
E' per questo motivo che i sistemi 1-way vengono utilizzati solo per l'autentificazione degli utenti in sistemi informatici, 
dove a priori e' nota l'informazione ( password dell'utente ).

L'utente digita la password, questa viene cryptata secondo l'algoritmo, e confrontata con la password originale cryptata 
al momento della registrazione dell'utente: se le due pass cryptate coincidono, allora l'utente viene autorizzato. 

E' chiaro che il nostro interesse si pone sul secondo tipo di sistema. 
Stiamo cercando di realizzare un filtro numerico che ammetta il suo inverso in modo da poter costruire due routines: crypt e decrypt.

L'algoritmo si basera' sostanzialmente su somme di convoluzione ( o correlazione ).
La scelta e' stata dettata dai seguenti motivi:

- Non sono un informatico e mi occupo piu' di fitri che di algoritmi che giocano con i bit.

- E' un sistema dinamico in cui l'utente definisce il grado di complessita'.



Approccio alle somme di correlazione: vantaggi.


I vantaggi introdotti dalla somma di correlazione sono notevoli: facciamo un esempio pratico per illustrarli.

Supponiamo di aver deciso di utilizzare un algoritmo poco intelligente il seguente:

'la stringa cryptata sara' il risutanto della somma (in byte) tra l'input e la key'. 

Vediamo il seguente schemetto.

---------------------------------------------------------
12 |45 |56 |23 |124| ... testo da cryptare
---------------------------------------------------------

+ + + + +

---------------------------------------------------------
5 | 5 |66 |23 |12 | chiave.
---------------------------------------------------------


---------------------------------------------------------
17 |50 | .... testo cryptato
--------------------------------------------------------- 

...abbiamo deciso di fare le somme carattere per carattere... 
applicando il modulo 256 per non sforare dal set :)

Cosa succede?
Cerchiamo di fare una analisi statistica.

Modelliamo la stringa in ingresso come un processo stocastico bianco A(n) distribuito secondo una certa legge.
Della distribuzione di ciascun carattere non ne parleremo... senza ledere nella generalita' della dimostrazione...
sceglieremo la gaussiana.

Lo stesso facciamo con KEY(n).

Adesso per semplificarci la vita poniamo che...


a(n) = A(n) - E{ A(n) }
key(n) = KEY(n) - E{ KEY(n) }

a(n) e key(n) sono adesso a valor medio nullo.

La funzione di autocorrelazione di a(n) e' pertanto... 

E{ a(k)a(n+k) } = Kronker(n)* potenza della sequenza.


( ho indicato con E{} l'operatore lineare di aspettazione )

Considereremo pure i due processi indipendenti... 


E{ key(k)key(n+k) } = Kronker(n) * potenza della chiave.

Il cryptato risulterebbe, in buona approssimazione, una cosa tipo questa.. 

C(n)=a(n)+key(n) per 0<n<N con N grande lunghezza della chiave.


Prima di procedere assumo che sia il testo che la chiave abbiano lunghezza infinita.


La funzione di autocorrelazione della stringa criptata sara'


E{ C(k)C(n+k) } = E{ ( a(k)+key(k) )*( a(n+k)+key(n+k)) } ...


ne segue che...

... = E{ a(k)a(n+k) } + E{ key(k)key(n+k)} + altri termini.... 

L'indipendenza di a() rispetto a key() ci porta ad affermare che gli atri termini nulli...
questo perche' stiamo lavorando con sequenze a valor medio nullo. 

Cosa si nota?

La funzione di autocorrelazione della sequenza cryptata e' sempre una delta di kronerk!!

Questo caratteristica di c(n) non e' ben voluta in quanto il nostro processo non ha subito sostanziali modifiche 
in termini stastistici durante la fase di crypt ( se non un cambiamento della potenza).

Cerchiamo di capire dove sta' il guaio. 

Abbiamo dimostrato che il processo C(n) e' ancora bianco. 

Cio' significa che due caratteri appertenenti a quella sequenza sono scorrelati.. 
se poi C(n) avesse una distro gaussiana allora risulterebbero indipendenti!!!

Sotto questa ipotesi il crackatore del messaggio e' in qualche modo aiutato, nel senso che se riusciesse ad inviduare 
parte della chiave, si vedrebbe comparire il messaggio quasi in chiaro. 
In altre parole se la chiave utilizzata fosse di lunghezza N, sbagliando un solo byte della chiave otterrebbe un messaggio 
decodificato al (N-1)/N * 100 %.


Benche' la potenza dell'algoritmo risulti buona... ( scegliendo un set di 96 char si ottengono 96^N chiavi possibili)
il molesto potrebbe aiutarsi con programmi intelligenti che sfuttano l'output per poter indirizzare il crack verso lidi piu' felici. 

Gia' assumendo la possibilita' di aver individuato il 50% dei bytes della chiave i casi si semplificherebbero 
in modo esponenziale... 96^(N/2).

In altri termini, e' vero che 1 sola chiave su 96^N decrypta completamente il messaggio, ma e' pure vero che vi sono altre chiavi 
che riescono ad ottenere dei buoni risultati.

Un calcoletto? 

Esistono 95*N chiavi che decryptano il messaggio sbagliando 1 solo carattere su N!
Scegliendo una chiave di lunghezza 10 char scopriamo che 950 chiavi diverse decryptano 'quasi alla perfezione'!!
Da qui ci rendiamo conto della poca efficenza dell'algoritmo a somma.

La situazione per la somma di correlazione e' ben diversa.




Algoritmo: una buona dose di calcoli.



Adesso e' giunto il momento di occuparci delle somme di convoluzione o correlazione che siano.
Iniziamo con il riprendere sotto mano le sequenze di prima.

a(n) = sequenza a valor medio nullo da cryptare
key(n) = chiave utilizzata ancora a valor medio nullo. 


Definiamo C(n) nel seguente modo:


C(n) = Sum(i=0,N-1) a(i+n) key(i) (somma di correlazione )


gli informatici potrebbero gradire di piu' la seguente scrittura analoga... 

for(i=0;i<N:i++)
C(n) += a(i+n) key(i);


nota: avrei potuto usare le somme di convoluzione che differiscono solo per un segno: 
basta prendere la key() e ribaltarla considerando key2(n)=Key(N-n). 
Ma non ci prediamo in questi particolari ed andiamo avanti....


Adesso prima di addentraci nel calcolo del filtro e del suo inverso, voglio mostrare che C(n) non e' piu' un processo bianco 
a meno che key() non sia un filtro particolare.

Per questo utilizzeremo le trasformata discreta di Fourier. 

La sequenza e' numerica, la sua straformata ovviamente sara' periodica di periodo pari all'inverso del tempo di campionamento.
Assumo tale periodo unitario. 

Cio' implica che a noi interesseranno solo le frequenze comprese tra -1/2 e +1/2. 

Vale la nota relazione..


Sc(f)= Sa(f) MOD( key(f))^2 

Segue che la desinta' spettrale di potenza Sc non sara' costante a meno che Key non sia un filtro la cui risposta impulsiva 
sia una delta di croneker (quest'utlimo caso e' scartato a priori).

In altri termini C(n) non e' piu' un processo bianco.

In effetti prima abbiamo utlizzato un approccio tipo Key: processo .Adesso invece lo consideriamo come sequenza deterministica ...


In ogni caso C(n) non sara' piu' bianco, ed i sui caratteri saranno correlati in quanto il filtro key(n) ne modifica completamente 
le caratteristiche statistiche.

La correlazione introdotta dal fitro ci garantisce che il nostro messaggio viene decryptato se la chiave utilizzata e' perfetta. 
Non mi sento in questa sede di dimostrare che non possono esistere altre sequenze in grado di invertire il processo, 
tuttavia e' ragionevole pensare che la loro probabilita' di esistenza e' nulla. 

Un solo errore su un byte della chiave porta a conseguenze disastrose che si riperquotono sull'intero messaggio.

Di fatto l'algoritmo sembra buono, ci manca solo di formalizzare il problema.

Procediamo con il calcolo algebrico del filtro inverso.



C(n)= SUM(i=0;N-1) a(i+n) key(i)

isolo l'ultimo termine dalla somma...

C(n)= a(N-1+n) key(N-1) + SUM (i=0;N-2) a(i+n) key(i)


e mi ricavo a(N-1+n)...


a(N-1+n)= ( C(n) - SUM (i=0;N-2) a(i+n) key(i) ) / key(N-1)


attenzione adesso il termina key(N-1) mi potrebbe dare fastidio!!! Be' poiche' sono io che gestisco key() di default fisso key(N-1)=1. 
( In realta' quello che faro' sara' allungare il fitro di un byte considerando key(N)=1.. ma questo non lede alla dimostrazione. ) 

vediamo..

a(N-1+n)= C(n) - SUM (i=0;N-2) a(i+n) b(n) 

Adesso la forma e' abbastanza semplice tuttavia notiamo che il primo carattere che possiamo decryptare e' a(N-1) per n=0 
avendo a disposizione a(k) con k che va' da 0 a N-2.

Ci stiamo rendendo conto che stiamo lavorando con una equazione ricorrente ( o ricorsiva ).

Senza entrare nei dettagli le eq. ricorrenti hanno una particolarita' molto importante: sono univocamente definite una volta note 
le condizioni iniziali.

Bene i caratteri di cui abbiamo bisogno a(0).. a(N-2) sono proprio le condizioni iniziali!

Allora come facciamo? Semplice! 
Aggiungiamo davanti alla sequenza da cryptare le condizioni iniziali, che debbono essere note sia al trasmettiore sia la ricevitore. 

Ora che le cond. iniziali sono note, siamo certi del risultato che andremo ad ottenere.


Ecco qui di seguito le formule con le varie condizoni poste.



Cryptatore.

C(n)= SUM(i=0;N-1) a(i+n) key(i) - a(n) per 0<n<N coincide con le cond. iniziali 
per n>= N coincide con la seq. da cryptare. 


- Key(n) per 0<n<N e' la chiave utilizzata per cryptare
per n=N vale 1
nota: =1 cosi' elimino il problema 
della divisione

- C(n) sequenza cryptata.


Decryptatore ricorsivo.

a(N-1+n)= C(n) - SUM (i=0;N-2) a(i+n) b(n)



- a(n) per n>N-1 sequenza originale.

- C(n) sequenza cryptata.



Non vi pare che ci stiamo dimenticando di qualcosa? Direi di si.

La cosa interessante e' che tutte le relazioni che ho scritto per il filtro ed il suo inverso, 
restano vere anche se considero le equivalenze in modulo anziche' pure.

Le seguenti relazioni ci vengono in auito...

a=b+c e quindi a-b=c

oppure...

a =|modx b+c da cui..... a-b =|modx c



RFC del sorgente.



Il set di caratteri ASCII e' fissato a 256 valori. 
Utilizzero' nelle routines gli unsigned char perche' sono piu' buoni da trattare in quanto assumono solo valori positivi.
In oltre dal momento che ci sono traumi notevoli sull'uso del char ascii 0 e 10 ho complicato un po' l'algoritmo rendendolo 
adatto alla sola cryptazione dei testi ascii ( ho limitato il set ASCII ).

Dimenticatevi quindi di utilizzare le routines qui allegate per crytpare binari: il loro uso e' consentito se in ingresso 
viene posta una sequenza limitata in valore tra 1 e 254. 

Di default percio' assumo un set di caratteri compresi nel seguente range...

1 <= ASCII <=254 ( estremi inclusi.)

Il char 0 e' il terribile terminatore di stringhe.
Il char 255 viene utilizzato per rimappare il char 10 newline.

Avrete a disposizione quindi 2 routines: conv e deconv da aggingere dei vostri sorgenti.


La conv e' in grando di cryptate + linee di testo in una sola stringa. La deconv e' il filtro inverso. 


I prototipi delle due funzioni sono i seguenti.


char *conv (char *STRINGA_DA_CRYPTARE, char *COND_INIZIALE, char *KEY);
char *deconv (char *STRINGA_DA_DECRYPTARE, char *COND_INIZIALE, char *KEY);


L'unica nota che possiamo mettere in evidenza e' il fatto che ci sono 2 stringhe KEY e CONDITION debbono essere note. 
In effetti si poteva fare a meno della cond. iniziale fissandola a priori, o addirittura estraendola da una parte della chiave stessa. 

Sono questi i migliromamenti che potete effetturare sul sorgente. 

Ripeto e' stato scritto al solo scopo educativo, pertanto e' giusto che le due stringhe siano differenziate vista 
la natura completamente diversa.

NOTA IMPORTANTE: Non dimenticate che key e cond.iniziali debbono avere la stessa lunghezza!

Cosa altro aggiugere? 

Se avete bisogno di una mano o se non avete capito qualcosa, scrivete pure. 

Saro' lieto di rispondervi, sempre che non debba tenervi un corso completo di elaborazione numerica dei segnali.

mailto:agwn@dislessici.org networking&telecommunication division.

-----------------------------------------------------------------------------

/* Sum of Correlation Crypter v4.0! Coded by agwn roofing (disLESSici)

This source is provided for educational purposes only.
Original Manufacture: agwn smartconding&telecommunication division.

mailto: agwn@dislessici.org

*/



#include <stdlib.h>
#include <string.h>
#include <stdio.h>



char *conv (char *, char *, char *);
char *deconv (char *, char *, char *);




char *
conv (char *seq, char *condition, char *key)
{
long int temp = 0;
int maxlen = 0, N = 0, i = 0, n = 0;
unsigned char *out, *jumper, *sp, *fp;
unsigned char *sequence, *supersequence, *supersequencejump;


maxlen = strlen (seq);
N = strlen (key);

out = (char *) malloc (maxlen + N + 1);
sequence = (char *) malloc (maxlen);
supersequence = (char *) malloc (maxlen + N);

supersequencejump = supersequence;

for (n = 0; n < N; n++)
*supersequencejump++ = *condition++;

for (n = 0; n < maxlen; n++)
*supersequencejump++ = *seq++ - 1;

jumper = out;
sp = supersequence;
fp = key;


for (n = 0; n < maxlen; n++)
{
temp = 0;
for (i = 0; i < N + 1; i++)
{
if (i == (N))
temp += *sp++;
else
temp += (*sp++ * *fp++);


}
fp = key;
sp = ++supersequence;

*jumper = (temp % 254) + 1;

if (*jumper == 10)
*jumper = 255;

jumper++;

}
*jumper = '\0';

return out;

}



char *
deconv (char *seq, char *condition, char *key)
{
int maxlen = 0, N = 0, i = 0, n = 0, temp = 0, temp2 = 0;
unsigned char *out, *jumper, *stepper, *stepper_save, *sp, *fp, *sequence;
unsigned char *temporary;

maxlen = strlen (seq);
N = strlen (key);

out = (char *) malloc (maxlen + N + 1);
sequence = (char *) malloc (maxlen);


strcpy (sequence, seq);

temporary = sequence;

while (*temporary != '\0')
{
if (*temporary == 255)
*temporary = 10;
temporary++;
}


stepper = out;
stepper_save = stepper;

jumper = out;
sp = sequence;
fp = key;

strcpy (jumper, condition);

for (n = 0; n < N; n++)
jumper++;


for (n = 0; n < maxlen; n++)
{
temp = 0;

for (i = 0; i < N; i++)
temp += (*stepper++ * *fp++);

fp = key;
stepper_save++;
stepper = stepper_save;

temp2 = (*sp++ - 1 - temp) % 254;
if (temp2 < 0)
temp2 += 254;

*jumper++ = temp2;

}

*jumper = '\0';

for (n = 0; n < N; n++)
out++;

temporary = out;
for (n = 0; n < maxlen; n++)
*temporary++ += 1;

return out;

}