UUID

UUID (Universally Unique Identifier) — это стандарт идентификации, используемый в создании программного обеспечения, стандартизированный Open Software Foundation (OSF) как часть DCE — среды распределённых вычислений (Distributed Computing Environment (англ.)). Основное назначение UUID — это позволить распределённым системам уникально идентифицировать информацию без центра координации. Таким образом, любой может создать UUID и использовать его для идентификации чего-либо с приемлемым уровнем уверенности, что данный идентификатор непреднамеренно никогда не будет использован для чего-то ещё. Поэтому информация, помеченная с помощью UUID, может быть помещена позже в общую базу данных, без необходимости разрешения конфликта имен. Наиболее распространённым использованием данного стандарта является Globally Unique Identifier (GUID) фирмы Microsoft. Другими значительными пользователями являются Linux (файловая система ext2/ext3, LUKS шифрованные разделы, GNOME, KDE) и Mac OS X — все они применяют реализацию, полученную из библиотеки uuid, находящейся в пакете e2fsprogs.

UUID представляет собой 16-байтный (128-битный) номер. В шестнадцатеричной системе счисления UUID выглядит как:

550e8400-e29b-41d4-a716-446655440000

Общее количество уникальных ключей UUID составляет 2¹²⁸ = 256¹⁶ или около 3,4 × 10³⁸. Это означает, что генерируя 1 триллион ключей каждую наносекунду, перебрать все возможные значения удастся лишь за 10 миллиардов лет.

UUID задокументирован как часть ISO/IEC 11578:1996 «Information technology — Open Systems Interconnection — Remote Procedure Call (RPC)» и позже в ITU-T Rec. X.667 | ISO/IEC 9834-8:2008. IETF опубликовала предлагаемый стандарт RFC 4122, который технически идентичен ITU-T Rec. X.667 | ISO/IEC 9834-8.

UUID со специальным идентификатором может быть преднамеренно использован повторно, для идентификации той же самой сущности в различных контекстах. Например, в Microsoft Component Object Model каждый компонент должен поддерживать стандартный интерфейс «IUnknown». Для этого создан UUID, представляющий «IUnknown». Во всех случаях, когда используется «IUnknown» — при доступе процессов к интерфейсу «IUnknown» в компоненте, или же для реализации поддержки интерфейса «IUnknown» самим компонентом, — всегда происходит отсылка к одному и тому же идентификатору: 00000000-0000-0000-C000-000000000046.

Вероятность совпадения UUID

Расчет вероятности совпадения хотя бы двух ключей из множества ключей, сгенерированных случайным образом вычисляется по формуле: $p(n)=1-{\frac {(N-1)!}{(N-n)!\cdot N^{n-1}}}\Longleftrightarrow p(n)=1-\exp \left(\ln \left({\frac {(N-1)!}{(N-n)!\cdot N^{n-1}}}\right)\right)$

Исходя из того, что $ln(N!)\approx N\cdot ln(N)-N$ при больших значениях N, получаем:

$p(n)\approx 1-\exp \left(N\cdot (\ln(N-1)-\ln(N-n))+n\cdot (\ln(N-n)-\ln(N)-1)-(\ln(N-1)-\ln(N)-1)\right)$

Где N — количество возможных вариантов (2¹²⁸); n — число сгенерированных ключей.

p(2⁵⁰) $\approx$ 1,87×10⁻⁹

p(2⁵⁹) $\approx$ 0.000489

p(2⁶⁴) $\approx$ 0.4

p(2⁶⁶) $\approx$ 0.999665

Можно с уверенностью сказать, что первый квадриллион ключей (10¹⁵) будут уникальными.

Программа для расчета вероятности на Java:

public void probabilityCoincidenceGUID() {
    MathContext mc = new MathContext(1000, RoundingMode.HALF_UP);
    BigDecimal N = BigDecimal.valueOf(2).pow(128, mc);
    BigDecimal n = BigDecimal.valueOf(2).pow(50, mc);
    BigDecimal result_ = calcProbabilityCoincidenceGUID(N, n, mc);
    double result = result_.doubleValue();
} 
    
private BigDecimal calcProbabilityCoincidenceGUID(BigDecimal N, BigDecimal n, MathContext mc) {
    // = N  \cdot (LN(N-1)-LN(N-n))  +  n \cdot (LN(N-n)-LN(N)-1)  -  (LN(N-1)-LN(N)-1)		
    BigDecimal N_1 = N.subtract(BigDecimal.valueOf(1), mc);
    BigDecimal N_n = N.subtract(n, mc);
    BigDecimal ln_N = BigDecimalUtils.ln(N, 400);
    BigDecimal ln_N_1 = BigDecimalUtils.ln(N_1, 400);
    BigDecimal ln_N_n = BigDecimalUtils.ln(N_n, 400);
    BigDecimal v1 = N.multiply(ln_N_1.subtract(ln_N_n, mc), mc);
    BigDecimal v2 = n.multiply(ln_N_n.subtract(ln_N, mc).subtract(BigDecimal.valueOf(1), mc), mc);
    BigDecimal v3 = ln_N_1.subtract(ln_N, mc).subtract(BigDecimal.valueOf(1), mc);
    BigDecimal exp = v1.add(v2, mc).subtract(v3, mc);
    BigDecimal result = BigDecimal.valueOf(1).subtract(BigDecimalUtils.exp(exp, 400));
    return result;
}

См. также

• GUID

Ссылки

• RFC 4122 — A Universally Unique IDentifier (UUID) URN Namespace
• Global UUID registration function at ITU-T
• Устройство и криптоанализ UUID-генератора в ОС Windows