Generowanie unikalnych id. Algorytm hashujący bez kolizji. Opcje

[SnakeEater]

Witam,
Buduję aplikację w której obiekt byłby identyfikowany na podstawie unikalnego id w postaci xxx-xxx-xxx-xxx, gdzie x to znak alfabetu a-z lub cyfra. id to miałoby być na tyle unikalne, żeby nie dało się zgadnąć. URL będzie wyglądał tak:

www.mojadomena.pl/books/394-a34-g34-dd2

W jaki sposób zahashować taki id do bazy? Chodzi o taki algorytm, żeby nie było kolizji, więc chyba md5 odpada. Wygenerowany hash ze względu na unikalność może być równie długi lub dłuższy, gdyż ze względu na założenia nie może być krótszy. To wiem. Problem tylko skąd wziąć taki algorytm? Zna ktoś może jakiś? A może zwyczajnie pozamieniać litery w stylu znak klucz -> znak wartość? Tylko wtedy chyba na podstawie kilku "tokenów" i ich zahaszowanych wersji da się złamać kod. Czyż nie?

Ten post edytował SnakeEater 26.03.2010, 15:26:51

[DiH]

Unikalny id uzyskasz choćby w taki sposób:

[PHP] pobierz, plaintext 
date("Y-md-Hi-u")
[PHP] pobierz, plaintext 

Dlaczego muszą to być akurat znaki a-z? Również, po co go hashować?

[erix]

W jaki sposób zahashować taki id do bazy? Chodzi o taki algorytm, żeby nie było kolizji, więc chyba md5 odpada. Wygenerowany hash ze względu na unikalność może być równie długi lub dłuższy, gdyż ze względu na założenia nie może być krótszy. To wiem. Problem tylko skąd wziąć taki algorytm? Zna ktoś może jakiś? A może zwyczajnie pozamieniać litery w stylu znak klucz -> znak wartość? Tylko wtedy chyba na podstawie kilku "tokenów" i ich zahaszowanych wersji da się złamać kod. Czyż nie?

uniqid

[SnakeEater]

chodzi o to, żeby kod był w taki sposób jak podałem. Chodzi o to, żeby nikt nie zgadł takiego kodu, bo nie książki będą tylko coś poważniejszego. Przy takiej ilość znaków jak podałem ilość kombinacji to będzie 36^12, a więc nikt przypadkiem go raczej nie znajdzie. Ten kod będzie jednocześnie służył jako login i hasło zarazem, a tego nie przechowuje się w formie niezaszyfrowanej przecież. Zaszyfrowana postać musi być unikalna z tego samego powodu. Trzeba przecież jednoznacznie znaleźć użytkownika. Przecież to będzie klucz główny, a on musi być unikalny, żeby nie wyskoczyło dwóch takich ludzi. Żeby komuś przypadkiem nie wygenerował się taki sam login-password ;P

[blooregard]

Ja bym to zrobił tak:

Generowałbym MD5 lub SHA1 (obojętnie) z czterech różnych unikalnych wartości, np. piewrszy z microtime(), drugi z daty z godziną w postaci tekstowej, trzeci z losowo wybranego znaku ASCII, czwarty jeszzce z czegoś tam.

Z każdego z haszy wycinałbym np. 3 pierwsze znaki z pierwszego, 3 licząc od 12 z drugiego, 3 licząc od 5 od końca z trzeciego i powiedzmy 3 ostatnie z czwartego.
Sklejałbym je poprzez '-' i otrzymywał to, co Ty potrzebujesz.
Przed zapisem w bazie sprawdziłbym tylko, czy zestaw jest unikalny, tak dla pewności, jeśli jakimś cudem by był, to powtórka.

[SnakeEater]

uniqid

Główny roblem polega na tym w jaki sposób go zaszyfrować w bazie. Zaszyfrowana wersja musi być unikalna, a przecież od dwóch różnych kluczy mogą powstać dwa takie same hashe, co prawda prawdopodobieństwo jest małe, ale jednak.
Chyba jednak posłucham się blooregarda i będę szyfrował zwykłą funkcją hashującą choćby md5 i sprawdzał, czy wartość zaszyfrowana jest w bazie jak będzie to jeszcze raz wylosuję kod i go zahaszuję. Nie powinno być z tym problemu. Rzecz nie powinna się często powtarzać. Prawdopodobnie ograniczę hasha do jakiś 16 znaków, gdyż taki długi klucz jak na przykład w md5 nie jest potrzebny.

[dr_bonzo]

Unikalny kod?

Polacz id rekordu z jakims md5() czy uniq-id, id jest unikalne wiec caly string bedzie unikalny

np. 0000000001-123123-12312-3-123-12-3-123

Ten post edytował dr_bonzo 26.03.2010, 22:11:05

[smentek]

Twój identyfikator musi składac się z 2 części które skonkatanujesz (złączysz) w jedno.
A wzór jest taki:

identyfikator = część unikalna + szum

Implementacja:

identyfikator = primary_key + md5( salt + primary_key )

gdzie:
salt = ciąg znaków (tajny) pobierany np. z pliku konfiguracyjnego systemu.
primary_key = autkoinkrementowany klucz (najlepiej primary key) tworzony automatycznie przez bazę podczas dodawania nowego rekordu
+ = znak konkatanacji

Wynika z tego że potrzebujesz 2 pingów do bazy jeden żeby stworzyć rekord i uzyskać nowy id (primary key)
drugi żey zpisac do bazy utworzyony identyfikator.

Można by to uprościc i primary_key zamienić na microtime(). Wtedy jednak bezpieczeństwo systemu wiążemy z zegarem systemowym.

Ale wszystko to teoria... Jeżeli strona jest dostępna publicznie to tego typu zabezpieczenie nie jest żadnym zabezpieczeniem. Jeżeli chcesz mieć zabezpieczone zasoby to dostęp musi być po zalogowaniu, dla konkretnych użytkowników.

Ten post edytował smentek 26.03.2010, 22:27:52

[jarosek]

...
Ale wszystko to teoria... Jeżeli strona jest dostępna publicznie to tego typu zabezpieczenie nie jest żadnym zabezpieczeniem. Jeżeli chcesz mieć zabezpieczone zasoby to dostęp musi być po zalogowaniu, dla konkretnych użytkowników.

Tu się nie zgodzę, to bardzo ważne zagadnienie, często lekceważone przez programistów. Często zdarza się, że strona składa się z wielu publicznych zasobów, np. hurtowania daje podstrony dla swoich dystrybutorów. Strony dostępne są publicznie, i teraz gdyby numery szły po kolei, ciach 30 sekund i mam wszystkie dane kontrahentów tej hurtowni.
Warto o pamiętać o dobrym mieszaniu w takich przypadkach.

[SnakeEater]

Dziękuję wszystkim, no więc zrobię chyba tak:
System wylosuje klucz dla danej osoby identyfikator w formie xxx-xxx-xxx-xxx. x to litera lub cyfa. będzie tego chyba 36 ^ 10=4 738 381 338 321 616 896, a więc całkiem sporo. Jeżeli w bazie będzie 100 000 rekordów to szansa trafienia to będzie około 1/47 383 813 383 216. Jeżeli przyjmie się, że nastąpi 10 prób na sekundę to wyszło mi, że zgadnie się jedno id po 150 253 latach, a więc nie jest źle. Do tego czasu na pewno zajrzę na serwer i wytnę go na stałe (IMG:style_emoticons/default/winksmiley.jpg)

Dodatkowo po kilku próbach w krótkim czasie z jednego ip dodam konieczność odczekania kilka sekund.
Kluczem będzie taka wartość (unikalny klucz z indeksem do wyszukiwania): identyfikator = md5( salt + primary_key + wylosowany Identyfikator). W ten sposób chyba klucz będzie "prawie" unikalny. Problem tylko jest taki, że ten klucz będzie bazował na głównym i nie wiem czy to bezpiecznie, bo jak tamten się zmieni... Może się zmienić? Użytkownik podczas tworzenie dla siebie takie czegoś w stylu konta ujrzy ten identyfikator i zapisze sobie na kartce. Po wpisaniu tego w formularzu wyskoczy mu cała historia. Te haszowanie to tylko dla bezpieczeństwa jakby ktoś do bazy się dorwał. Dziękuję wszystkim za pomoc.

Ten post edytował SnakeEater 29.03.2010, 19:47:39