Newsgroup: it.comp.lang.c
Titolo: CRC

Salve a tutti.
Chi vuole far luce sul CRC? Quali sono le regole per la sua implementazione?
Grazie.
Igor Rossetti


Ti faro' avere le specifiche de fu CCITT Lunedi'. Le ho nella mia casa
nelle Marche.
Comunque si tratta di calcolare il resto del buffer o trama considerata
come polinomio, per un polinomio di 16 bits (una specie di funzione di
hash)
e un' altra operazione che non ricordo, ma niente di complicato. Nel
capito-
lato CCITT del protocollo HDLC trovi una descrizione molto formale del
calcolo, compreso l' ordine di considerazione dei bits.
Le teorie matematiche di come vengano distribuiti i CRC rispetto alla
sequenza
di bits su cui vengono calcolati non le so citare, ma sono le stesse
delle
funzioni di hash. Comunque tutti concordano che sia migliore di
checksum.
A risentirci. Ciao.


[...]
mi potresti spiegare un po' cosa sono le funzioni di hash. Le ho trovate in
un testo inglese ma usa il termine senza spiegarlo.
thanks & bye

>Ti faro' avere le specifiche de fu CCITT Lunedi'. Le ho nella mia casa
nelle Marche.
Mitico ziofester! Garzie

 un testo inglese ma usa il termine senza spiegarlo.
Sono delle trasformazioni dirette da spazio dei dati a spazio delle
chiavi. Praticamente servono a minimizzare il tempo di accesso ad un
dato attraverso l'uso di chiavi univoche calcolate in base ad esso.
EMG

 thanks & bye
In genere le funzioni di HASH (dette anche "one-way hash function") sono delle
funzioni non invertibili che dato un input variabile restituiscono un output a
lunghezza costante.
In pratica dato un input il numero 'x' ricavo in output 'y' tramite la funzione
di hash: y = f(x).
Le particolarità di questa funzione sono sostanzilamente due:
1) Le dimensioni di 'y' rimangono sempre costanti anche se le dimensioni di 'x'
variano.
2) E' Praticamente impossibile ricavare 'x' dato 'y' (cioè non esiste la
funzione inversa f(y)^-1)
Queste funzioni sono molto utilizzate negli algoritmi di crittografia. Però non
so se lo ziofester intendeva queste o stava parlando d'altro.
Raffaele.

 thanks & bye
Non e' che habbia una grande preparazione sull' argomento.
Le funzioni di hash sono trattate sul libro di Donald Knut sugli
algoritmi di ricerca, ma possono essere utilizzare per verificare
l' integrita' di un documento (finger print o impronta digitale)
o anche per la generazione di numeri pseudo-casuali.
Possono essere molto complesse, come MD5, ma un esempio di funzione
di hash semplice e gia' usabile e' la funzione resto o modulo (%).
Colsiderando una qualunque stringa o testo come un polinomio di
arbitrarie dimensioni, si calcola f=h(p) come f=p MOD "numeroprimo".
Il risultato dell' operazione resto non potra' mai essere magg. o
uguale a "numeroprimo" scelto, qualunque sia la dimensione del testo.
Naturalmente, avendo il testo una cardinalita' molto maggiore di
"numeroprimo" utilizzato, ci saranno piu' possibili testi che restitui-
scono la stessa funzione di hash, ma la scelta di un numero primo
come divisore garantisce una buona distribuzione delle funzioni di hash.
Se questa funzione risulta debole, bisogna passare ad una piu'
complessa.
Il valore ottenuto puo' essere usato per accedere a tabelle di record
come cheave di ricerca (doppio hash), per verifica integrita' documenti,
autenticazione login...
Argomento MOLTO interessante.
ciao

 Igor Rossetti
Il capitolato del CCITT ce l' ho su carta e sono documenti
non di pubblico dominio, quindi non posso trascriverlo fedelmente,
solo commentarlo nel dettaglio.
Di solito per le esigenze di trasmissione dati e' implementato in
hardware, per implementazioni di finger print puoi vedere i sorgenti
di  GNU 'sum', GNU 'cksum' e GNU 'md5sum'.
Per il protocollo standard HDLC usato in trasmissione dati e' definito
in questo modo:
16 bits trasmessi accodati alla trama su cui e' stato calcolato, con il
bit piu' significativo trasmesso per primo.
E' il complemento a 1, cioe' il NOT di ogni bit della
SOMMA del
  RESTO della divisione di (0xFF seguito da tanti 0 quanti sono i bits
  della trama ) % 10000100000010001 detto polinomio generatore di 17
bits
con il
  RESTO della divisione tra trama_considerata_numero seguita da altri 16
  bits a 0, per lo stesso polinomio generatore 10000100000010001 di 17
bits.
Utilizzando 2 registri a 16 bits non e' difficile fare i calcoli.
Naturalmente devi iterare operazione modulo del C (%) e shift di
bit per rutta la lunghezza della trama o testo intesa come lunghezza
in bits.
se trama                       10010011101000110111100101000011
primo registro 111111111111111100000000000000000000000000000000 %
10000100000010001
sec.  registro 100100111010001101111001010000110000000000000000 %
10000100000010001
               ^           trama              ^                  
^polin. 17 bits ^
CRC = NOT binario di ( primo registro + secondo registro)
Credo di aver interpretato correttamente. Sto' capitolato e' scritto
come
un contratto di assicurazione.
ciao.

Grazie a tutti ora la cosa si fa un po' più chiara.
bye

Mi sembra di ricordare che sul manuale del vecchio Z80 SIO
il polinomio generatore di CRC conforme alle spec. CCITT
(che quel gioiellino calcolava) era di 16 bits non 17.
Su questo manuale tradotto in italiano dall' Istituto Sup.
Poste e Telegrafi si parla di bits 2^16+2^12+2^5+1 e ho pensato
di ricordare male, ma non vorrei che sia un errore di traduzione.
ciao a tutti.

 writes:

Un buon programma di CRC a 16 bits si trova sul sito di Bob Stout,
http://www.snippets.org
 (assieme a svariate altre goodies).
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it