2^25 のランダムな文字列の SHA256 ハッシュを見つける必要があります。そして、衝突を探します (たとえば、最後の 50 ビットのハッシュのみに誕生日のパラドックスを使用します)。
string:hash ペアを dict 変数に格納しています。次に、変数を値 (キーではなく) でソートし、O(n) ループを使用して衝突を探します。
問題は、2^25 文字列とその 2^25 ハッシュがあるため、dict 変数には 2^50 値が含まれることです。これは非常にリソースを消費します。では、たとえば 1GB 程度の限られた RAM でこれを行うにはどうすればよいでしょうか。
私がすでに試したこと：
1.これを6GBのスワップスペースで実行します。プログラムは一晩実行され、まだ完了していませんでした。これは基本的に、O(n_square) 検索よりもさらに遅くなります! ハッシュは、約 3.2 GB の RAM 使用量で計算されます。しかし、その後 sort コマンドになると、使用される RAM が再び急増し始めます。Python の並べ替えは In-Place-Quicksort を使用します
:(
データベースなどを使用することは想定されていません。せいぜいテキストファイルですが、それは役に立ちません。また、私はPythonにはかなり慣れていませんが、それがあなたの答えのレベルを制限することはありません.
PS: これは課題です。300MB RAM で 1 分以内に衝突を発見したと主張する人もいます。それが本当かどうかはわかりません。私は問題を解決しましたが、答えは到達できません! 仕事中なので、今はコードにアクセスできません。すぐに追加します。
コード：
from Crypto.Hash import SHA256
import os
import random
import string
from operator import itemgetter
def shaa():
trun=[]
clist={}
for i in range(0,33554432):
sha=SHA256.new(str(i)).hexdigest()
sha=int(bin(int(sha,16))[-50:],2)
clist[i]=sha
print 'Hashes done.'
clist=sorted(clist.items(), key=itemgetter(1))
for i in range(0,33554432):
if(clist[i]==clist[i+1]):
#print string[i],string[i+1]
print clist[i]
return 1
return 2
result=2
while(result==2):
result=shaa()