Дата: 2025-01-23
Принято
Можно разработать формат, содержащий любую значимую информацию, – возможно, зашифрованную или подписанную RSA-ключом.
Ключи должны быть:
Желательно:
В крупнейших онлайн-магазинах доставляется около 4 млн. заказов в день. Это 124 млн. в месяц, или 1.5 млрд. в год, или 100 млрд. заказов за 60-70 лет.
Для значений, используемых в чисто техническом смысле, то есть не для показа клиентам, – UUID версии 4 (случайное число). Если желательна сортировка ключей по времени создания, а раскрытие этого времени не несёт бизнес-рисков, то UUID версии 7 (таймстемп + случайное число).
Для значений, используемых в бизнес-смысле, то есть которые надо печатать на квитанциях, показывать клиентам, вводить в поисковых формах, – числовая строка FPE вида 012-345-678. Клиентам требуется вводить только цифры (на компактной цифровой клавиатуре смартфона) - разделители вставляются автоматически.
Самая правая цифра - контрольная, так что указанный выше шаблон достаточен для 100 миллионов заказов (минус 1). Контрольная цифра вычисляется так же, как для номеров кредитных карт, за исключением строк, состоящих только из нулей. Такие строки считаются недопустимыми, и при их генерации требуется повторная генерация (см. Вычисление контрольной цифры).
Для документов и упаковок рекомендуется генерировать QR-код с номером заказа либо в виде ссылки на форму оплаты, где уже указана сумма. Это облегчит оплату с помощью смартфона.
Записи в БД - потенциально big data - быстро ищутся и уникально индексируются способом, который не создаёт бизнес-рисков. Идентификаторы, предназначенные для показа клиентам и/или ввода клиентами, не раскрывают внутреннюю статистику, такую как общее кол-во записей.
[наверх]
Вручную вводимые номера должны быть защищены от опечаток с помощью контрольной цифры. Это важно для зачисления платежей на нужный номер заказа или банковский счет.
Для буквенно-цифровых строк (буквы A-Z и цифры 0-9) удобно использовать алгоритм валидации ISIN, который расширяет алгоритм Лу́на. Последний работает только с десятичными цифрами; ISIN сначала заменяет: A=10, B=11, …, Z=35, а затем вызывает алгоритм Лу́на. Таким образом, для десятичных строк алгоритм ISIN - это алгоритм Лу́на, защищающий номера кредитных карт.
В общем случае, любой алгоритм может быть применен к произвольным строкам путем предварительного преобразования их в цифровые - заменяя каждый символ его индексом в алфавите, например в Unicode, который содержит чуть более миллиона позиций.
Все алгоритмы, основанные на остатках от деления (Лу́на, ISIN, EAN13, ISBN), не работают со строками, состоящими только из нулей (0, 00, и т.д.), – по крайней мере, их реализация в библиотеке Apache Commons Validator. Если такие строки допустимы, подойдёт алгоритм Верхуффа (но он работает только для десятичных цифр). Как вариант, при получении такой строки можно повторить генерацию, взяв новое значение DB sequence. Финальная строка (с добавленной контрольной цифрой) не должна состоять только из нулей, т.к. такой номер заказа выглядит странно.
Отображается группами по 3 цифры (минимум 9 цифр, нули слева для малых значений): 000-111-222, 333-444-555-6. Хранится в БД и упоминается в логах в таком же виде, чтобы не было разночтений и проблем с поиском, формами ввода, копированием, пересылкой и т.п.
[наверх]
2^63 - 1 примерно равно 9 и ещё 18 цифр.[наверх]
Отображается группами по 3 цифры (минимум 9 цифр, нули слева для малых значений): 000-111-222, 333-444-555-6. Хранится в БД и упоминается в логах в таком же виде, чтобы не было разночтений и проблем с поиском, формами ввода, копированием, пересылкой и т.п.
Числа идут не подряд - для каждой записи прибавляется случайная дельта. Помимо главной функции - скрытия общего кол-ва записей - этa «разрежённость» является своего рода защитой от опечаток при ручном вводе, поэтому контрольная цифра не требуется (она снизила бы ёмкость числа в 10 раз). Если минимальная дельта - 100, а максимальная - 200, то 9 цифр хватит для (с поправкой на первоначальное значение DB sequence):
Самый первый номер - достаточно большое число без нулей справа. Например:
| Предыдущий номер записи | Дельта | Новый номер записи | Отображается | Комментарий |
|---|---|---|---|---|
| 23 456 | 23 456 | 002-345-6 | генерация самого первого номера | |
| 23 456 | 101 | 23 557 | 002-355-7 | |
| 23 557 | 200 | 23 757 | 002-375-7 | |
| 23 759 | 153 | 23 910 | 002-391-0 | |
| … | … | … | ||
| 999 999 999 | 100 | 1 000 000 099 | 100-000-009-9 | появление 10-й цифры |
Для оценки сверху (1.5 млрд. заказов в год) 11 цифр хватило бы на 60-70 лет. Однако с учётом уменьшения номерной ёмкости в 100-200 раз требуется на 2 цифры больше.
Для получения очередного значения нужно выполнить в Postgres (можно обернуть в процедуру, которая будет вызываться автоматически):
BEGIN;
ALTER SEQUENCE seq_name INCREMENT BY <случайное значение>;
SELECT nextval('seq_name');
COMMIT;
[наверх]
Если выделить первые 3 цифры на кол-во месяцев с некоторой даты (83 года - это 996 месяцев), то для оценки сверху (124 млн. записей в месяц) - и даже для 1 млрд. - достаточно 9 цифр, что с учётом уменьшения номерной ёмкости в 100-200 раз (случайная дельта) превращается в 11. Итого 14 цифр, как и в предыдущем варианте, только меньше нулей слева. И все эти разряды обязательно создать сразу.
Префикс может удлиняться влево сколько потребуется, но кол-во записей в месяц ограничено. Таково свойство всех форматов, использующих префикс.
В 1-м месяце номера будут выглядеть как 001-000-00-000-000, во 2-м - 002-000-00-000-000. Для каждого префикса нужна своя DB sequence. При создании записи используется DB sequence, соответствующая префиксу (кол-ву месяцев).
[наверх]
Математически доказана возможность (FPE - Format-Preserving Encryption), используя секретный ключ, зашифровать любую строку так, что результат:
Под алфавитом понимается полный набор всех возможных символов. Так, если алфавит - это цифры + латинские буквы + дефис, строка “567” может превратиться в “0T-” (если есть требование сохранять буквы как буквы и т.п., то строку придётся шифровать по частям, с разными алфавитами). Если алфавит состоит из только из цифр, то из одного набора цифр всегда получится другой набор цифр, однако это будет не число, а строка, где могут появиться нули слева.
Например, число 12 - виде строки “12” - может превратиться в “07”, а число 123 - в виде строки “123” - может превратиться в “007”. Если трактовать результат как число, то и там и там 7, что неверно. Если исключить нуль из алфавита, чтобы результат был именно числом, то алгоритм, как ни странно, будет шифровать, но вот расшифровать результат будет невозможно, т.к. алгоритм «не знает» о существовании нуля.
Можно использовать произвольный алфавит, например 16-ричный (0-9A-F), для чего исходное число нужно сначала закодировать этим алфавитом в строку, а затем преобразовать её. FPE, по определению, предназначен для сопоставления символов в рамках одного алфавита.
Рекомендована реализация FPE вида FF3 версии FF3-1, одобренная как стандарт NIST, – см. их документ, п.5.2. Была опробована реализация на Java, принимающая на вход, если выбран десятичный алфавит, строки длиной 6-56 символов. Этот лимит зависит от алфавита и обусловлен требованием FF3-1: кол-во возможных значений исходной строки должно быть не менее 1 млн.
В данном (десятичном) случае 10^6 = 1 000 000. Поэтому перед шифрованием необходимо дополнять десятичную строку, если она короче 6 символов, нулями слева. Что касается максимальной длины (56), то наибольшее 8-байтовое знаковое целое (Java long) состоит из 19 цифр.
Отображается группами по 3 цифры (минимум 9 цифр, нули слева для малых значений): 000-111-222, 333-444-555-6. Хранится в БД и упоминается в логах в таком же виде, чтобы не было разночтений и проблем с поиском, формами ввода, копированием, пересылкой и т.п.
Длина секретного ключа может составлять 128, 192 или 256 бит. Дополнительный ключ, так называемый tweak, составляет 56 бит.
Формат (алфавит + разделитель групп) определяется исключительно бизнес-требованиями; здесь лишь приводятся некоторые варианты.
Определим ID как строку переменной длины вида 012-345-678 - минимум 9 десятичных цифр, самая правая цифра - контрольная, так что длина строки остаётся постоянной до 100 млн. (минус 1) записей. Слева может быть любое кол-во нулей, которые имеют значение, их нельзя обрезать.
Разряды разделены слева направо дефисами по 3 (для визуальной гармонии). Разделители являются частью формата, т.к. если использовать их только для отображения, а хранить в БД 0123456 (с нулём слева!) вместо 012-345-678, возникнут разночтения и проблемы с поиском, формами ввода, копированием, пересылкой и т.п. Разделитель может быть любым, например точкой (012.345.678), наклонной чертой (012/345/678).
Для реалистичной оценки сверху - 1.5 млрд. записей в год - достаточно, на 60-70 лет, 11 значащих цифр (100 млрд. записей минус 1) плюс контрольная цифра: 999-999-999-99c, что вместе с разделителями групп даёт 15 символов.
Источник строки - порядковый номер, полученный из DB sequence. Строка может удлиняться влево по мере увеличения исходного числа: 000-000-000 → 000-000-000-0 и т.д. Формально, такое удлинение бесконечно, но в реальности будет не более 20 цифр: наибольшее 8-байтовое знаковое целое (Java long) занимает 19 цифр (9 и ещё 18 цифр), плюс контрольная цифра. Т.обр. максимальный возможный номер - это примерно 900-000-000-000-000-000-0c, где c - контрольная цифра, зависящая от алгоритма.
Можно использовать любой другой алфавит, например Crockford’s Base32, широко известный благодаря отсутствию неоднозначно выглядящих символов (0/O, 1/I, 1/L): 0123456789ABCDEFGHJKMNPQRSTVWXYZ. Тогда макс. номер записи займет уже не 26 символов, а 18: 2G1-D1V-5J0-000-0c. Для оценки сверху - 100 млрд. записей минус 1 - понадобится не 15 символов, а 10: 2X4-7FT-Zc. С другой стороны, это снижает читабельность, а цифра 5 иногда может быть спутана с буквой S.
Исходные порядковые номера (положительные значения, полученные из DB sequence) после конвертации в строку дополняются слева нулями до 8 разрядов: 123 -> 00000123. Если исходный номер занимает более 8 разрядов, он остаётся в исходном виде: 12 345 678 -> 12345678. Так, 8 нулей и 9 нулей - существующие и разные значения, см. их расшифровку ниже.
После того как строка шифруется:
Затем с целью самопроверки:
Пример работы алгоритма для 128-битного секретного ключа “2DE79D232DF5585D68CE47882AE256D6” и 56-битного вспомогательного ключа “CBD09280979564”:
| Исходный
порядковый номер → |
Дополнение
до 6 разрядов → |
Зашифровано → | Финальный номер
(с контр. цифрой ISIN) |
|---|---|---|---|
| 1 | 000001 | 943130351 | 943-130-351 |
| 2 | 000002 | 887763811 | 887-763-811 |
| 3 | 000003 | 308392836 | 308-392-836 |
| 1 000 | 001000 | 568737225 | 568-737-225 |
| 10 000 | 010000 | 216388769 | 216-388-769 |
| 100 000 | 100000 | 151996170 | 151-996-170 |
| 1 234 567 | 1234567 | 683768261 | 683-768-261 |
Поскольку любой комбинации цифр соответствует какое-то исходное значение, можно узнать, при каком порядковом номере (значении DB sequence) клиент получит заранее известные значения:
| Финальный номер
(«c» - контр. цифра) → |
Расшифровано → | Исходный
порядковый номер |
|---|---|---|
| 000-000-00c | 08959589 | 8 959 589 |
| 000-000-000-c | 746999857 | 746 999 857 |
| 000-000-01c | 93005957 | 93 005 957 |
| 000-000-02c | 62197228 | 62 197 228 |
| 000-000-10c | 69986121 | 69 986 121 |
[наверх]
Длина - 16 байт (128 бит). Наиболее распространённый вариант - просто случайное число, это версия 4.
6cb32aba-88a7-4188-b32a-ba88a751883c занимает 36 байт.6cb32aba-88a7-4188-b32a-ba88a751883c.Идемпотентность - свойство объекта или операции при повторном применении операции к объекту давать тот же результат, что и при первом применении. Например, если объект уже был создан, он не будет создан повторно.
↩