BugTraq.Ru: форум / programming / Оптимально думаю примерно так (+)

информационная безопасность
без паники и всерьез

подробно о проекте

Spanning Tree Protocol: недокументированное применение

Анализ криптографических сетевых...

Модель надежности двухузлового...

Специальные марковские модели надежности...

Очередное исследование 19 миллиардов...

Оптимизация ввода-вывода как инструмент...

Зловреды выбирают Lisp и Delphi

bugtraq.ru / форум / programming

Имя

Пароль

если вы видите этот текст, отключите в настройках форума использование JavaScript


ФОРУМ


	все доски
	FAQ
	IRC
	новые сообщения

	site updates
	guestbook
	beginners
	sysadmin
	programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap

регистрация

Легенда:

новое сообщение

закрытая нитка

новое сообщение

в закрытой нитке

старое сообщение

Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
Новичкам также крайне полезно ознакомиться с данным документом.

Оптимально думаю примерно так 07.09.06 10:40 Число просмотров: 2389
Автор: leo <Леонид Юрьев> Статус: Elderman

<"чистая" ссылка>

Получается, что задача сводится к тому, чтобы представить 128-бит GUID в виде 16 строковых символов XML.

Без потерь это можно сделать, только сохраняя 8 бит на символ. Поэтому первый вариант такой - определить алфавит в 256 строковых символов из набора Unicode/UTF-8.

Если ПО партнера не может Unicode/UTF-8, то придется жертвовать размером GUID. Тогда делаем так:
- определяем алфавит из допустимых строковых символов, их будет не меньше 64 (заглавные латинские буквы, прописные, пробел, подчерк и цифры);
- разбиваем GUID на две половины по 64 биnа, для вычисления на unsigned __int64;
- для каждой половины 8 раз берем остаток от деления на размер алфавита и переводим в соответствующий символ;
- если есть вероятность, что все GUID не случайные числа с нормальным распределением (например порядковый номер), то перед преобразованием берем MD5 (или SHA) от GUID, и дальше работаем с этим дайджестом. Свертка 8 байтов в 7через XOR очень плохое решение с точки зрения обеспечения уникальности результирующего DocID;
- вероятность коллизии 1.0/(размер_алфавита**16);

64-bit GUID's хеш в XML документе 07.09.06 06:17
Автор: void <Grebnev Valery> Статус: Elderman

<"чистая" ссылка>

Необходимо создать строковое представление "уникального" UID длиной 16символов

ПО нашего партнёра требует, чтобы каждый наш XML документ, направляемый этому партнёру, содержал уникальный UID длиной 16 символов. При этом он предъявляет странноватое требование, что мол, это должен быть GUID (128 бит).
Однако, непосредственно строковое представление GUID в XML документе, типа DocID = "da2ea19c3b394356a54eb6656b60a23b", программа нашего партнёра не воспринимает, т.к. максимальная длина этого поля в их ПО равна 16 символам. "Уникальность" должна быть обеспечена с большой вероятностью, хотя одна коллизия допускается и может быть разрешена (я буду проверять по нашей базе UID для всех документов).

Вопрос как получить UID-дообразный 16 символьный хеш, например GUID, который можно было без проверок на допустимые символы использовать в XML (желательно без сложных алгоритмов проверки и замены недопустимых символов).

Предлагается тупо:

1) получить GUID a массив BYTE b[16].

2) применить XOR:
b[0] = b[0]^b[8];
b[1] = b[1]^b[9];
...
b[7] = b[7]^b[15];

3) первые 16 байт, b[0]-b[15] писать в XML в base16. Это и будет UID.

4) проверить коллизии, и если есть, то повторить один раз, предполагая, что вероятность второй коллизии ничтожно мала.

С# код мог быть таков:

System.Guid guid = System.Guid.NewGuid();

// guid = {da2ea19c-3b39-4356-a54e-b6656b60a23b}
// string s = guid.ToString();
// s = "da2ea19c3b394356" + "a54eb6656b60a23b"

byte[] b = guid.ToByteArray();
//[0] 156
//[1] 161
//[2] 46
//[3] 218
//[4] 57
//[5] 59
//[6] 86
//[7] 67

//[8] 165
//[9] 78
//[10] 182
//[11] 101
//[12] 107
//[13] 96
//[14] 162
//[15] 59

int offset = b.Length / 2;
for (int i = 0; i < offset; i++)
{
b[i] ^= b[offset + i];
}

//[0] 57
//[1] 239
//[2] 152
//[3] 191
//[4] 82
//[5] 91
//[6] 244
//[7] 120

//[8] 165
//[9] 78
//[10] 182
//[11] 101
//[12] 107
//[13] 96
//[14] 162
//[15] 59

string sxor = "";
for(int i = 0; i < b.Length; i++)
{
sxor += Convert.ToString(b[i], 16);
}

//sxor = "39ef98bf525bf478" + "a54eb6656b60a23b"

sxor = sxor.Substring( 0, offset) ;

//sxor = "39ef98bf525bf478

Спасибо.

Оптимально думаю примерно так 07.09.06 10:40
Автор: leo <Леонид Юрьев> Статус: Elderman

<"чистая" ссылка>

Совершенно верно. 08.09.06 05:18
Автор: void <Grebnev Valery> Статус: Elderman

<"чистая" ссылка>

> Получается, что задача сводится к тому, чтобы представить
> 128-бит GUID в виде 16 строковых символов XML.

Совершенно верно.

> Без потерь это можно сделать, только сохраняя 8 бит на
> символ. Поэтому первый вариант такой - определить алфавит в
> 256 строковых символов из набора Unicode/UTF-8.

Спасибо за совет. Мы попробуем согласовать с партнёром поддерживаемый ими алфавит.

> Если ПО партнера не может Unicode/UTF-8, то придется
> жертвовать размером GUID. Тогда делаем так:
> - определяем алфавит из допустимых строковых символов, их
> будет не меньше 64 (заглавные латинские буквы, прописные,
> пробел, подчерк и цифры);
> - разбиваем GUID на две половины по 64 биnа, для вычисления
> на unsigned __int64;
> - для каждой половины 8 раз берем остаток от деления на
> размер алфавита и переводим в соответствующий символ;
> - если есть вероятность, что все GUID не случайные числа с
> нормальным распределением (например порядковый номер), то
> перед преобразованием берем MD5 (или SHA) от GUID, и дальше
> работаем с этим дайджестом. Свертка 8 байтов в 7через XOR
> очень плохое решение с точки зрения обеспечения
> уникальности результирующего DocID;
> - вероятность коллизии 1.0/(размер_алфавита**16);

Интересно. Но в силу моей тугодомчивости, не совсем понятно.
Есть последовательность из 16 байт. Есть алфавит из, пусть, 64 литер.
Можно "сдвинуть" каждый байт набора символов (0-255) к номеру символа в "координатах" алфавита (0-64):

b[0] = b[0] mod 64;
...
b[15] = b[15] mod 64;

Правильно ли я понял ("... для каждой половины 8 раз берем остаток от деления на
размер алфавита и переводим в соответствующий символ ...")?

Спасибо.

Да, как уже сказал amirul так будет правильно. Я как-то... 08.09.06 17:38
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 08.09.06 17:39 Количество правок: 1

<"чистая" ссылка>

> Интересно. Но в силу моей тугодомчивости, не совсем
> понятно.
> Есть последовательность из 16 байт. Есть алфавит из, пусть,
> 64 литер.
> Можно "сдвинуть" каждый байт набора символов (0-255) к
> номеру символа в "координатах" алфавита (0-64):
>
> b[0] = b[0] mod 64;
> ...
> b[15] = b[15] mod 64;
>
> Правильно ли я понял ("... для каждой половины 8 раз берем
> остаток от деления на
> размер алфавита и переводим в соответствующий символ
> ...")?
Да, как уже сказал amirul так будет правильно. Я как-то упустил из виду, что итоговых символов будет как и исходных байтов ровно 16. Есть только маленькое "но" - если исходные GUID генерируется не на основе случайных чисел, то для упрощенного варианта нужно обязательно взять MD5/SHA. Иначе вероятность коллизий сильно возрастет.

Волею судеб у меня оказался w3c-шный стандарт XML 1.1 [update] 08.09.06 15:21
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 08.09.06 15:42 Количество правок: 1

<"чистая" ссылка>

> > Получается, что задача сводится к тому, чтобы
> представить
> > 128-бит GUID в виде 16 строковых символов XML.
>
> Совершенно верно.

Еще одно уточнение. Каким именно элементом XML-я является этот DocID (насколько я понял это атрибут в стартовом теге типа <document DocID="guidbla-bla-bla" ....>)

Стандарт описывает значение атрибута как

AttValue	   ::=   	'"' ([^<&"] | Reference)* '"' 
			|  "'" ([^<&'] | Reference)* "'"

---

Это означает всего лишь, что в значении атрибута, ограниченном кавычками запрещены только три символа: '<', '&' и '\"'
Ну а в значении атрибута, ограниченном апострофами, соответственно вместо кавычки запрещен апостроф.
Reference это &, < и т.д.

Кстати, понимает ли ваш клиент reference-ы? Если да, то проблемы нет вообще. Просто записать в атрибуте 16 байт, заменяя все кавычки, амперсанды и знаки меньше их reference-ами. Если нет, то все как написал leo, используя алфавит из 253-х символов.

> Интересно. Но в силу моей тугодомчивости, не совсем
> понятно.
> Есть последовательность из 16 байт. Есть алфавит из, пусть,
> 64 литер.

64 - мало. Нужно сохранить как можно больше инфы. Для этого надо выбрать как можно бОльший размер алфавита.

> Можно "сдвинуть" каждый байт набора символов (0-255) к
> номеру символа в "координатах" алфавита (0-64):

> b[0] = b[0] mod 64;
> ...
> b[15] = b[15] mod 64;

> Правильно ли я понял ("... для каждой половины 8 раз берем
> остаток от деления на
> размер алфавита и переводим в соответствующий символ
> ...")?

Нет.
Это обычное преобразование из одной системы счисления в другую. Тебе надо перевести твой GUID в 253-ричную систему счисления.

Псевдокод:

int i;
bignum GUID;
char newGUID[16];

for (i = 0; i < 16; i++) {
newGUID[i] = GUID % 253; // здесь еще надо учесть, что "дырки" находятся не в конце, а в средине алфавита
GUID /= 253;
}

---

В принципе, если нет желания возиться с большими числами, можно преобразовать по 64-битным кусочкам (64-битная арифметика встроена во все современные компиляторы).

--------------------
Я понял, что ты хотел сказать. Действительно можно обойтись только 8-битной арифметикой. Никаких остатков от деления не надо. Просто заменяй амперсанд, кавычку и знак меньше на, к примеру, 0, 1 и 2 соответственно. Все остальное - без изменений.

Спасибо! Теперь понятно. 09.09.06 03:25
Автор: void <Grebnev Valery> Статус: Elderman

<"чистая" ссылка>

Page build time: 0 s

Design: Vadim Derkach