[C] Convertire un file in un numero intero

[fbcyborg]

Salve a tutti,

come da oggetto vorrei poter convertire un file qualsiasi in un numero intero. Per la trattazione degli interi utilizzo la libreria GMP (http://gmplib.org), quindi posso trattare interi molto grandi. Qualcuno se la cosa sia fattibile?

[british]

Un file è una sequenze ordinata di bit quindi è già un numero (tipicamente enorme) espresso in base 2... tuttavia quello che credo tu stia cercando è una funzione hash (http://en.wikipedia.org/wiki/Hash_function).

ciao!

british

[tuccio`]

magari qualche implementazione di md5

http://www.faqs.org/rfcs/rfc1321.html

[fbcyborg]

Un file è una sequenze ordinata di bit quindi è già un numero (tipicamente enorme) espresso in base 2...
Esatto. Ovviamente questo lo so bene, ed è proprio quel numero che vorrei ricavare.
Non voglio calcolare alcuna funzione di Hash, né SHA1, né MD5, che servono a tutt'altro. Mi serve sapere il file X corrisponde al numero Y. Stop. Mi serve un intero enorme, OK, anche in binario, ma posso (credo) sempre convertirlo in intero.

Grazie mille.

[wingman87]

Ho dato un'occhiata alla libreria GMP, visto che può trattare numeri arbitrariamente grandi si può fare a patto che la memoria sia sufficiente (quindi potrai ottenere un numero solo per file abbastanza piccoli).

[WarDuck]

Onestamente mi sembra un po' una follia. Il numero che cerchi potrebbe essere generato appunto dalla concatenazione dei numeri ASCII che rappresentano le lettere, il punto è che la grandezza di questo numero dipende strettamente dalla lunghezza della stringa.

Già una stringa di 80 caratteri vorrebbe dire mediamente un numero con 160 cifre, che è un NUMERO ENORME, immagina un file di qualche megabyte (1 milione di caratteri significherebbe un numero con in media 2 milioni di cifre).

Un hash SHA1 è un numero a 160bit, ovvero 20bytes, sai che la lunghezza sarà sempre quella e che la probabilità di collisione è comunque molto bassa.

Quindi un hash SHA1 in realtà è proprio quello che cerchi, per definizione di funzione di hash.

Poi bisognerebbe vedere esattamente cosa ci vorresti fare.

[fbcyborg]

(quindi potrai ottenere un numero solo per file abbastanza piccoli).
Questa non è una cosa felice per me, anche se a dire il vero forse si può frammentare il file, e "procedere" a blocchi.

Onestamente mi sembra un po' una follia.Lo so. Infatti detta così, non può sembrare altro che una follia, ma per scopi di ricerca, devo provare a crittografare dei file con la Homomorphic Encryption usando una libreria che però tratta interi. Questo tipo di crittografia ha alcune proprietà che a me interessano, e vorrei sfruttarle sui file.
Già una stringa di 80 caratteri vorrebbe dire mediamente un numero con 160 cifre, che è un NUMERO ENORME, immagina un file di qualche megabyte (1 milione di caratteri significherebbe un numero con in media 2 milioni di cifre).
Finché la libreria GMP "regge", questo problema per il momento non mi preoccupa. I problemi potranno esserci dal momento in cui si applica la crittografia sul file.

Ecco perché dell'hash non me ne faccio nulla. O almeno credo, dal momento che facendo l'hash di un file, il risultato è una "stringa" ma rispetto al file ho perso informazioni, e non posso recuperare il file originario dato l'hash.

[WarDuck]

[..]
Ecco perché dell'hash non me ne faccio nulla. O almeno credo, dal momento che facendo l'hash di un file, il risultato è una "stringa" ma rispetto al file ho perso informazioni, e non posso recuperare il file originario dato l'hash.

L'hash di un file è un numero intero, la sua rappresentazione in esadecimale ti può confondere facendoti credere che sia una stringa :D.

Chiaramente l'hash non è reversibile (quantomeno facilmente).

Comunque stavo pensando che potresti ridurre di molto i dati (specialmente se parliamo di testo) usando qualche libreria per la compressione prima di calcolare il numero.

Potresti fare quanto segue:

- applichi un algoritmo di compressione a tua scelta
- calcoli la sequenza di caratteri ascii associata al file compresso e tiri fuori un numero relativemente grosso

a quel punto per tornare indietro basterebbe:

- ricreare il file compresso a partire dal numero
- decomprimere il file risultante

Una nota: sarebbe auspicabile normalizzare i codici ASCII così che siano tutti della stessa lunghezza.

Cerco di spiegarmi: come saprai l'ASCII standard prevede i caratteri dallo 0 al 126.

Questo significa che se ti trovi davanti a 2 caratteri (32 e 107 per esempio) quando costruisci il numero otterresti 32107.

Questo numero chiaramente può essere interpretato in diversi modi, ad esempio potrei associarlo ai caratteri 32, 10, 7 oppure a 3, 21, 07 e così via...

Per cui dovresti cercare di normalizzarli affinché il numero più alto e quello più basso che vuoi rappresentare siano di dimensione fissa, ad esempio se decidi di farli di 2 cifre bisognerebbe farli rientrare in un intervallo tra 10 e 99 (ovvero 89 caratteri utili, quindi hai delle limitazioni).

Usando sequenze di 3 numeri potresti mappare tutti i caratteri, tuttavia già solo con stringhe di 2 caratteri ti troveresti un numero con 6 cifre.

Ribadisco che ci vuole poco affinché una cosa del genere diventi ingestibile.

[fbcyborg]

WarDuck: grazie. Oltre che estremamente chiaro, sei stato molto gentile. Apprezzo molto la tua risposta.

Quando parlavo di "stringa" (messa a posta tra virgolette), intendevo una quantità generica, ma hai fatto bene a puntualizzare.

La tua soluzione andrebbe anche bene, ma purtroppo non posso utilizzarla, perché lo scopo è quello di trattare qualsiasi tipo di file. Auspicabilmente di qualsiasi dimensione (entro certi limiti, ovviamente).

Il tuo post mi ha chiarito molte cose, e credo che dovrò riflettere bene sul da farsi perché quello che avevo in mente di fare comincia ad essere un po' problematico.

Grazie molte.

;)

[fbcyborg]

Scusa, mi stavo rifacendo un attimo due calcoli.
Tu hai scritto che "Già una stringa di 80 caratteri vorrebbe dire mediamente un numero con 160 cifre". Verissimo che hai detto "mediamente", ma volevo confrontarmi per vedere se i calcoli che ho fatto io siano giusti.

1 char = 1 byte = 8 bit
80 caratteri => 80x8 = 640bit
Quindi il numero massimo rappresentabile è 2^640 -1, ovvero circa 4*10^192, ovvero, 4 seguito da 192 zeri. Quindi un numero da 193 cifre. Giusto?

[bobbytre]

Scusa, mi stavo rifacendo un attimo due calcoli.
Tu hai scritto che "Già una stringa di 80 caratteri vorrebbe dire mediamente un numero con 160 cifre". Verissimo che hai detto "mediamente", ma volevo confrontarmi per vedere se i calcoli che ho fatto io siano giusti.

1 char = 1 byte = 8 bit
80 caratteri => 80x8 = 640bit
Quindi il numero massimo rappresentabile è 2^640 -1, ovvero circa 4*10^192, ovvero, 4 seguito da 192 zeri. Quindi un numero da 193 cifre. Giusto?

esatto , i tuoi calcoli sono corretti !

[fbcyborg]

Grazie per la conferma!

[WarDuck]

Mmm sarà l'ora ma non ho ben capito cosa intendiate...

Se ho una stringa tipo "ABCD", sono 4 byte, ovvero 4 caratteri.

Se ogni carattere ASCII lo rappresentassimo con 2 cifre (perché ad esempio abbiamo scelto di usare i numeri da 10 a 99), abbiamo un numero i cui simboli o cifre sono 8, ovvero il doppio.

Esempio:

A = 10
B = 11
C = 12
D = 13

ABCD (4 cifre) = 10111213 (8 cifre)

Per cifre intendo le cifre con cui viene rappresentato graficamente, non come viene rappresentato nel calcolatore, forse voi intendevate quest'ultima cosa?

[wingman87]

Questa non è una cosa felice per me, anche se a dire il vero forse si può frammentare il file, e "procedere" a blocchi.
Penso sia la cosa migliore da fare, d'altra parte quasi tutti gli algoritmi di crittografia si applicano a blocchi secondo diversi schemi.
Ad ogni modo se consideri un file come una stringa di testo o come un intero il numero di bit che ti serve per rappresentare l'uno o l'altro non cambia. Non so come GMP rappresenti internamente gli interi ma meglio di così non può fare senza perdere informazioni (a meno che non comprima i dati ma ne dubito). Quindi quando dicevo che non potrai ottenere numeri da file troppo grandi intendevo dire che c'è un limite fisico che è quello della memoria.

[tuccio`]

devo provare a crittografare dei file con la Homomorphic Encryption usando una libreria che però tratta interi.
e tu hai già una libreria che la implementa? e ti serve un array di int o cosa? se tu avessi una funzione che prende un array di char, unsigned char o void ti basterebbe fare un file mapping, non dovresti fare proprio nulla

il problema è che se piglia un array di int e il file non è di dimensione multipla della dimensione del tipo int è un casino :/

[fbcyborg]

forse voi intendevate quest'ultima cosa?
Sì sì, io intendevo proprio quello, ovvero data la rappresentazione binaria su disco di quel file, ottengo l'intero.
La soluzione ASCII la devo per forza scartare, nel mio caso.

Non so come GMP rappresenti internamente gli interi
Si tratta di interi a precisione multipla ed il tipo di dato è un mpz_t, ed ecco la parte di codice in questione nel file /usr/include/gmp.h:
typedef struct
{
int _mp_alloc; /* Number of *limbs* allocated and pointed
to by the _mp_d field. */
int _mp_size; /* abs(_mp_size) is the number of limbs the
last field points to. If _mp_size is
negative this is a negative number. */
mp_limb_t *_mp_d; /* Pointer to the limbs. */
} __mpz_struct;

#endif /* __GNU_MP__ */


typedef __mpz_struct MP_INT; /* gmp 1 source compatibility */
typedef __mpz_struct mpz_t[1];

Quindi quando dicevo che non potrai ottenere numeri da file troppo grandi intendevo dire che c'è un limite fisico che è quello della memoria.
Ok, certamente, in caso vedrò qual'è questo limite fisico e saprò fino a che punto potrò fare quello che mi serve.

e tu hai già una libreria che la implementa?
Sì, si chiama libpaillier (http://acsc.cs.utexas.edu/libpaillier/), e funziona molto bene (provando con numeri interi).

se tu avessi una funzione che prende un array di char, unsigned char o void ti basterebbe fare un file mapping, non dovresti fare proprio nulla
Dunque, queste sono le tre funzioni che servono ad inizializzare il tipo di dato da cifrare:

/*
Allocate and initialize a paillier_plaintext_t from an unsigned long
integer, an array of bytes, or a null terminated string.
*/
paillier_plaintext_t* paillier_plaintext_from_ui( unsigned long int x );
paillier_plaintext_t* paillier_plaintext_from_bytes( void* m, int len );
paillier_plaintext_t* paillier_plaintext_from_str( char* str );
Quindi in realtà potrei trattare il file come una stringa e provare a passargli quella. Però ancora non sono convinto.

[tuccio`]

probabilmente è più efficiente usare la versione long, perché hai 1/8 dei numeri.. però ti costringerebbe a fare un lavoro sui file.. e per file che superano la memoria messa a disposizione dall'os dovresti anche inventarti qualcosa per non tenere tutto in ram

con il mapping l'os fa tutto da solo

ps: dovresti usare la versione che prende void* non quella che prende char*

[fbcyborg]

OK, grazie, ora mi metto a fare delle prove.

[fbcyborg]

Confermo quanto detto fin'ora. Anche trasformando un file di pochi byte in un void*, il tipo di dato mpz, non riesce a contenere un intero corrispondente al contenuto del file:
gmp: overflow in mpz type
Aborted