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

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

12 голосов
/ 02 февраля 2011

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

Скажите Guid с сервера SQL: 5AC7E650-CFC3-4534-803C-E7E5BBE29B3D

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

обсудить = D

Ответы [ 6 ]

26 голосов
/ 02 февраля 2011

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

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

  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.

6 голосов
/ 02 февраля 2011

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

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

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

3 голосов
/ 02 февраля 2011

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

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

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

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

3 голосов
/ 02 февраля 2011

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

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

0 голосов
/ 02 февраля 2011

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

Как правило, вероятность столкновения для создания M направляющих над N возможными направляющими составляет 1 - (1- (1/N))^C(M,2), где C(M,2) - это "М выбрать 2"

0 голосов
/ 02 февраля 2011

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

...