funkcja haszujaca

arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

funkcja haszujaca

Post autor: arigo »

witam

wlasnie tworze pewiem programik i potrzebuje w nim zastosowac funkcje haszujaca. cel podstawowy musi byc ona latwa do zaimplementowania przy uzyciu podstawowych operacji bitowych. dane wejsciowe beda rzedu 10 bajtow a na wyjsciu 4. mam w glowe pare takich funkcji lecz niestety nie spelniaja one wymagan dotyczacych asymetrycznosci a co za tym idzie kolizji.

bylbym wdzieczny za roznego rodzaju wskazowki
Hrabia

funkcja haszujaca

Post autor: Hrabia »

pierwsze primo:
arigo pisze:potrzebuje w nim zastosowac funkcje haszujaca.
A co to jest ta funkcja haszująca? Hę?
Zapewne tak sobie przetłumaczyłeś angielskie 'hash function'.
Tylko że po polsku, w zależności od kontekstu, używa się terminów 'funkcja mieszająca' lub 'funkcja skrótu'. To są różne rzeczy, niestety. Wnioskując z całości twojego postu, chodzi ci o funkcję skrótu. Trzymaj się tego, bo taka jest Polska Norma w tej dziedzinie.
(Musiałem umieścić tę uwagę, bo niesamowicie irytują mnie podobne pseudoterminy.)

drugie primo:
arigo pisze:a na wyjsciu 4.
Hmm. 4 bajty, czyli 32 bity. No a 32-bitowa funkcja skrótu, nawet jakaś najlepsza, jest, że tak powiem, 'z natury' bardzo kolizyjna. Więc nic dobrego, moim zdaniem, i tak nie osiągniesz.
No ale może w jakimś stopniu to ci pomoże:
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

funkcja haszujaca

Post autor: arigo »

po 1 jak nie masz zamiaru odpowiadac na temat i wniesc czegos do dyskusji to sie nie wypowiadaj

po 2 tlumaczenia na jezyk polski sa bardzo rozne i tak kazdy wie o co dokladnie chodzi wiec dyskusje na tematy humanistyczne mozesz sobie darowac

po 3 logiczne ze skoro uzylem slowa 10 bajtow a potem pojawia sie sama cyfra to wiadomo ze musi ona dotyczyc bajtow to jest tzw. unikanie zbednych powtorzen wyrazow tak ad. Twej wielkiej poprawnosci humanistycznej postow

po 4 nie rozumiesz o co mi chodzi. to ze funkcje skrotu (pisze tak zebys nie mial problemow ze zrozumieniem o czym mowimy) sa z natury kolizyjne to wie kazdy, ja wyraznie zaznaczylem ze szukam algorytmu asymetrycznego, zeby znajac wyjscie nie mozna bylo otworzyc wejscia. wtedy sama kolizyjnosc juz nie jest az tak wielkim problemem dla tego zastosowania co robie. dodatkowo kolizyjnosc zmiejszam przez filtrowanie wejscia tylko do znakow alfanumerycznych

po 5 wyraznie zaznaczylem ze ten algorytm ma byc prosty do zaimplementowania z wykorzystaniem podstawowych operatorow bitowych. to ze w C sa piekne funkcje skrotu kazdy wie, problem sie pojawia tutaj ze ja ta funkcje pisze w asm i nie moze ona bardzo duzo rozkazow zajmowac.

po 6 ten post napisany jest takim tonem jakim odpowiedz na moje zapytanie
Awatar użytkownika
Elvis
Użytkownik
Użytkownik
Posty: 765
Rejestracja: 17 paź 2004, o 18:09
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 89 razy

funkcja haszujaca

Post autor: Elvis »

A program masz zlecony czy z własnej woli go piszesz?
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

funkcja haszujaca

Post autor: arigo »

z wlasnej woli w wolnych chwilach sobie rozne projekty robie
Awatar użytkownika
Elvis
Użytkownik
Użytkownik
Posty: 765
Rejestracja: 17 paź 2004, o 18:09
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 89 razy

funkcja haszujaca

Post autor: Elvis »

Moim zdaniem mógłbyś jednak opisać problem, bo nie wszyscy znają odpowiednie słownictwo (choćby ja).
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

funkcja haszujaca

Post autor: arigo »

hmmm tzn jak opisac problem jakiego slownictwa nie znasz ??
problemem jest znalezienie funkcji skrotu ktora spelnia warunki postawione w pierwszym poscie
Awatar użytkownika
Elvis
Użytkownik
Użytkownik
Posty: 765
Rejestracja: 17 paź 2004, o 18:09
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 89 razy

funkcja haszujaca

Post autor: Elvis »

Widzę, że bez znajomości tych pojęć nie da się zrozumieć problemu, więc nie będę już przeszkadzać.
gnicz
Użytkownik
Użytkownik
Posty: 507
Rejestracja: 16 wrz 2004, o 18:24
Płeć: Kobieta
Lokalizacja: ???

funkcja haszujaca

Post autor: gnicz »

CRC32? 32 bity to jednak troszke malo. Dlaczego nie poswiecisz wiecej bitow na hash?

Pozdrawiam, GNicz
Hrabia

funkcja haszujaca

Post autor: Hrabia »

Hehe, to żeś se ulżył. Ale to dobrze, przynajmniej będziesz spał spokojniej. Niestety, w żadnym punkcie nie masz racji.
arigo pisze:po 1 jak nie masz zamiaru odpowiadac na temat i wniesc czegos do dyskusji to sie nie wypowiadaj
Ależ mam zamiar i, wbrew pozorom, odpowiedź była na temat. Nawet jakiegoś linka zarzuciłem dla zachęty (32 bity i te sprawy...).
arigo pisze:po 2 tlumaczenia na jezyk polski sa bardzo rozne i tak kazdy wie o co dokladnie chodzi wiec dyskusje na tematy humanistyczne mozesz sobie darowac
Nie wiesz, jak bardzo się mylisz. Nomenklatura w niektórych przypadkach jest niesamowicie istotna. Bo termin funkcji 'haszującej' w j. polskim nie istnieje, przynajmniej jeśli idzie o kryptografię (mimo to w domu możesz sobie tak wołać). A funkcja skrótu i mieszająca to dwie zupełnie różne rzeczy, terminologicznie poprawne. I wcale kontekst wypodziedzi cię nie usprawiedliwia. I nie są to żadne wywody humanistyczne. Musisz się po prostu przyzwyczaić do pewnych rzeczy, takich, jak używanie poprawnej terminologii. Wyobraź sobie np. sytuację, gdy ktoś tłumaczy słowo 'field' w kontekście matematycznym z angielskiego na polski jako 'pole'. I co, nie zwróciłbyś uwagi? Oczywiście, bo po polsku nie ma 'pola' tylko jest 'ciało'. Widzisz, termin to termin.
arigo pisze:po 3 logiczne ze skoro uzylem slowa 10 bajtow a potem pojawia sie sama cyfra to wiadomo ze musi ona dotyczyc bajtow to jest tzw. unikanie zbednych powtorzen wyrazow tak ad. Twej wielkiej poprawnosci humanistycznej postow
A tego to zupełnie nie rozumiem, bo się wcale do tego nie czepiałem. Czytaj ze zrozumieniem.
arigo pisze:po 4 nie rozumiesz o co mi chodzi. to ze funkcje skrotu (pisze tak zebys nie mial problemow ze zrozumieniem o czym mowimy) sa z natury kolizyjne to wie kazdy, ja wyraznie zaznaczylem ze szukam algorytmu asymetrycznego, zeby znajac wyjscie nie mozna bylo otworzyc wejscia. wtedy sama kolizyjnosc juz nie jest az tak wielkim problemem dla tego zastosowania co robie. dodatkowo kolizyjnosc zmiejszam przez filtrowanie wejscia tylko do znakow alfanumerycznych
O, to jest ciekawy kawałek. Ale po kolei.
Rozumiem o co ci chodzi. (Nie mam problemów ze zrozumieniem o czym mówimy.) Tak, są kolizyjne, tylko czasami trudno to udowodnić.
Algorytmu asymetrycznego? O, w tym miejscu mnie zaskoczyłeś trochę. Bo skoro użyłeś słowa 'asymetryczność' względem funkcji (algorytmu) skrótu, to myślisz lub przypuszczasz, że istnieją również symetryczne f. skrótu. Tylko, że to jest bezsens. Bo f. skrótu są z definicji jednokierunkowe i nie ma możliwości ich odwrócenia, niezależnie od tego, ile by nie powodowały kolizji. Bo kolizje z tym akurat nie mają nic wspólnego.
Co do zmniejszania kolizyjności. W jaki sposób filtrujesz to wejście? Usuwając z niego znaki nie alfanumeryczne? Np. tak dla wejścia trójbajtowego: a#b daje ab? I wejście masz blokowe? Bo jeśli tak, to ty tym kolizyjność zwiększasz nie zmniejszasz. Jakie masz wejście, blokowe czy strumieniowe?
arigo pisze:po 5 wyraznie zaznaczylem ze ten algorytm ma byc prosty do zaimplementowania z wykorzystaniem podstawowych operatorow bitowych. to ze w C sa piekne funkcje skrotu kazdy wie, problem sie pojawia tutaj ze ja ta funkcje pisze w asm i nie moze ona bardzo duzo rozkazow zajmowac.
Hmm. To może wytłumacz, które operatory bitowe uważasz za podstawowe.
A, i pewnie tego kodu który ci w linku zapodałem nie przeczytałeś, no nie?
arigo pisze:po 6 ten post napisany jest takim tonem jakim odpowiedz na moje zapytanie
Heh. A skąd wiesz jakim tonem go pisałem? Zapewniam cię, że pisałem go tonem wesołym, radosnym i pogodnym. W również ten sam sposób przeczytałem obie twoje wypowiedzi. A to, że ty go inaczej przeczytałeś, to już nie miej do mnie pretensji.

W tym miejscu kończy się część pierwsza pod tytułem "Odpowiedzi na odpowiedzi" i zaczyna druga pod tytułem "Moje własne wypociny". Serdecznie zapraszam do lektury.

Może w rozwiązaniu twojego problemu pomoże ci funkcja VMPC. Wymyślił ją Polak i ponoć jest rewelacyjna (ponoć, bo osobiście nie sprawdzałem, ale sprawdzali inni).
Strona domowa:

Kod: Zaznacz cały

http://www.vmpcfunction.com/

Opis funkcji:

Kod: Zaznacz cały

http://www.vmpcfunction.com/function.htm
i http://www.vmpcfunction.com/vmpc.pdf
Powyższe strony są w j. angielskim, ale na pewno nie będziesz miał z tym problemu.
Nie jest to typowa f. skrótu. Dlaczego, to już sobie poczytaj.
Krótki polski tekst o niej możesz przeczytać tu: http://hacking.pl/news.php?id=3434 bo hacking.pl zimą o niej donosił.
Zanim mi odpowiesz na cokolwiek, zapoznaj się chociaż z niusem z hacking.pl.

Pozdrawiam wesoło, pogodnie i radośnie, czyli w tonie tej wypowiedzi.
.
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

funkcja haszujaca

Post autor: arigo »

hehehe pozno jakos juz (dochodzi druga w nocy) i nie bede mial tyle weny zeby na kazdy podpunkt odpisac :)))

pod pojeciem asymetryczna funkcja skrotu rozumiem funkcje skrotu gdzie po znajomosci wyjscia nie jestesmy w stanie okreslic jakie stany wejsciowe powoduja jego stan.
natomiast symetryczna funkcja skrotu daje nam (przy mniejszym lub wiekszym wysilku) mozliwosc odtowrzenia wszystkich danych wejsciowych ktore powoduja zadany stan wyjscia

a co do zmniejszania kolizji przez filtrowanie to sposrod wszystkich danych wejsciowych ktore powoduja wygenerowanie danego skrotu nalezy odrzucic wszystkie ktore nie spelniaja kryterium alfanumerycznosci co imho zmiejsza ich ilosc :)
dane mam strumieniowe

podstawowe operatory bitowe: xor and or not shl shr
no i nie bitowe inc i dec poniewaz po 1 bajcie zajmuja wiec to nie jest duzo :)

linka ktorego mi dales czytalem ale tego w sposob krotki i malo zajmujacy w asm raczej sie nie zaimplementuje

o funkcji VMPC slyszalem ale jeszcze sobie doczytam tylko juz nie teraz gdyz jest pozno

do gnicza:
z tego powodu ze wejscie bedzie mialo ok 15 znakow :) wiec taki duzy skrot mija sie z celem

dzieki Hrabii za pomoc :)))

jednak chyba zakoduja ta moja wlasna funkcje za genialna ona nie jest lecz ma wiele zalet po 1 nie jest znana wiec ktos kto to bedzie chcial obejsc bedzie musial uzyc mozgu i wiedzy i nie wystarczy odpalenie progsa napisanego przez kogos innego po 2 trzeba przyznac ze warunki stawiane tej funkcji sa bardzo specyficzne (prosta implementacja w asm oraz bardzo male dane wejsciowe i wyjscie ok 2-3 raza mniejsze od wejscia)

pozdrawiam
Hrabia
Użytkownik
Użytkownik
Posty: 55
Rejestracja: 27 lis 2004, o 22:24
Płeć: Mężczyzna
Lokalizacja: Hrabia is out there

funkcja haszujaca

Post autor: Hrabia »

arigo pisze:hehehe pozno jakos juz (dochodzi druga w nocy)
E tam późno. Właśnie, że wcześnie!
arigo pisze:pod pojeciem asymetryczna funkcja skrotu rozumiem funkcje skrotu gdzie po znajomosci wyjscia nie jestesmy w stanie okreslic jakie stany wejsciowe powoduja jego stan.
natomiast symetryczna funkcja skrotu daje nam (przy mniejszym lub wiekszym wysilku) mozliwosc odtowrzenia wszystkich danych wejsciowych ktore powoduja zadany stan wyjscia
W takim razie chyba źle rozumiesz. Funkcji skrótu nie dzielimy na symetryczne i asymetryczne, bo tak po prostu się nie da. W pewnym stopniu f. skrótu mają cechy obu rodzajów, które ty wyróżniasz.
Mając skrót wiadomości nie ma matematycznej możliwości znaleźć choćby jednej wiadomości, dającej dany skrót. Natomiast generując odpowiednią liczbę skrótów (kłania się paradoks dnia urodzin) jesteśmy niemal pewni znalezienia kolizji. A wszystkich wiadomości nigdy nie znajdziemy, bo dla każdej f. skrótu jest ich nieskończenie wiele. Natomiast znalezienie wiadomości dających określony skrót jest możliwe np. metodą brute-force. W twoim przypadku 10 bajtów do 4 bajtów, to jak mrugnięcie okiem. Niezależnie od jakości f. skrótu.
arigo pisze:a co do zmniejszania kolizji przez filtrowanie to sposrod wszystkich danych wejsciowych ktore powoduja wygenerowanie danego skrotu nalezy odrzucic wszystkie ktore nie spelniaja kryterium alfanumerycznosci co imho zmiejsza ich ilosc
dane mam strumieniowe
Pokaż przykład, jeśli możesz.
arigo pisze:do gnicza:
z tego powodu ze wejscie bedzie mialo ok 15 znakow wiec taki duzy skrot mija sie z celem
Co prawda nie do mnie, ale coś wtrącę. Duży skrót nigdy nie mija się z celem, bo im większy tym lepiej. Oczywiście w granicach wymagań bezpieczeństwa. Gdy długość skrótu masz mniejszą od ustalonej długości wiadomości, to masz pewne kolizje. Natomiast przy równej lub większej długości skrótu od wiadomości, w zależności od jakości f. skrótu, kolizji nie powinno być lub będzie ich niewiele.

Do gnicza jeszcze: crc nie jest bezpieczne kryptograficznie.
arigo pisze:dzieki Hrabii za pomoc ))
Hrabiemu
arigo pisze:jednak chyba zakoduja ta moja wlasna funkcje za genialna ona nie jest lecz ma wiele zalet po 1 nie jest znana
Przy funkcjach skrótu, zwłaszcza tak krótkich, nie jest to szczególna zaleta.
arigo pisze:wiec ktos kto to bedzie chcial obejsc bedzie musial uzyc mozgu i wiedzy i nie wystarczy odpalenie progsa napisanego przez kogos innego po 2 trzeba przyznac ze warunki stawiane tej funkcji sa bardzo specyficzne (prosta implementacja w asm oraz bardzo male dane wejsciowe i wyjscie ok 2-3 raza mniejsze od wejscia)
Mam jakieś takie wrażenie, że to chyba nie najszczęśliwszy pomysł 32-bitowa funkcja skrótu na wiadomości o określonej (tylko 10 bajtów!) długości. Może opisz do czego to ma służyć (no chyba, że robisz to dla wojska, to wtedy nie ryzykuj ), a może znajdzie się lepsze rozwiązanie.
.
gnicz
Użytkownik
Użytkownik
Posty: 507
Rejestracja: 16 wrz 2004, o 18:24
Płeć: Kobieta
Lokalizacja: ???

funkcja haszujaca

Post autor: gnicz »

Hrabia pisze:Do gnicza jeszcze: crc nie jest bezpieczne kryptograficznie..
Wiem, lecz implementacja jest bardzo prosta i daje na wyjsciu 32-bity, jak wymagal Arigo.
Hrabia pisze:E tam późno. Właśnie, że wcześnie!
Czyzby Hrabia Drakula?

Zamiast skrotu mozna zaszyfrowac ta wiadomosc. Aczkolwiek mozesz probowac napisac wlasna funkcje chyba ze masz co do niej duze wymagania.

Pozdrawiam, GNicz
arigo
Użytkownik
Użytkownik
Posty: 852
Rejestracja: 23 paź 2004, o 10:17
Płeć: Mężczyzna
Lokalizacja: Lublin
Pomógł: 28 razy

funkcja haszujaca

Post autor: arigo »

Hrabia pisze: E tam późno. Właśnie, że wcześnie!
hehehe wiem ze 2a.m. jest obiektywnie wczesna godzina lecz akurat wtedy dla mnie to bylo bardzo pozno
Hrabia pisze: W takim razie chyba źle rozumiesz. Funkcji skrótu nie dzielimy na symetryczne i asymetryczne, bo tak po prostu się nie da. W pewnym stopniu f. skrótu mają cechy obu rodzajów, które ty wyróżniasz.
Mając skrót wiadomości nie ma matematycznej możliwości znaleźć choćby jednej wiadomości, dającej dany skrót. Natomiast generując odpowiednią liczbę skrótów (kłania się paradoks dnia urodzin) jesteśmy niemal pewni znalezienia kolizji. A wszystkich wiadomości nigdy nie znajdziemy, bo dla każdej f. skrótu jest ich nieskończenie wiele. Natomiast znalezienie wiadomości dających określony skrót jest możliwe np. metodą brute-force. W twoim przypadku 10 bajtów do 4 bajtów, to jak mrugnięcie okiem. Niezależnie od jakości f. skrótu.
(...)
Pokaż przykład, jeśli możesz.
(...)
Przy funkcjach skrótu, zwłaszcza tak krótkich, nie jest to szczególna zaleta.
(...)
Mam jakieś takie wrażenie, że to chyba nie najszczęśliwszy pomysł 32-bitowa funkcja skrótu na wiadomości o określonej (tylko 10 bajtów!) długości. Może opisz do czego to ma służyć (no chyba, że robisz to dla wojska, to wtedy nie ryzykuj ), a może znajdzie się lepsze rozwiązanie.
w moim przypadku mozna znalezc wszystkie mozliwosci wejsciowe dajace ten sam skrot poniewaz wejscie jest ograniczone do okreslonej liczby znakow


mam teraz troche czasu i pisze programik typu crackme gdyz chce sie znalezc po "drugiej stronie"
i w jednym z poziomow na podane haslo mialbyc generowany skrot i porownywany ze skrotem wzorcowym - teraz juz powinno byc jasne dlaczego nie chce uzywac jakiegos ogolnie znanego algorytmu poniewaz ktos kto sie bedzie w to bawil ma sie wykazac wlasnymi umiejetnosciami a nie tylko odpalaniem czyis programow lamiacych. i wlasnie z zalozenia osoba to lamiaca mialaby napisac programik co by robil atak typu brute-force na ten algorytm. tylko ze niestety nie moge w prostyu sposob uzyskac efektu "asymetrycznosci" teraz moze wyjasnie na jakims banalnym przykladzie (zamieniajacym 2 bajty w 1) o co mi chdzilo w tym pojeciu

kod w skladni intela
mov al, ARG1
mov ah,ARG2
and al,ah
not al

zakladamy ze ARG1="a"(61h) oraz ARG2="o"(6fh)
01100001 and
01101111 =
01100001 (61h)

not 01100001 =
10011110 =9Eh

teraz stawiamuy sie w roli atakujacego ten algorytm wartosc 9Eh negujemy otrzymujemy wartosc 61h
01100001 widzimy ze jest to wynik iloczynu dwoch bajtow wiec tam gdzie sa "1" tam musza byc jedynki a tam gdzie sa "0" tam musi byc conajmniej jedno zero wiec
x11xxxx1
x11xxxx1
co daje nam 3*5=15 kombinacji wejsciowych dla ktorych generowany jest identyczny skrot
to rozumialem pod pojeciem "symetrycznosci" skrotu

teraz wyjasnie o co mi chodzilio ze zmnieszaniem kolozji dzieki wpuszczaniu na wejscie tylko danych alfanumerycznnych
w powyzszym przykladzie np
11100001
01100001
te 2 liczby spelniaja postawione przez nas wczesniej warunki lecz dzieki filtracji na wejsciu to by nie zadzialalo

chyba teraz stalo sie jasne czego szukam (generalnie chodzi o to by zmusic kogos do napisania sofu lamiacego ten skrot metoda brute-force a nie metoda inzynierii wstecznej)

pozdrawiam
Hrabia
Użytkownik
Użytkownik
Posty: 55
Rejestracja: 27 lis 2004, o 22:24
Płeć: Mężczyzna
Lokalizacja: Hrabia is out there

funkcja haszujaca

Post autor: Hrabia »

arigo pisze:i w jednym z poziomow na podane haslo mialbyc generowany skrot i porownywany ze skrotem wzorcowym - teraz juz powinno byc jasne dlaczego nie chce uzywac jakiegos ogolnie znanego algorytmu poniewaz ktos kto sie bedzie w to bawil ma sie wykazac wlasnymi umiejetnosciami a nie tylko odpalaniem czyis programow lamiacych. i wlasnie z zalozenia osoba to lamiaca mialaby napisac programik co by robil atak typu brute-force na ten algorytm.
No widzisz. I tu jest nieścisłość. Bo chcesz, żeby to było łamane brute-forcem. Ale jednocześnie algorytm jest niejawny. No to jak ktoś ma się wykazać umiejętnościami pisząc kod łamiący dla algorytmu, którego nie zna? W takim przypadku pozostaje tylko inżynieria odwrotna i metody matematyczne.
arigo pisze:tylko ze niestety nie moge w prostyu sposob uzyskac efektu "asymetrycznosci" teraz moze wyjasnie na jakims banalnym przykladzie (zamieniajacym 2 bajty w 1) o co mi chdzilo w tym pojeciu

/ciach przykład/

teraz stawiamuy sie w roli atakujacego ten algorytm wartosc 9Eh negujemy otrzymujemy wartosc 61h
01100001 widzimy ze jest to wynik iloczynu dwoch bajtow wiec tam gdzie sa "1" tam musza byc jedynki a tam gdzie sa "0" tam musi byc conajmniej jedno zero wiec
x11xxxx1
x11xxxx1
co daje nam 3*5=15 kombinacji wejsciowych dla ktorych generowany jest identyczny skrot
to rozumialem pod pojeciem "symetrycznosci" skrotu
Primo: raczej 3^5=243 kombinacji.
Co do przykładu. W twoim rozumowaniu symetryczności każda funkcja skrótu jest asymetryczna, ponieważ zmiana choćby jednego bitu na wejściu powoduje diametralną zmianę skrótu wiadomości. Jest to nieodłączna cecha funkcji skrótu i każdy taki algorytm jest projektowany z, między innymi, myślą o niej. Weźmy jako przykład znaną wszystkim MD5:
wiadomość: binarnie = skrót
bbbb: 1100010 1100010 1100010 1100010 = 65BA841E01D6DB7733E90A5B7F9E6F80
bbcb: 1100010 1100010 1100011 1100010 = 11CE37A7A62B156AC004AE7DF64D7D8D
W twoim przykładzie i również, wnioskując z całości dyskusji, w twoim aktualnym algorytmie ten warunek nie jest zachowany. Dlatego też trudno to nazwać funkcją skrótu. Bardziej bym się skłaniał do określenia "pewnego rodzaju szyfrowanie/kompresja stratne/a" lub może generowanie jakiegoś klucza z wiadomości.
arigo pisze:teraz wyjasnie o co mi chodzilio ze zmnieszaniem kolozji dzieki wpuszczaniu na wejscie tylko danych alfanumerycznnych
w powyzszym przykladzie np
11100001
01100001
te 2 liczby spelniaja postawione przez nas wczesniej warunki lecz dzieki filtracji na wejsciu to by nie zadzialalo
Hmm. W takim razie o tym, czy zmniejszasz, czy też zwiększasz tym kolizyjność swojego algorytmu nie można się wypowiedzieć, nie znając algorytmu. Ponieważ usunięcie pewnego zbioru danych wejściowych może powodować usunięcie ze zbioru wyników tych elementów, które się powtarzają (wówczas osiągasz swój cel), ale równiez może zachodzić sytuacja, że usuniesz właśnie te, które się nie powtarzają (i wówczas masz efekt odwrotny do zamierzonego). Zostawmy to nierozstrzygnięte.
Inna sprawa to to, że, z tego co widzę, ułatwiasz tym lekko zadanie atakującemu. Bo:
Liter i cyfr mamy łącznie 36. Zatem możliwości mamy 36^10. Ale to nie wszystko. Ponieważ, na zdrowy rozum, można również podać na wejście ciąg np. 8-znakowy. W takim razie zastosujmy sumę ciągu geometrycznego: S=36*(36^10-1)/35 (mam nadzieję, że nie skopałem). S=3760620109779060=3.76e15. Może dużo, może nie, zależy od mocy sprzętu i złożoności algorytmu. Ale abcdabcd i abcd##abcd będą dawać ten sam wynik, prawda? A gdybyś pozwolił na znaki inne niż alfanumeryczne, utrudniłbyś lekko zadanie. Lekko, bo by to była kwestia tylko dłuższego czasu. Bo główny problem tkwi w napisaniu programu.
arigo pisze:chyba teraz stalo sie jasne czego szukam (generalnie chodzi o to by zmusic kogos do napisania sofu lamiacego ten skrot metoda brute-force a nie metoda inzynierii wstecznej)
No jasne. Tylko musisz przy tym opisać swój algorytm. Bo inaczej to pozostaje deasemblacja i potem brute-force. Zauważ, że w takim przypadku niejawność algorytmu nie jest żadnym utrudnieniem. Natomiast mając algorytm (w ten czy inny sposób) nie jest wielkim wyzwaniem napisać prosty program szukający metodą brute-force zadanego wyniku. Jaki z tego wniosek? Taki, że to ty masz najtrudniejsze zadanie, bowiem algorytm powinien być taki, aby jego słowny opis (klarowny, nie ściemniany na siłę) wymagał jakichś (jakich - to już ty stawiasz zadanie) umiejętności do jego zaimplementowania. Bo gdy już mamy gotowy program, to wtedy brute-force i wio... jutro gotowe.

Pozdrawiam.
.
ODPOWIEDZ