Фрактальное шифрование
Я слышал, что можно шифровать данные, используя рисунки набора Mandlebrot, и что этот алгоритм шифрования является квантовобезопасным (не может быть разбит на квантовый компьютер, в отличие от многих часто используемых алгоритмов). Я заглянул в Google за дополнительной информацией, но я столкнулся только с некоторыми статьями, предназначенными для более нетехнической аудитории. У кого-нибудь есть источники на этом, что я мог бы использовать, чтобы узнать больше об этом увлекательном предмете?
Ответы
Ответ 1
Вот общая статья, описывающая процесс:
http://www.techbriefs.com/content/view/2579/32/
Это более подробно, предоставляя алгоритм и примеры:
http://medwelljournals.com/fulltext/ajit/2007/567-575.pdf
(альтернативный URL): 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
Это было результатом нескольких минут сотрясания, поэтому ваш пробег может измениться. Тем не менее тема звучит интересно. Даже если это не сразу практично, приятно, что есть исследователи, которые думают о разных подходах к проблеме.
Ответ 2
Во-первых, причина, по которой большая часть рецензий в Интернете кажется настолько тупой, состоит в том, что все они выглядят из нескольких патентных заявок. Патентные заявки на новые формулы и алгоритмы всегда, кажется, скрывают что-то, потому что они есть. Это, как известно, трудно подписать нелицензионное использование таких вещей, и заявители пытаются преодолеть рубеж между патентной защитой и защитой коммерческой тайны. Дело здесь в том, что это не обязательно означает, что все BS.
Во-вторых, все фрактальные отображения, о которых я знаю, в той или иной степени "потеряны", потому что карты не являются строго 1 к 1. Хотя это хорошая причина, чтобы верить, что нет эффективного способа разбить кода, это также означает, что все, что непосредственно "зашифровано" фракталом с потерями, также не может быть расшифровано даже с помощью ключа. Таким образом, любое прямое фрактальное хеширование не обратимо.
Следовательно, Fratcal Encryption не может означать, что само сообщение напрямую зашифровывается фракталом. Скорее, это должно означать, что фрактал используется как "главный ключ", чтобы обеспечить одновременную генерацию "локальных" или "последовательных" ключей, которые затем используются для шифрования и дешифрования фактических сообщений.
Прежде чем идти дальше, давайте рассмотрим основы шифрования:
Принципы алгоритма шифрования
Допустим, у вас есть серийные сообщения M (j) для j = 1 - N, которые вы хотите надежно передать получающей стороне. Вам понадобится обратимая функция шифрования E так:
E(M(j), k) --> X(j)
Где (k) - ключ шифрования, а X (j) - соответствующее зашифрованное сообщение. Затем сообщение передается нашему получателю, у которого есть дополнительная функция E ', чтобы расшифровать зашифрованное сообщение:
E'(X(j), k) --> M(j)
Однако AFAIK вы не можете использовать функцию E() и E '(), используя Fractals. С другой стороны, есть некоторые функции, такие как 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, демонстрирующий этот подход, наивную реализацию 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
Полный проект Visual Studio Windows и Windows exe можно найти по адресу http://www.codeplex.com/FractalEncryptDemo
Этот класс использует набор Юлии, основанный на квадратичной рекурсии Z (i + 1) = Z (i) ^ 2 - C в комплексной плоскости. Сгенерированный мастер-ключ состоит из 5 чисел, 4 значений с плавающей запятой двойной точности между 0 и 1 и 1 целых чисел от 1 до 1 000 000 000. Первые два двойных значения определяют действительную и мнимую части C в приведенном выше уравнении. Вторые два двойника определяют действительную и мнимую части начального значения, которые используются для генерации стартовых Z.
Оба эти значения отображаются (через операции модуля) в небольшую квадратную область от (0,1, 0,1) до приблизительно (0,55, 0,55). Это делается для того, чтобы попытаться обеспечить, чтобы наши фрактальные вычисления не переполнялись или нисходили (хотя я не уверен, что это еще не возможно). Наконец, целочисленное значение служит смещением для наших значений последовательности (наш "j" в приведенных выше формулах).
Сообщение кодируется по четыре символа ascii за раз. Сначала порядковый номер (j) добавляется к смещению последовательности, которое используется вместе с 4-байтовым смещением в сообщении как комплексное число, которое умножается на комплексное значение Seed, а затем перенаправляется обратно в активный прямоугольник, чтобы получить наш начиная с значения Z. Тогда рекурсия набора Юлии (Z = Z ^ 2 + C) применяется 16 раз, а окончательный результат снова возвращается обратно в активный прямоугольник.
Это окончательное комплексное значение затем умножается на 2 ^ 30, и реальная, и мнимая части преобразуются в целые числа, а затем нижние 16 бит каждого используются для предоставления 32 бит (4 байта) локального ключа. Это тогда XOR'd против соответствующих 4 байтов сообщения у отправителя для его шифрования или XOR'd против зашифрованного текста в приемнике для его расшифровки.
Ответ 3
Я слышал об этом подходе. Но это гораздо больше игрушка, чем алгоритм реального мира:
Вы используете окно координат mandelbrot, установленное как "pad", xoring ваш вход или что-то еще, и, таким образом, координаты окна (и расстояния ваших образцов) становятся вашим "паролем". Если вы выберете очень глубокое окно внутри набора, вам понадобится очень много итераций для оценки, и теоретически это сложно переборщить.
Остерегайтесь больших диапазонов сплошных чисел.. возможно, закодированный закольцованный мандлброт.
Я думаю, кто-то думает, что это может быть "квантовое доказательство", потому что оно итеративно, вы не можете подсчитать, сколько итераций потребуется для того, чтобы местоположение на наборе mandlebrot сходилось без фактического итерации. Я не знаю, если это правда или нет.
Однако, я не думаю, что есть какое-то преимущество для этого (помимо того, что он называется "фрактал" ), и есть множество недостатков и возможностей для создания уязвимостей. Вам будет намного лучше использовать хорошо изученный алгоритм шифрования общедоступного/закрытого ключа.
Ответ 4
Я хотел бы добавить, что вы можете захотеть взглянуть на Многомерные Crypto Systems Key Public (часто сокращенно MVKP), который является еще активной областью интерес к области криптографии, устойчивой к квантовым вычислениям.
Просто потому что что-то ссылка в Star Trek не делает его лучшим выбором;)
Ответ 5
Там нет системы шифрования, которая является "доказательством квантового компьютера", не говоря уже о нормальном компьютерном доказательстве. Все, что вы меняете, - это время, необходимое для разрыва шифрования. До сих пор не доказано, что существует какая-либо функция, для которой не существует таких обратных алгоритмов.
Единственное "нерушимое шифрование", которое мы имеем до сих пор, основано на квантовой модели, и даже тогда у нас по-прежнему нет того, о чем вы думаете, когда видите квантовый компьютер.
D-Wave Systems заявляет, что выпустила 128-битный компьютерный чип, хотя это требование еще не подтверждено.
От Wikipedia
Первый электронный квантовый процессор был только недавно создан.
Ответ 6
Самый безопасный метод шифрования/дешифрования, который я когда-либо слышал, был моим дедом, который работал в ВВС США сразу после Второй мировой войны. Это вариация одноразовая панель, известная как (SIGSALY).
Подготовка
Сначала определите фоновое фоновое излучение с помощью счетчика Гейгера. Используйте место, где нет больших звуковых секций тишины или искусственной реакции от ближайшего источника излучения. Я не уверен в статистике, но это было эквивалентно записи Космического микроволнового фона. Результирующий саундтрек одновременно записывается на двойные виниловые альбомы (клавиши), а затем помечен. Вы отправляете одну копию в передатчик, а другую - в приемник. Не требуется много времени или усилий для создания большого количества пар дисков с абсолютно случайными и, следовательно, уникальными записями.
Реализация
Когда приходит время для передачи защищенного сообщения, обе станции согласны с тем, какая маркированная запись используется. Случайный шум затем используется как несущая передатчиком, так что приемник может добиться молчания, отменив шум, когда их копия ключа синхронизируется с передающей клавишей, тем же самым местом в записи и той же скоростью воспроизведения.
Резюме
С установленным носителем вы можете гарантировать, что никто не сможет дешифровать сообщение, не получив двойной диск, используемый для шифрования сообщения. Это переводит безопасность сообщения от математического к физическому. Пока вы можете защитить записи и использовать каждую пару только один раз, у вас есть отличная безопасность.
Followup
Поскольку запись выполняется в аналоговом режиме, влияет ли это на то, сколько квантов потребуется квантовому компьютеру для разрыва этого типа сообщения?
Ответ 7
Теперь есть проект кода с C#
, требующим реализовать Фрактальное шифрование.
Алгоритм фрактального шифрования использует знаменитый фрактал Мандельброта для преобразования ключа шифрования (предоставленного пользователем) в более длинный ключ, который впоследствии XORed с открытым текстом (предоставленный пользователем), в результате чего получается зашифрованный текст. Алгоритм, описанный и приведенный ниже, является новым, изобретенным мной в момент творчества (то есть после обеда, около 14.30, с закрытыми глазами) и закодирован на следующее утро: это означает, что он может случайно сильный алгоритм шифрования, но он также может быть противоположным (т.е. алгоритм encrAption), и, следовательно, он не имеет никаких гарантий.
конечно, в комментариях:
Если фрактал используется для генерации ключа, но ключ только XORed с сообщением, шифрование далека от сильного, цитируя wikipedia (http://en.wikipedia.org/wiki/XOR_cipher):