Перейти к содержанию

РАЗВЕДЧИКИ И ПОГРАНИЧНИКИ


Рекомендуемые сообщения

РАЗВЕДЧИКИ И ПОГРАНИЧНИКИ

Дэнис Шаша

"В мире науки" февраль 2003г.

 

Теория чисел, некогда воспринимавшаяся как эзотерическая наука о загадочных свойствах простых чисел, самым неожиданным образом вторглась

в современную криптографию. Большинство электронных платежей теперь осуществляется при помощи цифровой подписи, известной как алгоритм Райвеста-Шамира-Адлемана (Rivest-Shamir-Adleman) (RSA). В его основе лежит принцип разложения числа, представляющего собой результат перемножения двух простых чисел на множители.

Перемножение двух больших простых чисел есть не что иное, как односторонняя функция. Этот процесс занимает всего несколько микросекунд,

а время, затраченное на выполнение данной операции, прямо пропорционально длине этого числа, отображенного в двоичной системе. Напротив, поиск двух простых множителей числа, скажем объемом в 512 бит, может занять несколько часов. Даже после того, как искомые величины будут найдены, перебор оставшихся вариантов продолжится. Для чисел в 2 048 бит подобный процесс считается нецелесообразным, поскольку он занимает практически неограниченно долгое время. Для защиты особо важной военной и промышленной информации используются более сложные способы криптографической защиты, при которых даже сверхбыстрый поиск оказывается неэффективным.

Это подводит нас к головоломке, придуманной Джоном Маккарти (John McCarthy), – автором языка программирования Lisp и теории искусственного интеллекта. В 50-х годах Майкл Рабин (Michael Rabin), известный изобретатель прикладных и развлекательных компьютерных программ, разгадал головоломку. Сумеете ли вы?

Задача формулируется следующим образом: группа разведчиков проникает на вражескую территорию. После выполнения задания бойцы возвращаются, но при переходе границы или их застрелят свои, приняв за шпионов, или пограничники пропустят вражеских агентов на свою территорию. Чтобы избежать недоразумений, каждый разведчик должен будет назвать свой пароль, который пограничник должен будет опознать. И разведчики, и пограничники вполне надежны, но вдруг они проболтаются за кружечкой пива в баре? Итак: какого рода информацию можно доверить пограничникам, и какие пароли должны называть разведчики, чтобы только они смогли пересечь границу, даже если пограничники выдадут известные им сведения? Подсказка – рассуждение о простых числах.

 

Web-решение: чтобы узнать ответ на головоломку, посетите сайт ww.sciam.com

Ссылка на комментарий
Поделиться на другие сайты

Если это наши разведчики я бы налил чайку.

 

Приходит советский разведчик в парижское бистро, заказывает чашку чая, сидит, пьёт. Тут подбегает к нему офицант и говорит

-О!, мсье русский шпион!

Ну, наш, понятно, сконфужен, как ты, спрашивает он офицанта, узнал, что я - шпион?!

- О, мсье положил сахару в чашку, размешал ложечкой, да так с

ложечкой в стакане и пьёт! Ну, в следующий раз чекист, умудрённый опытом,заказал чаю, положил сахару, размешал, а ложечку так аккуратненько об край стряхнул, сидит и пьёт чай без ложки. Тут опять к нему подскакивает офицант,

- О!, говорит, а мсье - русский шпион!

- Ну что за дела???!!, как ты, шельма, узнал?

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

- О, мсье - русский шпион! Ну, чекист звереет, как ты, говорит, теперь-то догадался???!!

- О, мсье ложечку так аккуратненько вытащил, взял чашечку так изящненько, А ПРАВЫЙ ГЛАЗ ПРИЩУРИЛ, чтоб туда ложка не попала!!!

Ссылка на комментарий
Поделиться на другие сайты

Если опасность только в длине языка пограничников - тогда задача проста.

Вариант первый:

Чтобы не морочить голову публике простыми числами, можно объяснить более просто - использованием понятий публичного ключа и ключа закрытого пары асимметричных ключей. Пограничникам нужно дать публичный ключ для зашифрования пароля.Парный ключ хранить в тайне. И дать уже готовые зашифрованные пароли, не раскрывая оргиналы. Пусть пьют пиво и болтают. Функции в принципе необратимы. Даже если враг получит в руки шифрованные пароли, он с ними ничего сделать не сможет. Разведчики, проходя границу, будут называть свои пароли, пограничники-шифровать их и сравнивать с "отпечатками". Сходится-проходи, не сходится-стреляем style_emoticons/default/smile1.gif

 

Второй вариант. Пограничникам ключи для расшифровки, разведчикам - для шифрования. Пограничников - в бар, разведку - на задание. Пароли - печатаем в местной газете. Даже если пограничники сдадут ключи, парные ключи известны только разведке и восстановить их невозможно. Разведчики при проходе границы шифруют пароли, погрничники - расшифровывают полученное, убеждаются что свои. Не расшифровывается - стреляют. style_emoticons/default/smile1.gif

 

 

Вариант третий. Вообще не использовать асимметирчную криптографию и простые числа.

Вариант похож на первый. Использовать функцию необратимого преобразования (хэш, по другому). Например, блочным шифром зашифровать пароль разведчика, в качестве ключа - тот же пароль. Криптостойкость слабенькая, но тем не менее."Отпечаткки" и алгоритм - пограничникам. Пусть пьют пиво и болтают. Разведка при возвращении называет пароли, погранцы - преобразовывают, сравнивают. Сходится-проходи, не сходится -снова стреляем style_emoticons/default/smile1.gif

 

Если болтать будут и разведчики и погрничники, задача не решается.

 

Я прав?

 

Анекдот СУПЕР!!!

Ссылка на комментарий
Поделиться на другие сайты

  • 1 месяц спустя...
Функции в принципе необратимы.

в принципе, математики еще не уверены, есть ли необратимые функции. пока они считаются трудно обратимыми. но это все в сторону np-полных задач и мало кому интересно... причем, вся криптография держится не на необратимых функциях - зашифровать, зашифровали, но уже не расшифруем. используются, так называемые, функции с секретом, когда знание ключа позволяет легко расшифровать посылку.

 

Вариант похож на первый. Использовать  функцию необратимого преобразования (хэш, по другому).

 

хэш-функция в общем случае не обязана быть необратимой.

 

Хэш преобразование - Это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины. Простейшими примерами являются контрольные суммы (например, crc32). Бывают криптографические и программистские хэши. Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим m - исходные данные, h(m) - хэш от них. Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0. Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1 не равно m2, но h(m1) = h(m2).

Криптографические хэш-функции разделяются на два класса:

хэш-функции без ключа (MDC (Modification (Manipulation) Detect Code) - коды),

хэш-функции c ключом (MАC (Message Authentication Code) - коды).

 

Хэш-функции без ключа разделяются на два подкласса:

слабые хэш-функции,

сильные хэш-функции.

 

Слабой хэш-функцией назывется односторонняя функция H(x), удовлетворяющая следующим условиям:

аргумент х может быть строкой бит произвольной длины;

значение H(x) должно быть строкой бит фиксированной длины;

значение H(x) легко вычислить;

для любого фиксированного x вычислительно невозможно найти другой x' != x, такой что H(x')=H(x).

Пара x' != x, когда H(x')=H(x) называется коллизией хэш-функции.

 

Сильной хэш-функцией называется односторонняя функция H(x), удовлетворяющая условиям 1-3 для слабой хэш-функции и свойству 4':

4') вычислительно невозможно найти любую пару x' != x, такой что H(x')=H(x).

 

Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 4' говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.

 

Хэш-функцией с ключом (MAC) называется функция H(k,x), удовлетворяющая свойствам:

аргумент х функции H(k,x) может быть строкой бит произвольной длины;

значение H(k,x) должно быть строкой бит фиксированной длины;

при любых k и x легко вычислить H(k,x);

для любого х должно быть трудно вычислить H(k,x) не зная k;

должно быть трудно определить k даже при большом числе неизвестных пар {x, H(k,x)} при выбранном наборе х или вычислить по этой информации H(k,x') для x' != x.

 

//сперто с infobez.ru

 

Если болтать будут и разведчики и погрничники, задача не решается.

Я прав?

нет style_emoticons/default/smile3.gif удостоверяющие центры могут спасти эту ситуацию.

 

Ссылка на комментарий
Поделиться на другие сайты

Заархивировано

Эта тема находится в архиве и закрыта для дальнейших ответов.

×
×
  • Создать...