Génération d'une phrase pseudo-naturelle à partir d'un grand entier de manière réversible

Question

J'ai un entier grand et "unique" (en fait un hachage SHA1).

Note: Pendant que je parle ici de hash SHA1, c'est pas une question cryptographie/sécurité! Je suis pas essayant de casser SHA1. Imaginez un entier aléatoire de 160 bits au lieu de SHA1 si cela peut aider.

Je veux (pour aucune autre raison que de s'amuser) trouver un algorithme pour mapper ce hachage SHA1 à une phrase (pseudo) anglaise générée par ordinateur. Le mappage doit être bidirectionnel (c'est-à-dire, connaissant l'algorithme, il faut être capable de calculer le hachage SHA1 d'origine à partir de cette phrase.)

La phrase n'a pas de sens. Je me contenterais même de tout un paragraphe de non-sens. (Bien que la qualité - anglaisness - d'un paragraphe devrait probablement être meilleure que pour une simple phrase.)

Un meilleur algorithme produirait des phrases plus courtes, plus naturelles et plus uniques.

Une variante: c'est OK si je ne peux travailler qu'avec une partie de hash. Dites, les six premiers chiffres hexadécimaux sont bien.

L'utilisation possible de la phrase générée: la version lisible par un humain de Git commit ID, à utiliser comme devise pour une version de programme donnée, qui est construite à partir de cette validation. (Comme je l'ai dit, c'est "pour le plaisir" Je ne prétends pas que c'est très pratique - ou être beaucoup plus lisible que le SHA1 lui-même.)

Approche possible: Dans le passé, j'ai essayé de construire une table de probabilités (de mots), et générer des phrases comme des chaînes de Markov, ensemencer le générateur (ramasser des branches de l'arbre de probabilité), selon les bits que j'ai lus dans le SHA. Ce n'était pas très réussi, les phrases résultantes étaient trop longues et laides. Je ne suis pas sûr que ce soit un bug, ou la faille générale dans l'algorithme, puisque j'ai dû l'abandonner assez tôt.

Maintenant, je pense à essayer de résoudre le problème une fois de plus. Des conseils sur la façon d'aborder cela? Pensez-vous que l'approche de la chaîne de Markov peut fonctionner ici? Autre chose?

Answer 1

Une approche très simple serait: Prendre la liste de dire 1024 noms, 1024 verbes et 1024 adjectifs chaque. Votre phrase pourrait alors être phrase de la forme

noun[bits_01-10] verb[bits11-20] adjective[bits21-30] verb[bits31-40], 
noun[bits_41-50] verb[bits51-60] adjective[bits61-70] verb[bits71-80], 
noun[bits_81-90] verb[bits91-100] adjective[bits101-110] verb[bits111-120] and 
noun[bits_121-130] verb[bits131-140] adjective[bits141-150] verb[bits151-160]. 

Avec un peu plus la pensée linguistique, vous pouvez probablement construire annonce un peu plus compliqué donc pas si répétitif phrases recherche (par exemple, un peu pour le singulier/pluriel, un peu de deux pour différents temps, ...). Les listes de mots plus longues utilisent un peu plus de bits mais je pense que vous atteignez des mots plutôt exotiques assez rapidement.

Answer 2

La fonction de hachage signifie qu'il n'est pas possible (dans des limites raisonnables) d'obtenir une donnée de hachage, sauf si elle est brisée (non sécurisée).

Question devrait être de briser SHA-1 algorithme de hachage - regardez Google, il est pas cassé. Donc non, vous ne pouvez pas créer phrase en anglais à partir du code de hachage SHA-1, si vous pouvez, s'il vous plaît faire un énorme papier à ce sujet, beaucoup d'entre eux sont inutiles, ce serait révolutionnaire :-)

Edit: si seulement partie de hachage est assez, je suggère juste la force brute (+ simple carte de hachage < -> phrase, éventuellement dans un fichier ou db), l'algorithme de hachage de rupture est très "soupe forte" (problème difficile).

Edit2: gars être plus précis lorsque vous demandez question, pas de ma faute ... Je ne supprimera pas cette sorte qu'il fait peur des autres gars :-) autour de crypto

Answer 3

Nous allons, permet de voir ... La langue anglaise has about 1,000,000 words. C'est environ 20 bits par mot. SHA1 est de 160 bits, donc vous aurez besoin de 8 mots.Théoriquement, tout ce que vous avez à faire est de prendre le nième mot du dictionnaire anglais oxford, où n est un groupe de 20 bits à la fois. Maintenant, pour le rendre plus naturel, vous pouvez essayer d'ajouter "in/at/on/et/the ..." entre les mots, en fonction de leur type (noms, verbes ...) en utilisant un algorithme simple . (Vous devriez supprimer tous ces mots de votre dictionnaire de base, bien sûr).

L'algorithme est réversible: Supprimez simplement tous les mots que vous avez ajoutés et convertissez chaque mot en index 20 bits.

Essayez également google "générateur d'insultes". Certains de ces générateurs sont plutôt sympas. Cependant, je ne suis pas sûr du nombre de combinaisons.

You can buy l'Oxford English Dictionary sur CD-ROM avec plus de 500 000 mots (19 bits). Cependant, je ne suis pas sûr que ce serait facile d'extraire les mots et leurs types. Je ne sais pas si c'est légal, mais je pense que vous ne pouvez pas revendiquer un brevet sur les entrées de dictionnaire ...

Answer 4

Ceci est une vieille question mais entropoetry est une bibliothèque JavaScript (Node/frontend) qui résout également ce problème. Il combine la poésie de Markov avec le codage de Huffman, donc donné le même dictionnaire (c'est-à-dire, la même version de la bibliothèque), la conversion des numéros de poésie sera bidirectionnelle.

Exemple, à partir de la ligne de commande Noeud:

> var Poet = require('entropoetry'); var p = new Poet(); 
> p.stringify(Buffer.from('deadbeef', 'hex')) 
'old trick of loving you\nif you but' 
> console.log(p.parse(`old trick of loving you 
... if you but`)) 
<Buffer de ad be ef> 

Et comme technology marches on, ce qui semblait être un « fun que » l'idée en 2011 a des utilisations réelles en 2017: mémorisation des clés privées de crypto-monnaie (porte-monnaie du cerveau), Liens Dat/IPFS, etc.