Czy istnieją algorytmy które pozwalają na tworzenie skrótu który byłby odwracalny, tzn ze kiedy się posiada klucz można ze skrótu odtworzyć dane wejściowe?. Zakładam ze jeśli takie algorytmy istnieją to potrzebują do działania ogromnej ilości ramu oraz szybkiego procesora i wykonanie zajmuje dużo czasu,ale mimo tego chciałbym znaleźć jakieś materiały dotyczące tego zagadnienia.
0
1
Chodzi ci o algorytm który potrafiłby stworzyć skrót jakichś danych (zmniejszając efektywnie ich rozmiar) ale umożliwiające odwrócenie procesu>
Tak, nazywamy te algorytmy algorytmami kompresji.
Prawdziwe funkcje skrótu/funkcje hashujące są z zasady nieodwracalne i ich "łamanie" polega na szukaniu konfliktów. Konflikt polega na tym że funkcja skrótu dla różnych danych wejściowych może zwrócić ten sam hash. W efekcie mimo że złamiesz zashashowanie hasło, to wcale nie musisz faktycznego hasła poznać (bo twoje zahashowane hasło lubie_kozy_i_owce może mieć taki sam skrót jak lubie_konie_i_jednorożce)
0
skrót (hash) z definicji jest jednostronny. co najwyżej możesz brute forcem próbować znaleźć kolizję, a brute force przyspieszyć używając rainbow tables ("tęczowe tablice" - po polsku to brzmi jak męskie stringi). dany hash może powstać z nieskończenie wielu kombinacji danych, więc nie masz żadnej gwarancji, że znaleziona kolizja to oryginalne dane.
odwracalne jest szyfrowanie oraz - tak jak napisał Shalom - kompresja bezstratna.
0
No wiec zmodyfikuje moje pytanie. Czy dysponując dostatecznie duzą ilosc ramu i szybkim procesorem , mozna dane kompresowac od maksymalnie malych rozmiarow? Jakie najlepsze do tego sa algorytmy?
0
Co to znaczy "od maksymalnie małych rozmiarów"?
Mam wrażenie, że pomyliłeś komputer ze szklaną kulą.
0
@sbs1 nie, bo entropii nie oszukasz. Nie da się kompresować do dowolnie mały rozmiarów.
http://pl.wikipedia.org/wiki/Kompresja_bezstratna
Jeśli chodzi o aplikacje kompresujące to bardzo dobrze sprawdzają się takie korzystające z http://pl.wikipedia.org/wiki/UHarc
0
sbs1 napisał(a)
No wiec zmodyfikuje moje pytanie. Czy dysponując dostatecznie duzą ilosc ramu i szybkim procesorem , mozna dane kompresowac od maksymalnie malych rozmiarow? Jakie najlepsze do tego sa algorytmy?
Zastanów się o co konkretnie Ci chodzi:
- o kompresję
- o szyfrowanie
- o skrót (MD5, SHA-x)
Nie da się skompresować danych do dowolnie małego rozmiaru - są ograniczenia.
Przyda się też poczytać coś z teorii informacji:
http://pl.wikipedia.org/wiki/Kodowanie_Huffmana
Najlepszy kompresor jaki znam (bezstratny) - który jest w miarę przystępny (czas kompresji/stopień kompresji) to 7-zip.
Ale chyba nie o to Ci chodzi.
1
A jeśliby zastosować słownik?
0
Strony na których można znaleźć informacje o albo porównania programów kompresujących bezstratnie:
- http://mattmahoney.net/dc/text.html - kompresja zrzutu XML z Wikipedii,
- http://www.squeezechart.com/ - wiele rodzajów porównań
- http://nanozip.net/ http://freearc.org/ - szybka i dobra kompresja
- http://encode.ru/forum.php - dużo najświeższych programów kompresujących,
Czy dysponując dostatecznie duzą ilosc ramu i szybkim procesorem
Nie znam programu pakującego, który ma jakieś wymagania co do procesora - po prostu na X razy wolniejszym procesorze program będzie działał X razy wolniej. Kompresor to nie gra, żeby się stał niegrywalny.
Co rozumiesz pod pojęciem słownik? Jeśli słownik to stan obliczony na podstawie wcześniejszych danych wejściowych to w zasadzie każdy algorytm kompresujący posiada słownik.
0
To niech mi ktoś wytłumaczy jak działa taki program: KGB.
Przykładowo jest tu spakowane tym programem 670MB do 64KB:
http://chomikuj.pl/genio1396/GTA/gta+IV/GTA+IV+ULTRA+RIP+64KB,419553951.kgb
Wszystko wypakowuje się wiele godzin,ale za to zajmuje ekstremalnie mało miejsca i właśnie o to mi chodziło cały czas w tym temacie.
0
@sbs1:
A udało ci się kiedyś taki plik rozpakować?
Czy komukolwiek się udało?
Mi np.po paru godzinach wywaliło błąd (potem musiałem kupić nową matrycę, ponieważ ze złości mój komputer pocałował podłogę :P).
0
Ten plik jest po prostu urwany po 64KB (w całości jest jedynie autorun.inf i kawałek Autorun.exe), oryginalne archiwum ważyło o wiele więcej.
0
Aha, to dzieki za odpowiedzi :)