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?

Annettaannette

Is this the same as "fractal compression"? It sounds like a different thing, but it's not completely clear. en.wikipedia.org/wiki/Fractal_compression – Someplace

Somehow this triggers my BS detector. Do you have any links? – Eleusis

@Eleusis Second result for "fractal encryption" on Google: tinyurl.com/fractalencrypt . It's vaguely rude to make such an accusation without at least looking at the front page Google results (especially given that I explicitly referenced Google in my post). – Annettaannette

There are a couple of patents that come up when querying google for "patent encryption" e.g. US Patent #6782101 did you follow up on those ? – Frippery

Sounds like one for Schneier's DogHouse. – Yordan

@Annettaannette tinyurl.com/fractalencrypt - if the original question made by BS sense tingle, that link moves it to Defcon 1. That's one of the most BS heavy pieces of text I've seen. Maybe there's something legitimate behind this but based on that article I have my doubts. – Skit

This reminds me of the perfect compression scheme. It can compress any size input down to a single bit. Decompression was out-of-scope, not to mention impossible. If you only care about measuring compression efficiency what's the big deal? </sarcasm/> – Taylor

Answer 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.

Felicio

2nd and 4th links (the most interesting) are 404. And this is why we should not answer with links only (but I get this question would be hard enough to answer without copyright infringments...) – Etiology

Unless I'm missing something, when you expand the recurrence relations in the 2nd link, the "secret key" turns out to be the product of the two public keys, adjusted by a known power of the constant c, which is also public. – Sabbath

Answer 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.

Exostosis

Answer 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.

Springing

Answer 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 ;)

Gaberdine

Fun fact: real-life fractal encryption wasn't referenced in Star Trek. Instead, the invention of real-life fractal encryption was inspired by Star Trek: a NASA developer saw the Star Trek episode and after some thought, he realized that fractals could be used as a basis for encryption and wrote code that did it. – Annettaannette

Lattice based encryption is also thought to be quantum resistant. – Zobias

Answer 5

There isn't an encryption system out there that is "quantum computer proof", let alone normal computer proof. All you're changing is the amount of time it takes to break the encryption. It has not yet been proven that any function exists for which no such reverse algorithms exist.

The only "unbreakable encryption" we have so far is based on a quantum model, and even then we still really don't have what you're thinking of when you see quantum computer.

D-Wave Systems claims to have produced a 128 qubit computer chip, though this claim has yet to be verified.

From Wikipedia

The first electronic quantum processor was only recently created.

Regenerative

And quantum cryptography isn't exactly a form of encryption. – Severity

I was thinking along the lines of using it to make the key and going from there. – Regenerative

When I say "Quantum-proof" I mean not capable of being cracked in a reasonable amount of time by a reasonably strong computer. Say for example that I can encrypt something and it would take X computer and average of 100 years to crack it. I would be satisfied calling such an agorithm X-proof, since there isn't any reasonable way that any information I have could possibly be of any value in 100 years. – Annettaannette

It's also worth noting that I'm not looking into this for any security reasons, I'm looking out of curiosity. – Annettaannette

Reasonably strong? What like an end-user's computer? Anything that takes 100 years to crack now will only take a few minutes 5-10 years from now, if not sooner. – Regenerative

If Someone really has made a 128 qubit processor, it would be the most dramatic technological change in the history of the world. That would be the equivalent of 256x10^36 parallel processors. I am having a haed time imaganining anything that that could not compute. – Exostosis

Hopefully we can get things to last longer than a microsecond. The analogy used in the article about the first processor is pretty good: "Instead of having to go through each of the four numbers and try them for the right one, it tries all four at once and only the right one goes through." – Regenerative

@Exostosis not necessarily. Most, if not all, of quantum computers that exist today are really powerful for one specific task (and maybe a few related ones as well). Even if someone really has made a 128 qubit processor that is the equivalent of 256x10^36 parallel processors, it probably was designed for something like particle physics simulations or something else science stuff that I don't understand. It likely would not be that useful for breaking encryption. – Selfimmolation

Answer 6

There is Code Project now with C# claiming to implement Fractal Encryption.

The fractal encryption algorithm uses the famous Mandelbrot fractal to convert the encryption key (provided by the user) to a longer key that is subsequently XORed with the plain text (provided by the user) resulting in an encrypted text. The algorithm as explained and implemented herein below is new, invented by me in a moment of creativity (i.e. after lunch, around 14.30, with eyes half closed), and coded during the next morning: this means that it could by chance be a very strong encryption algorithm, BUT it could also be the opposite (i.e. an encrAption algorithm), and thus it comes with no warranty.

of course in the comments:

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):

Hewie

Found this topic by mistake. I am using fractal encryption privately to make automated data transfers. Basis: 3-dimensional fractal image generation. Method: produce an unpredictable infinitely modifiable matrix. Practical 2D example: a 32-bit image system: 2^32 for a simple 1024*1024 pixels image - result 2^52 variations per symbol combined with a key of 1MB (or larger). Complexity grows infinitely with 3D and larger Keys and multiple input images (matrixed). Keys do not have to be transmitted, just their pointers. Note that I will not provide code for this, just a basic clue to start with. – Natation

Answer 7

The most secure encryption/decryption method I've ever heard was one my grandfather worked on in the U.S. Airforce right after WWII. It is a variation of the one-time pad, known as (SIGSALY).

Preparation

First, detect the ambient background radiation using a geiger-counter. Use a location where there is no large audio sections of either silence or artificial reaction from a nearby radiation source. I'm not sure of the statistics of it but it was the equivalent of recording the Cosmic Microwave Background. The resulting soundtrack is simultaneously recorded onto twin vinyl albums (the keys) and then labeled. You send one copy to the transmitter, the other to the receiver. It does not take much time or effort to produce large quantities of disk pairs with completely random, and thus unique, recordings.

Implementation

When it comes time to transmit a secure message, the two stations agree upon which labeled recording to use. The random noise is then used like a carrier by the transmitter such that the receiver can achieve silence by canceling out the noise when their copy of the key is in sync with the transmitting key, same location in the recording and same playback speed.

Summary

With this carrier established, you can guarantee that nobody can decypher the message without obtaining the twin disk used to encrypt the message. This translates the security of the message from a mathematical one to a physical one. As long as you can secure the records and only use each pair a single time, you have perfect security.

Followup

Since the recording is done in analog, does it affect how many qubits would be needed by a quantum computer to break this type of message?

Taylor

It is not possible to measure the Cosmic Microwave Background (CMB) with a Geiger counter on the surface of the earth. The CMB is very low energy and is easily washed out by the earth-normal ambient radiation (made up primarily of solar radiation and radiation from radioactive elements in the ground/earth) nothing less than a Radio Telescope can detect it on earth. You may have been thinking of Cosmic Rays which are intermittent, random and very high-enery and thus can be picked up with a Geiger counter. – Exostosis

The rough analogy is to the static on a old-TV screen tuned to a non-existent broadcast channel. I heard somewhere that that type of TV static was related to the CMB. Even if the CMB is too weak to be used this way, the idea is to find a source of radiation to trigger the geiger-counter because of the truely random nature of radiation which allows generating one-time pads for perfect security. – Taylor