ЛКС35
LCS35 — это криптографическая задача и головоломка, поставленная Роном Ривестом в 1999 году. Задача состоит в том, чтобы вычислить значение
где t — определенное 14-значное (или 47-битное) целое число, а именно 79685186856218, а n — определенное 616-значное (или 2048-битное) целое число, которое является произведением двух больших простых чисел (которые не указаны). Затем значение w можно использовать для расшифровки зашифрованного текста z , еще одного целого числа из 616 цифр. Открытый текст предоставляет скрытую информацию о факторизации n , что позволяет легко проверить решение.
Идея задачи заключается в том, что единственный известный способ найти значение w, не зная факторизации n, — это последовательное возведение в квадрат. Значение t было выбрано таким образом, чтобы для этого грубого расчета потребовалось около 35 лет, используя в качестве отправной точки скорости чипа 1999 года и принимая во внимание закон Мура . Ривест отмечает, что «так же, как несоблюдение закона Мура может сделать головоломку сложнее, чем предполагалось, прорыв в искусстве факторинга сделает головоломку проще, чем предполагалось».
Задача была поставлена (и получила свое название) на праздновании 35-летия Лаборатории компьютерных наук Массачусетского технологического института, которая теперь является частью Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института .
Задача LCS35 была решена 15 апреля 2019 года, двадцать лет спустя, программистом Бернаром Фабротом. [1] [2] Открытый текст начинается с «!!! С Днем Рождения LCS !!!». [3]
14 мая 2019 года Рональд Л. Ривест опубликовал новую версию LCS35 (названную CSAIL2019), чтобы расширить головоломку до 2034 года. [4]
Ссылки
[ редактировать ]- ^ «Криптоголоволомка LCS35 с блокировкой времени» (PDF) . люди.csail.mit.edu .
- ^ «Программисты решают криптографическую головоломку MIT 20-летней давности | MIT CSAIL» . www.csail.mit.edu .
- ^ «20-летняя крипто-головоломка MIT LCS35 Time Capsule решена - Страница 3 - mersenneforum.org» . www.mersenneforum.org . Проверено 5 июня 2019 г.
- ^ «Описание крипто-головоломки Time Capsule CSAIL2019» . люди.csail.mit.edu .