Конспект первых лекций

Добрый вечер!
Конспект 2007 г., но эта часть не будет существенно меняться!

Страница 24, рассмотрение одностороннего шифрования.

"Для каждого шифрованного пароля получается множество вариантов дешифрованных, что затрудняет проникновение в систему".

Облегчает! Ведь достаточно угадать любой из множества вариантов, чтобы система "пустила".
Они же проверяют как в этих случаях: берут пароль, указанный пользователем при входе, осуществляют над ним хэш-преобразование и сравнивают с хранимым хэшем. Если хэши совпадают, то пользователя пускают.
Если пользователь подобрал другой пароль, дающий в результате тот же хэш, то его пустят. Чем больше вариантов паролей, дающих тот же хэш, тем ниже устойчивость этого аккаунта ко взлому.

to cathatsis:

Не согласен. Здесь говорится о том, что если в некоторой системе шифрования "Для каждого шифрованного пароля получается множество вариантов дешифрованных..." - это именно затруднит вход в систему: на вход программе проверки надо давать именно пароль, а не хэш-сумму! Чем больше паролей получается при расшифровке - тем хуже взломщику.

Если речь идет о современных алгоритмах хэширования (в частности md5), то о совпадении двух паролей, дающих один хэш говорить не приходится: каждому паролю из множества A единственным псевдослучайным образом противопоставляется хэш-сумма из множества B. Просто обратное действие теоретически невозможно за реальный отрезок машинного времени. Относительно единственности отображения в другую сторону надо смотреть в описании соответствующего протокола.



Исправлений: 2. Последний раз редактировал Alexandr в 09.09.2009, 01:01.

На вход система получает пароль, потом делает из него некоторым (неоднозначно и долго обратимым) образом некоторое значение. Это значение сравнивается со значением, хранящимся в базе. Если они совпадают, то пользователя пустили. Сам пароль в базе не хранится - в чем смысл-то! - системе не известен.

Далее, про MD5. Как известно, этот алгоритм позволяет получать дайджесты сообщений любой длины, при этом длина самого дайджеста фиксированная - 128 бит. Таким образом, одному и тому же дайджесту соответствует бесконечное множество сообщений. Если Вы подберете любое сообщение из этого множества, система получит необходимый дайджест, а Вы, соответственно, доступ к системе. Другое дело, что подбор таких сообщений невозможен за разумный отрезок времени.

Но! Загляните на http://passcracking.ru/ ^) Все просто - люди составляют таблицы, которые сопоставляют md5-дайджесты входным сообщениям.

По-моему в конспекте лекции про машину Тьюринга допущена ошибка. Там где описывается копирование слова из нескольких палочек. В состоянии "Поиск последней скопированной буквы" для пробела прописано движение влево и переход в состояние "последняя скопированная буква найдена". Но в этом случае мы попадём в ячейку с палочкой, а для состояния "последняя скопированная буква найдена" такого действия не определено. я считаю что в состоянии поиска последней скопированной буквы для пробела должно быть действие записывания в эту ячейку палочки и перехода к 10 состоянию. а в 10 состоянии для пробела нужно двигаться налево и перейти в 11 состоянию.
кстати в таблице на странице 47 опечатка. в состоянии 9 для | должно быть движение направо.

Kolyanych Написал:
-------------------------------------------------------
> По-моему в конспекте лекции
> про машину Тьюринга
> допущена ошибка. Там где
> описывается копирование
> слова из нескольких
> палочек. В состоянии "Поиск
> последней скопированной
> буквы" для пробела
> прописано движение влево и
> переход в состояние
> "последняя скопированная
> буква найдена". Но в этом
> случае мы попадём в ячейку
> с палочкой, а для состояния
> "последняя скопированная
> буква найдена" такого
> действия не определено. я
> считаю что в состоянии
> поиска последней
> скопированной буквы для
> пробела должно быть
> действие записывания в эту
> ячейку палочки и перехода к
> 10 состоянию. а в 10 состоянии
> для пробела нужно
> двигаться налево и перейти
> в 11 состоянию.
> кстати в таблице на
> странице 47 опечатка. в
> состоянии 9 для | должно
> быть движение направо.
Вторая таблица, помещённая в tu4, работоспособна, т.к. в состоянии q9 в рабочей ячейке палочки не может быть по определению, эта ветка никогда не выполняется и всё равно, какое действие там указано:

00,|,<,01
00, ,<,01
01,|,<,01
01, , ,02
02,|,>,03
02, ,>,03
03,|,|,04
03, , ,16
04,|, ,05
04, , ,05
05,|,>,06
05, ,>,06
06,|,>,06
06, , ,07
07,|,>,08
07, ,>,08
08,|,>,08
08, , ,09
09,|,|,10
09, ,|,10
10,|,<,11
10, ,<,11
11,|,<,11
11, , ,12
12,|,<,13
12, ,<,13
13,|,<,13
13, , ,14
14,|,|,15
14, ,|,15
15,|,>,03
15, ,>,03
16,|,>,17
16, ,>,17
17,|,>,17
17, , ,18
18, , ,18

В первой, текстовой, версии таблицы действительно ошибка, возможно возникшая при вёрстке в ТеХ. Несколько лет тому назад мы её заметили и хотели переделать таблицу 1976 г.
Семён составил более лаконичную версию этой программы, также проверенную на тестах:

00, ,<,01
01,|,<,01
01, ,>,02
02, ,>,09
02,|, ,03
03, ,>,04
04,|,>,04
04, ,>,05
05,|,>,05
05, ,|,06
06,|,<,06
06, ,<,07
07,|,<,07
07, ,|,08
08,|,>,02
09,|,>,09
09, , ,09

такую, что:
1. Пустое слово копируется правильно
2. Слова из 1, 2, 3, 4, 5 палочек копируются правильно.

Как говорил Эйлер, опечатки весьма оживляют чтение скучных математических текстов!

Quote

Вторая таблица, помещённая в tu4, работоспособна...
...
08,|,>,08
08, , ,09
...

ну тогда ошибка в 08 состоянии. Там для пробела не нужно движение налево.


PS Вообщем в любом случае или в 08 состоянии надо убрать движение налево или в 09 добавить движение направо.



Исправлений: 2. Последний раз редактировал Kolyanych в 01.10.2009, 22:10.

"Лишь то ошибка, что не исправляется!"
Конфуций
Моё утверждение о правильности программы было основано на продемонстированных на лекции тестах, но из Вашего сообщения стало ясно, что дело теперь в том, что оказывается программа из второй таблицы была введена не в точности, как написано в конспекте, а правильно, причём это получилось непроизвольно.

Можете выложить новые страницы.

White_man Написал:
-------------------------------------------------------
> Можете выложить новые
> страницы.

Не могу, при переводе svg в eps осыпаются стрелки в диаграмме!

Валентин Евгеньевич, здравствуйте! Хотя наиболее вероятно, что "стрелки осыпаются" при переводе в формат eps в связи с нехваткой возможностей формата (извините если не очень правильно выразился), быть может вы попробуете два следующих БЕСПЛАТНЫХ обработчика данных форматов - Inkscape (www.inkscape.org) и Imagemagick (www.imagemagick.org). Спасибо за прочтение

А можете выложить до куда мы сегодня прошли там где то 125 стр, если можете?

Лучше поздно, чем никогда!
Получилось благодаря асп. Дубинину, изменившему техпроцесс.

А можно выложить Ваши лекции в .doc например?
А то нет возможности делать комментарии на компьютере... Да и добрая половина конвертеров кривые...

Artem Написал:
-------------------------------------------------------
> А можно выложить Ваши
> лекции в .doc например?
> А то нет возможности делать
> комментарии на
> компьютере... Да и добрая
> половина конвертеров
> кривые...
По договорённости с издательством для издания в недалёком будущем этого курса его точные представления распостранению не подлежат. Только djvu или ксерокопия 300 dpi.
Комментарии на компьютере можно делать в форме списка замечаний или wiki с координатами в тексте.