È questo il modo giusto per trovare un checksum?

Question

Sto provando a calcolare il checksum per alcuni dati. Questo è il codice:

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

int main() 
{ 
    char MyArray[] = "my secret data"; 
    char checksum = 0; 
    int SizeOfArray = strlen(MyArray); 

    for(int x = 0; x < SizeOfArray; x++) 
    { 
      checksum += MyArray[x]; 
    } 
    printf("Sum of the bytes for MyArray is: %d\n", checksum); 

    printf("The checksum: \n"); 
    checksum = (checksum^0xFF); 
    printf("%d\n",checksum); 
} 

uscita:

Sum of the bytes for MyArray is: 70 
The checksum: 
-71 

modifica nel codice:

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

int main() 
{ 
    char MyArray[] = "my secret data"; 
    char checksum = 0; // could be an int if preferred 
    int SizeOfArray = strlen(MyArray); 

    for(int x = 0; x < SizeOfArray; x++) 
    { 
      checksum += MyArray[x]; 
    } 
    printf("Sum of the bytes for MyArray is: %d\n", checksum); 

    //Perform bitwise inversion 
    checksum=~checksum; 
    //Increment 
    checksum++; 
    printf("Checksum for MyArray is: %d\n", checksum); 
    } 

uscita:

Sum of the bytes for MyArray is: 70 
Checksum for MyArray is: -70 

Perché modifica valore di checksum? Differenti algoritmi forniranno checksum differenti?

Come sarà utile il valore finale? Beh, in realtà non sono chiaro riguardo il checksum e il suo uso nella convalida dei dati. Ho cercato la rete, ho trovato molti articoli, ma non sono ancora chiaro. Spero che capirò del checksum qui oggi.

Answer 1

Questa è la bellezza di algoritmo di checksum: che il modo in cui si produce il checksum e il modo in cui si controlla è in qualche modo simmetrica!

1. chi checksum

checksum è tipicamente utilizzato per verificare l'integrità dei dati, specialmente su canale di comunicazione rumoroso/unrealiable. Pertanto, viene utilizzato principalmente per il rilevamento degli errori . Cioè, per sapere se i dati ricevuti sono corretti o non.

Questo è abbastanza diverso con, ad esempio, la correzione degli errori . Dal momento che il suo utilizzo è non solo per verificare se vi è errore, ma anche per correggerlo, in genere i dati con correzione dell'errore overhead cresce in dimensioni piuttosto proporzionalmente con i suoi dati originali (poiché più dati hai, più sovraccarico è necessario ripristinarlo).

Così, in questo senso un algoritmo di checksum buona è tipicamente quella che utilizza la quantità minima dei dati di overhead per rilevare l'errore ma con grande robustezza verso risultato falso.

E con ciò la comprensione del problema risiede, dal momento che la robustezza del checksum in realtà, non solo dipende dalla algoritmo, ma anche dipende dalle canale caratteristiche. Alcuni canali possono essere soggetti a determinati tipi di errore mentre gli altri canali sono altri. In generale, ci sono alcuni checksum che sono noti per essere più robusti e più popolari degli altri (uno dei miei preferiti è CRC - Cyclic Redundancy Check). Ma non esiste un checksum perfetto per ogni scenario, in realtà dipende dall'utilizzo e dallo scenario.

Ma ancora, è possibile misurare robustness di un algoritmo di checksum. E c'è un modo matematico per farlo, che penso sia oltre lo scopo di questa discussione.Pertanto, alcuni checksum, in questi sensi, possono essere considerati più deboli degli altri. I checksum che hai mostrato nella tua domanda sono anche quelli deboli.

2. Informazioni sul codice

XOR con 0xFF per 8-bit è perfettamente equivalente con binario invertente un valore, e non è troppo difficile da vedere .

XOR con 0xFF

1110 0010 
1111 1111 
--------- XOR 
0001 1101 //notice that this is exactly the same as binary inverting! 

Così, quando si fanno XOR con 0xFF e ~checksum, si ottiene lo stesso risultato -71 (e dal momento che il tipo di dati è char, ha numero negativo). Quindi lo incrementa di 1, quindi ottieni -70.

3. circa 2' Complemento complemento

Two è un'operazione matematica su numeri binari, così come un binario con segno rappresentazione dei numeri in base a questa operazione. Il suo ampio utilizzo in informatica lo rende l'esempio più importante di un complemento di radix. (wikipedia)

In altre parole, 2' complementare è quello di trovare la rappresentazione negativo di un valore (in Computer binario) e il suo metodo è, come avete fatto correttamente, invertendo tutti i bit e quindi aggiungere uno a esso. Ecco perché ottieni -70 per 2 'completando 70. Ma questo è non significa che 2 'complemento e XOR di 0xFF è lo stesso, e come puoi vedere dall'esempio, non è proprio lo stesso.

Ciò che XOR by 0xFF fa nei dati a 8 bit è semplicemente equivalente a invertire tutti i suoi bit. Non ne aggiunge uno.

4. Circa il modo di leggere aggiungere/leggere checksum

Dal momento che la somma di controllo viene utilizzato per conoscere il dell'integrità dei dati (se si è alterato o non), le persone cercano di trovare le migliori pratiche per farlo. Quello che fai è in realtà di ottenere il checksum per 2 'complementare o da XOR con 0xFF.

E questi sono ciò che fanno:

• 2' completano checksum. Diciamo che la lunghezza del tuo messaggio è N. Poiché ciò che ottieni sommando i numeri N sono, diciamo, 70. Quindi aggiungendo il checksum di 2'completo (ovvero -70), Nel ricevitore, devi semplicemente sommare tutti i messaggi N + 1 incluso il checksum e si dovrebbe ottenere 0 se il messaggio è inalterato. Ecco come usare correttamente il checksum del complemento 2 '.
• Per XOR con 0xFF Ancora, con lo stesso esempio del precedente, si dovrebbe ottenere -1 se si sommano tutti i messaggi N + 1, compreso il checksum.E dal momento che la rappresentazione esadecimale di -1 è 0xFF a 8-bit con segno, in tal modo dal XOR ing risultato (-1) con 0xFF, si dovrebbe ottenere 0xFF^0xFF = 0 se il messaggio contiene nessun errore

Quindi, in entrambi i casi, è sufficiente verificare se il messaggio contiene errori o meno controllando se il risultato finale è 0 (nessun errore) o no !! E questo è tipicamente vero per gli algoritmi di checksum!

Questa è la bellezza di algoritmo di checksum: che il modo in cui si produce il checksum e il modo in cui si controlla è in qualche modo simmetrica!

Answer 2

È necessario capire cos'è un checksum prima di pensare a come lo si genera. Assumere il problema dell'invio di dati attraverso un canale di comunicazione inaffidabile, ad esempio una connessione di rete. Devi assicurarti che non ci siano state interferenze che hanno influenzato il tuo messaggio.

Un approccio per eseguire questa operazione è inviare il messaggio due volte e controllare le differenze (infatti, vi è una piccola possibilità che si verifichi esattamente lo stesso errore durante la trasmissione di entrambi i messaggi). Tuttavia, questo richiede di usare parecchia banda (inviando il messaggio due volte).

Un approccio più efficiente consiste nel calcolare un valore in base al messaggio e allegarlo al messaggio. Il destinatario applica quindi la stessa funzione e verifica se il valore è lo stesso.

Per ottenere un esempio più intuitivo, il checksum di un libro può essere il numero di pagine. Comprate un libro dalla biblioteca e contate le sue pagine. Se il numero di pagine non è quello che ti aspettavi, c'è un problema.

Si implementa una funzione di checksum specifica (LSB di somma) che va bene. Tutte le funzioni del checksum hanno alcune proprietà di cui dovresti essere a conoscenza, ma il punto è che non esiste un modo corretto per calcolare un checksum. Ci sono molte funzioni che possono essere utilizzate per questo scopo.

Answer 3

Un checksum viene solitamente utilizzato per rilevare una modifica dei dati. Comunicazioni, crittografia/firma, ecc ... i checksum sono usati ovunque.

Come un checksum può essere può essere utile?

• rileva un cambiamento su 1 bit per esempio
• rileva anche i cambiamenti quando più di 1 bit vengono modificate

che può sembrare un paradosso, ma quando solo 1 modifiche bit, i checksum lavoro. Tuttavia, prendere

(A) checksum += 0x11 instead of 0x10 

e successivamente

(B) checksum += 0x30 instead of 0x31 

In (A) il checksum sarà -1 ... e in (B) sarà +1. Più e meno 1 == 0.I due errori saranno non rilevati dal checksum.

Fondamentalmente la qualità di una checksum dipende

• sulla lunghezza del checksum (maggiore è la somma di controllo, maggiore sarà abbracciare dati più grandi, senza "loop" (un byte ha solo 256 checksum possibili , 2 byte ha 65536, nota che nel caso precedente con il tuo algoritmo che non cambierebbe il risultato)

• la qualità del calcolo del checksum, al fine di evitare il più possibile che due differenze si annullino reciprocamente

Ci sono molti algoritmi disponibili. This answer on SO è un buon inizio.