Esiste un buon modo per "codificare" i dati binari come parole plausibili e restituite?

Question

Per darvi un esempio molto semplice e cattivo. I dati sono divisi in 4 bit. I 16 numeri possibili corrispondono alle prime 16 consonanti. Aggiungi una vocale casuale per renderla pronunciabile. Quindi "08F734F7" può diventare "ba lo ta ku fo go ta ka". Puoi unirti ad alcune sillabe e aggiungere punteggiatura e maiuscole e può diventare "Balo ta kufogo, Taka?" che sembra un linguaggio plausibile.

Giusto per chiarire, non sto cercando di proteggere i dati binari.

Voglio usarlo dopo aver compresso e crittografato il mio diario di testo normale (UTF-8). I dati binari risultanti dovrebbero apparire abbastanza casuali. Ho bisogno di convertire questi dati in un linguaggio dall'aspetto plausibile e poterli ripristinare. Stamperò la "lingua" su carta e realizzerò un libro personalizzato.

Quindi quello che sto cercando è il metodo migliore per convertire dati casuali in parole plausibili leggibili. Per buono intendo il più grande rapporto tra i bit e le lettere (pur facendo sembrare un linguaggio reale). Nel mio esempio è esattamente 2 bit per lettera. O 4 lettere per un byte.

Answer 1

FASCINANTE domanda!

La mia soluzione migliore finora codifica 12 bit in 2 o 4 caratteri, dando da 3 a 6 bit per lettera. (Il venerdì non è un buon giorno per fare i calcoli necessari sulla distribuzione irregolare delle lunghezze delle parole, quindi non ho elaborato i bit medi per lettera).

L'idea è di lavorare con "fonemi" che iniziano con una o due consonanti e terminano con una o due vocali. Ci sono 21 consonanti e sento che ognuno potrebbe essere seguito da un h, l, r, wey, e comunque sembra ragionevole. Quindi il tuo fonema inizia con una delle 126 parti consonanti - b, bh, bl, br, bw, da, c, ch, cl, cr, ..., z, zh, zl, zr, zw, zy (ammettiamolo, pensa come yy e zl sembra un po 'strano, ma dopotutto è una lingua straniera :))

126 è così allettantemente vicino a 128 che potremmo aggiungere t' eb '(per esempio) per gli ultimi due valori - fornendoci un dizionario di 128 valori, per memorizzare 7 bit. Potresti anche aggiungere sostituire yy con d 'e zl con p' o qualsiasi altra cosa.

Analogamente, la parte vocale può essere una singola vocale o una coppia di vocali. Ho eliminato aa, ii e uu perché sembrano troppo strani per me (preferenza personale) anche se si presentano in alcune parole reali (chi ha deciso che il "continuum" dovrebbe essere scritto in quel modo comunque!). Quindi questo dà 27 possibili parti vocaliche: a, e, i, o, u, ae, ai, ao, ..., ue, ui, uo.

27 è vicino a 32, quindi immettere 5 valori utilizzando le vocali accentate (é, â, ecc.). Questo ci dà 5 bit con l'ulteriore vantaggio di alcuni accenti sparsi.

Quindi questo è 12 bit in 2, 3 o 4 lettere.

Per più divertente, se il bit successivo è un 1, inserisci uno spazio il 90% delle volte (a caso) o un segno di punteggiatura l'altro 10% - ma se il bit successivo è uno 0, non inserire qualcosa - basta avviare il prossimo fonema. Capitalizza la prima lettera dopo la punteggiatura.

Questo dovrebbe darvi qualcosa di simile:

Bwaijou t'ei OLP ku bhaproti! Llanoi proimlaroo jaévli.

Forse qualcuno può portarlo oltre.

Answer 2

Leggi qui http://email.about.com/cs/standards/a/base64_encoding.htm

codifica Base64 prende tre byte, ciascuno costituito da otto bit, e li rappresenta come quattro stampabili caratteri nello standard ASCII. Lo lo fa essenzialmente in due passaggi.

Il primo passaggio consiste nel convertire tre byte in quattro numeri di sei bit. Ogni carattere nello standard ASCII consiste di sette bit. Base64 solo utilizza 6 bit (corrispondenti a 2^6 = 64 caratteri) per garantire che i dati codificati siano stampabili e leggibili. Nessuna dei caratteri speciali disponibili in ASCII. I 64 caratteri (da cui il nome Base64) sono 10 cifre, 26 caratteri minuscoli, 26 caratteri maiuscoli nonché "+" e "/".

Se, per esempio, i tre byte sono 155, 162 e 233, il flusso di bit corrispondente (e spaventoso) è 100110111010001011101001, che a volta corrisponde al 6 bit valori 38, 58, 11 e 41.

Answer 3

Personalmente userei C++. Per un programma che avrebbe fatto ciò che si descrive vorrei fare qualcosa di simile:

void JumbleData(const void *src, int srcLen, char *dest) 
{ 
    for(int i = 0; i < srcLen; i++) 
    { 
    unsigned char data = *((unsigned char*)src+i); 
    unsigned char lower = data & 0x0F; 
    unsigned char higher = (data & 0xF0) >> 4; 

    dest = 'a' + lower; dest++; 
    dest = 'a' + higher; dest++ 
    } 
} 

Questo dovrebbe rompere i dati src in 4 sezioni bit, aggiungere che, per 'a' e metterlo nella destinazione. È quindi possibile passare e aggiungere lettere aggiuntive tra, ma solo fino a quando si dispone di una stringa per invertire il processo.

Per renderlo un po 'meno ovvio, userei più di 4 bit alla volta, ma neanche un 8. Ecco un esempio con l'utilizzo di blocchi di 6 bit:

void AddData(char* &dest, unsigned char data); 

void JumbleData(const void *src, int srcLen, char *dest) 
{ 
    for(int i = 0; i < srcLen; i+=3) 
    { 
    unsigned char data0 = *((unsigned char*)src+i); 
    unsigned char data1 = *((unsigned char*)src+i+1); 
    unsigned char data2 = *((unsigned char*)src+i+2); 

    unsigned char chunk0 = data0 & 0x3F; 
    unsigned char chunk1 = (data0 >> 6) | ((data1 & 0x0F) << 2); 
    unsigned char chunk2 = (data1 >> 4) | ((data2 & 0x03) << 4); 
    unsigned char chunk3 = data2 >> 2; 

    AddData(dest, chunk0); 
    AddData(dest, chunk1); 
    AddData(dest, chunk2); 
    AddData(dest, chunk3); 
    } 
} 

void AddData(char* &dest, unsigned char data) 
{ 
    const char vowels[] = {'a', 'e', 'i', 'o'}; 
    char letter1 = 'a' + (data & 0x0F); 
    char letter2 = vowels[((data & 0x0C) >> 2)]; 
    char letter3 = 'n' + ((data & 0x3C) >> 2); 
    *dest = letter1; 
    dest++; 
    *dest = letter2; 
    dest++; 
    *dest = letter3; 
    dest++; 
    *dest = ' '; 
    dest++; 
} 

Ciò farebbe un miscuglio 3 parole lettera per ogni pezzo di 6 bit.

Answer 4

Si potrebbe eseguire un semplice algoritmo di sostituzione con una tabella di conversione impostata che varia in base alla potenza della cifra nel numero originale. Ponderare i valori nelle tabelle di conversione in modo che le vocali e alcune consonanti siano più comuni. Scegli una base abbastanza grande da avere varietà attraverso i luoghi. Per esempio. (Dati hex based):

value | place 
     | 0 1 2 ... 
------|------ - - - 
    0 | a a a ... 
    1 | e e e 
    2 | i i i 
    3 | o o q 
    4 | u u w 
    5 | y q r 
    6 | q w f 
    7 | w r g 
    8 | r f h 
    9 | t g j 
    A | p h k 
    B | s j c 
    C | d k v 
    D | f l b 
    E | g z n 
    F | h x m ... 

(Questo potrebbe essere fatto anche con semplici formule ben scelti per ogni colonna ...)

Quindi,

B4B => "suc" 
3AA => "ohk" 
F62 => "iwm" 
... 

estendere questo fuori a sufficienza colonne per controllare bene la distribuzione di tutti i personaggi. Se i tuoi dati di origine non hanno una distribuzione puramente casuale, potresti anche voler confondere l'ordine da una colonna all'altra. Nota come alcuni caratteri esistono in ogni colonna e alcuni esistono solo una volta. Anche la vocale alla frequenza di consonante può essere ottimizzata cambiando il rapporto medio in ogni colonna.

Prendere blocchi di dati di dimensioni grandi e gestirli attraverso il convertitore, quindi applicare un algoritmo di spaziatura/punteggiatura/capitalizzazione.

(Non v'è alcuna garanzia che non finirà con un all parola conteggio vocale consonante o estremamente basso, ma si può avere l'algoritmo di capitalizzazione rendono tutti i tappi a guardare come un acronimo/sigla)

Answer 5

Sommario

---

Questa soluzione vi permetterà di utilizzare qualsiasi di un gran numero di lingue tra cui assurdità pronunciabile con un'efficienza personalizzabile. Puoi persino creare qualcosa che sembra grammaticalmente corretto, ma senza significato inglese o francese (o peggio, qualcosa che si sposta tra i due come un poliglotta ubriaco). L'idea di base è quella di utilizzare i dati per selezionare continuamente i percorsi da una grammatica senza contesto finché non si esauriscono i dati.

dettagli

---

aggiungere una stringa alla fine del vostro input che non si verifica in qualsiasi punto all'interno di esso ("Questa è la fine del mio ingresso, ringrazio molto" sarebbe molto improbabile si verificano in una stringa di testo crittografato, per esempio.) Puoi farlo senza la stringa ma rende più facile.

Considera l'input come un intero molto lungo codificato a basso bit per primo. Ovviamente la tua macchina non sarà in grado di elaborare un numero intero così grande, ogni volta che avrai un byte alto zero, togli i valori del prossimo byte dal tuo file e moltiplicali.

Crea la tua lingua come context free grammar. Per evitare di dimenticare la codifica, puoi stamparla alla fine del tuo libro. Evita l'ambiguità. Se la tua grammatica è ambigua, non sarai in grado di decodificare. Questo non è difficile, in sostanza non utilizzare lo stesso terminale in due punti, assicurarsi che la concatenazione di due terminali non possa creare un altro terminale e assicurarsi che leggendo l'output si possa sapere dove si trovano i simboli di formattazione.

Ora, per prendere un numero intero e trasformarlo in linguaggio, utilizzare il seguente pseudo-codice che utilizza n per scegliere la produzione da prendere.

cur=grammar.root (cur is a list of tokens) 
n=my input as one big integer 
while(n > 0 || cur != grammar root){ 
    if (cur.first.isTerminalSymbol) { 
     output cur.first 
     cur.pop_first 
     if(cur.isEmpty){ 
      cur = grammar root 
     } 
    }else{ 
     p = grammar[cur.first].number of productions 
     t = n mod p // t = low order digit base p 
     n = n div p // Shift left in base p 
     cur.pop_first 
     cur.push_first(grammar[cur.first].productionNumber[t]) 
    } 
} 

Per decodificare si utilizza un generatore di parser standard come GNU bison che dovrebbe anche aiutare a evitare la creazione di una grammatica ambigua.

Eseguire il parser sull'input. Ora, avviare n a 0. È possibile ottenere il numero di produzione in ogni momento facendo riferimento alla struttura sintattica generata dal parser. Quindi moltiplicare n per il numero di produzioni e aggiungere il numero di produzione per ottenere n dopo quel particolare input. Quando si riempie il byte inferiore della parola macchina, spostarla nel file decodificato. Quando leggi la tua frase univoca, smetti di decodificare.

Esempio 1

---

Questo sarà più chiaro con un esempio o tre.

La mia semplice lingua di esempio è la seguente (i non-terminali sono in maiuscolo). Nota a causa delle grandi dimensioni dei terminali rispetto alla loro profondità dell'albero, non è molto efficiente ma penso che avere più terminali o renderli più brevi possa darti l'efficienza che desideri (fino al numero di bit sprecati per carattere usando n bit per carattere).

• S -> __capital Noun I-Verb Punct | __capital Noun T-Verb Noun Punct
• Noun -> joe | sally | spot | la macchina | il biscotto | il tubo
• I-Verb -> runs | vite | salti | mosche
• T-Verb -> salti sopra | mangia | cresce | giri
• Punct ->. | ! | ?

Si potrebbe facilmente fare questo con sillabe come un'espansione di verbi e nomi. Puoi anche includere frasi di parole e frasi verbali per avere aggettivi ecc. Nella tua lingua. Probabilmente vorrete anche i simboli di paragrafi e capitoli che si suddividono in sottounità appropriate con la formattazione. Il numero di scelte alternative a un certo livello dell'albero determina il numero medio di bit codificati da ciascun simbolo. __capital è un esempio di un simbolo di formattazione che, in uscita, rende maiuscola la parola successiva.

Quindi, immaginare che il mio ingresso diventa il numero 77. Poi vorrei codificarlo come segue:

S va a due cose. 77% 2 = 1. Resto 77/2 = 38.

Ora il nostro numero è 38 e stiamo espandendo __capital, Noun, T-verbo, Noun, Punct

prima parola è __capital che è un simbolo terminale . Output __capital (impostazione della routine di stampa per rendere maiuscola la parola successiva).

Ora espandendo nome. Noun ha 6 opzioni. 38% 6 = 2. 38/6 = 6. Scegliamo lo spot

Ora spot espandibile, verbo T, nome, punto. Spot è il terminale. Punto di uscita. La stampante in modalità maiuscola scrive "Spot" sul file di output.

Ora in espansione T-Verb. Il nostro numero è 6. T-verbo ha 4 opzioni. 6% 4 = 2. 6/4 = 1. Quindi scegliamo "cresce". Nel prossimo passaggio, l'output cresce nel nostro file poiché è un terminale.

Ora espandendo Noun, Punct. Noun ha 6 opzioni. Il nostro numero è 1. 1% 6 = 1 1/6 = 0. Quindi scegliamo "sally", che viene emesso nel passaggio successivo.

Infine stiamo espandendo Punct che ha 3 opzioni. Il nostro numero è 0 (e rimarrà così per sempre - è per questo che aggiungi una stringa di fine testo alla fine del tuo input, altrimenti la decodifica terminerebbe con una stringa infinita di zeri.) Scegliamo ".", che viene emesso.

Ora la stringa corrente da espandere è vuota, quindi la riportiamo alla radice "S". Ma poiché n è 0, l'algoritmo termina.

Così 77 è diventato "Spot grow sally."

Esempio 2

---

Le cose si fanno più efficiente se sostituisco il mio terminali con:

• I-verbo IVS _space | IVS I-verbo
• IVS IVSS vocale
• IVSS w | r
• Vocalico a | e | i | o | u | y
• T-Verb TVS _space | TVS T-Verb
• TVS TVSS vocale
• TVSS p | s
• Noun NS _space | NS
• Voce NSS NS
• NSS j | v

77 rese "Jo papa ja." sotto questa codifica (ed è veramente codificata dal proprio "Jo" e il fatto che papà ha 2 sillabe. L'extra sarebbe una piccola frazione in qualsiasi file libro-lunghezza.)

Esempio 3

---

L'esempio "08F734F7" è "1000111101110011010011110111" in binario, che è "1110111100101100111011110001" al contrario e cioè 250793713 in decimale.

Se corro che attraverso la grammatica più compatto, ottengo:

25079713 % 2 = 1 n=125396856, S-> __capital Noun T-Verb Noun Punct 
125396856 % 2 = 0 n=62698428, Noun->NS _space-> NSS Vowel _space 
62698428 % 2 = 0 n=31349214, NSS->j 
31349214 % 6 = 0 n=5224869, Vowel->a 
5224869 % 2 = 1 n=2612434, T-Verb->TVS T-Verb->TVSS Vowel T-Verb 
2612434 % 2 = 0 n=1306217, TVSS->p 
1306217 % 6 = 5 n=217702, Vowel->y 
217702 % 2 = 0 n=108851, T-Verb->TVSS Vowel _space 
108851 % 2 = 1 n=54425,  TVSS->s 
54425 % 6 = 5  n=9070,  Vowel->y 
9070 % 2 = 0  n=4535,  Noun->NSS Vowel _space 
4535 % 2 = 1  n=2267  NSS->v 
2267 % 6 = 5  n=377  Vowel->y 
377 % 3 = 2  n=125  Punct->? 
125 % 2 = 1  n=62   S->__capital Noun T-Verb Noun Punct 
62 % 2 = 0  n=31   Noun->NSS Vowel _space 
31 % 2 = 1  n=15   NSS->v 
15 % 6 = 3  n=2   Vowel->o 
2 % 2 = 0   n=1   T-Verb->TVSS Vowel _space 
1 % 2 = 1   n=0   TVSS->p 
        n=0   Vowel _space Noun Punct -> "a ja." 

Questo produce: "? Ja pysy Vy Vo pa ja". da 08F734F7 (notare che la mia routine di stampa rimuove gli spazi prima della punteggiatura)

Answer 6

Questa è una vecchia domanda, ma molto interessante.

Una volta volevo fare una conversione simile, ma avendo altri obiettivi. Guid (uuids) di solito non sono a misura di occhi, quindi ho dovuto convertirlo in parole plausibili. Il sistema finale era basato sull'occorrenza della lettera inglese dopo due precedenti. Questo tavolo è stato realizzato utilizzando un corpus di frasi inglesi e quelle che sono state utilizzate troppo raramente sono state escluse. Così il tavolo finale conteneva le linee che sembra

... 
    (key:'_t'; next:'aehioruwy'), 
    (key:'_u'; next:'lmnprst'), 
    (key:'_w'; next:'aehiory'), 
    (key:'ab'; next:'abeilorsuwy'), 
    (key:'ac'; next:'_acehikloqrtuy'), 
    ... 

contenente circa 200-300 linee, dove 'prossimo' è tutte le possibili lettere che possono apparire dopo le lettere 'chiave' (_ è l'inizio o la fine della parola a seconda sul fatto che sia nella chiave o nel prossimo).

Il processo di conversione ha preso il valore corrente, dividerlo modulo lunghezza (successivo) e prende il resto come la lettera corrispondente come il prossimo simbolo "plausibile", il quoziente diventa nuovo valore corrente. Per evitare parole lunghe, c'era un trucco per terminare esplicitamente le parole usate simmetricamente mediante codifica e decodifica.Tale sistema potrebbe produrre per esempio tali sequenze (ingresso per ciascuno è 128 bit guid/uuid)

Furepas_Wann_Hunkare_Rylacid_Makinuag_Dreem 

Togo_Ragam_Omb_Bonsbe_Gonn_Eclecki_Op 

o se prendiamo alcuni GUID ampiamente utilizzati, ad esempio MS IWebBrowser2 {D30C1661-CDAF-11D0-8A3E-00C04FC9E26E }

Lakar_Rupplex_Waylagit_Munghim_Paddato_Molu 

("Lakar Rupplex" è un buon nome umano per un browser, non è vero?)

per quanto riguarda la densità, questo sistema ha dato circa 3 bit per la densità lettera.