UUID: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Нет описания правки |
Matolch (обсуждение | вклад) м →Ссылки |
||
Строка 67: | Строка 67: | ||
* RFC 4122 — A Universally Unique IDentifier (UUID) URN Namespace |
* RFC 4122 — A Universally Unique IDentifier (UUID) URN Namespace |
||
* [http://www.itu.int/ITU-T/asn1/uuid.html Global UUID registration function at ITU-T] |
* [http://www.itu.int/ITU-T/asn1/uuid.html Global UUID registration function at ITU-T] |
||
* [ |
* [https://rsdn.ru/article/Crypto/UuidCrypto.xml Устройство и криптоанализ UUID-генератора в ОС Windows] |
||
[[Категория:Идентификаторы]] |
[[Категория:Идентификаторы]] |
Версия от 08:00, 26 июля 2015
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 составляет 2128 = 25616 или около 3,4 × 1038. Это означает, что генерируя 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
Возможно, этот раздел содержит оригинальное исследование. |
Расчет вероятности совпадения хотя бы двух ключей из множества ключей, сгенерированных случайным образом вычисляется по формуле:
Исходя из того, что при больших значениях N, получаем:
Где N — количество возможных вариантов (2128); n — число сгенерированных ключей.
p(250) 1,87×10−9
p(259) 0.000489
p(264) 0.4
p(266) 0.999665
Можно с уверенностью сказать, что первый квадриллион ключей (1015) будут уникальными.
Программа для расчета вероятности на 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;
}
См. также
Ссылки
- RFC 4122 — A Universally Unique IDentifier (UUID) URN Namespace
- Global UUID registration function at ITU-T
- Устройство и криптоанализ UUID-генератора в ОС Windows