Как создать длинный гид? - PullRequest
14 голосов
/ 19 мая 2010

Я хотел бы сгенерировать длинный UUID - что-то вроде сеансового ключа, используемого gmail. Он должен быть не менее 256 символов и не более 512. Он может содержать все буквенно-цифровые символы и несколько специальных символов (те, которые находятся под функциональными клавишами на клавиатуре). Это уже сделано или есть образец?

C ++ или C #

Обновление: недостаточно GUID. Мы уже видели столкновения и должны исправить это. 512 является максимальным на данный момент, потому что он не позволит нам изменить материал, который уже был отправлен.

Обновление 2: Для парней, которые настаивают на том, насколько уникальным является GUID, если кто-то хочет угадать ваш следующий идентификатор сессии, ему не нужно вычислять комбинации в течение следующих 1 триллиона лет. Все, что им нужно сделать, это использовать ограничить фактор времени, и они будут выполнены за часы.

Ответы [ 9 ]

28 голосов
/ 19 мая 2010

Если ваши GUID сталкиваются, могу я спросить, как вы их генерируете?

Астрономически невероятно, чтобы GUID сталкивался, поскольку они основаны на:

  • 60 бит - метка времени при генерации
  • 48 бит - идентификатор компьютера
  • 14 бит - уникальный идентификатор
  • фиксированные 6 бит

Вы должны запустить генерацию GUID на одной и той же машине примерно 50 раз в один и тот же момент времени, чтобы получить 50% -ную вероятность столкновения. Обратите внимание, что момент измеряется до наносекунд.

Обновление:

В соответствии с вашим комментарием "помещение GUID в хеш-таблицу" ... именно метод GetHashCode() является причиной коллизии, а не GUID:

public override int GetHashCode()
{
    return ((this._a ^ ((this._b << 0x10) | ((ushort) this._c))) ^ ((this._f << 0x18) | this._k));
}

Вы видите, что он возвращает int, поэтому, если у вас более 2 ^ 32 «GUID» в хеш-таблице, вы на 100% столкнетесь с конфликтом.

13 голосов
/ 19 мая 2010

Согласно вашему обновлению2, вы правы в Guids, и это предсказуемо, даже если msdn ссылается на это. Вот метод, который использует crptographicly сильный генератор случайных чисел для создания идентификатора.

static long counter; //store and load the counter from persistent storage every time the program loads or closes.

public static string CreateRandomString(int length)
{
    long count = System.Threading.Interlocked.Increment(ref counter);
    int PasswordLength = length;
    String _allowedChars = "abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNOPQRSTUVWXYZ23456789";
    Byte[] randomBytes = new Byte[PasswordLength];
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    rng.GetBytes(randomBytes);
    char[] chars = new char[PasswordLength];
    int allowedCharCount = _allowedChars.Length;
    for (int i = 0; i < PasswordLength; i++)
    {
        while(randomBytes[i] > byte.MaxValue - (byte.MaxValue % allowedCharCount))
        {
            byte[] tmp = new byte[1];
            rng.GetBytes(tmp);
            randomBytes[i] = tmp[0];
        }
        chars[i] = _allowedChars[(int)randomBytes[i] % allowedCharCount];
    }
    byte[] buf = new byte[8];
    buf[0] = (byte) count;
    buf[1] = (byte) (count >> 8);
    buf[2] = (byte) (count >> 16);
    buf[3] = (byte) (count >> 24);
    buf[4] = (byte) (count >> 32);
    buf[5] = (byte) (count >> 40);
    buf[6] = (byte) (count >> 48);
    buf[7] = (byte) (count >> 56);
    return Convert.ToBase64String(buf) + new string(chars);
}

РЕДАКТИРОВАТЬ Я знаю, что есть некоторое смещение, потому что allowedCharCount не делится поровну на 255, вы можете избавиться от смещения, выбрасывая и получая новое случайное число, если оно приземлится в ничейной стране остаток.

EDIT2 - это не гарантированно уникально, вы можете хранить статический 64-битный (или выше, если необходимо) монотонный счетчик, кодировать его в base46 и иметь первые 4-5 символов идентификатора.

ОБНОВЛЕНИЕ - теперь гарантированно будет уникальным

ОБНОВЛЕНИЕ 2: алгоритм теперь медленнее, но убрал смещение.

РЕДАКТИРОВАТЬ: Я только что выполнил тест, я хотел, чтобы вы знали, что ToBase64String может возвращать не алфавитно-цифровые символы (например, 1 кодирует "AQAAAAAAAAA="), просто чтобы вы знали.

Новая версия:

Начиная с Ответ Мэтта Дотсона на этой странице, если вы не очень беспокоитесь о пространстве клавиш, вы можете сделать это таким образом, и он будет работать намного быстрее.

public static string CreateRandomString(int length)
{
    length -= 12; //12 digits are the counter
    if (length <= 0)
        throw new ArgumentOutOfRangeException("length");
    long count = System.Threading.Interlocked.Increment(ref counter);
    Byte[] randomBytes = new Byte[length * 3 / 4];
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    rng.GetBytes(randomBytes);

    byte[] buf = new byte[8];
    buf[0] = (byte)count;
    buf[1] = (byte)(count >> 8);
    buf[2] = (byte)(count >> 16);
    buf[3] = (byte)(count >> 24);
    buf[4] = (byte)(count >> 32);
    buf[5] = (byte)(count >> 40);
    buf[6] = (byte)(count >> 48);
    buf[7] = (byte)(count >> 56);
    return Convert.ToBase64String(buf) + Convert.ToBase64String(randomBytes);
}
10 голосов
/ 19 мая 2010
StringBuilder sb = new StringBuilder();
for (int i = 0; i < HOW_MUCH_YOU_WANT / 32; i++)
   sb.Append(Guid.NewGuid().ToString("N"));
return sb.ToString();

а зачем?

8 голосов
/ 19 мая 2010

Проблема здесь в почему , а не как . Идентификатор сеанса больше , чем GUID, бесполезен, потому что он уже достаточно велик, чтобы предотвратить атаки методом перебора.

Если вы беспокоитесь о предсказании GUID, не беспокойтесь. В отличие от более ранних последовательных идентификаторов GUID, идентификаторы GUID V4 криптографически безопасны на основе RC4. Единственный известный мне эксплойт зависит от полного доступа к внутреннему состоянию процесса, который генерирует значения, поэтому он никуда не денется, если у вас есть только частичная последовательность GUID.

Если вы параноик, сгенерируйте GUID, добавьте в него что-то вроде SHA-1 и используйте это значение. Однако это пустая трата времени. Если вас беспокоит перехват сеанса, вам следует обратить внимание на SSL, а не на это.

3 голосов
/ 19 мая 2010
byte[] random = new Byte[384];

//RNGCryptoServiceProvider is an implementation of a random number generator.
RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
rng.GetBytes(random);
var sessionId = Convert.ToBase64String(random);

Вы можете заменить символы "/" и "=" из кодировки base64 на любые специальные символы, приемлемые для вас.

Кодировка Base64 создает строку, которая на 4/3 больше байтового массива (следовательно, 384 байта должны дать вам 512 символов).

Это должно дать вам на порядки больше значений, чем в кодировке guid с кодировкой base16 (hex). 512 ^ 16 против 512 ^ 64

Также, если вы помещаете их на сервер sql, обязательно отключите нечувствительность к регистру.

1 голос
/ 20 мая 2010

Возможно, вы захотите проверить поддержку Uuid Library . Он поддерживает различные генераторы, в том числе генератор случайных чисел, который может удовлетворить ваши потребности.

1 голос
/ 19 мая 2010

Есть два очень простых способа (C #):

1) Создайте группу Guids, используя Guid.NewGuid (). ToString ("N"). каждый GUID будет иметь длину 32 символа, поэтому просто сгенерируйте 8 из них и объедините их, чтобы получить 256 символов.

2) Создайте постоянную строку (const string sChars = "abcdef") из допустимых символов, которые вы хотели бы использовать в своем UID. Затем в цикле случайным образом выбирайте символы из этой строки, генерируя случайным образом число от 0 до длины строки допустимых символов (sChars), и объединяйте их в новую строку (используйте stringbuilder, чтобы сделать его более производительным, но строка будет работать тоже).

0 голосов
/ 23 мая 2014

https://github.com/bigfatsea/SUID Простой уникальный идентификатор

Хотя это на Java, но может быть легко перенесено на любой другой язык. Вы можете ожидать дублирования идентификаторов в том же экземпляре 136 лет спустя, что достаточно для средних и малых проектов.

Пример:

long id = SUID.id().get();
0 голосов
/ 19 мая 2010

Я бы использовал какой-то хэш std :: time (), вероятно, sha512. ex (используя crypto ++ для кодирования sha hash + base64).

#include <iostream>
#include <sstream>
#include <ctime>
#include <crypto++/sha.h>
#include <crypto++/base64.h>

int main() {
    std::string digest;
    std::stringstream ss("");
    ss << std::time(NULL);

    // borrowed from http://www.cryptopp.com/fom-serve/cache/50.html
    CryptoPP::SHA512 hash;
    CryptoPP::StringSource foo(ss.str(), true,
        new CryptoPP::HashFilter(hash,
           new CryptoPP::Base64Encoder(
               new CryptoPP::StringSink(digest))));
    std::cout << digest << std::endl;

    return 0;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...