基于混沌的加密

• 下载源代码 - 172 KB

引言

密码学中的一个挑战是生成看似随机的数字序列，用于加密密钥。

您可能知道，计算机生成的任何“随机”数都不是真正随机的，它们被称为“伪随机”——这些数字来自给定“种子”数的递归求解数学方程。序列将与每个给定的种子值不同，如果您有一组数字并可以访问创建它们的算法，那么计算机很快就能确定使用的种子值。

现代对称加密系统使用长达 256 位（至少对我们普通人来说）的起始“密钥”，并将其与初始化向量（也长达 256 位）结合。通过一些复杂的数学运算将向量应用于密钥，可以创建数百万种独特的排列，这些排列与数据结合以混淆它。然后，此过程可以反向运行以检索原始信息（因此称为“对称”）。

这些数学加密系统的一个问题是，该过程是数学推导的，并且算法已发布。对于每种创建的加密算法，最终总会有人找到一种数学方法来破解它。即使是最新、最强大的 AES 算法，现在也被理论上破解了。

混沌理论可用于生成加密密钥的想法并非新颖，但到目前为止我还没有看到任何例子。

背景

混沌理论告诉我们，即使非常简单的规则也能导致极其复杂和不可预测的行为。滴水龙头的水滴散落每次都不会完全相同，尽管每一滴都与上一滴几乎完全相同。环境中微小的变化会对水中单个粒子的路径产生巨大影响。

然而，如果您能够将滴水的环境复制到量子级别，那么水滴飞溅的路径将是相同的。

事实上，关于滴水龙头混沌的著作有很多。

1970 年，约翰·康威 (John Conway) 对简化冯·诺依曼 (von Neumann) 的有限状态自动机（一种“生活”在二维笛卡尔网格上的假设性自复制机器）感兴趣，他提出了一套简单的规则，后来成为“生命游戏”。

生命游戏在一个网格上进行，网格被分成单元格。每个单元格可以“存活”或“死亡”，一组四条规则决定在每次迭代中任何给定的单元格将如何存活、死亡或诞生。

游戏简单的规则集催生了令人惊讶的复杂和引人入胜的行为，并围绕它涌现了一个名为“元胞自动机”的新研究领域。

在生命游戏的边界内，甚至可以构建整个世界，甚至是冯·诺依曼的自复制结构，我们自己的宇宙的简单规则集与生命游戏的规则集之间的平行关系一直是许多科学、哲学甚至宗教辩论的主题。

从这个领域可以得出的一点是，任何元胞自动机模拟，无论多么复杂，都完全由网格上细胞的初始状态决定。如果您以相同的方式排列初始细胞，经过一定代数后，结果将始终相同。

这引发了关于自由意志本质的有趣辩论——如果我们的宇宙被重置为完全相同的量子初始排列，它会变成这样吗？这说明了我们的选择什么？

抛开哲学不谈，这有一些有用的方面：从网格内的单一细胞配置，可以构建海量不可预测的复杂信息。经过一千代，谁能预测哪些细胞会活跃，而不实际知道初始状态并运行整个模拟？

如果初始配置中的一个细胞不同，经过足够多的代数后，每个细胞的状态最终都会不同。

在密码学中的应用

元胞自动机在密码学领域有用吗？尽管是确定性的，元胞自动机模拟的细胞所代表的信息不是通过可逆的、逻辑数学算法生成的；它是通过一种类似于现实生活的过程生成的。这实际上可能就是我们从计算机生成真正随机数据并能完全复制它的最接近的办法，前提是我们知道初始配置。

通过选择网格上的细胞排列、一组规则以及商定的代数数量，应该可以生成几乎无限的、不重复的、看似随机的数字序列，这些数字可能用于安全加密敏感数据。

初始细胞排列和代数数量将成为加密的“密钥”。

通过按行或按列展开网格，并将“存活”选择为真，“死亡”选择为假，可以将细胞网格变成一串二进制数字。

由于数据模式不重复，也不遵循逻辑数学进展，即使通常在密码学上较弱的独占或 (XOR) 操作来混淆数据的过程也变得更强大。

我打算通过开发一个使用元胞自动机生成密钥数据的安全加密系统，并使用简单的 XOR 来加密每一位来探索这一点。

设计软件

第一步显然是创建一个元胞自动机模拟。这是一个相当典型的编程问题，经常被设置为学生的编程任务。我过去曾自己写过一些有趣的程序；然而，这个程序需要稍有不同。

与该问题的典型解决方案（一对二维布尔数组，一个用于保存当前一代，另一个用于保存下一代的结果）不同，我想使用面向对象的 (OO) 设计理念来快速实现解决方案，并且数据易于以线性方式访问——不受数组维度的限制。

我最终选择将数据保存在一个单元格列表中。每个单元格对象将记住其网格位置、当前和待定状态，并与其邻居相连。

这不是一个特别快的解决方案，但它提供了灵活性，并且易于快速编程。比我聪明得多的人花了很多时间来研究 CA 算法的非常快速的实现；我不会尝试这项壮举。

我通过使用公共字段而不是属性获得了一些优化，并尽可能使“cell”类保持小巧。此外，按特定顺序生成单元格的行和列意味着可以轻松计算每个网格坐标的索引，从而允许通过索引和 x/y 坐标访问单元格。

/// <summary>
/// based on the order the grid is created, and the width and height of the
/// grid, calculate the index of a given grid-cell.
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
protected int getIndex(int x, int y)
{
    return (x * _height) + y;
}

一旦我创建了基本的单元格网格，我就添加了两组规则。康威的原始四条规则集，以及更简单的弗莱德金规则（它基于存活的邻近细胞数量是奇数还是偶数）。

我发现康威规则在此特定应用中存在的问题是，除非设置了一个非常特定的初始模式，否则它会在几代之内耗尽。大多数细胞死亡，少数细胞在相同的固定模式中来回振荡。

相比之下，简单的弗莱德金规则意味着在任何给定的迭代中大约有一半的细胞会存活，这有利于数据的良好统计分布，并且不会在有限的代数后消失或稳定。

弗莱德金规则

/// <summary>
/// run a generation of the CA grid using the Fredkin Rule.
/// </summary>
public void RunFredkinRule()
{
    // enumerate the cells:
    foreach (var cell in _cells)
    {
        if (cell.LivingNeighbours % 2 == 0)
            cell.NextState = false;
        else
            cell.NextState = true;
        }
        Commit();
}

康威规则

/// <summary>
/// run Conway's rules for the game of life.
/// </summary>
public void RunConwaysRule()
{
    // proces conways rules for game of life for each cell
    // enumerate the cells:
    foreach (var cell in _cells)
    {

        // count the cells neighbours:
        int neighbours = cell.LivingNeighbours;

        // a living cell with less than 2 living neighbours will die of loneliness
        if (cell.State && neighbours < 2)
            cell.NextState = false;

        // a living cell with 2 or 3 neighbours remains alive
        if (cell.State && (neighbours == 2 || neighbours == 3))
            cell.NextState = true;

        // a living cell with more than 3 neighbours dies of overcrowding.
        if (cell.State && neighbours > 3)
            cell.NextState = false;

        // an empty cell with exactly 3 neighbours becomes alive.
        if (!cell.State && neighbours == 3)
            cell.NextState = true;

    }

    // commit the changes
    Commit();
}

初始化网格

下一步是决定网格如何初始化。最终我提出了三种解决方案。

第一个是使用现有的位图图像。网格的宽度和高度被设置为与原始图像相同的尺寸，并且每个单元格的状态是从相应源像素的亮度设置的，通过一个称为误差扩散的过程（像素越暗，单元格成为活动状态的可能性越大，黑色像素有 100% 的几率，白色像素有 0% 的几率）。

下方：原始位图和使用误差扩散初始化的相应 CA 网格的视觉表示。

这个解决方案仍然让我很困扰，因为我想能够输入一个简单的种子或“密码”来生成网格的初始状态。

我通过编写“密码”到位图中来动态创建位图，然后使用现有的基于误差扩散的代码初始化网格。我给背景添加了一个渐变以增加复杂性。

这样，位图将是密码唯一的，并且我可以使用我的初始方法。

我提出的第三种初始化方法是使用 .NET 内置的伪随机数生成器，使用种子值作为“密钥”，随机地将每个单元格设置为“存活”或“死亡”。

虽然随机数生成器本身是一种非常不安全的生成密钥的方法，但我认为该过程的性质应该克服这一点，因为即使经过一代，原始序列也不会剩下任何东西。

/// <summary>
/// populates a grid from a pseudo-random number set.
/// </summary>
/// <param name="seed"></param>
/// <param name="width"></param>
/// <param name="height"></param>
public void BuildFromPseudoRandomNumbers(int seed, int width, int height)
{
    BuildGrid(width, height);
    Random rnd = new Random(seed);
    foreach (var cell in _cells)
    {
        if (rnd.NextDouble() > 0.5)
            cell.State = true;
    }
}

要从网格中检索二进制数据，只需枚举单元格并使用每个单元格的“状态”填充布尔数组。

/// <summary>
/// get len bits of binary cell data from the ca-grid.
/// </summary>
/// <param name="len"></param>
/// <returns></returns>
public bool[] GetBinaryCellData(int len)
{
    bool[] data = new bool[len];
    for (int i = 0; i < data.Length; i++)
    {
        data[i] = _cells[i].State;
    }
    return data;
}

使用 .NET BitArray 类将其转换为字节数组。

/// <summary>
/// get binary key data from the CA grid.
/// </summary>
/// <param name="bytes"></param>
/// <returns></returns>
public byte[] GetBytes(int bytes)
{
    // initialize a bit-array:
    BitArray ba = new BitArray(GetBinaryCellData(bytes * 8));

    // initialize the output array:
    byte[] buffer = new byte[bytes];

    // copy & return:
    ba.CopyTo(buffer, 0);

    return buffer;
}

使用单元格数据进行加密

我为此苦苦思索了一段时间。我不是密码学家，也不是数学家。我认为这样做的方法是将我要加密的信息的每一位与生成的单元格数据的每一位进行比较，利用两者之间的关系来得出第三位。

为了检索信息，这必须也能向后工作。

逻辑运算 XOR 似乎非常适合此目的，但我有一些疑虑——XOR 加密非常容易破解。

所以我做了一些研究，似乎 XOR 加密的问题在于，如果您可以猜测足够多的源数据（例如常见的文件的头部），或者如果源数据有很长的零序列，密钥的一部分可能会被泄露。

但这假设，泄露密钥的一部分将有助于计算密钥的其余部分。对于由传统的、算法化的伪随机数生成器生成的密钥数据，这绝对是真的：获得足够多的序列就可以反向追踪种子。

然而，对于评估元胞自动机衍生的密钥（不重复）的强度而言，XOR 实际上是完美的：如果加密无法被破解，鉴于如此简单的编码方法，那么这就很好地表明了将混沌理论应用于加密密钥生成是有效的。

生成大量密钥数据

从网格中检索的数据量取决于网格的大小。网格越大，计算所需的处理越多。

此外，.NET 列表对象的索引字段只有 24 位长。这限制了内容为 1670 万项。

每项只有 1 位，单个块的最大生成数据量为 2 MB，这有点受限。

然而，如果读取一个网格的内容，并再次处理 CA 规则，就可以从网格中读取一整块新数据。

因此，通过初始化一个生成例如 1KB 数据的小尺寸块，并反复迭代 CA 规则，就可以生成无限的数据集。

我担心这是否每次都会产生真正独特的数据，所以我通过此过程生成了 10MB 的数据（这花费了一些时间），并对其进行了 Die-Hard 统计测试。测试结果表明数据仍然是随机的，没有显著重复的数字集。

缺点

主要缺点似乎是生成密钥数据所需的处理量。与其他加密技术相比，此方法不能有效地加密大量数据。

使用更高效的算法来运行 CA 网格可以弥补一些不足，但无法达到例如 Rijndael 算法的性能。

Using the Code

该系统有两个主要组成部分

• CAGrid 类是元胞自动机模拟的简单实现。它包含一个 Cell 对象列表、构建网格并将每个单元格连接到其邻居的方法、运行规则和增加每个代的方法，以及以字节或布尔数组形式检索数据的方法。
• CAEncryption 类利用 CAGrid 来提供加密功能。

CAEncryption 类的静态方法用于生成大量密钥数据。它们使用从网格中提取数据然后重新运行模拟以提供更多数据的渐进方法。还提供了额外的静态方法用于对称地加密流和文件。

提供了一个可以序列化到磁盘的类，用于保存加密文件。它包含原始文件名作为属性，以便于解密数据。加密文件存储在该类的字节数组中。

所有静态加密方法都使用 Random 类来使用种子值初始化网格。

通过实例化 CAEncryption 类，实现了从位图生成加密密钥数据的方法。

所有这些都通过系统的主要窗体 FrmCellularEncryption 整合在一起。

证明概念

我发布这篇文章时有些犹豫，我预计很多人会自动声称整个概念本身就不安全，并且很容易被击败。

因此，我在此发出挑战，给那些唱反调的人一个机会，用真金白银证明他们。

我挑战任何读者恢复这段加密字符串的原始文本

W/frtrsDSreqBwK2N7bS14jUsUX88NgjHJEndWDd16YuHYjBoxy6goa6hS53
   jWI1zQCl1lE3DP5h8rEVeLvKHVJ0t5D/+Pz0lWQsS992KgBsVWEaMPZJBuIfUBMrqBKLOx5
   kXClqEJ5lpflfy9+NO31okIB4w6thbD77bwrSf0nxFW/tsRDxXv4uvAzdbqny009+CUVSaO
   ZAtsQc1NoLaymcsPGamzcH6NhdMuqnTfR1KqlJfIrYyyfjT/lXAOGOi2jdvW69wjbb8EdWBP+
   nm1tS6q7sC56RwKx+jQBGDRPJaUXGkj0OKt/o6DP28HVWL35oY9XPVn9QrksF0C3Huu6uw5k3
   b8FWeGfv6CLaCWYMg6GSgtADNOm+e8zKTOK6xOpmK8zwUV+P5DiAu0nylHn43BawqA2DhB/b
   hedkSNxfmUBXObJMl2AWXv3jagbmRA2qqLV7gDWlOE90SfoObHpPTk+irSTpW6ulOA==

您拥有执行加密的源代码（因此比在现实生活中获得的信息多得多）；如果您成功并发布原始文本，您将赢得我的尊重，并有权抱怨您想抱怨的一切。此外，在此过程中，我们可以证明或反驳使用元胞自动机加密敏感数据的可行性。