Teoretyczne informatyka hash-function

4

Czy istnieje funkcja skrótu dla zbioru liczb całkowitych (tj. Wielu), która ma dobre gwarancje teoretyczne?

Ciekawe, czy istnieje sposób przechowywania skrótu zbioru liczb całkowitych, który ma następujące właściwości, najlepiej: Wykorzystuje spację O (1) Można go zaktualizować, aby odzwierciedlał wstawianie lub usuwanie w czasie O (1) Dwie identyczne kolekcje (tj. Kolekcje, które mają te same elementy o tych samych wielokrotnościach) zawsze powinny mieć skrót do tej …

36 ds.algorithms ds.data-structures hash-function

3

Jaka jest różnica między drugim atakiem preimage a atakiem kolizyjnym?

Wikipedia definiuje drugi atak preimage jako: biorąc pod uwagę ustaloną wiadomość m1, znajdź inną wiadomość m2, taką jak hash (m2) = hash (m1). Wikipedia definiuje atak zderzeniowy jako: znajdź dwa dowolne różne komunikaty m1 i m2 takie, że hash (m1) = hash (m2). Jedyną różnicą, którą widzę, jest to, że …

24 cr.crypto-security hash-function

1

Dlaczego ważne jest, aby sekret znajdował się na końcu podczas podpisywania przy użyciu MD5?

często mówi się, że używając algorytmu MD5 do podpisywania dowolnych informacji, wspólny sekret musi znajdować się na końcu. Dlaczego?

16 hash-function cr.crypto-security

1

Skróty filtra Bloom: więcej czy więcej?

Podczas wdrażania filtra Bloom tradycyjne podejście wymaga wielu niezależnych funkcji skrótu. Kirsch i Mitzenmacher pokazali, że tak naprawdę potrzebujesz tylko dwóch, a resztę możesz wygenerować jako kombinacje liniowe. Moje pytanie brzmi: jaka tak naprawdę jest różnica między dwiema funkcjami skrótu i jedną z podwójną entropią? Wynika to z patrzenia na …

15 ds.data-structures it.information-theory hash-function

1

Ponowne użycie 5 niezależnych funkcji skrótu do sondowania liniowego

W tablicach skrótów, które rozwiązują kolizje za pomocą sondowania liniowego, w celu zapewnienia oczekiwanej wydajności , zarówno konieczne, jak i wystarczające jest, aby funkcja skrótu pochodziła z 5-niezależnej rodziny. (Wystarczalność: „Sondowanie liniowe ze stałą niezależnością”, Pagh i in. , Konieczność: „O k-niezależności wymaganej przez sondowanie liniowe i niezależność minutową”, Pătraşcu …

14 ds.data-structures hash-function randomized-algorithms security

3

Asocjacyjne mieszanie skrótów

Rozważ mało pojedynczo połączoną listę w czysto funkcjonalnym otoczeniu. Jego pochwały śpiewano ze szczytów górskich i nadal będą śpiewane. Zajmę się tutaj jedną z wielu jego mocnych stron i pytaniem, w jaki sposób można ją rozszerzyć na szerszą klasę czysto funkcjonalnych sekwencji opartych na drzewach. Problem jest następujący: Chcesz przetestować …

14 ds.data-structures cr.crypto-security functional-programming hash-function

1

Ile niezależności jest potrzebne do oddzielnego łączenia?

Jeśli kulek zostanie rozmieszczonych losowo w koszach równomiernie, w najbardziej obciążonym pojemniku znajdują się kulki z dużym prawdopodobieństwem. W „The Power of Simple Tabulation Hashing” Pătraşcu i Thorup wspominają, że „Chernoff-Hoeffding ogranicza się do aplikacji o ograniczonej niezależności” ( lustro ) pokazuje, że to ograniczenie populacji najbardziej obciążonego pojemnika utrzymuje …

13 ds.data-structures randomness hash-function independence

1

Stan badań nad atakami zderzeniowymi SHA-1

Bezpieczeństwo SHA-1 zostało omówione, ponieważ algorytm znajdowania kolizji został po raz pierwszy opublikowany w CRYPTO 2004, a następnie został ulepszony. Wikipedia wymienia kilka odniesień , jednak wydaje się, że najnowsze badania opublikowane (a później wycofane) na ten temat miały miejsce w 2009 r. (Cameron McDonald, Philip Hawkes i Josef Pieprzyk …

11 cr.crypto-security hash-function cryptographic-attack

1

Czy istnieją „refleksyjne” algorytmy mieszające?

Czy istnieje klasa algorytmów mieszających, teoretycznych lub praktycznych, tak że algorytm w tej klasie można uznać za „zwrotny” zgodnie z definicją podaną poniżej: hash1 = algo1 („tekst wejściowy 1”) hash1 = algo1 („tekst wejściowy 1” + hash1) Operator + może być konkatenacją lub dowolną inną określoną operacją, aby połączyć wynik …

11 ds.algorithms hash-function

2

Jak wybrać funkcjonalną strukturę danych słownika?

Przeczytałem trochę o następujących strukturach danych: Bagwell's Ideal Hash Próby Dynamiczne tabele skrótów Larsona Czerwono-czarne drzewa Drzewa Patricia ... i jestem pewien, że jest tam wielu innych. Niewiele widziałem na temat tego, do czego każdy jest bardziej odpowiedni, ani dlaczego wybieram siebie nawzajem. Oto kilka pytań w tym zakresie: O …

10 ds.data-structures functional-programming tree hash-function

2

Hashowanie zbiorów liczb całkowitych do testów włączenia

Szukam funkcji skrótu nad zestawami H (.) I relacją R (.,.) Tak, że jeśli A jest zawarte w B, to R (H (A), H (B)). Oczywiście R (.,.) Musi być łatwe do zweryfikowania (czas stały), a H (A) należy obliczyć w czasie liniowym. Jednym z przykładów H i R jest: …

10 ds.algorithms hash-function

2

Prawie uniwersalny skrót znaków w i sublinearnej przestrzeni

Oto dwie rodziny funkcji skrótu na ciągach :x⃗ =⟨x0x1x2…xm⟩x→=⟨x0x1x2…xm⟩\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle Dla prime i , dla \ in \ mathbb {Z} _p . Dietzfelbinger i in. pokazane w „Wielomianowe funkcje skrótu są niezawodne”, że \ forall x \ neq y, P_a (h ^ 1_a …

9 ds.data-structures randomness hash-function

1

Jak Knuth wyprowadził A?

Interpretując klucze jako liczby naturalne, możemy użyć następującej formuły. h(k)=⌊m(kAmod1)⌋h(k)=⌊m(kAmod1)⌋\begin{equation} h(k) = \lfloor m (kA\bmod{1}) \rfloor \end{equation} Trudno mi zrozumieć, w jaki sposób wybieramy wartość A, gdzie: 0<A<10<A<1\begin{equation} 0 < A < 1 \end{equation} Według Knutha optymalna wartość to: A≈(5–√−1)/2=0.6180339887...A≈(5−1)/2=0.6180339887...\begin{equation} A \thickapprox (\sqrt{5} - 1) / 2 = 0.6180339887... \end{equation} …

9 hash-function

1

Dlaczego SHA-224 i SHA-256 używają różnych wartości początkowych?

Wikipedia - mówi SHA-2 SHA-224 jest identyczny z SHA-256, z wyjątkiem tego, że: początkowe wartości zmiennych od h0 do h7 są różne, i wyjście jest konstruowane przez pominięcie h7. RFC3874 - 224-bitowa jednokierunkowa funkcja skrótu: mówi SHA-224 Zastosowanie innej wartości początkowej zapewnia, że skróconej wartości skrótu komunikatu SHA-256 nie można …

9 cr.crypto-security hash-function

2

Jaka jest optymalna struktura danych dla drzewa map.

Szukam struktury danych, która jest w zasadzie drzewem map, w których mapa w każdym węźle zawiera nowe elementy, a także elementy w mapie jego węzła nadrzędnego. Przez mapę rozumiem tutaj mapę programowania z kluczami i wartościami, taką jak mapa w STL lub dict w python. Na przykład może istnieć węzeł …

9 ds.data-structures tree hash-function

Pytania otagowane jako hash-function