algorithm - 分形加密

Question

我听说可以使用 Mandlebrot 集的绘图来加密数据，并且这种加密算法是量子安全的（与许多常用算法不同，量子计算机无法破解）。我在 Google 上四处查看以获取更多信息，但我只看到了一些面向非技术受众的文章。有没有人有这方面的任何资料可以用来更多地了解这个迷人的主题？

Answer 1

首先，互联网上的大多数文章看起来如此迟钝的原因是它们似乎都来自少数专利申请。新公式和算法的专利申请似乎总是隐藏一些东西，因为它们是。众所周知，监管此类物品的未经许可使用非常困难，申请人试图跨越专利保护和商业秘密保护之间的界限。这里的重点是，这并不一定意味着这都是废话。

其次，我所知道的所有分形映射在某种程度上都是“有损”的，因为映射不是严格的 1 对 1。虽然这是一个很好的理由相信没有有效的方法来破解代码，但它也意味着任何被有损分形直接“加密”的东西也无法解密，即使使用密钥也是如此。因此，任何类型的直接分形散列都是不可逆的。

因此，分形加密不能意味着消息本身直接用分形加密。相反，它必须意味着分形被用作“主密钥”，以支持同时生成“本地”或“顺序”密钥，然后用于加密和解密实际消息。

在我们继续之前，让我们回顾一下加密的基础知识：

加密算法原理

假设您有一系列消息 M(j)，j=1 到 N，您希望能够安全地传输给接收方。您将需要一个可逆加密函数 E ，如下所示：

E(M(j), k) --> X(j)

其中 (k) 是加密密钥，X(j) 是相应的加密消息。然后消息被传输给我们的接收者，接收者具有互补函数 E' 来破译加密的消息：

E'(X(j), k) --> M(j)

但是，AFAIK 您不能使用分形同时创建 E() 和 E'() 函数。另一方面，有一些函数，比如 XOR 是它们自己的补充：

( M(j) XOR k ) --> X(j)  *and also* ( X(j) XOR k ) --> M(j)

但 XOR 也是一个弱加密功能，虽然它对于单个消息是完全安全的，但如果我们使用相同的密钥 (k) 多次使用它，很容易对 (k) 进行逆向工程，从而使 XOR 不安全用于单密钥加密系统。这可以通过每次使用不同的密钥来解决：

M(j) XOR K(j) --> X(j)

和

X(j) XOR K(j) --> M(j)

这解决了一个问题，但引入了另一个问题，即我们如何确保发送者和接收者拥有相同的密钥集？传输一系列密钥不是解决方案，因为这使我们回到了安全传输一系列消息的原始问题。

相反，我们希望在发送者和接收者上独立地生成一系列相同的密钥。但是我们需要能够生成一系列本身具有密码安全性的密钥。也就是说，即使外部观察者知道所有前面的键，他们仍然无法准确地预测系列中的下一个键。而且因为我们每次都需要一个完全不同的键系列（使它们不可猜测），我们实际上需要键系列本身是基于键的。

解决方案是使用主密钥 MK 和不同的加密函数 H，为每条消息生成特定密钥：

H(MK, j) --> K(j);  M(j) XOR K(j) --> X(j)

和

H(MK, j) --> K(j);  X(j) XOR K(j) --> M(j)

这就是我们分形的用武之地，因为正如我们在上面看到的，H 函数不需要互补函数 H'。所以我们可以自由地使用一个基于分形的函数和一个主密钥来生成我们的一系列本地密钥。

示例实现和解释

下面是一个演示这种方法的 VB.NET 类，它是分形加密的简单实现：

Option Explicit On

Public Class FractalEncrypt
'Fractal Encryption / Decryption demo class'
' 2009-08-08    RBarryYoung Created.'
' note: '
'   Property of R. Barry Young & Proactive Performance Solutions, Inc.,'
'   protected under open source license'
Public Const CrLower As Double = 0.1
Public Const CrUpper As Double = Math.PI / (2 * Math.E)
Public Const CiLower As Double = 0.1
Public Const CiUpper As Double = Math.PI / (2 * Math.E)

Public ReadOnly Cr As Double, Ci As Double, Sr As Double, Si As Double
Public ReadOnly BaseSeq As Integer

Public Sub New(ByVal KeyR As Double, ByVal KeyI As Double, ByVal SaltR As Double _
        , ByVal SaltI As Double, ByVal SeqStart As Integer)
    Cr = ((KeyR - CrLower) Mod (CrUpper - CrLower)) + CrLower
    Ci = ((KeyI - CiLower) Mod (CiUpper - CiLower)) + CiLower

    Sr = ((SaltR - CrLower) Mod (CrUpper - CrLower)) + CrLower
    Si = ((SaltI - CiLower) Mod (CiUpper - CiLower)) + CiLower

    BaseSeq = SeqStart
End Sub

Public Function Encrypt(ByVal Text As String, ByVal Seq As Integer) As String
    'Encrypt the string passed, adding on the sequence as a header.'
    Debug.Print("Encrypt<" & Seq & ">" & Len(Text) & ":" & Text)
    Dim CurSeq = BaseSeq + Seq
    'make the sequence prefix'
    Dim enc As String = Format(Seq, "000000000") & ":"

    Dim EncryptedOffset As Integer = 0
    Do While EncryptedOffset < Len(Text)
        'encrypt each 4 characters separately'
        enc = enc & Encrypt4(Text, EncryptedOffset, CurSeq)
        EncryptedOffset = EncryptedOffset + 4
    Loop

    Return enc
End Function

Public Function Decrypt(ByVal CrypText As String) As String
    'Decrypt the string passed, extracting the Sequence header first.'

    'Extract the sequence'
    Dim Seq As Integer = CInt(Left(CrypText, 9))
    Dim CurSeq = BaseSeq + Seq

    'Extract the encrypted message payload'
    CrypText = Mid(CrypText, 11)
    Debug.Print("Decrypt<" & Seq & ">" & Len(CrypText) & ":" & CrypText)

    'Now decrypt it 4 characters at a time'
    Dim txt As String = ""
    Dim EncryptedOffset As Integer = 0
    Do While EncryptedOffset < Len(CrypText)
        'encrypt each 4 characters separately'
        txt = txt & Encrypt4(CrypText, EncryptedOffset, CurSeq)
        EncryptedOffset = EncryptedOffset + 4
    Loop

    Return txt
End Function

Public Function Encrypt4(ByVal text As String, ByVal StrOffs As Integer _
        , ByVal CurSeq As Integer) As String
    'Encrypt/Decrypt 4 characters of the string.'
    ' (note: encrypt and decrypt are the same because XOR is its own complement)'
    Dim str As String = Mid(text, StrOffs + 1, 4)
    Dim enc As String

    'generate the seeds from the current message sequence and the current string offset'
    '1.   define complex Seq as (CurSeq, StrOffs)'
    Dim SeedR As Double = (Sr * CurSeq) - (Si * StrOffs)
    Dim SeedI As Double = (Sr * StrOffs) + (Si * CurSeq)
    '2.   remap the result back into the valid range'
    SeedR = SeedR Mod (CrUpper - CrLower)
    SeedI = SeedI Mod (CiUpper - CiLower)

    'generate the local keys from the master keys'
    Dim Zr As Double = SeedR, Zi As Double = SeedI
    Dim r As Double, i As Double, zx As Integer = 0, zy As Integer = 0
    '1.  apply the julia formula 16 times to hash it up good.'
    For j As Integer = 1 To 16
        'Z(n+1) = Z(n)^2 - C:'
        r = Zr * Zr - Zi * Zi - Cr
        i = 2 * Zr * Zi - Ci
        If Double.IsInfinity(r) Or Double.IsNaN(r) Then r = (zx \ zy) 'force an error'
        If Double.IsInfinity(i) Or Double.IsNaN(i) Then i = (zx \ zy) 'force an error'
        'put back into Z:'
        Zr = r : Zi = i
    Next
    '2.  remap the back into our results window'
    Zr = ((Zr - CrLower) Mod (CrUpper - CrLower)) + CrLower
    Zi = ((Zi - CiLower) Mod (CiUpper - CiLower)) + CiLower

    'Form the local keys into the Mask Keys variables (M).'
    Dim Mr As Integer, Mi As Integer
    '1.  scale them both into the range of about 2^30.'
    Mr = CInt((1024 * 1024 * 1024) * (Zr - CrLower) / (CrUpper - CrLower))
    Mi = CInt((1024 * 1024 * 1024) * (Zi - CiLower) / (CiUpper - CiLower))
    '2.  only use the lower 16 bits that are left:'
    Mr = Mr And 65535 : Mi = Mi And 65535

    'encode the current 4 characters as a 2 * 2-byte integer'
    Dim R2 As Integer, I2 As Integer
    If StrOffs + 1 <= Len(text) Then R2 = Asc(Mid(text, StrOffs + 1, 1))
    If StrOffs + 2 <= Len(text) Then R2 = R2 + 256 * Asc(Mid(text, StrOffs + 2, 1))
    If StrOffs + 3 <= Len(text) Then I2 = Asc(Mid(text, StrOffs + 3, 1))
    If StrOffs + 4 <= Len(text) Then I2 = I2 + 256 * Asc(Mid(text, StrOffs + 4, 1))

    'Encrypt (or Decrypt) the data by masking it with the local Keys'
    R2 = R2 Xor Mr
    I2 = I2 Xor Mi

    'recode them as ascii strings again:'
    enc = Chr(R2 And 255) & Chr(R2 \ 256) & Chr(I2 And 255) & Chr(I2 \ 256)

    Return enc
End Function
End Class

可以在http://www.codeplex.com/FractalEncryptDemo找到完整的 Visual Studio Windows 项目和 Windows exe

此类使用基于复平面中的二次递归 Z(i+1) = Z(i)^2 - C 的 Julia 集。生成的主密钥由 5 个数字、4 个 0 到 1 之间的双精度浮点值和 1 个 1 到 1,000,000,000 之间的整数组成。前两个 double 值定义了上述等式中 C 的实部和虚部。后两个双精度值定义用于生成起始 Z 的种子值的实部和虚部。

这两个值都被映射（通过模运算）到一个从 (0.1, 0.1) 到大约 (0.55, 0.55) 的小正方形区域。这样做是为了确保我们的分形计算不会溢出或下溢（尽管我不确定这仍然是不可能的）。最后，整数值作为我们的序列值的偏移量（我们在上面的公式中的“j”）。

消息一次编码四个 ascii 字符。首先将序列号 (j) 添加到序列偏移量中，该序列偏移量与 4 字节偏移量一起作为复数与复数种子值相乘，然后重新映射回活动矩形以获得我们的起始 Z 值。然后 Julia 集合递归 (Z = Z^2 + C) 应用 16 次，最终结果再次重新映射回活动矩形。

然后将这个最终的复数值乘以 2^30，将实部和虚部都转换为整数，然后每个的低 16 位用于提供本地密钥的 32 位（4 字节）。然后在发送方对相应的 4 个消息字节进行异或运算以对其进行加密，或者对接收方对加密文本进行异或运算以对其进行解密。

Answer 2

这是概述该过程的一般文章：

http://www.techbriefs.com/content/view/2579/32/

这个比较深入，提供算法和例子：

http://medwelljournals.com/fulltext/ajit/2007/567-575.pdf
（备用网址）：http ://docsdrive.com/pdfs/medwelljournals/ajit/2007/567-575.pdf

在 sci.crypt 组上有一些讨论：

http://groups.google.com/group/sci.crypt/browse_thread/thread/f7ce14c1f6c0df3f/559895f2f267644?hl=en&ie=UTF-8&q=mandelbrot+fractal+encryption+algorithm

这是日本的一家公司，它提供代码和样品（看起来包装价格为 50 美元）：

http://www.summersoftlabs.com/intro.htm

这是几分钟的结果，因此您的里程可能会有所不同。不过，这个话题听起来很有趣。即使它不是立即实用，也很高兴有研究人员考虑不同的方法来解决这个问题。

Answer 3

我听说过这种方法。但它更像是一个玩具，而不是现实世界的算法：

您将 mandelbrot 的坐标窗口设置为“pad”，对您的输入或其他东西进行异或运算，因此窗口的坐标（以及样本的间距）成为您的“密码”。如果您在集合中选择一个非常深的窗口，您将需要非常多的迭代来评估，并且理论上很难强制这样做。

注意大量的实心数字......也许是一个游程编码的 mandlebrot。

我猜有人认为这可能是“量子证明”，因为它是迭代的，您无法计算 mandlebrot 集上的某个位置在没有实际迭代的情况下收敛需要多少次迭代。我不知道这是不是真的。

但是，我认为这样做没有任何好处（除了称其为“分形”），而且有很多缺点和制造漏洞的机会。使用经过充分研究的公钥/私钥加密算法会更好。

Answer 4

我要补充一点，您可能希望查看多元公钥加密系统（通常缩写为 MVKP），这是抗量子计算密码学领域的另一个活跃领域。

仅仅因为《星际迷航》中引用了某些东西并不能使它成为最佳选择；）

Answer 5

那里没有“量子计算机证明”的加密系统，更不用说普通的计算机证明了。您所改变的只是破解加密所需的时间。尚未证明存在任何不存在此类反向算法的函数。

到目前为止，我们唯一的“牢不可破的加密”是基于量子模型的，即便如此，当你看到量子计算机时，我们仍然真的没有你所想的。

D-Wave Systems 声称已经生产了一个 128 量子位的计算机芯片，尽管这一说法尚未得到证实。

来自维基百科

第一个电子量子处理器是最近才创建的。

Answer 6

现在有 Code ProjectC#声称要实现Fractal Encryption。

分形加密算法使用著名的 Mandelbrot 分形将加密密钥（由用户提供）转换为更长的密钥，该密钥随后与纯文本（由用户提供）进行异或运算，从而得到加密文本。下面解释和实现的算法是新的，由我在创造性的时刻发明（即午餐后，大约 14.30，眼睛半闭），并在第二天早上编码：这意味着它可能是一个非常强大的加密算法，但它也可能是相反的（即 encrAption 算法），因此它没有任何保证。

当然在评论中：

If fractal is use to generate a key, but the key is just XORed with message the encryption is far from strong, quoting wikipedia (http://en.wikipedia.org/wiki/XOR_cipher):

Answer 7

我听过的最安全的加密/解密方法是我祖父在二战后在美国空军工作的一种方法。它是一次性垫的一种变体，称为 ( SIGSALY )。

准备

首先，使用盖革计数器检测环境背景辐射。使用没有来自附近辐射源的无声或人工反应的大型音频部分的位置。我不确定它的统计数据，但它相当于记录宇宙微波背景。生成的音轨同时录制到双黑胶唱片（键）上，然后进行标记。您将一份副本发送到发送器，另一份发送到接收器。生成大量具有完全随机且因此独特的记录的磁盘对并不需要太多时间或精力。

执行

当需要传输安全消息时，两个站点会就使用哪个标记记录达成一致。然后，发射器将随机噪声用作载体，这样当接收器的密钥副本与传输密钥同步、记录中的相同位置和相同的播放速度时，接收器可以通过消除噪声来实现静音。

概括

有了这个载体，你可以保证没有人可以在没有获得用于加密消息的双盘的情况下解密消息。这将消息的安全性从数学安全性转换为物理安全性。只要您可以保护记录并且只使用每对记录一次，您就拥有完美的安全性。

跟进

由于记录是以模拟方式完成的，它是否会影响量子计算机需要多少量子比特来破解这种类型的消息？