6

大きくて「一意の」整数（実際にはSHA1ハッシュ）があります。

注：ここでSHA1ハッシュについて話している間、これは暗号化/セキュリティの質問ではありません！私はSHA1を壊そうとはしていません。それが役立つ場合は、SHA1の代わりにランダムな160ビット整数を想像してみてください。

私は（楽しむ以外の理由はありませんが）そのSHA1ハッシュをコンピューターで生成された（疑似）英語のフレーズにマップするアルゴリズムを見つけたいと思っています。マッピングは双方向である必要があります（つまり、アルゴリズムを知っていると、そのフレーズから元のSHA1ハッシュを計算できる必要があります）。

フレーズは意味をなす必要はありません。私はナンセンスの段落全体でさえ解決するでしょう。（ただし、段落の品質（英語性）は、単なるフレーズよりも優れているはずです。）

より良いアルゴリズムは、より短く、より自然に見える、よりユニークなフレーズを生成します。

バリエーション：ハッシュの一部しか扱えなくても大丈夫です。たとえば、最初の6桁の16進数で問題ありません。

生成されたフレーズの可能な使用法：GitコミットIDの人間が読めるバージョン。そのコミットから構築された、特定のプログラムバージョンのモットーとして使用します。（私が言ったように、これは「楽しみのため」です。これが非常に実用的であるとは言いません。または、SHA1自体よりもはるかに読みやすくなっています。）

考えられるアプローチ：過去に、SHAから読み取ったビットに従って、（単語の）確率テーブルを作成し、マルコフ連鎖としてフレーズを生成し、ジェネレーターをシード（確率ツリーからブランチを選択）しようとしました。これはあまり成功しませんでした、結果として生じるフレーズは長すぎて醜いものでした。これがバグなのか、アルゴリズムの一般的な欠陥なのかはわかりません。十分に早く放棄しなければならなかったからです。

今、もう一度問題を解決しようと考えています。これにアプローチする方法について何かアドバイスはありますか？マルコフ連鎖アプローチがここで機能すると思いますか？他に何かありますか？

4

4 に答える 4

3

非常に単純なアプローチは次のとおりです。たとえば、1024個の名詞、1024個の動詞、および1024個の形容詞のリストをそれぞれ取得します。その場合、あなたのフレーズは次の形式の文になる可能性があります

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].

もう少し言語学的に考えると、おそらく少し複雑な広告を作成できるため、繰り返しのように見える文は作成できません（たとえば、単数形/複数形の場合は少し、時制の場合は2つなど）。長い単語リストはさらに数ビットを消費しますが、私の推測では、かなりエキゾチックな単語に非常に速く到達します。

于 2011-01-13T20:23:26.927 に答える
1

見てみましょう...英語には約1,000,000語があります。これは、ワードあたり約20ビットです。SHA1は160ビットなので、8ワードが必要です。理論的には、オックスフォード英語辞典のn番目の単語を取得するだけです。nは一度に20ビットのグループです。

さて、より自然にするために、いくつかの簡単なアルゴリズムを使用して、単語のタイプ（名詞、動詞...）に応じて、単語の間に「in / at / on / and/the...」を追加してみることができます。（もちろん、これらの単語はすべてベース辞書から削除する必要があります）。

アルゴリズムはリバーシブルです。追加したすべての単語を削除し、各単語を20ビットのインデックスに変換するだけです。

また、グーグル「侮辱ジェネレーター」を試してみてください。それらのジェネレーターのいくつかはかなりいいです。ただし、組み合わせの数はわかりません。

オックスフォード英語辞書は、CD-ROMで500,000語（19ビット）以上で購入できます。ただし、単語とそのタイプを簡単に抽出できるかどうかはわかりません。合法かどうかはわかりませんが、辞書のエントリで特許を申請することはできないと思います...

于 2011-01-13T18:49:34.943 に答える
1

これは古い質問ですが、エントロポエトリーはJavaScript（ノード/フロントエンド）ライブラリであり、この問題も解決します。マルコフ詩とハフマン符号化を組み合わせているため、同じ辞書（つまり、同じバージョンのライブラリ）が与えられると、詩↔✧の数値の変換は双方向になります。

例、Nodeコマンドラインから：

> 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>

そして、テクノロジーが進歩するにつれて、2011年に「楽しいだけ」のアイデアのように見えたものが2017年にいくつかの実際の用途を持っています：暗号通貨の秘密鍵（ブレインウォレット）、Dat/IPFSリンクなどを記憶する。

于 2017-12-31T01:47:40.163 に答える
0

ハッシュ関数は、データが壊れている（安全でない）場合を除いて、ハッシュからデータを取得することが（妥当な制限内で）不可能であることを意味します。

質問はSHA-1ハッシュアルゴリズムを破ることについてであるはずです-グーグルを見てください、それはそれほど破られていません。いいえ、SHA-1ハッシュコードから英語のフレーズを作成することはできません。可能であれば、それについて巨大な論文を作成してください。それらの多くは役に立たないので、これは画期的なことです:-)

編集：ハッシュの一部だけで十分な場合は、ブルートフォース（+ハッシュ<->フレーズの単純なマップ、おそらくファイルまたはデータベース内）をお勧めします。ハッシュアルゴリズムを破ることは非常に「強力なスープ」です（難しい問題）。

Edit2：質問をするときは、私のせいではなく、より具体的にします...これを削除しないので、周りの他の暗号通貨の人を怖がらせます:-)

于 2011-01-13T18:44:48.127 に答える