分形加密

Question

我听说可以使用Mandlebrot集的图形来加密数据,并且这种加密算法是量子安全的(与许多常用算法不同,不能用量子计算机来破解).我在Google上查看了更多信息,但我只看到了一些针对更多非技术受众的文章.有没有人有这方面的资料,我可以用它来了解这个有趣的主题？

Answer 1

首先,互联网上的大多数文章看起来如此晦涩的原因是它们似乎都来自少数专利申请.新公式和算法的专利申请总是倾向于隐藏某些东西,因为它们是.众所周知,很难控制未经许可使用此类物品,申请人试图跨越专利保护和商业秘密保护之间的界线.这里的要点是它并不一定意味着它都是BS.

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

因此,Fratcal Encryption并不意味着消息本身是使用分形直接加密的.相反,它必须意味着分形被用作"主密钥",以便能够同时生成"本地"或"顺序"密钥,然后用于加密和解密实际消息.

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

加密算法原理

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

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

其中(k)是加密密钥,X(j)是相应的加密消息.然后将消息发送给我们的接收器,该接收器具有补充功能E'以解密加密消息:

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

但是,AFAIK使用Fractals不能同时使用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)

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

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

解决方案是使用主密钥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)

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

示例实现和说明

下面是一个演示这种方法的VB.NET类,它是Fractal Encryption的一个天真实现:

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之间.前两个双精度值定义了上述等式中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设置的坐标窗口作为"填充",输入您的输入或其他内容,因此窗口的坐标(以及样本的间距)将成为您的"密码".如果你在集合中选择一个非常深的窗口,你将需要很多迭代来进行评估,从理论上讲,它很难用力.

注意大量固体数字......也许是一个游程编码的mandlebrot.

我猜有人认为这可能是"量子证明",因为它是迭代的,你无法计算在没有实际迭代的情况下,mandlebrot集合上的位置需要多少次迭代才能收敛.如果那是真的,我不知道.

但是,我认为这样做没有任何好处(除了称之为"分形"),并且存在许多创造漏洞的缺点和机会.使用经过充分研究的公钥/私钥加密算法会好得多.