Category: математика

Для нача­ла немно­го тео­рии.

Как хра­нят­ся паро­ли в опе­ра­ци­он­ных систе­мах, веб­сай­тах, и т.д. Не откры­тым тек­стом, разу­ме­ет­ся. Они хра­нят­ся в виде хешей. Хеш — это стро­ка опре­де­лён­ной дли­ны, полу­ча­е­мая при обра­бот­ке вво­да (паро­ля в дан­ном слу­чае) хеш-функ­ци­ей. До недав­не­го вре­ме­ни (да и сей­час кое-где) исполь­зо­вал­ся алго­ритм MD5. Так, хеш MD5 сло­ва «password» пред­став­ля­ет собой стро­ку 5f4dcc3b5aa765d61d8327deb882cf99.

Поэто­му когда ты логи­нишь­ся на веб­сайт, пароль обра­ба­ты­ва­ет­ся алго­рит­мом MD5, и срав­ни­ва­ют­ся хеши. Если на выхо­де 5f4dcc3b5aa765d61d8327deb882cf99, то всё нор­маль­но. Вин­да дела­ет немно­го по-дру­го­му: хеш гене­ри­ру­ет­ся пря­мо на кли­ен­те, и пере­сы­ла­ет­ся не пароль, а сра­зу хеш. Это цуцуть без­опас­нее. Ещё хеш солят, но про это в дру­гой раз.

Что­бы взло­мать пароль, надо сна­ча­ла украсть хеш паро­ля. Взлом паро­лей пере­би­ра­ет все воз­мож­ные ком­би­на­ции, хеши­ру­ет их и срав­ни­ва­ет хеши. Но это тупой пере­бор, есть вари­ан­ты поин­те­рес­нее, типа сло­ва­рей, ком­би­на­ций заме­ны букв на циф­ры, и мате­ма­ти­че­ско-ста­ти­сти­че­ские мето­ды, типа цепей Мар­ко­ва. Но подроб­ное раз­би­ра­ние этих мето­дов — это мате­ри­ал для огром­но­го отдель­но­го поста.

Я уже дав­но люб­лю про­грам­му кото­хеш (hashcat) для взло­ма паро­лей. У неё исклю­чи­тель­но высо­кая про­из­во­ди­тель­ность, так как она исполь­зу­ет видео­кар­ту для рас­чё­тов вме­сто цен­траль­но­го про­цес­со­ра. Нет, она и про­цес­сор может исполь­зо­вать, про­сто на видео­кар­те быст­рее, там этих про­цес­со­ров тыся­чи, а хеши­ро­ва­ние исклю­чи­тель­но хоро­шо рас­па­рал­ле­ли­ва­ет­ся.

Сло­ма­ем MD5 хеш 5f4dcc3b5aa765d61d8327deb882cf99:

hashcat.exe ‑m 0 ‑a 3 hash.txt ?l?l?l?l?l?l?l?l

И мень­ше, чем за секун­ду всё сло­ма­но.

На моей уже ста­рень­кой 1070GTX поиск хешей MD5 про­ис­хо­дит со ско­ро­стью око­ло 8 мил­ли­ар­дов ком­би­на­ций в секун­ду.

Даже если сме­нить пароль на более слож­ный, типа P@$$w0rd, то 8‑значный пароль взла­мы­ва­ет­ся в обо­зри­мые сро­ки, даже на не очень новом желе­зе — за несколь­ко дней.

НО. Подоб­ные сро­ки — они для паро­лей, хеши­ро­ван­ных MD5. От кото­ро­го вез­де отка­зы­ва­ют­ся как могут. Он счи­та­ет­ся крип­то­гра­фи­че­ски нестой­ким: во-пер­вых, он под­вер­жен кол­ли­зи­ям (т.е. два совер­шен­но раз­ных паро­ля могут дать оди­на­ко­вый хеш), а во-вто­рых он име­ет недо­ста­точ­ную вычис­ли­тель­ную слож­ность. Т.е. тот факт, что даже на моём ста­ром желе­зе я могу пере­би­рать восемь мил­ли­ар­дов паро­лей в секун­ду — он из-за это­го про­ис­хо­дит.

А недав­но я попро­бо­вал сло­мать бекап смарт­фо­на Apple. Для тёщи, кото­рая рас­ко­ка­ла теле­фон вдре­без­ги, успев, прав­да, неза­дол­го до сде­лать ему бекап. Но вот беда — она забы­ла пароль от бека­па! Она толь­ко зна­ла, что пароль вось­ми­знач­ный.

Хеш паро­ля для айфон­но­го бека­па берёт­ся в фай­ле Manifest.plist. Этот файл скарм­ли­ва­ет­ся вот это­му сай­ту, напри­мер, и тебе дают хеш.

Так вот хеш там — какой-то про­при­е­тар­ный. И име­ет настоль­ко высо­кую вычис­ли­тель­ную слож­ность, что на моей видео­кар­те кото­хеш пере­би­ра­ет ком­би­на­ции со ско­ро­стью… 83 вари­ан­та в секун­ду. Надо отдать долж­ное чув­ству юмо­ра раз­ра­бот­чи­ков кото­хе­ша: во вре­мя рабо­ты оно пока­зы­ва­ет, сколь­ко вре­ме­ни оста­лось до пере­бо­ра всех вари­ан­тов. Так вот в дан­ном слу­чае оно гово­рит, что рабо­та про­грам­мы закон­чит­ся после сле­ду­ю­ще­го Боль­шо­го Взры­ва 😀

Вот так вот Плот­нег лосос­нул тун­ца.

Огром­ный респек­ти­щ­ще Эпплу — я в оче­ред­ной раз убе­дил­ся, что уж с чем-чем, а с надёж­но­стью шиф­ро­ва­ния у них всё все­гда было в пол­ном поряд­ке. Огром­ным плю­сом явля­ет­ся то, что Эппл кон­тро­ли­ру­ет весь цикл про­из­вод­ства теле­фо­на — от желе­за до соф­та. Поэто­му что, как и каким спо­со­бом — все­гда было хоро­шо извест­но и задо­ку­мен­ти­ро­ван­но. Ну и тра­ди­ци­он­но, пнём Вед­ро­ид 🙂 На Вед­ро­и­дах, кто шиф­ру­ет что и как — а хер его зна­ет! Кто из про­из­во­ди­те­лей как захо­тел, тот так и шиф­ру­ет. И ска­жи ещё спа­си­бо, если задо­ку­мен­ти­ро­ва­но. А могут и тово, на хрен послать.

Моя гнев­ная теле­га по пово­ду наци­о­наль­ных осо­бен­но­стей пре­по­да­ва­ния мате­ма­ти­ки в началь­ной шко­ле полу­чи­ла доволь­но про­стой ответ: дети всё же уме­ют скла­ды­вать дву­знач­ные чис­ла в стол­бик.

А зачем тогда таб­ли­ца до ста? Это для отста­ю­щих детей, кото­рые до сих пор не вру­ба­ют­ся во-пер­вых, а во-вто­рых это мост в обу­че­ние добав­ле­нию еди­нич­ки в более стар­ший раз­ряд, если сум­ма чисел преды­ду­ще­го раз­ря­да пре­вы­ша­ет десять. Так как у нас закан­чи­ва­ют­ся кле­точ­ки, и надо начать сно­ва (спу­стив­шись вниз) — дети долж­ны осо­знать, что мы добав­ля­ем ещё деся­ток.

Топо­ры-вилы-факе­лы отста­вить.

Вот это, по-мое­му, и назы­ва­ет­ся «доэто­са­мить­ся до мышей». Мате­ма­ти­ка, в том виде, в кото­ром она пре­по­да­ёт­ся в шко­лах и ВУЗах, ока­зы­ва­ет­ся, расист­ский пред­мет. Что, доро­гой чита­тель, ты не подо­зре­вал, что утвер­жде­ние «в кру­ге 2π ради­ан» явля­ет­ся расист­ским? Ну, а как же, конеч­но же расист­ское, какие могут быть раз­го­во­ры? Ведь это в Запад­ной циви­ли­за­ции при­ду­ма­ли ради­а­ны. И застав­ля­ют теперь всех осталь­ных их исполь­зо­вать, изна­си­ло­вав мест­ные поня­тия. А может быть, дикие австра­лий­ские або­ри­ге­ны по-дру­го­му расчи­ты­ва­ют углы? Да и вооб­ще — по-дру­го­му счи­та­ют циф­ры.

Так счи­та­ет школь­ный округ Сиэт­ла. И пред­ла­га­ет пре­по­да­вать пред­мет «этни­че­ские иссле­до­ва­ния в мате­ма­ти­ке».

Ста­тья.

Вко­нец охе­ре­ли. От вме­ня­е­мо­го пре­по­да­ва­ния мате­ма­ти­ки в аме­ри­кан­ских шко­лах и так уже оста­лись рож­ки да нож­ки. Мате­ма­ти­ку в мест­ных шко­лах гро­ми­ли уже два­жды — сна­ча­ла в 1960х, вве­дя «New Math», и в 2010м, вве­дя «Common Core». Вме­сто нор­маль­но­го пре­по­да­ва­ния нуж­ных пред­ме­тов вво­дят вот такую вот лабу­ду.

Когда уже закон­чит­ся этот цикл деби­лов?

Хотел напи­сать про то, как мне лич­но было непо­нят­но, чем так гор­дит­ся груп­па иссле­до­ва­те­лей Мас­са­чус­сет­ско­го Тех­но­ло­ги­че­ско­го, кото­рая нашла зна­че­ния x, y, и z, при кото­рых x³ + y³ + z³ = 42.

Набро­сал для рас­чё­тов свою про­гу на Джа­ве. И не могу ска­зать, что она не рабо­та­ла. Она пре­крас­но рабо­та­ла для мно­гих цифр, в том чис­ле, и для люби­мо­го чис­ла Шел­до­на Купе­ра (73). Но даль­ше, имея на руках поряд­ки полу­чен­ных в MIT цифр для 42, при­ки­нул вычис­ли­тель­ную слож­ность, и охре­нел — т.к. решать дан­ную про­бле­му, как гово­рит­ся, «в лоб» на самом уль­тра­со­вре­мен­ном супер­ком­пью­те­ре с его дву­мя сот­ня­ми петафлоп­сов с лихе­ром при­дёт­ся э.… не намно­го мень­ше, чем воз­раст наблю­да­е­мой Все­лен­ной.

Усты­дил­ся, пошёл читать про алго­ритм, кото­рым рань­ше было реше­но урав­не­ние x³ + y³ + z³ = 33. Ока­за­лось, что там, мяг­ко гово­ря, очень не в лоб реша­ли. Усты­дил­ся окон­ча­тель­но. Полез­но вот так ино­гда, рожей об стол, для скром­но­сти и сми­рен­но­сти.

По интер­не­ту гуля­ет мате­ма­ти­че­ская загад­ка — каков резуль­тат выра­же­ния 8 / 2(2+2)?

У одних полу­ча­ет­ся 16, у дру­гих 1. Сло­ма­ны уже тыся­чи вир­ту­аль­ных копий.

Оче­вид­но, что ответ полу­ча­ет­ся раз­ным из-за раз­ной интер­пре­та­ции после­до­ва­тель­но­сти мате­ма­ти­че­ских дей­ствий. Что делать пер­вым — делить 8 на 2 или умно­жать 2 на (2 + 2)?

Ответ, что харак­тер­но, может быть раз­ным в отли­чие от стра­ны. В США и Рос­сии, напри­мер, под­ра­зу­ме­ва­е­мое умно­же­ние (как тут, 2(2 + 2)) — сто­ит по при­о­ри­те­ту выше, чем умно­же­ние обыч­ное или деле­ние, поэто­му ответ дол­жен быть 1.

А в дру­гих стра­нах (ИМХО, в Бри­та­нии) у под­ра­зу­ме­ва­е­мо­го умно­же­ния нет спе­ци­аль­но­го ста­ту­са, и, соот­вет­ствен­но, в таких слу­чая мы про­сто про­во­дим опе­ра­ции сле­ва напра­во, и ответ — 16.

Аме­ри­ка­но-рос­сий­ский вари­ант мне кажет­ся более логич­ным: ведь 2(2 + 2), исполь­зуя дис­три­бу­тив­ность, мож­но запи­сать как 4 + 4, и выра­же­ние при­мет вид 8 / (4 + 4), и ответ, есте­ствен­но, будет 1.

А вооб­ще эта загад­ка, как и мно­же­ство дру­гих голо­во­ло­мок (напри­мер, про тот несчаст­ный само­лёт на бего­вой дорож­ке), не сто­ит выеден­но­го яйца. Пото­му что выра­же­ние запи­са­но через одно место, и интер­пре­ти­ро­вать его мож­но по-раз­но­му, отсю­да и интер­нет­ные бит­вы. Если запи­сать его так, что­бы исклю­чить воз­мож­ность дру­го­го про­чте­ния, то и спо­рить было бы не о чем.

Кста­ти, если запро­грам­ми­ро­вать это выра­же­ние (я исполь­зо­вал Питон, Джа­ву, Сишарп) — то выда­ёт­ся один и тот же ответ — 16. Пото­му что нет под­ра­зу­ме­ва­е­мо­го умно­же­ния в этих язы­ках (а в каких есть?), и оно тупо дела­ет опе­ра­ции сле­ва напра­во, по-англий­ски.

Инте­рес­но, как про­по­нен­ты идеи того, что мы живём внут­ри симу­ля­ции раз­ре­ша­ют про­бле­му того, что неко­то­рые вычис­ле­ния, свя­зан­ные с симу­ля­ци­ей, име­ют чрез­вы­чай­но высо­кую вычис­ли­тель­ную сто­и­мость?

Вот, напри­мер, гра­ви­та­ция. Она опи­сы­ва­ет­ся урав­не­ни­я­ми гра­ви­та­ци­он­ной зада­чи N тел. Наша пла­не­та вза­и­мо­дей­ству­ет с Солн­цем, Луной, и все­ми осталь­ны­ми пла­не­та­ми сол­неч­ной систе­мы. Даже если не при­ни­мать во вни­ма­ние луны осталь­ных пла­нет и асте­ро­и­ды, то N в дан­ном слу­чае будет рав­но 10 (коли­че­ство пла­нет плюс Солн­це и Луна). Про­бле­ма в том, что для N > 3 гра­ви­та­ци­он­ная зада­ча не явля­ет­ся реша­е­мой. К реше­нию мож­но толь­ко при­бли­зить­ся, сиречь, дей­ство­вать чис­лен­ны­ми мето­да­ми, схо­дя­щи­ми­ся ряда­ми. Потом, даже в такой про­стой зада­че мы при­ни­ма­ем такие упро­ще­ния, что пла­не­ты явля­ют­ся дис­кре­ты­ми точ­ка­ми, не име­ю­щи­ми раз­ме­ров, слож­ной фор­мы, мас­ко­нов, как на Луне, и так далее. Чис­лен­ные мето­ды реше­ния гра­ви­та­ци­он­ной зада­чи так­же име­ют вычис­ли­тель­ную слож­ность N². То-есть, при уве­ли­че­нии коли­че­ства тел в два раза, при­дёт­ся про­из­ве­сти в четы­ре раза боль­ше вычис­ле­ний. Оче­вид­но, что коли­че­ство вычис­ле­ний очень быст­ро уле­та­ет в бес­ко­неч­ность.

В реаль­но­сти же гра­ви­та­ци­он­ное вза­и­мо­дей­ствие есть меж­ду моим паль­цем и какой-нибудь чёр­ной неза­буд­кой, рас­ту­щей на пла­не­те в далё­кой галак­ти­ке. Да, оно ничтож­но. Но оно, блин, есть. И как это воз­мож­но симу­ли­ро­вать — реши­тель­но непо­нят­но.