Какова вероятность угадать (сопоставить) Guid?

Просто любопытно, а какова вероятность совпадения с Guid?

Произнесите руководство с SQL-сервера: 5AC7E650-CFC3-4534-803C-E7E5BBE29B3D.

факториал?: (36*32)! = (1152)!

обсудить =D


guid math probability
person RhinoDevX64    schedule 02.02.2011    source источник
comment
Давайте подумаем, что один через... если бы в GUID было только два символа, это было бы (2*36)! ? 36 * 36 звучит более вероятно ... Разработайте это для трех символов, а затем посмотрите, какой ответ будет иметь смысл.   -  person dave jones    schedule 02.02.2011
comment
Почему вы думаете, что это факториал. Это было бы только в том случае, если бы вы не могли повторять значения.   -  person Babak Naffas    schedule 02.02.2011
comment
Могу поспорить, что только одно из этих полей (например, E7E5BBE29B3D) является случайным. Другие фиксированы (например, по хосту или экземпляру сервера) или основаны на текущем времени. Это серьезно снижает возможности.   -  person Arnaud Le Blanc    schedule 02.02.2011
comment
Я думал, что 26 букв плюс 10 возможных чисел дают 36 возможных значений для одной позиции в GUID, исключая тире. не уверен, почему я думал о факториале, возможно, отрывочная память !! знак равно   -  person RhinoDevX64    schedule 02.02.2011

Ответы (6)


arrow_upward
31
arrow_downward

Не понятно, о чем вы спрашиваете. Я вижу два варианта интерпретации вашего вопроса.

  1. Учитывая GUID g, какова вероятность того, что кто-то угадает его? Предположим для простоты, что доступны все 128 бит GUID. Тогда вероятность угадать g равна 2^-128. Это мало. Давайте получим некоторую интуицию вокруг этого. Предположим, что наш злоумышленник может генерировать один миллиард GUID в секунду. Чтобы угадать g с вероятностью 50 %, злоумышленник должен сгенерировать 2^127 GUID. При скорости один миллиард в секунду потребуется 5391448762278159040348 лет для создания 2^127 GUID.

  2. Мы создаем коллекцию руководств. Какова вероятность столкновения? То есть какова вероятность того, что мы сгенерируем два гида с одинаковым значением? Это парадокс дня рождения. Если вы сгенерируете последовательность из n GUID случайным образом, то вероятность по крайней мере одной коллизии будет приблизительно равна p(n) = 1 - exp(-n^2 / 2 * 2^128) (это проблема дня рождения с числом возможных дней рождения, равным 2^128).

n p(n) 2^30 1.69e-21 2^40 1.77e-15 2^50 1.86e-10 2^60 1.95e-03

Таким образом, даже если вы сгенерируете 2 ^ 60 GUID, шансы на столкновение крайне малы. Если вы можете генерировать один миллиард GUID в секунду, все равно потребуется 36 лет, чтобы иметь вероятность столкновения 1,95e-03.

person jason    schedule 02.02.2011
comment
Правильно ли 2^64? Половина 2^128 равна 2^127. Статистика не является моей сильной стороной, поэтому, возможно, для достижения порога 50% требуется только sqrt(n). - person Jimothy; 04.11.2014

arrow_upward
5
arrow_downward

Количество возможных GUID (128-битное значение) составляет 2 ^ 128 или 3,4 × 10 ^ 38 — примерно 2 триллиона на кубический миллиметр всего объема Земли.

Другими словами, как-то низко.

(Источник ссылки на том Земли: WikiPedia)

person Stu    schedule 02.02.2011

arrow_upward
3
arrow_downward

Зависит от типа алгоритма генерации GUID. Текущие алгоритмы используют 124 случайных бита, поэтому вероятность составляет 1 из 2^124.

Со старыми алгоритмами (которые используют время и MAC-адрес) вероятность намного выше.

person John    schedule 02.02.2011

arrow_upward
3
arrow_downward

В ваших расчетах есть ряд ошибок. Во-первых, 36*32 подразумевает, что любой буквенно-цифровой символ может быть частью GUID. Это не тот случай; разрешены только HEX-символы.

Во-вторых, количество уникальных идентификаторов GUID рассчитывается как количество допустимых символов (16: 0-9, A-F) ^ длина GUID (32 символа).

Итак, у нас есть 16 ^ 32 ==> 2 ^ (4 ^ 32) ==> 2 ^ 128.

Вероятность угадывания любого GUID составляет 1/2^128.

person Babak Naffas    schedule 02.02.2011
comment
Это предполагает, что каждый отдельный байт GUID является действительно случайным. Чтобы гарантировать уникальность GUID среди хостов, большинство частей UUID фактически фиксированы (например, MAC-адрес). Затем остальное дополняется текущим временем, а несколько байтов выбираются случайным образом. И даже эти случайные байты можно угадать, если вы знаете некоторые из ранее сгенерированных UUID.) Скажем, 48 бит MAC-адреса + 64 бита микровремени. 128-48-64=16. Я бы сказал, что шансы ближе к 2^16, чем к 2^128. - person Arnaud Le Blanc; 03.02.2011

arrow_upward
0
arrow_downward

Это 1 / (количество уникальных номеров, возможных с заданной длиной UID). В приведенном выше примере мы видим 16 байт или 128 бит. 2^128, поэтому вероятность совпадения 1/2^128.

person Nathan Kidd    schedule 02.02.2011

arrow_upward
0
arrow_downward

Это зависит от того, сколько GUID создано. Это похоже на проблему дня рождения в статистике. См. Википедию и http://betterexplained.com/articles/understanding-the-birthday-paradox/ (здесь есть пример GUID)

В общем, вероятность коллизии для создания M направляющих из N возможных направляющих равна 1 - (1- (1/N))^C(M,2), где C(M,2) означает «M выбрать 2».

person dfb    schedule 02.02.2011