单字符签名方案(最小安全性)

Question

注意:我最初将其发布到信息安全,但我开始认为它可能更相关,因为它确实是关于确定我应该如何处理请求而不是保护信息.

情况

系统A:

我有一个A向用户提供请求的系统.此服务器执行某些操作,然后将用户重定向到系统B.在该重定向期间,服务器A可以向用户提供32个字符的字母数字信息串以传递给系统B.需要31个字符的信息,但其中一个可用作校验和.此字符串可以或多或少地被视为请求ID.

系统B:

当系统B接收来自用户的请求时,它可以验证该请求(以及ID-等字符串)是有效的通过解析31个字符的字符串,查询数据库,再跟系统A.本系统可以绝对肯定验证请求有效并且没有被篡改,但它的计算成本非常高.

攻击者:

该系统可能会看到许多欺骗ID的尝试.这可以通过以后的检查进行过滤,因此我并不担心单个角色完全签署ID,但我确实希望避免花费更多资源来处理这些请求.

我需要的

我正在寻找一个校验和/签名方案,它可以用一个字符让我很好地了解请求是否应该继续进行验证过程,或者是否应该立即将其丢弃为无效.如果一条消息被丢弃,我需要100%确定它是无效的,但如果我保留无效的消息也没关系.我相信理想的解决方案意味着保留1/62无效请求(攻击者必须猜测检查字符),但作为最小解决方案,丢弃所有无效请求的一半就足够了.

我试过的

我看过使用卢恩算法(这是用于信用卡相同),但我想能够使用一键生成的字符,使其更难以攻击者欺骗校验.

作为创建签名方案的第一次尝试,我用一个31字节的密钥对31字节的id进行按位,对结果字节求和,转换为十进制并将数字加在一起直到它小于62,然后映射它到集合中的字符[a-bA-Z0-9](下面的伪代码).问题是虽然我很确定这不会丢弃任何有效的请求,但我不确定如何确定这将通过无效ID的频率,或者是否可以使用最终值检索密钥.

Set alphabet to (byte[]) "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
Set keystring to "aLaklj14sdLK87kxcvalskj7asfrq01";

Create empty byte[] key;
FOR each letter in keystring
  Push (index of letter in alphabet) to key;

Create empty byte[] step1;

FOR each (r, k) in (request, key)
  Push r XOR s to step1;

Set step2 to 0;
FOR each b in step1
  Add (int) b to step2;

WHILE step2 > 62
  Copy step2 to step3;
  Set step2 to 0;
  Convert step3 to String;
  Split step3 between characters;
  FOR each digit in step3
    Add (int) digit to step2;
END WHILE

RETURN alphabet[step2]

正式陈述

确定性散列函数,其中,给定私钥和31字节长的输入,在集合中产生输出{x | x ? ?, x < 62},其中猜测输出将比计算私钥更有效.(可变长度输入的加分点)

这最终将在NodeJS/JavaScript中实现,但实际上并不依赖于语言.

---

免责声明:如果这个问题过于含糊和理论化,我深表歉意.如果需要,请评论澄清.显然,我有办法解决这个问题,但在这种情况下,我正在寻找尽可能直接的解决方案.

Answer 1

如果您想要带有私钥的“确定性哈希函数”，那么我相信您可以使用 sha256 （或加密库中的任何其他哈希函数）并将密钥附加到输入：

sha256(input+key).toString('hex');

然后，取出哈希值的最后几位，将其从十六进制字符串转换为整数，将整数除以62，得到余数，根据余数确定字符。

这不会为每个字符提供完美的 1/62 分布概率（十六进制字符串应该对每个值有均匀分布，但不是除以 62 后的余数），但应该非常接近。