c# - 通过算法从用户 ID 生成唯一的随机好友代码

Question

我正在寻找一种从顺序用户 ID 为用户生成随机、唯一的 9 位 friend 代码的方法。这背后的想法是，人们无法通过逐个搜索 friend 代码来枚举用户。如果有 1000 个可能的代码和 100 个注册用户，搜索随机代码应该有 10% 的机会找到用户。

一种可能的方法是随机生成一个代码，检查该代码是否已经在使用，如果是，再试一次。我正在寻找一种方法(主要是出于好奇)，其中 friend 代码是通过算法生成的，并且保证对于该用户 ID 第一次尝试是唯一的。

具体来说，给定一个数字范围(1 到 999,999,999)，对这个数字运行函数应该返回同一范围内的另一个数字，该数字与输入数字成对且唯一。只有当范围发生变化和/或随机性的输入种子发生变化时，这种配对才会有所不同。

理想情况下，个人应该无法在不知道种子和算法(或拥有非常大的样本池和大量时间 - 这不需要加密安全)的情况下轻松地从 friend ID 逆向工程用户 ID，所以简单地从最大范围中减去用户 ID 不是一个有效的解决方案。

下面是一些 c# 代码，它通过生成整个数字范围、打乱列表、然后通过将用户 ID 视为列表索引来检索 friend ID 来完成我所追求的目标:

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
不幸的是，这不适合大范围 - 该程序需要 8GB 的​​ RAM 才能运行，使用 10 或 12 位 friend 代码在内存或数据库中预先生成列表是不可行的。我正在寻找不需要此预生成步骤的解决方案。

如果可能的话，我对使用种子随机数生成器或按位技巧来实现此目的的解决方案感兴趣。上面的函数是可逆的(通过搜索列表的值)，但解决方案不需要。

Answer 1

快速数学课!

您正在考虑开发一种将一个整数值(原始“ secret ”UserId 值)映射到另一个((加密的)“公共(public)”值)并再次返回的方法。这正是 block 密码所做的(除了每个“ block ”通常为 16 个字节而不是单个字符或整数值)。所以换句话说，你想创建自己的密码系统。

(请注意，即使您正在考虑将 UserId 123 转换为 string 而不是整数，例如 YouTube 视频 ID，如 "dQw4w9WgXcQ" ) - 它仍然是整数:因为存储在计算机中的每个标量值，包括字符串，可以表示为整数 - hence the "illegal primes" problem back in the late-1990s )。

最大的，most important take-away from any undergraduate-level computer-science class on cryptography is never create your own cryptosystem !.

有了这个...

如果安全不是最重要的问题...

...并且您只关心防止披露递增的整数 Id 值(例如，让您的访问者和用户看不到您真正拥有多少数据库记录)然后使用 Hashids 库:https://hashids.org/

对于 .NET，使用此 NuGet 包:https://www.nuget.org/packages/Hashids.net/

.NET 概述:https://hashids.org/net/

项目页面:https://github.com/ullmark/hashids.net

在您的代码中，构造一个 Hashids对象(我会使用公共(public) static readonly 字段或属性 - 或者更好的是:单例可注入(inject)服务)并使用 .Encode转换任意整数的方法 int/ Int32值转换为 string值(value)。

转换 string值回到原来的 int/ Int32 , 使用 .Decode方法。

顺便说一句，当散列是单向函数时，我不喜欢库被称为“Hashids”的方式——因为这些值仍然是可逆的——尽管使用了一个 secret 的“salt”值(为什么不是称为“ key ”？)它不是真正的哈希，imo。

如果安全真的很重要...

然后，您需要将每个整数值视为分组密码中的一个离散 block (不是流密码，因为每个值都需要自己独立加密和解密)。

出于实用的目的，您需要使用 对称分组密码 具有小块大小。不幸的是，许多具有小块大小的 block 密码不是很好(TripleDES 的 block 大小为 64 位 - 但今天它很弱)，所以让我们坚持使用 AES。

AES 的 block 大小为 128 位(16 字节) - 这与两个 Int64 相同相互连接的整数。假设您使用 base64url对 16 字节的值进行编码，那么您的输出将是 22 个字符长(因为 Base64 每个字符使用 6 位)。如果您对这种长度的字符串感到满意，那么您就一切就绪。 The shortest URL-safe string you can generate from a 128-bit value is 21 (hardly an improvement at all)因为 Base-73 是您可以安全地在所有现代 URL 传输系统中使用的 URL 中最安全的(在处理纯文本时，永远不要自动假设任何地方都支持 Unicode)。

可以调整 AES 以生成更小的输出 block 大小，但在这种情况下它不起作用 because using techniques like CTR Mode mean that the generated output needs to include extra state information (IV, counter, etc) which will end-up taking up the same amount of space as was gained .

这是代码:

非常重要的注意事项 :

这使用 CBC 模式 - 这意味着相同的输入导致相同的输出(这是设计所要求的!)。 CBC 在独立加密 block 时很有用。

这会重复使用相同的 IV - 这是此应用程序有意且实际需要的 - but generally speaking do not reuse IVs when using AES for any other purpose and make sure you understand what you're doing .

*

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 );
}