12.4 C
Москва
Пятница, 14 августа, 2020

Наше мнение

Китай надеется, что Трамп не победит, Россия пытается оклеветать Байдена, Иран распространяет дезинформацию

Представители американской разведки считают, что Российская Федерация использует различные меры для клеветы на кандидата в президенты от демократов Джо Байдена в преддверии президентских выборов...

Как Tesla станет самой дорогой автомобильной компанией в мире

Вчера стоимость акции Tesla подскочила на 900 долларов, что внезапно повысило рыночную стоимость компании до 168,5 миллиарда долларов. Аналитики разделились: одни говорят, что акции...

Новое исследование одобрено в лечении коронавируса

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

Стоимость тройской унции золота достигла исторического максимума

Уже в середине июля золото стало самой выгодной валютой для продажи, так как средняя цена тройской унции достигла 1.800$. Стремительный скачок продолжается до сих...

5 продуктов, провоцирующих появление морщин

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

«Лукашенко из любимца масс стал человеком, которого ненавидят белорусы»

«Лукашенко отрицает, что кто-то может быть против него, и приравнивает своих оппонентов к врагам государства. Это плохие люди, которые действуют в интересах иностранных сил...

На что жалуются российские туристы на отдыхе

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

Канада наносит ответный удар по продукции США

«В то время, когда мы сталкиваемся с пандемией, работая по обе стороны канадско-американской границы, чтобы предотвратить гибель людей и защитить рабочие места, торговый спор...

Теория случайности может быть ключом к безопасности в Интернете

Этот вопрос был центральным в криптографии на протяжении тысячелетий и лежит в основе усилий по обеспечению конфиденциальности частной информации в Интернете. В новой статье исследователи Cornell Tech определили проблему, являющейся ключом к тому, может ли быть нарушено все шифрование, а также удивительную связь с математической концепцией, целью которой является определение и измерение случайности.

«Наш результат не только показывает, что криптография имеет «материнскую» проблему, но также показывает глубокую связь между двумя совершенно разными областями математики и информатики – криптографией и алгоритмической теорией информации», – рассказывает Рафаэль Пасс, профессор компьютерных наук в Cornell Tech.

Пасс является соавтором книги «Об односторонних функциях и колмогоровской сложности», которая будет представлена на симпозиуме IEEE по основам информатики 16-19 ноября в Дареме, штат Северная Каролина.

«Результатом, – сказал он, – является то, что вычислительная проблема, возникшая в 1960-х годах в Советском Союзе, характеризует осуществимость базовой криптографии – например, шифрование личным ключом, цифровой подписью и аутентификацией».

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

Например, легко зажечь спичку, но невозможно вернуть горящую спичку в ее прежнее состояние, не переставив атомы.

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

Но исследователи не смогли доказать существование односторонней функции. Наиболее известный кандидат, который также является основой наиболее часто используемых схем шифрования в Интернете, полагается на целочисленную факторизацию. Легко умножить два случайных простых числа – например, 23 и 47 – но значительно сложнее найти эти два фактора, кроме как с учетом их произведения.

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

«Центральный вопрос, стоявший перед такой задачей: существует ли такой алгоритм? Есть ли какая-то естественная проблема, которая характеризует существование односторонних функций? Если это обнаружат, мы получим способ решить проблему и получить возможность сломать все предполагаемые односторонние функции. В противном случае мы можем получить безопасную криптографию» – говорит Пасс.

Между тем математики в 1960-х годах определили так называемую сложность Колмогорова, которая относится к количественному определению количества случайности или последовательности чисел. Колмогоровская сложность строки чисел определяется как длина самой короткой компьютерной программы, которая может генерировать строку; для некоторых строк, таких как 121212121212121212121212121212, существует короткая программа, которая генерирует ее – альтернативные 1 и 2. Но для более сложных и явно случайных строк чисел, таких как 37539017332840393452954329, может не существовать программы, которая короче длины самой строки.

Проблема давно интересовала математиков и компьютерщиков, в том числе Юриса Хартманиса, почетного профессора информатики и инженерии. Поскольку компьютерная программа, пытающаяся сгенерировать это число, может занять миллионы или даже миллиарды лет, исследователи в Советском Союзе в 1960-х годах, а также Хартманис и другие в 1980-х годах разработали ограниченную во времени сложность Колмогорова – самую короткую программу, которая может выводить строку чисел за определенное время.

В статье Пасс и аспирант Яньи Лю показали, что если вычисление ограниченной по Колмогорову сложности сложно, то односторонние функции существуют.

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

«Если вам удастся придумать алгоритм, чтобы решить ограниченную во времени проблему сложности Колмогорова, то вы можете взломать все крипто, все схемы шифрования, все цифровые подписи», – сказал Пасс. «Однако, если не существует эффективного алгоритма для решения этой проблемы, вы можете получить одностороннюю функцию, и, следовательно, вы можете получить безопасное шифрование, цифровые подписи и так далее».

Поделиться:

ОСТАВЬТЕ КОММЕНТАРИЙ

Please enter your comment!
Please enter your name here

Последние новости

Трофимовский мост в Саратове планируют открыть к 1 октября

В столице региона продолжаются работы по масштабному обновлению Трофимовского путепровода. Движение по мосту полностью перекрыто. Открытие проезда по мосту планируют уже 15 августа. Полностью...

Ливни с сильным ветром ожидаются в Нижегородской области

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

Туристам запретили посещать кипарисовое озеро в анапском экопарке

Из-за засушливой погоды водоем в экопарке пересох и на его восстановление на данный момент не хватает природных ресурсов. Поэтому деревья сейчас находятся под угрозой....

Что предупредит о критическом ухудшении состояния здоровья

Он подчеркнул, что признаки наблюдаются, если у человека есть серьезные хронические заболевания. По его словам, если человек страдает сердечной недостаточностью, то примерно за два...

Власти Кузбасса сняли запрет на выезд из региона

Теперь жители региона могут свободно выезжать за пределы области. Однако есть один нюанс. По возвращении граждане будут обязаны отправиться на двухнедельную самоизоляцию. Правда такое...