![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapovСегодняшняя байка - про конкретное использование абстрактной машины Тьюринга.
Сегодня случайно попалась на глаза старая шутка с bash.org.ru:
На этой почве у меняразвилась возникло несколько ассоциаций, которыми я хочу поделиться.
В цикле книг "Про Дракона" Павла Шумила в одной из побочных сюжетных линий был описан некий космический артефакт - гигантский компьютер размером с небольшую солнечную систему. Возраст компьютера насчитывал несколько миллионов лет, физические масштабы поражали воображение, его долго исследовали, но несмотря на все усилия, никому так и не удавалось понять, что же именно он считает и для чего/кого.
По ходу пьесы выяснилось, что этот компьютер - творение рук ... одного из исследователей, который пытался взломать перебором пароль на компьютере своего коллеги, чтобы сунуть нос в результаты его исследований. Проблема была в том, что коллега был параноик, и вел свою работу внутри виртуальной машины, запущенной на своем компьютере, что сильно усложняло атаку перебором. В результате, когда первый исследователь случайно получил доступ к технологии перемещения во времени, он забросил в прошлое компьютер, который мог модифицировать и развивать самого себя. и занимался исключительно творческим взломом и подбором паролей к виртуальной машине второго исследователя. Правда, второй исследователь к этому времени уже что-то начал подозревать, и подсунул первому бэкап-копию якобы своего компьютера, которая на самом деле содержала в себе "матрешку" из десятка запущенных друг в друге виртуальных машин, последняя из которых содержала те самые ценные сведения ...
Заброшенный в прошлое компьютер за пару миллионов лет "замодернизировал" себя до неузнаваемости, но "матрешку" из виртуальных машин так и не разобрал и пароль так и не подобрал ... Зато стал объектом исследования незадачливой парочки :)
Да, к чему это я?
Когда я был курсе на втором-третьем, нам читали курс лекций по теории вычислений, на котором, помимо прочего, познакомили нас с разнообразными машинами Тьюринга. Если кто не знает, машина Тьюринга - это такая асбтрактная модель компьютера (состоящая из ленты в клеточку, карандаша, резинки и набора правил), на которой удобно исследовать вычисления и строить доказательства о свойствах процесса вычисления.
Так вот, уже на этом достаточно абстрактном уровне можно заниматься виртуализацией: можно построить универсальную машину Тьюринга, которой на вход будет подаваться программа для обычной машины Тьюринга и исходные данные, после чего универсальная М.Т. проэмулирует работу обычной М.Т. с не более чем квадратичным замедлением и выдаст результат.
Поскольку универсальная машина Тьюринга на базовом уровне является разновидностью обычной машины Тьюринга, для нее в свою очередь можно построить соотвествующую универсальную машину Тьюринга, и так далее, и тому подобное.
А тут как раз в FIDO-шной эхоконференции RU.PERL зашел разговор о том, что на Perl-е, конечно, можно написать код любой степени нечитаемости, но за счет отладчика и отладочной печати любой такой можно распутать и в конце-концов понять.
Прикола ради я написал на perl-е реализацию универсальной машины Тьюринга, которой на вход давалась программа для другой универсальной машины Тьюринга, которой на вход давалась программа для обычной машины Тьюринга, которой на вход давалось побитовое представление ASCII-строки, и эта последняя машина проверяла какое-то свойство этого бинарного представления - типа, что кол-во единиц в бинарном представлении больше кол-ва нулей в два раза, или что-то в этом роде. За счет двух (трех?) уровней эмуляции подобная проверка делалась примерно секунд 10.
Написал, и закинул в RU.PERL. Без описания того, что делает программа, но с примером строки, которая проходит подобную проверку. И предложил найти еще одну подобную строку. Если мне не изменяет мой склероз, то желающие были, но положительного результата они так и не достигли :)
Мораль: никогда не знаешь, когда тебе придется применить на практике знания, которые в институте кажутся оторванными от реальности и никому не нужными.
PS
Just for fun, та самая программа на perl-е (найденная внутри devel.zip, который был внутри old_computer.zip, который был внутри backup_to_sort_later.tgz, который бы в old_notebook.tar.bz2 :)
Сегодня случайно попалась на глаза старая шутка с bash.org.ru:
mordaha: Картинка: http://mordaha.com/sc2l.jpg
Это старкон2, запущенный в DosBox, под иксами в Дебиане, который запущен в VMWare, которая в WinXP
Куда мне вопрос о неработающем звуке задавать? :)))))
gregory_777: Санитарам.
На этой почве у меня
В цикле книг "Про Дракона" Павла Шумила в одной из побочных сюжетных линий был описан некий космический артефакт - гигантский компьютер размером с небольшую солнечную систему. Возраст компьютера насчитывал несколько миллионов лет, физические масштабы поражали воображение, его долго исследовали, но несмотря на все усилия, никому так и не удавалось понять, что же именно он считает и для чего/кого.
По ходу пьесы выяснилось, что этот компьютер - творение рук ... одного из исследователей, который пытался взломать перебором пароль на компьютере своего коллеги, чтобы сунуть нос в результаты его исследований. Проблема была в том, что коллега был параноик, и вел свою работу внутри виртуальной машины, запущенной на своем компьютере, что сильно усложняло атаку перебором. В результате, когда первый исследователь случайно получил доступ к технологии перемещения во времени, он забросил в прошлое компьютер, который мог модифицировать и развивать самого себя. и занимался исключительно творческим взломом и подбором паролей к виртуальной машине второго исследователя. Правда, второй исследователь к этому времени уже что-то начал подозревать, и подсунул первому бэкап-копию якобы своего компьютера, которая на самом деле содержала в себе "матрешку" из десятка запущенных друг в друге виртуальных машин, последняя из которых содержала те самые ценные сведения ...
Заброшенный в прошлое компьютер за пару миллионов лет "замодернизировал" себя до неузнаваемости, но "матрешку" из виртуальных машин так и не разобрал и пароль так и не подобрал ... Зато стал объектом исследования незадачливой парочки :)
Да, к чему это я?
Когда я был курсе на втором-третьем, нам читали курс лекций по теории вычислений, на котором, помимо прочего, познакомили нас с разнообразными машинами Тьюринга. Если кто не знает, машина Тьюринга - это такая асбтрактная модель компьютера (состоящая из ленты в клеточку, карандаша, резинки и набора правил), на которой удобно исследовать вычисления и строить доказательства о свойствах процесса вычисления.
Так вот, уже на этом достаточно абстрактном уровне можно заниматься виртуализацией: можно построить универсальную машину Тьюринга, которой на вход будет подаваться программа для обычной машины Тьюринга и исходные данные, после чего универсальная М.Т. проэмулирует работу обычной М.Т. с не более чем квадратичным замедлением и выдаст результат.
Поскольку универсальная машина Тьюринга на базовом уровне является разновидностью обычной машины Тьюринга, для нее в свою очередь можно построить соотвествующую универсальную машину Тьюринга, и так далее, и тому подобное.
А тут как раз в FIDO-шной эхоконференции RU.PERL зашел разговор о том, что на Perl-е, конечно, можно написать код любой степени нечитаемости, но за счет отладчика и отладочной печати любой такой можно распутать и в конце-концов понять.
Прикола ради я написал на perl-е реализацию универсальной машины Тьюринга, которой на вход давалась программа для другой универсальной машины Тьюринга, которой на вход давалась программа для обычной машины Тьюринга, которой на вход давалось побитовое представление ASCII-строки, и эта последняя машина проверяла какое-то свойство этого бинарного представления - типа, что кол-во единиц в бинарном представлении больше кол-ва нулей в два раза, или что-то в этом роде. За счет двух (трех?) уровней эмуляции подобная проверка делалась примерно секунд 10.
Написал, и закинул в RU.PERL. Без описания того, что делает программа, но с примером строки, которая проходит подобную проверку. И предложил найти еще одну подобную строку. Если мне не изменяет мой склероз, то желающие были, но положительного результата они так и не достигли :)
Мораль: никогда не знаешь, когда тебе придется применить на практике знания, которые в институте кажутся оторванными от реальности и никому не нужными.
PS
Just for fun, та самая программа на perl-е (найденная внутри devel.zip, который был внутри old_computer.zip, который был внутри backup_to_sort_later.tgz, который бы в old_notebook.tar.bz2 :)
#!/usr/bin/perl -w
#
# Correct passwd: '3is>}.gK' (without '')
#
$data="Z043ZZZZZ111110ZZ0Z0ZZ0Z1102Z11110ZZ0ZZZZZ1110ZZ0Z102ZZZZ11111110Z110Z111111".
"111111110ZZ0Z1102ZZZZZ1111111110Z0ZZZZZ1111111110Z0Z1102ZZZZ111111110ZZ0ZZZZ".
"111111110Z0Z102Z111110ZZ0ZZZZZ1110ZZ0Z102ZZZZ11110Z10ZZZZ11110Z10Z102Z110ZZ0".
"ZZZZZ1110ZZ0Z102Z111110Z0Z1111110Z0Z1102ZZZZZ11111111110ZZ0ZZZZZ11110ZZ0Z102".
"ZZZZZ1111111110Z10ZZZZZ1111111110Z10Z1102ZZZZ11111110ZZ0ZZZZ11111110Z10Z102Z".
"ZZZ111111110Z110Z111111111111110ZZ0Z1102Z11111110Z10Z111111110Z10Z1102Z10Z10".
"Z110Z10Z1102Z111111110Z0Z1111111110Z0Z1102ZZZZZ1110Z10ZZZZZ1110Z10Z102ZZZZZ1".
"1110ZZ0Z0ZZ0Z1102ZZZZZ1110ZZ0ZZZZZ111111110ZZ0Z1102Z10Z0Z110Z0Z1102ZZZZ11111".
"0ZZZZ10ZZZZ1111110Z10Z102Z1110Z10Z11110Z10Z1102ZZZZ10Z0ZZZZ10Z0Z102ZZZZ1110Z".
"Z0ZZZZ1110Z10Z102ZZZZ1110Z10ZZZZ1110Z10Z102Z11111110ZZ0ZZZZZ1110ZZ0Z102Z1111".
"1110Z0Z111111110Z0Z1102ZZZZ11110Z110Z111111111111110ZZ0Z1102Z110Z0Z1110Z0Z11".
"02ZZZZ111111110ZZZZ10ZZZZ1111111110Z10Z102ZZZZZ1110ZZZZ10ZZZZZ111111110ZZZZ1".
"0Z1102Z1110Z0Z11110Z0Z1102Z1111111110ZZ0Z1111111110ZZ0Z102Z110Z10Z1110Z10Z11".
"02Z10ZZ0ZZZZZ1110ZZ0Z102ZZZZ11110ZZZZ10ZZZZ111110Z0Z102ZZZZZ11111111110Z10ZZ".
"ZZZ11111111110Z10Z1102ZZZZ111110Z110Z111111111111110ZZ0Z1102ZZZZ111110Z0ZZZZ".
"111110Z0Z102Z0ZZ0Z0ZZ0Z1102ZZZZ111110ZZ0ZZZZ111110Z10Z102ZZZZ10Z110Z11111111".
"1111110ZZ0Z1102ZZZZ11111110ZZZZ10ZZZZ111111110Z0Z102ZZZZZ111110Z0ZZZZZ1110ZZ".
"0Z102ZZZZZ11110Z10ZZZZZ1110ZZ0Z102ZZZZ110ZZ0ZZZZ110Z0Z102ZZZZZ11110Z0Z111111".
"111111110Z10Z1102ZZZZZ1110Z0ZZZZZ1110Z0Z102Z111111110Z10Z1111111110Z10Z1102Z".
"ZZZ1111111110ZZ0ZZZZ1111111110Z0Z102ZZZZZ111111110Z10ZZZZZ11111111110ZZ0Z110".
"2ZZZZ1111111110ZZZZ10ZZZZ10Z10Z102Z1111111110Z10ZZZZZ1110ZZZZ10Z102ZZZZZ1111".
"1111110Z0ZZZZZ11111111110Z0Z1102ZZZZ1111110ZZZZ10ZZZZ11111110Z0Z102ZZZZZ1111".
"111110ZZZZ10ZZZZZ111110ZZZZ10Z102Z111111110ZZ0ZZZZZ1110ZZ0Z102Z0Z110Z0Z110Z1".
"102Z0ZZZZ10Z10ZZZZ10Z1102Z1111111110Z0ZZZZZ1110ZZZZ10Z102Z0Z1110ZZZZ10Z1110Z".
"102ZZZZZ11111111110ZZZZ10ZZZZZ11110ZZZZ10Z102ZZZZ1111110Z110Z111111111111110".
"ZZ0Z1102ZZZZ1110Z110Z111111111111110ZZ0Z1102ZZZZ10ZZ0ZZZZ10Z10Z102ZZZZ110Z10".
"ZZZZ110Z10Z102Z11110Z10Z111110Z10Z1102ZZZZ110ZZZZ10ZZZZ1110Z10Z102ZZZZZ11111".
"1110ZZ0Z0ZZ0Z1102ZZZZ1111111110Z11011111111110ZZ0Z1102Z0Z0Z10ZZZZ10Z1102Z111".
"1110Z10Z11111110Z10Z1102ZZZZZ111111110Z0ZZZZZ1111111110ZZ0Z1102ZZZZZ11111111".
"10ZZ0ZZZZZ111110ZZ0Z102Z11110Z0Z111110Z0Z1102ZZZZ11110ZZ0ZZZZ11110Z0Z102Z111".
"110Z10Z1111110Z10Z1102ZZZZ110Z110Z111111111111110ZZ0Z1102Z1110ZZ0ZZZZZ1110ZZ".
"0Z102Z1111110Z0Z11111110Z0Z1102ZZZZ1110ZZZZ10ZZZZ11110Z0Z102ZZZZZ111110Z10Z1".
"11111111111110Z0Z1102Z1111110ZZ0ZZZZZ1110ZZ0Z102ZZZZ1111110ZZ0ZZZZ1111110Z0Z".
"102Z0Z10Z10ZZZZ10Z1102ZZZZ10ZZZZ10ZZZZ110Z0Z102";
sub crackme($) {
my ($s,$c,$m,$r);
$r="";
foreach (split(//,"2\@".$_[0]."\@3")) {
$s=("1" x (ord($_)))."0";
$r.=$s;
}
$r=~s/1{32}0/0/g;
$data=~s/Z/1111111111111111/g;
$data=~s/4/4$r/;
$data=~s/41/4\#/;
$s="1111111111111110";
while (not(341 % length($s) == 0)) {
if ($data=~/^(1+0)4.*?\#(1+0).*?(?:3.+?[^1]|3)(\1)([1]\2)(1+0)(1+0)(1+0)2/) {
$s=$5;$c=$6;$m=$7;
if (length($m)>18) {
$data=~s/\#1+01/$c\#/;
} else {
$data=~s/1(1+0)\#1+0/\#$1$c/;
}
$data=~s/^.*4/4/;
$data=$s.$data;
}
}
print "Password ";
if ($s=~/1{15}/) {
print "in";
}
print "correct\n";
}
crackme(unpack("B*",$ARGV[0]));
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2007-03-01 11:56 am (UTC)По нажатию на "p" в stdout вылезло МНОГО бинарных данных. Повторный запуск с перенаправлением stdout показал, что запуск кодекса генерирует 15 мб данных, которые ... являются еще одной программой для UM!
(no subject)
Date: 2007-03-01 02:49 pm (UTC)(no subject)
Date: 2007-03-01 03:54 pm (UTC)(no subject)
Date: 2007-03-01 11:59 am (UTC)А в абзаце номер 10 ты пропустил слово «свойства» в конце последнего предложения. =-)
(no subject)
Date: 2007-03-01 02:48 pm (UTC)PS
fixed
(no subject)
Date: 2007-03-01 02:57 pm (UTC)Но мне вспоминается нечто капельку более душещипательное про выпускника, лектора и шляпу... Ну да это невелика разница.
(no subject)
Date: 2007-03-01 12:10 pm (UTC)(no subject)
Date: 2007-03-01 12:14 pm (UTC)(no subject)
Date: 2007-03-01 12:15 pm (UTC)Эх, знал бы я тогда про крутизну компьютеров ))
(no subject)
Date: 2007-03-01 12:26 pm (UTC)(no subject)
Date: 2007-03-01 02:22 pm (UTC)(no subject)
Date: 2007-03-01 12:18 pm (UTC)(no subject)
Date: 2007-03-01 02:39 pm (UTC)У автора продуманная модель мира, и он следит за ее соблюдением, чем очень мне импонирует.
(no subject)
Date: 2007-03-01 03:23 pm (UTC)Отличная science fiction.
вспомнилось по поводу машины Тьюринга
Date: 2007-03-01 12:20 pm (UTC)http://www.syngress.com/catalog/?pid=2435
"The LEGO Turing Machine by Giulio Ferrari, is a revolutionary device created to study computability, and which allows us to journey to the time of Artificial Intelligence."
(no subject)
Date: 2007-03-01 12:20 pm (UTC)Чего пишем так мало? Ребенок не дает отвлечься? Судя по малочисленным подробностям и сухости изложения - да! Но байка то ведь интересная!! Хотелось бы чаще читать их.
(no subject)
Date: 2007-03-01 02:38 pm (UTC)А книжки Шумила я читал достаточно давно - года четыре тому. если не больше...
(no subject)
Date: 2007-03-01 09:20 pm (UTC)(no subject)
Date: 2007-03-01 09:52 pm (UTC)А в чем же стало проще?
(no subject)
Date: 2007-03-02 11:26 am (UTC)(no subject)
Date: 2007-03-01 01:13 pm (UTC)Идея о защите прожраммок путём встраивания в них интерпретатора какой-нибудь личной версии брейнфака мне весьма нравицо. Единственное что: во-первых, это типичный случай security by obscurity, поэтому использовать обычную машину Тьюринга не очень правильно, это тебе просто повезло, что на перле пишет довольно специфический контингент =) Нужен самостоятельно построенный язык, причём весьма нетривиальный для программирования. Во-вторых, в евонное нутро нужно ныкать реальные важные куски кода, а не просто проверку серийника, вызов которой можно взять и вырезать ваще. Соответственно, этот самый язык должен быть всё же доступен для программирования хотя бы лично тобой, а лучше иметь компилятор в него из какого-нибудь MSIL. Ну и интерпретироваться он должен довольно быстро.
Поэтому если такое сделать, то, к сожалению, погордиться перед общественностью достигнутыми результатами не удастся, ибо детали реализации придётся держать в Жутком Секрете.
(no subject)
Date: 2007-03-01 02:31 pm (UTC)(no subject)
Date: 2007-03-01 03:31 pm (UTC)есть такая занимательная система шифрования спутникового телевидения - Nagravision. Вот ее смарт-карты очень плохо поддаются клонированию, несмотря на почти известный алгоритм собственно шифрования. Потому что в отличие от остальных систем, которые получают снаружи только данные для расшифровки, в нагре в этих данных могут встречаться команды типа "а вот тут надо на процессоре карты выполнить вот этот бинарный код". Причем код вполне может использовать текущие значения каких-нибудь регистров процессора, образовавшиеся в результате прошлой работы.
И получается, что единственный способ нормально сэмулировать работу карты - вынуть из нее дампы РОМов и ПРОМов (что тоже совершенно не тривиально) и запускать их в программном интерпретаторе. По-другому никак.
(no subject)
Date: 2007-03-01 07:07 pm (UTC)(no subject)
Date: 2007-03-01 08:57 pm (UTC)Собственно, в DVB-C и -T применяются те же самые методы шифрования.
(no subject)
Date: 2007-03-01 09:54 pm (UTC)(no subject)
Date: 2007-03-01 11:34 pm (UTC)(no subject)
Date: 2007-03-01 10:16 pm (UTC)(no subject)
Date: 2007-03-01 10:31 pm (UTC)(no subject)
Date: 2007-03-01 02:35 pm (UTC)> # Correct passwd: '3is>}.gK' (without '')
Date: 2007-03-01 01:53 pm (UTC):-)
Re: > # Correct passwd: '3is>}.gK' (without '')
Date: 2007-03-01 02:37 pm (UTC)(в ужасе убегает)
Мне до сих пор этот решатель на прологе в страшных снах снится.
(no subject)
Date: 2007-03-01 02:27 pm (UTC)(no subject)
Date: 2007-03-01 03:25 pm (UTC)(no subject)
Date: 2007-03-01 03:26 pm (UTC)(no subject)
Date: 2007-03-01 08:48 pm (UTC)(no subject)
Date: 2007-03-20 09:38 pm (UTC)(no subject)
Date: 2007-03-01 10:24 pm (UTC)Так вот, главный спор в те времена был на тему, какова скорость этого арвида. Противники железки орали, что низкая, сторонники - что вполне высокая.
И вот однажды, в одной из эх некий фанат устройства заявил: "Достаточная там скорость! Я записал на кассету фильм в mpeg и смотрел его без всяких тормозов!", на что сразу получил ответ: "Свершилось! Наконец фидошники сумели приспособить бытовой видеомагнитофон для просмотра видео!".
(no subject)
Date: 2007-03-06 08:16 pm (UTC)(no subject)
Date: 2007-03-02 06:44 pm (UTC)(no subject)
Date: 2007-03-03 09:49 pm (UTC)'3is>}.g3':)(no subject)
Date: 2007-03-20 09:37 pm (UTC)А полностью из других символов слабо? :)
(no subject)
Date: 2007-03-21 05:42 am (UTC)(no subject)
Date: 2007-03-21 06:32 am (UTC)Не составит труда полечить мой склероз и напомнить мне, какие же пароли я считал "правильными"? (без издевки, я реально не помню, что за проверку я реализовал)
(no subject)
Date: 2007-03-21 08:21 pm (UTC)дык подбор же :) что-то с количеством битов, я ещё поковыряю когда будет время.
машину Тьюринга реально сложно вернуть обратно в понятное описание, а в этой 25 хороших состояний/86 хороших переходов - много.
надо что-нибудь автоматизированное на эту тему придумать.
(no subject)
Date: 2007-03-21 09:10 pm (UTC)(no subject)
Date: 2007-03-22 03:01 pm (UTC)картинк:
(no subject)
Date: 2010-03-06 09:39 pm (UTC)