logo标签列表

分形加密

algorithmencryptionfractals
20

我听说可以使用Mandlebrot集的图形来加密数据，并且这种加密算法是量子安全的（与许多常用算法不同，无法被量子计算机破解）。我在谷歌上搜索了更多信息，但只找到了一些针对非技术人员的文章。有没有任何来源可以让我了解更多这个引人入胜的主题？

9
不知为何这触发了我的谎言检测器。你有任何链接吗？ - starblue
7
"fractal encryption"在Google的第二个搜索结果：http://tinyurl.com/fractalencrypt。在没有查看Google的首页搜索结果之前就这样指责是有点粗鲁的（尤其是我在帖子中明确提到了Google）。请注意，我只是翻译上述内容，不包括解释或其他内容。 - Imagist
3
听起来像是让Schneier's DogHouse来负责的事情。 - skaffman
3
@Imagist tinyurl.com/fractalencrypt - 如果原来的问题让BS sense tingle，这个链接将其转移到Defcon 1。这是我见过的最充满BS的文字之一。也许背后有一些合法的东西，但基于那篇文章，我对此表示怀疑。 - mattnewport
1
这让我想起了完美的压缩方案。它可以将任何大小的输入压缩到单个比特中。解压缩超出了范围，更不用说是不可能的。如果您只关心测量压缩效率，那有什么大不了的呢？</sarcasm/> - Kelly S. French
显示剩余2条评论
7个回答
23

首先，互联网上大多数关于此类主题的文章看起来很晦涩，原因是它们似乎都来源于少数专利申请。新公式和算法的专利申请总是让人感觉有所隐瞒，因为它们确实如此。对未经授权使用此类内容进行监督是极其困难的，申请人试图在专利保护和商业秘密保护之间寻找平衡。这里要说的是，这并不一定意味着所有内容都是胡扯。

其次，我所知道的所有分形映射都在一定程度上是“有损的”，因为这些映射不是严格的1对1。虽然这是相信没有有效的方法破解代码的好理由，但它也意味着任何直接通过有损分形“加密”的内容也不能被解密，即使使用正确的密钥也不行。因此，任何形式的直接分形哈希都是不可逆的。

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

在我们进一步讨论之前，让我们回顾一下加密的基础知识：

加密算法原理

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

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

其中(k)是加密密钥，X(j)是对应的加密消息。然后将消息传输给我们的接收器，该接收器具有一个补充函数E'，以解密加密的消息：

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

不过，据我所知，使用分形图形你无法同时创建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可执行文件。

该类基于具有复平面中Quadratic recursion Z（i+1）= Z（i）^ 2 - C的Julia集。生成的主密钥包含5个数字，4个双精度浮点值，范围在0到1之间，以及一个介于1和1,000,000,000之间的整数。前两个双精度值定义了上述方程中的C的实部和虚部。后两个双精度值定义了用于生成起始Z值的种子值的实部和虚部。

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

消息每次编码四个ASCII字符。首先，将序列号（j）加到序列偏移量上，然后使用4字节偏移量与消息一起作为复数乘以复杂的种子值，并重新映射回活动矩形以获取我们的起始Z值。然后应用16次Julia集递归（Z = Z ^ 2 + C），最终结果再次映射回活动矩形。

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

15

以下是一篇概述该过程的文章：

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

这是对该主题进行了几分钟的探索的结果，因此您的体验可能会有所不同。尽管这种方法并不立即实用，但很高兴看到研究人员正在考虑不同的解决问题的方法。

5
第二个和第四个链接（最有趣的）已经失效。这就是为什么我们不应该只回答链接的原因（但我知道这个问题很难回答，因为版权侵犯的问题）。 - Andrea Ligios
除非我漏掉了什么，否则当您在第二个链接中展开递归关系时，“秘密密钥”将是两个公钥的乘积，通过已知常数c的幂次调整，该常数也是公开的。 - BlueD
9

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

您使用曼德博集合的坐标窗口作为“填充”，对输入进行异或处理等操作，因此窗口的坐标（以及样本的间距）成为您的“密码”。如果您选择在集合中非常深的窗口，则需要非常多的迭代来评估，理论上很难通过暴力破解。

注意大量连续的数字...可能是运行长度编码的曼德博集合。

我猜有人认为这可能是“量子证明”的，因为它是迭代的，您无法计算出曼德博集合上某个位置收敛所需的迭代次数，而不实际进行迭代。我不知道这是否正确。

然而，我认为这样做没有任何优势（除了称之为“分形”），并且存在许多缺点和创造漏洞的机会。您最好使用经过充分研究的公钥/私钥加密算法。

4
我想补充一点，您可能希望查看多元公钥加密系统（通常缩写为MVKP），这是量子计算抗性密码学领域的另一个活跃领域。只是因为某些东西在星际迷航中被引用并不意味着它是最好的选择;)
18
有趣的事实：真实的分形加密并未在《星际迷航》中被提及。相反，真实的分形加密是受到《星际迷航》的启发而发明的：一个NASA开发者观看了《星际迷航》的某一集，思考后认识到分形可以用作加密基础，并编写了相应的代码。 - Imagist
基于格的加密也被认为是量子抗性的。 - Antimony
1
现在有一个名为Code Project的项目，声称使用C#实现分形加密。
分形加密算法使用著名的曼德博集合来将加密密钥（由用户提供）转换为更长的密钥，然后与明文（由用户提供）进行异或运算，从而得到加密文本。所述算法如下所述是新的，由我在创造性的一刻（即午餐后，大约14.30，眼睛半闭）中发明，并在第二天早上编写：这意味着它可能是一个非常强的加密算法，但也可能是相反的（即一个加密算法），因此不提供任何保证。
当然，在评论中：
如果使用分形来生成密钥，但密钥只是与消息进行异或运算，则加密远非强大，引用维基百科（http://en.wikipedia.org/wiki/XOR_cipher）：
无意中发现了这个话题。我正在私下使用分形加密进行自动数据传输。基础：三维分形图像生成。方法：产生一个不可预测的、可以无限修改的矩阵。实际的二维例子：一个32位图像系统：2^32对于一个简单的1024*1024像素的图像 - 结果是每个符号组合有2^52种变化，再加上1MB（或更大）的密钥。随着3D和更大的密钥以及多个输入图像（矩阵化），复杂度会无限增长。密钥不必传输，只需传输它们的指针。请注意，我不会提供代码，只提供一个基本的提示来开始。 - Overmind
1

目前还没有一种加密系统是“量子计算机证明”的，更不用说普通计算机了。你所改变的只是破解加密所需的时间。尚未证明存在任何函数，其逆算法不存在。

到目前为止，我们唯一拥有的“无法破解的加密”是基于量子模型的，即使这样，当你看到量子计算机时，我们仍然没有你想象中的那种东西。

D-Wave Systems声称已经生产出了一个128量子比特的计算机芯片，但这一声明尚未得到验证。

来自维基百科

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

1
量子密码学并不是一种加密形式。 - Gab Royer
当我说“量子安全”时，我的意思是指在合理的时间内无法被相对强大的计算机破解。例如，假设我可以加密某些内容，并且需要 X 台计算机平均 100 年才能破解它。那么我会满意地称这种算法为 X 安全，因为在 100 年内，我所拥有的任何信息都不可能具有任何价值。 - Imagist
值得注意的是，我研究这个并不是出于任何安全原因，而是出于好奇心。 - Imagist
1
相对强度如何？像终端用户的计算机一样吗？如果不是更快，那么现在需要100年才能破解的任何东西，5-10年后只需要几分钟就可以了。 - Sneakyness
1
如果真的有人制造了一台128量子比特处理器，那将是世界历史上最具戏剧性的技术变革。这相当于256x10^36个并行处理器。我很难想象有什么东西它无法计算。 - RBarryYoung
显示剩余3条评论
0

我听说过的最安全的加密/解密方法之一是我的祖父在二战后在美国空军工作时研发的，这是一次性密码本的变体，被称为SIGSALY。

准备

首先，使用盖革计数器检测周围的背景辐射。使用没有大量静音或人造反应的区域，以便避免附近放射源的干扰。虽然我不确定具体的统计数据，但相当于记录宇宙微波背景辐射。同时将结果录制成双黑胶唱片，即密钥，并进行标记。将其中一份复印件发送给发射机，另一份发送给接收机。生产大量具有完全随机、因此独特的录音的唱片对不需要太多时间或精力。

实施

当需要传输安全信息时，两个电台会就使用哪个标记的记录达成一致。随机噪声然后被发射器用于作为载波，以便接收器可以通过在其密钥副本与传输密钥处于同步状态、相同录音位置和相同播放速度时抵消噪声来实现静默。

摘要

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

跟进

由于记录是以模拟方式完成的，它是否会影响量子计算机需要多少个qubit才能破解此类消息呢？

无法使用地表的盖革计数器测量宇宙微波背景辐射（CMB）。CMB能量非常低，很容易被地球正常环境辐射所淹没（主要由太阳辐射和地下/地球中放射性元素的辐射组成），只有无线电望远镜才能在地球上探测到它。您可能在想宇宙射线，它们是间歇性、随机的，能量非常高，因此可以用盖革计数器检测到。 - RBarryYoung
1
大致的比喻是，好像在调谐到不存在的广播频道的旧电视屏幕上看到的静态。我听说过那种类型的电视静态与宇宙微波背景辐射有关。即使宇宙微波背景辐射太微弱而无法以此方式使用，想法是找到一种辐射源来触发盖革计数器，因为辐射的真正随机性允许生成用于完美安全的一次性密码本。 - Kelly S. French
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接