algorithm - Cifrado fractal

encryption fractals

Question

He escuchado que uno puede cifrar datos usando dibujos del conjunto de Mandlebrot, y que este algoritmo de cifrado es seguro cuánticamente (no se puede romper con una computadora cuántica, a diferencia de muchos algoritmos de uso común). Busqué más información en Google, pero solo he encontrado algunos artículos destinados a una audiencia más no técnica. ¿Alguien tiene alguna fuente sobre esto que pueda usar para aprender más sobre este tema fascinante?

Answer 1

Ahora existe Code Project con C# afirma implementar Fractal Encryption .

El algoritmo de encriptación fractal utiliza el famoso fractal de Mandelbrot para convertir la clave de encriptación (proporcionada por el usuario) en una clave más larga que posteriormente está XORed con el texto sin formato (proporcionado por el usuario) que resulta en un texto encriptado. El algoritmo tal como se explica e implementa a continuación es nuevo, inventado por mí en un momento de creatividad (es decir, después del almuerzo, alrededor de las 14.30, con los ojos medio cerrados), y codificado durante la mañana siguiente: esto significa que podría ser por casualidad fuerte algoritmo de encriptación, PERO también podría ser lo opuesto (es decir, un algoritmo de encriptación), y por lo tanto no tiene garantía.

Por supuesto en los comentarios:

Si se usa fractal para generar una clave, pero la clave solo está en XOR. El mensaje está lejos de ser fuerte, citando wikipedia ( http://en.wikipedia.org/wiki/XOR_cipher ):

Answer 2

Aquí hay un artículo general que describe el proceso:

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

Esto es más profundo, proporcionando un algoritmo y ejemplos:

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

Hay una discusión al respecto en el grupo sci.crypt:

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

Y aquí hay una compañía en Japón que ofrece código y muestras (parece que el paquete cuesta $ 50):

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

Esto fue el resultado de unos pocos minutos dando vueltas, por lo que su kilometraje puede variar. El tema suena interesante, sin embargo. Incluso si no es práctico de inmediato, es bueno que haya investigadores que piensan en diferentes enfoques del problema.

Answer 3

El método de cifrado / descifrado más seguro que he escuchado es el que mi abuelo trabajó en la Fuerza Aérea de los Estados Unidos justo después de la Segunda Guerra Mundial. Es una variación del pad de una sola vez , conocido como ( SIGSALY ).

Preparación

Primero, detecte la radiación ambiental de fondo usando un contador geiger. Use una ubicación donde no haya grandes secciones de audio de silencio o reacción artificial de una fuente de radiación cercana. No estoy seguro de las estadísticas, pero era el equivalente a grabar el Fondo de Microondas Cósmico. La banda sonora resultante se graba simultáneamente en dos álbumes de vinilo (las teclas) y luego se etiqueta. Usted envía una copia al transmisor, la otra al receptor. No toma mucho tiempo ni esfuerzo producir grandes cantidades de pares de discos con grabaciones completamente aleatorias y, por lo tanto, únicas.

Implementación

Cuando llega el momento de transmitir un mensaje seguro, las dos estaciones acuerdan qué grabación etiquetada utilizar. Luego, el transmisor utiliza el ruido aleatorio como un portador, de manera que el receptor puede lograr silencio al cancelar el ruido cuando su copia de la clave está sincronizada con la clave de transmisión, la misma ubicación en la grabación y la misma velocidad de reproducción.

Resumen

Con este operador establecido, puede garantizar que nadie podrá descifrar el mensaje sin obtener el disco doble utilizado para cifrar el mensaje. Esto traduce la seguridad del mensaje de uno matemático a uno físico. Siempre que pueda asegurar los registros y usar solo cada par una vez, tendrá una seguridad perfecta.

Seguir

Dado que la grabación se realiza en forma analógica, ¿afecta la cantidad de qubits que una computadora cuántica necesitaría para interrumpir este tipo de mensaje?

Answer 4

En primer lugar, la razón por la que la mayoría de los artículos escritos en Internet parecen tan obtusos es que todos parecen haber sido extraídos de un puñado de solicitudes de patentes. Las solicitudes de patentes para nuevas fórmulas y algoritmos siempre tienden a ocultar algo, porque lo son. Es notoriamente difícil controlar el uso sin licencia de tales cosas y los solicitantes tratan de establecer una línea divisoria entre la protección de patentes y la protección de secretos comerciales. El punto aquí es que no significa necesariamente que todo sea BS.

En segundo lugar, todas las asignaciones de Fractal que conozco son, hasta cierto punto u otra "con pérdidas", porque las asignaciones no son estrictamente 1 a 1. Si bien esta es una buena razón para creer que no hay una manera eficiente de romper el código, También significa que cualquier cosa directamente "encriptada" por un fractal con pérdida, tampoco puede ser desencriptada, incluso con la clave. Por lo tanto, cualquier tipo de hashing fractal directo no es reversible.

Por lo tanto, Fratcal Encryption no puede significar que el mensaje en sí está directamente encriptado con el fractal. Más bien, debe significar que el fractal se usa como una "clave maestra" para permitir la generación simultánea de claves "locales" o "secuenciales" que luego se usan para cifrar y descifrar los mensajes reales.

Antes de continuar, revisemos los conceptos básicos del cifrado:

Principios del algoritmo de cifrado

Digamos que tiene una serie de mensajes M (j) para j = 1 a N que desea poder transmitir de forma segura a una parte receptora. Necesitarás una función de cifrado reversible E así:

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

Donde (k) es una clave de cifrado y X (j) es el mensaje cifrado correspondiente. Luego, el mensaje se transmite a nuestro receptor, que tiene una función complementaria E ''para descifrar el mensaje cifrado:

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

Sin embargo, AFAIK no puede hacer que las funciones E () y E ''() utilicen Fractales. Por otro lado, hay algunas funciones, como XOR, que son sus propios complementos:

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

Pero XOR también es una función de encriptación débil y, aunque es perfectamente seguro para un solo mensaje, si lo usamos más de una vez con la misma clave (k), resulta muy fácil realizar una ingeniería inversa (k), lo que hace que XOR sea inseguro. Para sistemas de cifrado de una sola clave. Esto se puede resolver utilizando una clave diferente cada vez:

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

y

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

Esto resuelve un problema, pero introduce otro, que es, ¿cómo nos aseguramos de que tanto el remitente como el receptor tengan el mismo conjunto de claves? Transmitir la serie de claves no es una solución porque nos remite al problema original de transmitir de manera segura una serie de mensajes.

En su lugar, queremos generar una serie de claves idénticas tanto en el remitente como en el receptor de forma independiente. Pero tenemos que ser capaces de generar una serie de claves que son criptográficamente seguras por derecho propio. Es decir, incluso si un observador externo conociera todas las claves anteriores, aún no sería capaz de predecir la siguiente clave de la serie con precisión. Y dado que necesitaremos una serie de claves completamente diferente cada vez (para que no se puedan adivinar), en realidad necesitamos que la propia serie de claves esté basada en claves.

La solución a esto es usar una clave maestra MK y una función de cifrado H diferente, para generar las claves específicas para cada mensaje:

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

y

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

Aquí es donde entran nuestros Fractales, porque como podemos ver arriba, la función H no necesita una función complementaria H ''. Por lo tanto, podemos utilizar libremente una función basada en Fractal con una clave maestra para generar nuestra serie de claves locales.

Ejemplo de Implementación y Explicación

A continuación se muestra una clase de VB.NET que demuestra este enfoque, una implementación ingenua de cifrado fractal:

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

Un proyecto completo de Visual Studio para Windows y un exe de Windows se pueden encontrar en http://www.codeplex.com/FractalEncryptDemo

Esta clase usa el conjunto de Julia basado en la recursión cuadrática Z (i + 1) = Z (i) ^ 2 - C en el plano complejo. La clave maestra generada consta de 5 números, 4 valores de punto flotante de precisión doble entre 0 y 1, y 1 entero entre 1 y 1,000,000,000. Los dos primeros valores dobles definen las partes reales e imaginarias de C en la ecuación anterior. Las dos segundas dobles definen las partes reales e imaginarias de un valor semilla que se utiliza para generar las Z iniciales.

Ambos valores se asignan (mediante operaciones de módulo) en un área cuadrada pequeña desde (0.1, 0.1) hasta aproximadamente (0.55, 0.55). Esto se hace para tratar de asegurar que nuestros cálculos fractales no se desborden o se desborden (aunque no estoy seguro de que esto todavía no sea posible). Finalmente, el valor entero sirve como un desplazamiento para nuestros valores de secuencia (nuestra "j" en las fórmulas anteriores).

Los mensajes se codifican cuatro caracteres ASCII a la vez. Primero se agrega el número de secuencia (j) al desplazamiento de secuencia que se usa junto con el desplazamiento de 4 bytes en el mensaje como un número complejo que se multiplica por el valor Semilla complejo y luego se vuelve a asignar al rectángulo activo para obtener nuestra A partir del valor z. Luego, la recursión del conjunto de Julia (Z = Z ^ 2 + C) se aplica 16 veces y el resultado final se vuelve a asignar nuevamente al rectángulo activo.

Este valor complejo final se multiplica por 2 ^ 30, tanto las partes reales como las imaginarias se convierten en números enteros y luego se utilizan los 16 bits inferiores de cada uno para proporcionar los 32 bits (4 bytes) de la clave local. Esto entonces es XOR''d contra los 4 bytes de mensaje correspondientes en el remitente para cifrarlo, o XOR''d contra el texto cifrado en el receptor para descifrarlo.

Answer 5

He oído hablar de este enfoque. Pero es mucho más un juguete que un algoritmo del mundo real:

Usas una ventana de coordenadas del conjunto de mandelbrot como un "pad", marcando tu entrada o algo así, y así las coordenadas de la ventana (y el espaciado de tus muestras) se convierten en tu "contraseña". Si elige una ventana muy profunda dentro del conjunto, necesitará muchas iteraciones para evaluar y es, en teoría, difícil forzar esto.

Tenga cuidado con las bandas grandes de números sólidos ... tal vez un mandlebrot codificado de longitud de ejecución.

Supongo que alguien piensa que esto podría ser una "prueba cuántica" porque es iterativo, no puede contar cuántas iteraciones tomará para que una ubicación en el conjunto de mandlebrot converja sin iterar realmente. No sé si eso es verdad o no.

Sin embargo, no creo que haya ninguna ventaja al hacer esto (además de llamarlo "fractal"), y hay un montón de desventajas y oportunidades para crear vulnerabilidades. Estaría mucho mejor usando un algoritmo de cifrado de clave pública / privada bien estudiado.

Answer 6

Me gustaría agregar que es posible que desee echar un vistazo a los sistemas de cifrado de clave pública multivariable (a menudo abreviado MVKP), que es otra área activa de interés en el ámbito de la criptografía resistente a la computación cuántica.

El hecho de que se haga referencia a algo en Star Trek no la convierte en la mejor opción;)

Answer 7

No hay un sistema de cifrado por ahí que sea "prueba de computadora cuántica", por no hablar de la prueba de computadora normal. Todo lo que está cambiando es la cantidad de tiempo que lleva romper el cifrado. Todavía no se ha probado que exista ninguna función para la cual no existan tales algoritmos inversos.

El único "cifrado irrompible" que tenemos hasta ahora está basado en un modelo cuántico, e incluso entonces todavía no tenemos lo que estás pensando cuando ves una computadora cuántica.

D-Wave Systems afirma haber producido un chip de computadora de 128 qubit, aunque esta afirmación aún no se ha verificado.

De Wikipedia

El primer procesador cuántico electrónico fue creado recientemente.