ТРОИЧНАЯ ЛОГИКА Исторически, логика развивалась как наука о суждениях, их истинности и алгоритмах словесного мышления. Изучались правила вывода новых истинных суждений из имеющихся, критики сомнительных суждений, построения доказательств, выдвижения гипотез, не точные методы логического вывода и искусства риторики и полемики. В классической логике высказываний каждому суждению приписывалось значение истинности, 1 = истина, 0 = ложь. Кроме суждений с известными значениями истинности рассматривались логические связки AND, OR, XOR, IMPLY, для построения сложных суждений из простых. Изучались около десяти законов логики - правил вывода истинных суждений из имеющихся истинных, записываемых в нотации с большой горизонтальной чертой. Демонстрации доказательств записывались в виде дерева логического вывода, листья которого соответствовали фактам, истинным суждениям, а корень дерева - окончательному выводу из фактов. Связям между вершинами дерева логического вывода соответствовали правила вывода, аналогично состояниям и действиям в графе состояний в искусственном интеллекте. В современной логике атомарным объектом является не суждение, а понятие. Суждение получается из понятий при помощи теоретико-множественных операций над объёмами понятий. Это даёт формальную модель суждения, нужную для программ искусственного интеллекта, как то говорящие чат-боты с алгоритмами логического вывода. Имея модели объёмов понятий и суждений и используя операции теории множеств, можно как устанавливать логическое следование между суждениями и понятиями, так и порождать новые суждения и понятия при помощи операций теории множеств. Поэтому, современная логика основывается на теории множеств и является логикой классов, где класс есть синонимом термина множество. Более примитивная математическая логика нашла приложение в схемотехнике и компьютерных науках. В этой логике значениями истинности являются 0 и 1, это известная всем программистам булева логика. Она используется и в построении выражения в компьютерных программах и в прототипировании цифровых схем по конечным автоматам в цифровой схемотехнике. Это одна из самых простых логик, из-за чего в ней не получить весомых логических результатов, так-же и и-за ошибки в модели логического следования. Например, в этой логике по воскресеньям истинно суждение "если сегодня понедельник, то сегодня вторник". То есть A влечёт не A и не выполняется закон исключённого третьего. Ошибочна не вся эта логика, а лишь модель импликации - логического следования одного суждения из другого. Однако, несмотря на этот логический дефект, булева логика получила всеобщее распространение и применение и с этим историческим недоумением приходится сосуществовать в мире схемотехники и программирования. Троичная логика обратимых программ расширяет булеву логику третьим значением истинности - неопределённостью между 0 и 1, что можно обозначить как целочисленный интервал [0;1], множеством двух значений {0;1} и просто третьей константой u, от слова undefined. Определения операций с участием третьего значения истинности строятся по принципу не противоречия действиям над двумя значениями истинности, ведь третье значение истинности состоит из первых двух. Итак, троичная логика обратимых программ просто расширяет булеву логику, двоичную логику, третьим значением истинности и переносит действия булевой логики на комбинации аргументов с третьим значением истинности [0;1]. Далее идут прямая и обратная троичные логики, нужные для прямого и обратного выполнения программ в обратимых вычислениях. Заметим, что возможно не единственное построение трёхзначной логики, таких логик может быть столько, сколько и их авторов. Это - вопросы формализации и построений, не противоречащих физике, математике или здравому смыслу. Краткий словарь логических терминов можно найти в брошюре автора по логике надобности, доступной для скачивания в конце страницы. ПРЯМАЯ ТРОИЧНАЯ АРИФМЕТИКА Прямая троичная логика оперирует с тремя значениями истинности: 0, 1, [0;1], где последнее значение истинности обозначает неопределённость, любое значение истинности. Как и в двоичной логике, логические связки, побитовые операции, задаются для всех возможных комбинаций аргументов и для них назначается результат действия. Это - табличное определение функции, где для каждой возможной пары аргументов задаётся результат функции. Прямая троичная арифметика используется при прямом выполнении обратимых программ, при выполнении программы сверху-вниз. Ниже приводится прямая троичная арифметика для базисных функций логики. NOT ~0 = 1 ~1 = 0 ~[0;1] = [0;1] AND 0 & 0 = 0 0 & [0;1] = 0 0 & 1 = 0 [0;1] & 0 = 0 [0;1] & [0;1] = [0;1] [0;1] & 1 = [0;1] 1 & 0 = 0 1 & [0;1] = [0;1] 1 & 1 = 1 OR 0 | 0 = 0 0 | [0;1] = [0;1] 0 | 1 = 1 [0;1] | 0 = [0;1] [0;1] | [0;1] = [0;1] [0;1] | 1 = 1 1 | 0 = 1 1 | [0;1] = 1 1 | 1 = 1 XOR 0 ^ 0 = 0 0 ^ [0;1] = [0;1] 0 ^ 1 = 1 [0;1] ^ 0 = [0;1] [0;1] ^ [0;1] = [0;1] [0;1] ^ 1 = [0;1] 1 ^ 0 = 1 1 ^ [0;1] = [0;1] 1 ^ 1 = 0 ОБРАТНАЯ ТРОИЧНАЯ АРИФМЕТИКА Обратная троичная арифметика используется при обратном выполнении программ, выполнении программ снизу-вверх. В двоичном коде для операции (x &= A) = B по результату двоичного оператора B и аргументу действия A надо восстановить предыдущее состояние переменной x. Такое восстановление делается на каждой инструкции обратимой программы при обратном выполнении. Далее приводится табличное задание базисных функций обратной троичной логики, нужное для обратного выполнении обратимых программ, и позволяющее восстановление предыдущих значений переменных при проходе снизу-вверх. NOT ~x = 0 x = 1 ~x = 1 x = 0 ~x = [0;1] x = [0;1] AND x & 0 = 0 x = [0;1] x & [0;1] = 0 x = 0 x & 1 = 0 x = 0 x & 0 = [0;1] x = [0;1] x & [0;1] = [0;1] x = [0;1] x & 1 = [0;1] x = [0;1] x & 0 = 1 x = [0;1] x & [0;1] = 1 x = 1 x & 1 = 1 x = 1 OR x | 0 = 0 x = 0 x | [0;1] = 0 x = 0 x | 1 = 0 x = [0;1] x | 0 = [0;1] x = [0;1] x | [0;1] = [0;1] x = [0;1] x | 1 = [0;1] x = [0;1] x | 0 = 1 x = 1 x | [0;1] = 1 x = 1 x | 1 = 1 x = [0;1] XOR x ^ 0 = 0 x = 0 x ^ [0;1] = 0 x = [0;1] x ^ 1 = 0 x = 1 x ^ 0 = [0;1] x = [0;1] x ^ [0;1] = [0;1] x = [0;1] x ^ 1 = [0;1] x = [0;1] x ^ 0 = 1 x = 1 x ^ [0;1] = 1 x = [0;1] x ^ 1 = 1 x = 0 ПРИМЕР СОКРАЩЕНИЯ ПЕРЕБОРА С ИСПОЛЬЗОВАНИЕМ ТРОИЧНОЙ ЛОГИКИ В этом примере будет показано, как сократить перебор ключа для получения нужного хэш-значения модифицированной хэш-функции Дженкинсона FAQ6. Эта хэш-функция была выбрана для примера из-за её простоты и немного модифицирована, а именно операция сложения ADD была заменена на операцию побитового исключающего или XOR, из-за того, что библиотека троичной логики пока не поддерживает суммирование. Эта модификация почти ничего не изменила в поведении хэш-функции, ведь и сложение ADD и XOR меняют 0 на 1 и 1 на 0 почти одинаковым образом, если не рассматривать бит переноса из предыдущего разряда при сложении. То есть качество примера после модификации хэш-функции осталось тем-же. Ниже следует код рассматриваемой хэш-функции на языке C#, написанный с использованием вызовов библиотеки троичной логики и обратимых вычислений Ternary Logic Library. Приведённый метод строит в памяти компьютера обратимый код хэш-функции вызовом метода Emulator.Compile(). В коде - четыре тридцати-двух битных слова ключа, по которым рассчитывается хэш-значение с использование вспомогательных переменных, то есть ключ имеет длину 128 битов. Code: public override void Code() { Name("FAQ6_modified"); SetInput("key0", new Mask(128u)); SetInput("key1", new Mask(129u)); SetInput("key2", new Mask(130u)); SetInput("key3", new Mask(131u)); MoveConst("hash", 0); for (int i = 0; i < 4; i++) { Move("KeyCopy" + i, "key" + i); Xor("KeyCopy" + i, "hash"); Move("store" + i, "hash"); Move("hash", "KeyCopy" + i); Copy("tmp"+i, "hash"); ShiftLeftConst("tmp"+i, 10); Xor("hash", "tmp"+i); Copy("tmp2"+i, "hash"); ShiftRightConst("tmp2"+i, 6); Xor("hash", "tmp2"+i); } Copy("tmp30", "hash"); ShiftLeftConst("tmp30", 3); Xor("hash", "tmp30"); Copy("tmp31", "hash"); ShiftRightConst("tmp31", 11); Xor("hash", "tmp31"); Copy("tmp32", "hash"); ShiftLeftConst("tmp32", 15); Xor("hash", "tmp32"); } Для сокращения перебора функция выполняется обратно, снизу - вверх. При обратном выполнении предыдущие состояние переменных рассчитываются, по текущим состояниям переменных, по правилам обратной троичной арифметики. Зная текущее состояние переменной, действие и аргумент действия, рассчитывается предыдущее состояние переменной. При этом часть битов получают определённые значения, а часть битов - неопределённые значения. Для обратного выполнения хэш-функции задаются хэш-значение и временные переменные на выходе функции и обратным выполнением восстанавливаются входы функции. Далее приводится код вызовов прямого и обратного выполнения модифицированной функции Дженкинсона. Code: static void Main(string[] args) { // создадим эмулятор с обратимым кодом Emulator emul = new Program(); emul.Compile(); // выведем обратимый код на экран Console.WriteLine(emul.Text); // выполним код прямо, сверху-вниз emul.RunStraight(); Console.WriteLine(emul.Variables); // установим известное хэш-значение на выходе emul.SetOutput("hash", new Mask(0xffffffff)); // установим значения вспомагательных переменных emul.SetVariables(new string[] { "tmp30", "tmp31", "tmp32" }, new Mask[] { new Mask(11111111u), new Mask(22222222u), new Mask(33333333u)}); emul.SetVariables(new string[] { "tmp0", "tmp20" }, new Mask[] { new Mask(0x00000000u), new Mask(0x00000000u) }); emul.SetVariables(new string[] { "tmp1", "tmp21" }, new Mask[] { new Mask(0x00000000u), new Mask(0x00000000u) }); emul.SetVariables(new string[] { "tmp2", "tmp22" }, new Mask[] { new Mask(0x00000000u), new Mask(0x00000000u) }); emul.SetVariables(new string[] { "tmp3", "tmp23" }, new Mask[] { new Mask(0x00000000u), new Mask(0x00000000u) }); emul.SetVariables(new string[] { "store0" }, new Mask[] { new Mask(0u) }); emul.SetVariables(new string[] { "store1" }, new Mask[] { new Mask(1u) }); emul.SetVariables(new string[] { "store2" }, new Mask[] { new Mask(2u) }); emul.SetVariables(new string[] { "store3" }, new Mask[] { new Mask(3u) }); // выполним программу обратно, снизу-вверх emul.RunBackStepByStep(); // распечатаем найденную маску битов ключа, сокращающую перебор Console.WriteLine(emul.Variables); Console.WriteLine("cracked successfully"); } Обратное выполнение хэш-функции, по заданному выходу - хэш-значению, рассчитывает вход - ключ хэш-функции. Ниже приводится результат такого обратного выполнения модифицированной хэш-функции Дженкинсона FAQ6, для установленного на выходе хэш-значения 0xffffffffu. VARIABLES: key0 = uuuuuuuuuu0000000000000000uuuuuu key1 = uuuuuuuuuu0000000000000000uuuuuu key2 = uuuuuuuuuu0000000000000000uuuuuu key3 = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu В полученной маске входа известны 48 битов, нулевые значения, их не надо перебирать, перебирая лишь неизвестные биты. Обратный логический вывод известных значений битов сократил перебор в 2^48 раз (два в степени сорок восемь раз), то есть упростил задачу перебора в 260 триллионов раз! Ниже приводятся обратимый код модифицированной хэш-функции Дженкинсона и трасса её обратного выполнения, отладочный вывод библиотеки Ternary Logic Library. Code: CODE: 0) FAQ6_modified: 1) hash <- 0 2) KeyCopy0 <- key0 3) KeyCopy0 ^= hash 4) store0 <- hash 5) hash <- KeyCopy0 6) tmp0 := hash 7) tmp0 <<= 10 8) hash ^= tmp0 9) tmp20 := hash 10) tmp20 >>= 6 11) hash ^= tmp20 12) KeyCopy1 <- key1 13) KeyCopy1 ^= hash 14) store1 <- hash 15) hash <- KeyCopy1 16) tmp1 := hash 17) tmp1 <<= 10 18) hash ^= tmp1 19) tmp21 := hash 20) tmp21 >>= 6 21) hash ^= tmp21 22) KeyCopy2 <- key2 23) KeyCopy2 ^= hash 24) store2 <- hash 25) hash <- KeyCopy2 26) tmp2 := hash 27) tmp2 <<= 10 28) hash ^= tmp2 29) tmp22 := hash 30) tmp22 >>= 6 31) hash ^= tmp22 32) KeyCopy3 <- key3 33) KeyCopy3 ^= hash 34) store3 <- hash 35) hash <- KeyCopy3 36) tmp3 := hash 37) tmp3 <<= 10 38) hash ^= tmp3 39) tmp23 := hash 40) tmp23 >>= 6 41) hash ^= tmp23 42) tmp30 := hash 43) tmp30 <<= 3 44) hash ^= tmp30 45) tmp31 := hash 46) tmp31 >>= 11 47) hash ^= tmp31 48) tmp32 := hash 49) tmp32 <<= 15 50) hash ^= tmp32 Running back... 50) hash ^= tmp32 hash = 11111110000000110101111110101010 49) tmp32 <<= 15 tmp32 = uuuuuuuuuuuuuuu00000001111111001 48) tmp32 := hash hash = uuuuuuuuuuuuuuuu0u0uuu111u1u10uu 47) hash ^= tmp31 hash = uuuuuuuuuuuuuuuu0u0uuu100u1u01uu 46) tmp31 >>= 11 tmp31 = 100110001010110001110uuuuuuuuuuu 45) tmp31 := hash hash = uuuuuuuuuuuuuuuu0uuuuuuuuuuuuuuu 44) hash ^= tmp30 hash = uuuuuuuuuuuuuuuu1uuuuuuuuuuuuuuu 43) tmp30 <<= 3 tmp30 = uuu00000000101010011000101011000 42) tmp30 := hash hash = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 41) hash ^= tmp23 hash = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 40) tmp23 >>= 6 tmp23 = 00000000000000000000000000uuuuuu 39) tmp23 := hash hash = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 38) hash ^= tmp3 hash = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 37) tmp3 <<= 10 tmp3 = uuuuuuuuuu0000000000000000000000 36) tmp3 := hash hash = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 35) hash <- KeyCopy3 KeyCopy3 = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 34) store3 <- hash hash = 00000000000000000000000000000011 33) KeyCopy3 ^= hash KeyCopy3 = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 32) KeyCopy3 <- key3 key3 = uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu 31) hash ^= tmp22 hash = 00000000000000000000000000000011 30) tmp22 >>= 6 tmp22 = 00000000000000000000000000uuuuuu 29) tmp22 := hash hash = 00000000000000000000000000uuuuuu 28) hash ^= tmp2 hash = 00000000000000000000000000uuuuuu 27) tmp2 <<= 10 tmp2 = uuuuuuuuuu0000000000000000000000 26) tmp2 := hash hash = uuuuuuuuuu0000000000000000uuuuuu 25) hash <- KeyCopy2 KeyCopy2 = uuuuuuuuuu0000000000000000uuuuuu 24) store2 <- hash hash = 00000000000000000000000000000010 23) KeyCopy2 ^= hash KeyCopy2 = uuuuuuuuuu0000000000000000uuuuuu 22) KeyCopy2 <- key2 key2 = uuuuuuuuuu0000000000000000uuuuuu 21) hash ^= tmp21 hash = 00000000000000000000000000000010 20) tmp21 >>= 6 tmp21 = 00000000000000000000000000uuuuuu 19) tmp21 := hash hash = 00000000000000000000000000uuuuuu 18) hash ^= tmp1 hash = 00000000000000000000000000uuuuuu 17) tmp1 <<= 10 tmp1 = uuuuuuuuuu0000000000000000000000 16) tmp1 := hash hash = uuuuuuuuuu0000000000000000uuuuuu 15) hash <- KeyCopy1 KeyCopy1 = uuuuuuuuuu0000000000000000uuuuuu 14) store1 <- hash hash = 00000000000000000000000000000001 13) KeyCopy1 ^= hash KeyCopy1 = uuuuuuuuuu0000000000000000uuuuuu 12) KeyCopy1 <- key1 key1 = uuuuuuuuuu0000000000000000uuuuuu 11) hash ^= tmp20 hash = 00000000000000000000000000000001 10) tmp20 >>= 6 tmp20 = 00000000000000000000000000uuuuuu 9) tmp20 := hash hash = 00000000000000000000000000uuuuuu 8) hash ^= tmp0 hash = 00000000000000000000000000uuuuuu 7) tmp0 <<= 10 tmp0 = uuuuuuuuuu0000000000000000000000 6) tmp0 := hash hash = uuuuuuuuuu0000000000000000uuuuuu 5) hash <- KeyCopy0 KeyCopy0 = uuuuuuuuuu0000000000000000uuuuuu 4) store0 <- hash hash = 00000000000000000000000000000000 3) KeyCopy0 ^= hash KeyCopy0 = uuuuuuuuuu0000000000000000uuuuuu 2) KeyCopy0 <- key0 key0 = uuuuuuuuuu0000000000000000uuuuuu 1) hash <- 0 0) FAQ6_modified: Итак, в этом не сложном примере показано, как обратное выполнение хэш-функции, в троичной логике, позволяет сократить множество перебираемых ключей в сотни триллионов раз. Обратное выполнение хэш-функции восстанавливает некоторые биты её входа, оставляя другие биты неопределёнными. Оригинальный сайт со статьёй
