puteți genera rapid un număr de identificare, fără coliziuni și fără ca ID-urile să dezvăluie informații?

Există o modalitate standard de a genera numere de identificare una după alta, astfel încât:

• Puteți garanta, sau aproape garanta, că evitați coliziunile. (Prin „aproape garanție”, mă refer, de exemplu, dacă ați generat numere complet aleatorii de 24 de cifre și ați generat „doar” 1 milion dintre ele, atunci chiar și cu paradoxul zilei de naștere, șansele de coliziune ar fi mici.)
• Vrei ca numerele de identificare să fie scurte, nu grele - în special, tu nu doresc să se bazeze pe lungimea numărului de identificare (și pe alegerea valorilor aleatorii) pentru a evita coliziunile, așa cum este descris în punctul anterior. Trebuie să o faci altfel.
• Nu doriți să evitați coliziunile de fiecare dată când generați o nouă valoare, uitându-vă la toate valorile preexistente pentru a vedea dacă a fost deja folosită. Aceasta ar fi doar o căutare log(n) de fiecare dată pe o listă sortată, dar să presupunem că vreau să evit oricum asta.
• Nu doriți ca numărul de identificare să dezvăluie informații despre momentul în care a fost generat sau despre câte numere de identificare au fost generate între numărul ID X și numărul ID Y. Fără această condiție, problema este banală; ați putea folosi doar ora ceasului (plus o valoare aleatorie suficient de mare pentru a evita coliziunile între numerele generate în aceeași valoare a timpului de ceas) sau puteți folosi doar numere întregi secvențiale (cu excepția faptului că acum un atacator știe că dacă cineva a generat valoarea ID-ului 5000 pe 1 martie și valoarea ID 6000 pe 1 aprilie, au fost generate alte 1000 de valori între atunci).

Am încercat să găsesc un răspuns banal, dar niciunul dintre cele pe care le-am încercat nu părea să funcționeze. Puteți lua pur și simplu codul hash SHA-256 al numerelor 1, 2, 3 etc. (plus o cheie secretă), dar aceasta are aceeași problemă ca doar alegerea numerelor aleatorii din spațiul disponibil -- dacă vă bazați pe lungimea hash-ului (de exemplu SHA-256) pentru a evita coliziunile, numerele de identificare rezultate sunt lungi și greu de manevrat, iar dacă scurtați hash-ul, creșteți șansa de coliziuni.

Sau ați putea genera ID-uri noi incrementând de fiecare dată cu o valoare aleatorie între 1 și n, în loc să creșteți întotdeauna cu 1. Problema este că, în funcție de ceea ce poate face atacatorul, își pot da seama ce este n -- dacă au capacitatea de a genera două ID-uri în secvență și de a face acest lucru în mod repetat, ar putea da seama de n, sau dacă au capacitatea de a verifica care ID-uri sunt valide, ar putea verifica fiecare număr dintr-un interval mic, pentru a vedea cât de dens este împachetat validul ID-urile sunt și descoperă n din asta.

Singura soluție pe care am putut să o găsesc este următoarea: mai întâi, faceți ceva pregătire în avans. Pentru oricâte valori de ID vă așteptați să generați (să zicem, 1 milion), luați toate numerele întregi de la 1 la 1 milion și, în ordine, începeți să calculați hash-ul fiecărui număr întreg plus o cheie secretă. Trunchiați hash-ul la orice valoare credeți că este suficient de scurtă. Dar, cu o trunchiere suficient de scurtă, vă așteptați să vedeți ciocniri. Deci, de fiecare dată când generați un nou hash trunchiat pentru un anumit întreg, verificați-l cu valorile generate anterior și, dacă există o coliziune, adăugați acel număr întreg la o listă L de numere întregi în care hash-ul acelui întreg se ciocnește cu cel al unui întreg mai mic. (Deci, de fapt, dacă planul tău este să generezi 1 milion de ID-uri, în timpul lucrării sale de pregătire va trebui să mergi puțin la ultimul milion de numere întregi, pentru a compensa cele pe care le-ai omis.)

Apoi, în timpul execuției, când generați ID-urile, începeți doar cu un numărător întreg. De fiecare dată când generați un nou ID, creșteți numărul întreg și verificați dacă este în lista dvs. L, iar dacă este, săriți și pentru a trece la următorul întreg. (Acest lucru implică o „căutare log n”, aparent încălcând una dintre regulile pe care le-am declarat, dar ceea ce voiam cu adevărat să fac era să evit să fiu nevoit să verific fiecare nouă valoare ID cu fiecare valoare generată până acum; verificarea L ar trebui să fie mult mai rapidă.) Și puteți ajusta acest lucru pentru compromisuri (cu cât faceți hashurile trunchiate mai lungi, cu atât L va fi mai scurt și, prin urmare, cu atât verificarea va fi mai scurtă de fiecare dată când generați un nou ID; dar este posibil ca valorile ID mai lungi să nu fie de dorit).

Dar asta se simte ca un hack. Există o modalitate standard? Dacă nu, vă puteți gândi la o modalitate mai bună?