Каква е вероятността да се познае (съвпадне) 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 в секунда. За да има 50% шанс да познае g, нашият атакуващ трябва да генерира 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. Статистиката не е силната ми страна, така че може би е необходим само sqrt(n), за да достигне праг от 50%. - person Jimothy; 04.11.2014

arrow_upward
5
arrow_downward

Контекстните менюта не се показват в резултат на WM_RBUTTONUP, те се показват в резултат на WM_CONTEXTMENU. Причината за това е да се позволи на клавиатурата (Shift+F10 или клавиш за контекстно меню) да извика контекстното меню. Няма начин да се разграничи извикването на WM_CONTEXTMENU от клавиатура или мишка. Ако искате указаното поведение, ще трябва да се откажете от функционалността на клавиатурата. Горещо препоръчвам да запазите „нормалното“ поведение и вместо двукратно щракване с десния бутон да използвате друг механизъм като Ctrl+Щракване с ляв бутон.
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 са генерирани. Това е подобно на проблема с рождения ден в статистиката. Вижте Wikipedia и 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