Алгоритмическое создание уникального случайного кода друга на основе идентификатора пользователя - PullRequest
2 голосов
/ 18 июня 2020

Я ищу способ сгенерировать случайный уникальный код друга 9 di git для пользователя из последовательного идентификатора пользователя. Идея заключается в том, чтобы люди не могли перечислять пользователей, просматривая коды друзей один за другим. Если существует 1000 возможных кодов и 100 зарегистрированных пользователей, поиск случайного кода должен иметь 10% шанс найти пользователя.

Возможный способ сделать это - сгенерировать код случайным образом, проверить, является ли код уже используется, и если это так, попробуйте еще раз. Я ищу подход (в основном из любопытства), в котором код друга генерируется алгоритмически и гарантированно будет уникальным для этого идентификатора пользователя с первой попытки.

В частности, учитывая диапазон чисел (от 1 до 999 999 999) запуск функции для этого числа должен вернуть другое число в том же диапазоне, которое является парным и уникальным для входного числа. Эта пара должна отличаться только в том случае, если диапазон изменяется и / или изменяется начальное значение случайности.

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

Вот код c#, который выполняет то, что я хочу, путем генерации всего диапазона чисел, перетасовки списка, а затем получения идентификатора друга, обрабатывая идентификатор пользователя как индекс списка:

int start = 1; // Starting number (inclusive)
int end = 999999999; // End number (inclusive)
Random random = new Random(23094823); // Random with a given seed

var friendCodeList = new List<int>();
friendCodeList.AddRange(Enumerable.Range(start, end + 1)); // Populate list

int n = friendCodeList.Count;

// Shuffle the list, this should be the same for a given start, end and seed
while (n > 1)
{
    n--;
    int k = random.Next(n + 1);
    int value = friendCodeList[k];
    friendCodeList[k] = friendCodeList[n];
    friendCodeList[n] = value;
}

// Retrieve friend codes from the list
var userId = 1;
Console.WriteLine($"User ID {userId}: {friendCodeList[userId]:000,000,000}");

userId = 99999999;
Console.WriteLine($"User ID {userId}: {friendCodeList[userId]:000,000,000}");

userId = 123456;
Console.WriteLine($"User ID {userId}: {friendCodeList[userId]:000,000,000}");

User ID 1: 054,677,867 User ID 99999999: 237,969,637 User ID 123456: 822,632,399

К сожалению, это не подходит для больших диапазонов - эта программа требует 8 ГБ ОЗУ для запуска, с кодом друга 10 или 12 di git было бы невозможно предварительно -сгенерировать список либо в памяти, либо в базе данных. Я ищу решение, которое не требует этого шага предварительной генерации.

Меня интересуют решения, в которых для достижения этой цели используется либо генератор случайных чисел с начальным значением, либо побитовые хитрости, если это возможно. Вышеупомянутая функция обратима (путем поиска значений в списке), но решение не обязательно.

Ответы [ 2 ]

5 голосов
/ 18 июня 2020

Быстрый урок математики!

Вы думаете о разработке способа сопоставить одно целочисленное значение (исходное «секретное» UserId значение) другому ((зашифрованное) «publi c» значение) и обратно. Именно это и делает блочный шифр (за исключением того, что каждый «блок» обычно имеет размер 16 байт, а не является одиночным символом или целочисленным значением). Другими словами, вы хотите создать свою собственную криптосистему.

(Обратите внимание, что даже если вы думаете о преобразовании UserId 123 в string вместо целого числа, например, YouTube Идентификатор видео, например "dQw4w9WgXcQ") - это все еще целое число: потому что каждое скалярное значение, хранящееся в компьютере, включая строки, может быть представлено как целое число - отсюда и проблема «недопустимых простых чисел» еще в конце 1990-х ).

И самый большой, самый важный вывод из любого курса информатики на бакалавриате по криптографии - это никогда не создавайте свою собственную криптосистему !.

Без этого ...

При условии, что безопасность не является главной проблемой ...

... и вас беспокоит только с предотвращением раскрытия увеличивающихся значений целочисленных идентификаторов (например, ваши посетители и пользователи не видят, сколько записей в базе данных у вас действительно есть), затем используйте библиотеку Hashids: https://hashids.org/

В своем коде создайте один объект Hashids (я бы использовал поле или свойство publi c static readonly, или еще лучше: одноэлементный вводимый сервис) и используйте .Encode метод преобразования любого целого числа int / Int32 в значение string.

Чтобы преобразовать значение string обратно в исходное int / Int32, используйте .Decode method.

Кстати, мне не нравится, как библиотека называется «Hashids», когда хеши предназначены для односторонних функций - потому что значения по-прежнему обратимы - хотя и с использованием секретное значение "соли" (почему оно не называется "ключом"?) на самом деле это не ha sh, imo.


Если безопасность действительно имеет значение ... .

Затем вам нужно рассматривать каждое целочисленное значение как дискретный блок в блочном шифре (а не потоковый шифр, потому что каждое значение должно быть зашифровано и дешифровано независимо само).

В целях практичности необходимо использовать блочный шифр symri c с небольшим размером блока. К сожалению, многие блочные шифры с маленькими размерами блоков не очень хороши (TripleDES имеет размер блока 64 бита, но сегодня он слаб), поэтому давайте придерживаться AES.

AES имеет размер блока 128 бит (16 байт) - это то же самое, что и два Int64 целых числа, соединенных друг с другом. Предполагая, что вы используете кодировку base64url для 16-байтового значения, ваш вывод будет иметь длину 22 символа (поскольку Base64 использует 6 бит на символ). Если вас устраивают струны такой длины, то все готово. Самая короткая URL-безопасная строка, которую вы можете сгенерировать из 128-битного значения, - 21 (вряд ли улучшение вообще) потому что Base-73 - это максимум, который вы можете безопасно использовать в URL, который переживет все современные URL -системы передачи (никогда автоматически не предполагайте, что Unicode поддерживается где-либо при работе с открытым текстом). использование таких методов, как режим CTR, означает, что сгенерированный вывод должен включать дополнительную информацию о состоянии (IV, счетчик и т. д. c), которая в конечном итоге займет столько же места, сколько было получено .

Вот код:

Очень важные примечания :

private static readonly Byte[] _key = new Byte[] { }. // Must be 128, 192 or 256 bits (16, 24, or 32 bytes) in length.

private static readonly Byte[] _iv = new Byte[8]; // You could use the default all-zeroes.

// Note that this method works with Int32 arguments.
private static Byte[] ProcessBlock( Byte[] inputBlock, Boolean encrypt )
{
    Byte[] outputBlock;

    using( Aes aes = Aes.Create() )
    {
        aes.Key = _key;
        aes.IV  = _iv;

        using( ICryptoTransform xform = encrypt ? aes.CreateEncryptor() : aes.CreateDecryptor() )
        {
            outputBlock = xform.TransformFinalBlock( inputBlock, 0, inputBlock.Length );
        }
    }
}

public static Byte[] EncryptInteger( Int64 value )
{
    Byte[] inputBlock = new Byte[16];
    inputBlock[0] = (Byte)(value >>  0 & 0xFF);
    inputBlock[1] = (Byte)(value >>  8 & 0xFF);
    inputBlock[2] = (Byte)(value >> 16 & 0xFF);
    inputBlock[3] = (Byte)(value >> 24 & 0xFF);
    inputBlock[4] = (Byte)(value >> 32 & 0xFF);
    inputBlock[5] = (Byte)(value >> 40 & 0xFF);
    inputBlock[6] = (Byte)(value >> 48 & 0xFF);
    inputBlock[7] = (Byte)(value >> 56 & 0xFF);

    return ProcessBlock( inputBlock, encrypt: true );
}

public static Int64 DecryptInteger( Byte[] block )
{
    Byte[] outputBlock = ProcessInteger( value, encrypt: false );

    return
        (Int64)outputBlock[0] <<  0 |
        (Int64)outputBlock[1] <<  8 |
        (Int64)outputBlock[2] << 16 |
        (Int64)outputBlock[3] << 24 |
        (Int64)outputBlock[4] << 32 |
        (Int64)outputBlock[5] << 40 |
        (Int64)outputBlock[6] << 48 |
        (Int64)outputBlock[7] << 56;
};

public static String EncryptIntegerToString( Int64 value ) => Convert.ToBase64String( EncryptInteger( value ) ).Replace( '+', '-' ).Replace( '/', '_' );

public static Int64 DecryptIntegerFromString( String base64Url )
{
    if( String.IsNullOrWhiteSpace( base64Url ) ) throw new ArgumentException( message: "Invalid string.", paramName: nameof(base64Url) );

    // Convert Base64Url to Base64:
    String base64 = base64Url.Replace( '-', '+' ).Replace( '_', '/' );

    Byte[] block = Convert.FromBase64String( base64 );
    return DecryptInteger( block );
}
0 голосов
/ 18 июня 2020

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

ulong Next(ulong current)
{
    unchecked
    {
        return (999_999_937L * current + 383_565_383L) % 999_999_999L;
    }
};

Из памяти эта функция может генерировать последовательность из 999_999_999 цифр, если значения в функции выбраны правильно.

Мой тестовый код показывает, что этот метод может производить 500_499 чисел без повторения.

Мой компьютер может произвести всю последовательность чуть менее чем за 9 миллисекунд, так что это довольно быстрый алгоритм .

Первые десять элементов этой последовательности (с дополнением начальными нулями):

383565383, 602511613, 027845340, 657154301, 639998680, 703647183, 757439993, 422285770, 201847617, 869013116


5_960_464 * current + 383_565_383L дает длину последовательности 1_000_998 перед повторением.

...