随机字节可以是唯一的吗?碰撞百分比

Question

我在这里搜索了一下，但没有找到关于我的问题的任何信息。所以，我在这里发布了这个初学者喜欢的问题。random_bytes()可以是唯一的吗？它能防碰撞吗？或者至少是碰撞的百分比？谢谢你。

Answer 1

根据手册：

生成适合加密使用的任意长度的加密随机字节字符串

因此，您可以假设唯一性，当然这取决于生成的字符串的长度。如果你需要生成ID，那么看看UUIDv4，例如，并遵循它的生成算法，那么你应该是最安全的。

Answer 2

我用这个脚本做了一个完全不科学的测试：

<?php
// collisions.php -- check collisions of random_bytes()
set_time_limit(0);
if(count($argv) < 2) die("Usage: php collisions.php nn       where n is the number of triesn");
$tries = floatval($argv[1]);
if($tries < 1) die("Number of tries must be at least 1.n");
$t = time();
$chkUnqiue = [];
for($i = 0; $i < $tries; $i++) {
$r = bin2hex(random_bytes(16));
if(isset($chkUnique[$r]))
$chkUnique[$r]++;
else
$chkUnique[$r] = 0;
}
$t = time() - $t;
echo "Collisions by random_bytes() after " . number_format($tries) . " tries: " .
array_sum($chkUnique) .
"nTook approx. $t sec.n";

并尝试了多达3000万次：

php collisions.php 30000000

结果是：

Collisions by random_bytes() after 30,000,000 tries: 0
Took approx. 53 sec.

超过3000万，它开始抛出out of memory错误。在CLI模式下运行时，我将内存限制设置为-1(无限制)，因此我没有空间在该服务器上进行更大的测试。。。也许有人可以在更多的试验中确认没有碰撞？

Answer 3

取决于您有多少个样本。假设您有2**32个样本，即MySQL的INTEGER UNSIGNED PRIMARY KEY可以具有的最大行数，单个生日悖论冲突的可能性是，这取决于您有多少字节：

2 bytes (16 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM730:3 3 bytes (24 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM730:3 4 bytes (32 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM730:3 5 bytes (40 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM730:3 6 bytes (48 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM730:3 7 bytes (56 bits): 99.9999999999999999999999999999999999999999999999999999974277905506997710587292686339838902053735038700
VM730:3 8 bytes (64 bits): 39.3469340216757114443741147076524842535626297825119964120927656555694024010908849471206150350857576700
VM730:3 9 bytes (72 bits): 0.1951218892070667250691497618471341831283295867954105629289252904440205299685786313768276645954696700
VM730:3 10 bytes (80 bits): 0.0007629365425717214706546969135582274422418854676363968117948350144755994256511242528910872277978400
VM730:3 11 bytes (88 bits): 0.0000029802321936667213364915605164519421014838352168471986663538895912445823072181581020658714403100
VM730:3 12 bytes (96 bits): 0.0000000116415321793053496565701278938242180316180229154385854539613876581244379897746327435643373700
VM730:3 13 bytes (104 bits): 0.0000000000454747350780481602973028357258824524741808886645719662583624822340299760166371533522862700
VM730:3 14 bytes (112 bits): 0.0000000000001776356838986658580689920341771905249751487982825962897403206620033498485817835300659600
VM730:3 15 bytes (120 bits): 0.0000000000000006938893902291641219700815236415536973326707821666710799551368023517110331739557467100
VM730:3 16 bytes (128 bits): 0.0000000000000000027105054305826723608319686584071090612151716924874531166001386472295273703307943900
VM730:3 17 bytes (136 bits): 0.0000000000000000000105879118382135639094920963639717342367514169992334119994205609169765348700055000
VM730:3 18 bytes (144 bits): 0.0000000000000000000000413590306180217340207731884661994264643204800215944245231226111034388785296700
VM730:3 19 bytes (152 bits): 0.0000000000000000000000001615587133516473985229467482865854604918557525775081822180266458433233768500
VM730:3 20 bytes (160 bits): 0.0000000000000000000000000006310887240298726504781880555495324182972214491567209876737141250404779600
VM730:3 21 bytes (168 bits): 0.0000000000000000000000000000024651903282416900409251509930277214040045879950791758797419961100446700
VM730:3 22 bytes (176 bits): 0.0000000000000000000000000000000096296497196941017224000648308071750262313022774985636346295341923700
VM730:3 23 bytes (184 bits): 0.0000000000000000000000000000000000376158192175550848525607074969627342466723345527152673112010015400
VM730:3 24 bytes (192 bits): 0.0000000000000000000000000000000000001469367938185745502077497353638838041947981767579266263262484300
VM730:3 25 bytes (200 bits): 0.0000000000000000000000000000000000000005739718508538068367607380245230866731819297069453628708059800
VM730:3 26 bytes (208 bits): 0.0000000000000000000000000000000000000000022420775423976829560312306451660097730814868981669950354800
VM730:3 27 bytes (216 bits): 0.0000000000000000000000000000000000000000000087581153999909490468506273382135243039566652995353267000
VM730:3 28 bytes (224 bits): 0.0000000000000000000000000000000000000000000000342113882812146447145140572235690531714961455513974300
VM730:3 29 bytes (232 bits): 0.0000000000000000000000000000000000000000000000001336382354734947059183940911779352100739447565046900
VM730:3 30 bytes (240 bits): 0.0000000000000000000000000000000000000000000000000005220243573183386949861632625818803905141244681700
VM730:3 31 bytes (248 bits): 0.0000000000000000000000000000000000000000000000000000020391576457747605273239632510419320514419007900
VM730:3 32 bytes (256 bits): 0.0000000000000000000000000000000000000000000000000000000079654595538076583100463431089878263573867700
VM730:3 33 bytes (264 bits): 0.0000000000000000000000000000000000000000000000000000000000311150763820611652731146870615334746084900
VM730:3 34 bytes (272 bits): 0.0000000000000000000000000000000000000000000000000000000000001215432671174264268459900465860940311000
VM730:3 35 bytes (280 bits): 0.0000000000000000000000000000000000000000000000000000000000000004747783871774469798732096132207018400
VM730:3 36 bytes (288 bits): 0.0000000000000000000000000000000000000000000000000000000000000000018546030749119022650939250161419400
VM730:3 37 bytes (296 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000072445432613746182231915763612700
VM730:3 38 bytes (304 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000282989971147446024342031727400
VM730:3 39 bytes (312 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000001105429574794711032570163000
VM730:3 40 bytes (320 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000004318084276541839970990100
VM730:3 41 bytes (328 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000016867516705241562386800
VM730:3 42 bytes (336 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000065888737129849853100
VM730:3 43 bytes (344 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000257377879413476000
VM730:3 44 bytes (352 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000001005382341458900
VM730:3 45 bytes (360 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000003927274771300
VM730:3 46 bytes (368 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000015340917100
VM730:3 47 bytes (376 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000059925500
VM730:3 48 bytes (384 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000234100
VM730:3 49 bytes (392 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000900
VM730:3 50 bytes (400 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

我想说，10个字节是一个很好的选择，10给了你0.0007%的机会发生一次生日碰撞，这意味着如果你制作了142856个这样完全耗尽的数据库，你会发现大约有1个碰撞！

但是如果你有2**64个样本，MySQL的BIGINT UNSIGNED PRIMARY KEY可以存储的最大值呢？嗯，单个生日悖论碰撞的可能性是

2 bytes (16 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 3 bytes (24 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 4 bytes (32 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 5 bytes (40 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 6 bytes (48 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 7 bytes (56 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 8 bytes (64 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 9 bytes (72 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 10 bytes (80 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 11 bytes (88 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 12 bytes (96 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 13 bytes (104 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 14 bytes (112 bits): 100.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
VM739:3 15 bytes (120 bits): 99.9999999999999999999999999999999999999999999999999999974277906273575851562551628356447378966618610200
VM739:3 16 bytes (128 bits): 39.3469340287366576382767925051732039111443153312804614295448573882265327272181291266477621149279583500
VM739:3 17 bytes (136 bits): 0.1951218892524527289843252381047865603764957222291271541480405006250432867062615884385798395379814800
VM739:3 18 bytes (144 bits): 0.0007629365427493557992860364860221112540909113715577924612454205239852919524216540352421599644821300
VM739:3 19 bytes (152 bits): 0.0000029802321943606107060124716601695555770480242114789127059106834577558114278058404382818849390000
VM739:3 20 bytes (160 bits): 0.0000000116415321820158550869336177541161192708042329396354372821407046099857585335768804584013669800
VM739:3 21 bytes (168 bits): 0.0000000000454747350886360721356472707553077383794388148388467031092149898899242894843511891589892000
VM739:3 22 bytes (176 bits): 0.0000000000001776356839400248886867060739748432641003887840996012082625529387068758566288828246623200
VM739:3 23 bytes (184 bits): 0.0000000000000006938893903907228353122013439546439654554534861148024868828951568601096253132705644900
VM739:3 24 bytes (192 bits): 0.0000000000000000027105054312137610848504151844244226582645015901891537094464883977706983309067526600
VM739:3 25 bytes (200 bits): 0.0000000000000000000105879118406787542380559818153552580761590493204820090151213597342039664118779500
VM739:3 26 bytes (208 bits): 0.0000000000000000000000413590306276513837412019011322033428139921844672864993463944210874339175696900
VM739:3 27 bytes (216 bits): 0.0000000000000000000000001615587133892632177363699581708083450556373782285492737794813680820086690800
VM739:3 28 bytes (224 bits): 0.0000000000000000000000000006310887241768094442873768259672103428738043488813587964420920500179336500
VM739:3 29 bytes (232 bits): 0.0000000000000000000000000000024651903288156618917904277536152490969617930133521422178837855248989900
VM739:3 30 bytes (240 bits): 0.0000000000000000000000000000000096296497219361792646668335845222979331712244829793887159929935484900
VM739:3 31 bytes (248 bits): 0.0000000000000000000000000000000000376158192263132002532368596032914379779622178807755678094035179900
VM739:3 32 bytes (256 bits): 0.0000000000000000000000000000000000001469367938527859384926580837241064625725400753694854192313141500
VM739:3 33 bytes (264 bits): 0.0000000000000000000000000000000000000005739718509874450722276514189516525055697225162842123281183600
VM739:3 34 bytes (272 bits): 0.0000000000000000000000000000000000000000022420775429197073133502632535983656519454594026157465249600
VM739:3 35 bytes (280 bits): 0.0000000000000000000000000000000000000000000087581154020301066928862714348183649721268304345914487000
VM739:3 36 bytes (288 bits): 0.0000000000000000000000000000000000000000000000342113882891801042684266036993809630797496883272904900
VM739:3 37 bytes (296 bits): 0.0000000000000000000000000000000000000000000000001336382355046097823016484384004566655778216477125900
VM739:3 38 bytes (304 bits): 0.0000000000000000000000000000000000000000000000000005220243574398819621132515461399494807301758736400
VM739:3 39 bytes (312 bits): 0.0000000000000000000000000000000000000000000000000000020391576462495389144755614630195814541560310100
VM739:3 40 bytes (320 bits): 0.0000000000000000000000000000000000000000000000000000000079654595556622613846940286552600807168740500
VM739:3 41 bytes (328 bits): 0.0000000000000000000000000000000000000000000000000000000000311150763893057085342114209801516894280100
VM739:3 42 bytes (336 bits): 0.0000000000000000000000000000000000000000000000000000000000001215432671457254239609298286726606327700
VM739:3 43 bytes (344 bits): 0.0000000000000000000000000000000000000000000000000000000000000004747783872879899373468521962698428000
VM739:3 44 bytes (352 bits): 0.0000000000000000000000000000000000000000000000000000000000000000018546030753437106927740795504373200
VM739:3 45 bytes (360 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000072445432630613698935821187794700
VM739:3 46 bytes (368 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000282989971213334761469181164800
VM739:3 47 bytes (376 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000001105429575052088912010822600
VM739:3 48 bytes (384 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000004318084277547222312489700
VM739:3 49 bytes (392 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000016867516709168837158600
VM739:3 50 bytes (400 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000065888737145190770100
VM739:3 51 bytes (408 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000257377879473401400
VM739:3 52 bytes (416 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000001005382341693000
VM739:3 53 bytes (424 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000003927274772200
VM739:3 54 bytes (432 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000015340917100
VM739:3 55 bytes (440 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000059925500
VM739:3 56 bytes (448 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000234100
VM739:3 57 bytes (456 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000900
VM739:3 58 bytes (464 bits): 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

• 现在18字节似乎是一个不错的选择，您有0.0007%的机会发生单个碰撞。不过，就我个人而言，我可能会选择20字节，因为SHA1是20字节，这会给你0.00000001%的碰撞机会。ofc，你可以疯狂地使用58个字节，这将使你比0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001%的碰撞几率更小。(但这只是浪费磁盘空间。我猜任何超过20字节的东西都是浪费磁盘空间)

这是使用Decimal.js计算的，公式如下：

function collision_chance2(samples,number_of_possible_hashes){
var Decimal100 = Decimal.clone({ precision: 100, rounding: 8 });
var k=Decimal100(samples);
var N=Decimal100(number_of_possible_hashes);
var MinusK=Decimal100(samples);
MinusK.s=-1;
var ret=((MinusK.mul(k.sub(1))).div(N.mul(2))).exp();
ret=ret.mul(100);
ret=Decimal100(100).sub(ret);
return ret.toFixed(100);
}

不幸的是，我忘记了我从哪里得到这个公式，那是一个数学家伙的个人博客，但我不记得那个家伙/博客的名字：(编辑：找到了！算法学分归这个家伙：https://preshing.com/20110504/hash-collision-probabilities/

Answer 4

随机，它不保证唯一！基本问题：唯一的文本，可能对多少人来说是唯一的？

例如：

数字在1-9之间，唯一分配给9个人。但不是唯一的数字到第十个人。

您必须编写自己的唯一字节函数。如果可以使用md5()和uniqid()函数，则可以生成一个唯一的32个字符长的十六进制键。

例如：

$uid = md5(uniqid(mt_rand(), true));

如果您需要一个唯一密钥的更多长度，可以使用mcrypt_encrypt()函数。有时，您会使用到微秒的随机数(如mt_rand()函数)来生成唯一的密钥

Answer 5

我使用bin2hex+random_bytes来创建随机字符串，例如

• 如果您只需要一个唯一的ID，请使用bin2hex(random_bytes(16))。它比UUIDv4简单而且严格意义上要好
• 如果您明确需要与UUID进行互操作，或者将来可能需要，请使用UUID

例如：

$uuid = bin2hex(random_bytes(16));

据Reddit报道。我们知道，如果它在Reddit 上，那是真的

回应吴的评论。它可能不够独特。PHP开发人员认为这已经足够了。阅读帖子上的推荐答案以供参考。