密码学文本中级开发 C#

从密钥生成可变替换框

Bruno Tabbia

5.00/5 (3投票s)

2022年5月7日

GPL3

10分钟阅读

6530

142

从密钥创建替换框并在直接替换密码中使用它

引言

这是一个新算法……或者，至少我是这么认为的，因为我没有找到任何关于类似算法的参考资料。
它是一个加密算法。
当我说“加密”时，我的意思是仅凭此算法，您就可以隐藏一些东西，例如一条消息；
我并不是说这种加密很强。
恰恰相反：如果单独使用，这是一种相当弱的密码算法，
它太弱了，只能成功地隐藏您的8岁儿子（除非您是高斯家族成员）的消息；
但不要用它来隐藏您老板的东西。

那么……为什么呢？
正如我之前所说，如果单独使用，此算法是弱的。
它应该作为多个算法序列的一部分来使用，例如在AES/Rijdael算法中就是这样做的。
AES加密在概念上相当简单：它由四个简单的算法组成，这些算法在数据块上多次（轮）应用。
特别是，每一轮大致包含四个步骤：

字节替换（Sub-Bytes）
行移位
列混淆
与密钥异或

这些步骤重复一定次数。

这些步骤中的每一个，单独来看，都相当容易破解，但当它们一起多次应用时，它们会变得非常强大。
如果您对AES及其工作原理感兴趣，请参阅此处。

现在，本文的目的是描述一种新算法。
我不会解释如何将其与其他算法结合使用：那将是另一篇文章的目的。

提供的DLL是一个Notepad++插件，允许您测试当前算法。

背景

要完全理解此算法，您应该了解密码学基础知识；
还建议查看AES算法的“Sub-Bytes”步骤。
了解字节操作基础知识和哈希算法是什么也会有所帮助。
此外，为了测试此算法，我使用了我在CodeProject上发布的Notepad++插件。

算法描述

此算法执行替换，即：它将明文消息中的每个字节替换为另一个字节。

最简单的替换加密形式是由凯撒密码执行的。凯撒密码只是将字母替换为字母表中固定数量的位置后的字母，
因此，为了解密，您只需要知道所述的位置数。
它在2000多年前被使用（猜猜是谁？），到中世纪它就已经过时且易于破解。

另一方面，AES的Sub-Bytes使用一个“映射”（S-box）来执行替换（这比凯撒的方法复杂得多），
但该映射是固定的；它是算法描述的一部分，永不改变）。
这可能是因为有些映射比其他映射弱，所以选择固定映射时选择了“好”的映射。

当前提出的算法创建一个“映射”（S-box，如AES中所示），该映射根据密钥而变化（如凯撒密码中所示）。

S-box是如何创建的？

S-Box是一个简单的字节数组，有256个位置（每个字节值一个）；
此字节数组中的每个位置都填充有0到255之间的不同数字。
因此，字节数组中的每个位置都将包含一个唯一值（替换值）。
大致：密码被哈希，
然后在一个循环中（从0到255），它会为S-box的每个位置（256个位置）进行一次哈希。
在循环的每个步骤中，哈希的第一个字节将指向结果S-box中的位置，
而循环的索引将是该位置中包含的值。
详细描述将在下面的“使用代码”部分中给出。

S-Box是如何使用的？

与AES Sub-Bytes步骤中的方式完全相同
输入的每个字节都将被视为S-Box中的一个位置
并被所述位置S-Box的内容替换。
对于解密，S-box将被反转，然后以相同的方式使用。

Using the Code

解决方案包含两个项目
第一个项目“Encoders”与我关于Notepad++插件的文章中解释的完全相同（如前所述）；第二个项目“HashGenSboxEncoder”包含

实现“IEncoder”接口的高级类
包含此算法的Hash类
完成繁重工作的低级类

我们首先谈谈最有趣的部分：S-box的创建，这在CreateSboxFromHash方法（在Hash类中）中进行了详细说明；算法的核心就在这里。

List<byte> sbox = new List<byte>();
List<int> startValues = new List<int>(Enumerable.Range(0, 256));
...
while (sbox.Count <= 0xff) 
    {
    hval = HashUntilFind(hval, left);
    int pos;
    int i = 0;
    do
        {
        pos = hval[countStartZeroes + i] % startValues.Count;
        } while ((countStartZeroes + i++) < hval.Length && 
                  startValues[pos] == sbox.Count);

    if (startValues[pos] == sbox.Count)
        {
        pos = (pos + 1) % startValues.Count;
        }

    sbox.Add((byte)startValues[pos]);
    startValues.RemoveAt(pos);
    }

最初，有一个第一个空列表“sbox”，在过程结束时，它将包含结果S-Box。
使用一个while循环，逐个填充结果S-box的256个位置，每个循环一个。

在while循环内部

进行哈希
该哈希的第一个字节被添加到结果“sbox”列表中。

这听起来很容易，但如果以这种方式进行，很可能会出现重复值。

所以我们需要一种方法来防止这种情况：一个“startValues”列表用于此目的。
“startValues”列表填充了从0到255的所有值（Enumerable.Range(0, 256)）。
值从这个“startValues”列表中移除，每次循环一个，然后添加到结果“sbox”列表中。

三段论
由于“startValues”列表中的所有值都不同，
而且由于我们将使用这些值来填充结果“sbox”列表，
所以结果“sbox”列表中不会有重复项，

这就解决了重复值的问题。

因此，在while循环内部

进行哈希，
该哈希的第一个字节给出“startValues”中的位置“pos”，
“startValues”中位置“pos”处的字节被添加到结果“sbox”列表中，
位置“pos”从“startValues”列表中移除。

所以，每次循环，结果“sbox”列表将增加一个位置，而“startValues”列表将减少一个位置。

但是，如果“startValues”列表变小，那么它将小于256个元素长。
那么……看上面的循环解释的第二点，如果“该哈希的第一个字节”大于“startValues”列表长度会发生什么？
它将引发异常。不好。

这通过简单地将“该哈希的第一个字节”对“startValues”列表长度取模来解决（模运算在此处作为整数除法的余数执行，即“%”运算符）。
这就解决了当列表变小时在“startValues”列表中选择位置的问题。

那么有时，存在存储与“sbox”列表中位置相等的值的风险。
例如：sbox { 32, 187, 41, 19, 4, ...
在这种情况下，在位置4（数组从0开始）中，我们有值4，这很糟糕。
因为在执行替换时，我们会用4替换4。不好。
我们必须尽可能地阻止这种情况发生。

因此，我们将检查要添加到“sbox”中的值是否与值位置相同，
这由do{} while循环的第二次检查处理。

startValues[pos] == sbox.Count

所以，当我们发现一些上述不幸的值时，我们将获取哈希中的下一个值并重复检查。

如果我们非常不幸（这意味着我们哈希中的所有字节都具有相同的值，并且该值等于我们在sbox数组中的位置），那么获取startValues中的下一个值（这肯定与前一个值不同）。

现在，如果此时我们将“HashUntilFind”函数视为一个简单的Hash256函数，那么算法已经运行良好。

但是，在这一点上，我想让这个算法更难以计算，以便任何潜在的暴力攻击可能需要巨大的计算能力。
比特币挖矿已经解决了这个问题，通过连续哈希直到找到以给定数量的零开头的哈希。所以我尝试了同样的方法。
“HashUntilFind”函数通过在while循环中重复哈希，直到找到与给定字节数组的初始字节完全相同的哈希。这可能非常耗电。

因此，在创建S-Box期间，必须选择一个difficulty参数；该difficulty用于创建一个简单的数组（在代码中称为“left”），该数组只包含零，并且长度与“difficulty”相同。
值，因此，例如，通过设置difficulty = 3 -> 我们将获得一个等于 { 0, 0, 0 } 的“left”数组；
这意味着HashUntilFind 将继续其哈希操作，直到找到以三个零开头的哈希。

这也意味着，如果难度设置为零，那么“HashUntilFind”函数将执行为标准的Sha256哈希。

我尝试使用difficulty = 1，算法运行良好。
但是，从difficulty = 2开始，算法的计算已经开始非常缓慢。

我们现在进入高级部分：EncoderHashGenSbox类。

这个类继承自“Encoders”项目中定义的IEncoder，在这篇文章中有所解释。

这个类的实现展示了一种使用算法的方法，特别是使用字符串作为输入。

必须提供Encode和Decode方法，它们只需要一个输入文本和一个密码。

让我们看看Encoding方法中的代码

1)  byte[] bclear = ByteLogic.Conversions.ToByteArray(cleartext);
2)  byte[] sbox = GetSbox(pass, difficulty);
3)  byte[] bencoded = ApplySbox(bclear, sbox);
4)  string encodedtext = Convert.ToBase64String(bencoded);

第一行只是将string转换为byte数组，
第二行计算S-Box，
第三行将Sbox应用于输入，
第四行将结果byte数组转换为Base64编码文本。

应用Sbox非常简单：对于输入中的每个字节，将该字节作为S-Box中的位置进行搜索，并获取对应的值。该值将被写入输出中。

示例：输入字节 = { 14, 234, 02, 06, ...
因此，在输入中的零位置，我们有14。
在S-box的14位置进行搜索，并读取其中包含的字节（例如65）。
在输出中，在零位置，将是65。

解码时第2点和第3点相同，但它们之间有一个附加步骤，S-Box被反转。反转意味着创建一个新数组，其中旧数组中包含的值现在是位置，而旧位置现在是数组中的值。

S-Box和反向S-Box都长256个位置；以下示例显示了只有16个位置的两个S-Box（这些永远不会与当前算法一起使用：它们仅用于提供简单解释）

S-BOX

09	12	00	07
14	15	01	03
04	10	02	05
13	06	08	11

反向S-BOX

02	06	10	07
08	11	13	03
14	00	09	15
01	12	04	05

在S-Box中的位置00，我们有09；在反向S-Box中，在位置09我们有00。所有其他值都相同。

在ByteLogic.cs文件中实现的低级功能中，唯一值得一提的是执行两个字节数组之间相等性测试的函数，其中字节逐字节比较是在两个指针（每个比较的字节数组一个）的帮助下进行的，这两个指针同步地遍历整个数组长度。

历史

版本 1.0