给定常规分块大小的强分块密码，是否可以创建具有小分块大小的强分块密码？

#1 楼

您正在寻找的东西可以使用现有的格式保留加密（FPE）方案来完成。通常，FPE方案将现有的强大算法（如AES）转换为可对任何大小的集合进行操作的分组密码。例如，FPE可以将15位整数加密为其他15位整数（例如，信用卡号，这是使用FPE的常见原因之一）。这些方案大多数都可以很容易地适应集合[0 ... 2 ^ 20），通常无需进行特殊更改。有关更多详细信息，请参见本文或Wikipedia文章。

我假设您知道任何20位分组密码都存在严重的固有弱点（例如，在CBC模式下使用它时发生冲突），并且有特定的原因需要20位排列。

#2 楼

对于这些参数，如果速度不成问题，则使用平衡的Feistel构造并在舍入函数中使用强密码来构建新密码是合理的。

经过足够的回合，可以除了一个细节外，在计算上与理想密码没有区别：获得的排列是偶数。当且仅当对手能够获得$ 2 ^ {20} -2 $个不同的明文/密文对时，这才是一个问题，因为这可以确定剩下的两个对。也可以通过将两个特定的密文交换成一半的密钥来解决，就像下面的伪代码示例一样。

parameters:
    B = 10                        // half the number of bits per block, see note
    N = 8                         // number of rounds, see note

key setup with a 128-bit key:
    derive the AES subkeys from the 128-bit key
    encipher the 128-bit constant zero with AES, and..
    set X to 0 or 1, according to some bit of the result

enciphering plaintext block P, assumed to be 2*B bits
    L := P>>B                      // extract left  B bits
    R := P & ((1<<B)-1)            // extract right B bits
    for I from 1 to N              // round loop
      encipher ((I<<B) | R) with AES, keep the B right bits H
      L := L ^ H
      exchange R and L
    C =  (R<<B) | L                // append the halves, with R on the left
    if C < 2                       // swap ciphertext 0 and 1 for half the keys
      C := C^X                     // here X is 0 or 1 as obtained in key setup
   output ciphertext block C

deciphering ciphertext block C, assumed to be 2*B bits
    if C < 2                       // swap ciphertext 0 and 1 for half the keys
      C := C^X                     // here X is 0 or 1 as obtained in key setup
    L := C>>B                      // extract left  B bits
    R := C & ((1<<B)-1)            // extract right B bits
    for I from N downto 1          // round loop
      encipher ((I<<B)|R) with AES, keep the B right bits H
      L := L ^ H
      exchange R and L
    P =  (R<<B) | L                // append the halves, with R on the left
    output plaintext block P

注意：Luby和Rackoff的经典结果可确保随着$ B $的增长，$ N = 4 $轮次渐近足以使密码可证明是安全的（或在对手无权解密时仅$ N = 3 $），通常是一个安全的假设）针对仅限于$ 2 ^ {（（2 \ cdot B）/ 4} $纯文本/密文对的对手。但是这里的$ B $很小，也许我们对获得的排列的均匀分布感兴趣。例如，在彩票中使用密码，根据票证号码分配奖励，并通过增加奖励逐步显示号码与奖励的对应关系；人们可以分析分配给较低奖励机票的内容，然后在剩下两三张时获得一些有关其可能分配的信息。在这种情况下，对于非常小的$ B $，尤其是$ B = 2 $，我们需要$ N> 3 $。很容易表明$ N = 4 $，$ B = 2 $是不足够的：{的选择不超过$ 2 ^ {N \ cdot B \ cdot 2 ^ B + 1} = 2 ^ {33} $ B-> B位的N个舍入函数，一个额外的位X}，这不是$ 2 \ cdot B $位的排列数目的倍数，即$（2B）！= 24 $，因此某些排列必然比其他人更有可能，并且在适度的努力下可以发现。同样也是最重要的是，必须允许舍入函数的非线性扩展（并且对于$ B = 1 $完全不扩展，必须将其排除在外）。尽管如此，对于$ B = 10 $，$ N = 8 $仍然是安全的一面，但是我缺乏证明。

注意：Feistel构造（以及Luby-Rackoff证明）假定具有独立的舍入函数。通过在AES输入中插入舍入数字，可以用单个AES密钥对此进行近似。类似地得出交换密文0和1的决定。小心将不相交的AES块范围用于这些$ N + 1 $用途，并且仅使用一小部分AES块空间。

#3 楼

Granboulan和我自己做了一个通用的构造，表明它可以“完美地”完成：如果您有一个可寻找的伪随机流（可以在CTR模式下使用常规的分组密码获得），那么您可以在任意大小$ N $的域上的伪随机置换，因此评估给定输入上的置换使用可忽略的内存，并在可搜索流中使用$ O（（\ log N）^ 3）$查找。 >
不幸的是，这需要评估一个超几何分布，这很麻烦。我们使用的原型完全遵循该分布，因此是“完美”的，但是隐含着高精度地摆弄浮点数，这很昂贵。一台基本的PC会使用该代码（未经彻底优化）每秒最多加密十二个值。

近似的解决方案，例如不平衡的Feistel网络（请参阅@Jack的答案），将为您提供一些对于大多数用途而言，“足够好”且有效。