Fractal Encryption

Question

I've heard that one can encrypt data using drawings of the Mandlebrot set, and that this encryption algorithm is quantum-safe (can't be broken with a quantum computer, unlike many commonly-used algorithms). I looked around on Google for more information but I've only come across some articles intended for a more non-technical audience. Does anyone have any sources on this that I could use to learn more about this fascinating subject?

Solution 1

Here's a general article outlining the process:

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

This is more in-depth, providing an algorithm and examples:

http://medwelljournals.com/fulltext/ajit/2007/567-575.pdf
(alternate URL): http://docsdrive.com/pdfs/medwelljournals/ajit/2007/567-575.pdf

There is some discussion of it on the sci.crypt group:

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

And here's a company in Japan that is offering code and samples (it looks like the package costs $50):

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

This was the result of a few minutes poking around, so your mileage may vary. The topic sounds interesting, though. Even if it isn't immediately practical, it's nice that there are researchers thinking of different approaches to the problem.

Solution 2

First, the reason that most of the write-ups on the internet seem so obtuse is that they all appear to be drawn from a handful of patent applications. Patent applications for new formulas & algorithms always tend appear to be hiding something, because they are. It's notoriously difficult to police unlicensed use of such things and the applicants try to straddle the line between patent protection and trade secret protection. The point here is that it doesn't necessarily mean that it's all BS.

Secondly, all Fractal mappings that I know of are, to some extent or another "lossy", because the mapings are not strictly 1 to 1. While this is a good reason to beleive that there is no effecient way to break the code, it also means that anything directly "encrypted" by a lossy fractal, can not be decrypted either, even with the key. Thus any kind of direct fractal hashing is not reversible.

Therefore, Fratcal Encryption cannot mean that the message itself is directly encrypted with the fractal. Rather, it must mean that the fractal is used as a "master key" to enable simultaneous generation of "local" or "sequential" keys that are then used to encrypt and decrypt the actual messages.

Before we go any further, let's review the basics of encryption:

Encryption Algorithm Principles

Lets say you have a series messages M(j) for j=1 to N that you want to be able to transmit securely to a Receiving party. You'll need a reversible encryption function E like so:

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

Where (k) is an encryption key and X(j) is the corresponding encrypted message. Then the message is transmitted to our receiver who has a complementary function E' to decipher the encrypted message:

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

However, AFAIK you cannot make both an E() and E'() function using Fractals. On the other hand, there are some functions, like XOR that are their own complements:

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

But XOR is also a weak encryption function and although it is perfectly secure for a single message, if we use it more than once with the same key (k), it becomes very easy to reverse-engineer (k), thus making XOR unsafe for single key encryption systems. This can be solved by using a different key every time:

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

and

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

This solves one problem, but introduces another, which is, how do we insure that both sender and receiver have the same set of keys? Transmitting the series of keys is no solution because that takes us back to the original problem of securely transmitting a series of messages.

Instead we want to generate a series of identical keys on both the sender and receiver independently. But we need to be able to generate a series of keys that are cryptographically secure in their own right. That is, even if an external observer knew all of the preceding keys, they still would not be able to predict the next key in the series with any accuracy. And because we will need a completely different series of keys every time (to make them unguessable) we actually need the Key series itself to be key-based.

The solution to this is to use a Master Key MK, and a different encryption function H, to generate the specific keys for each message:

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

and

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

This is where our Fractals come in, because as we can see above, the H function does not need a complementary function H'. So we can freely use a Fractal-based function with a master key to generate our series of local keys.

Example Implementation and Explanation

Below is a VB.NET class that demonstrates this approach, a naive implementation of 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

A complete Visual Studio Windows project and a Windows exe can be found at http://www.codeplex.com/FractalEncryptDemo

This class uses the Julia set based on the Quadratic recursion Z(i+1) = Z(i)^2 - C in the complex plane. The Master Key generated consists of 5 numbers, 4 Double precision floating-point values between 0 and 1, and 1 integer between 1 and 1,000,000,000. The first two double values define the real and imaginary parts of C in the equation above. The second two doubles define the real and imaginary parts of a seed value that is used to generate the starting Z's.

Both of these values are mapped (via modulus operations) into a small square area from (0.1, 0.1) to approximately (0.55, 0.55). This is done to try and insure that our fractal calculations do not overflow or underflow (though I am not certain that this is not still possible). Finally, the integer value serves as an offset for our sequence values (our "j" in the formulas above).

Message are encoded four ascii characters at a time. First the sequence number (j) is added to the sequence offset which is used along with the 4-byte offset into the the message as a complex number that is multipled by the complex Seed value and then remapped back into the active rectangle to get our starting Z value. Then the Julia set recursion (Z = Z^2 + C) is applied 16 times and the final result is again remapped back into the active rectangle.

This final complex value is then multiplied by 2^30, both real and imaginary parts are converted to integers and then the bottom 16 bits of each are used to provide the 32 bits (4 bytes) of the local key. This then is XOR'd against the corresponding 4 message bytes at the sender to encrypt it, or XOR'd against the encrypted text at the receiver to decrypt it.

Solution 3

I've heard of this approach. But it's much more of a toy than a real world algorithm:

You use a window of coordinates of the mandelbrot set as a "pad", xoring your input or something, and thus the coordinates of the window (and the spacing of your samples) become your "password". If you choose a very deep window within the set, you will need very many iterations to evaluate and it is, in theory, difficult to brute force this.

Watch out for large bands of solid numbers.. perhaps a run-length encoded mandlebrot.

I guess someone thinks this might be "quantum proof" because it's iterative, you can't count how many iterations it will take for a location on the mandlebrot set to converge without actually iterating. I dunno if that's true or not.

However, I don't think there's any advantage to doing this (besides calling it "fractal"), and there's tons of disadvantages and opportunities to create vulnerablities. You'd be much better off using a well studied public/private key encryption algorithm.

Solution 4

I would add that you may wish to take a look at Multivariate Public Key Crypto Systems (often abbreviated MVKP) which is another active area of interest in the realm of Quantum computing resistant cryptography.

Just because something is referenced in Star Trek does not make it the best choice ;)

View more solutions