Страшний «криптокаліпсис» (смерть поточного шифрування) може настати раніше, ніж очікувалося, – спричинений обчисленнями в пам’яті ASIC, а не квантовими комп’ютерами, повідомляє Security Week.
Компанія MemComputing із Сан-Дієго досліджує використання ASIC (спеціальних інтегральних схем для обробки в пам’яті) для потенційного зламу 2048-бітного RSA в реальному часі.
MemComputing – це компанія та філософія комп’ютерів, яка зародилася на основі теорії. Теорія полягає в тому, що якщо обробку та дані можна об’єднати в пам’яті, можна подолати так зване вузьке місце фон Неймана. Вузьке місце – це затримка, яка виникає через розділення сховища й обробки, а також, відповідно, необхідність обміну даними між ними.
Зі збільшенням обчислювальної складності час обробки, необхідний класичним комп’ютерам, також збільшується, але експоненціально.
Результатом вузького місця є те, що категорія складних математичних проблем не може бути розв’язана за допомогою класичної системи (базова архітектура фон Неймана) у будь-які значущі часові періоди.
«Серед важкорозв’язних комбінаторних проблем широкомасштабне розкладання на прості множники є загальновідомою проблемою», – пишуть дослідники MemComputing у статті «Збільшення розкладання на прості множники за допомогою самоорганізувальних вентилів: підхід до мемкомп’ютингу».
Саме важкорозв’язність цієї проблеми зберігає теоретичну безпеку шифрування на основі RSA так довго. Справа не в тому, що це математично неможливо, просто це займе надто багато часу, щоб реалізуватися за допомогою класичних комп’ютерів.
Якщо теорію неможливо продемонструвати фактами, проблема та рішення емулюються програмним забезпеченням.
Для зламу RSA:
«Нині ситові методи представляють найсучасніші перспективні алгоритми, причому найефективнішим є метод сита загального поля чисел. Тим не менш, навіть цим методам важко розкласти 2048-бітний ключ RSA протягом розумного періоду часу, а в минулих випадках для того, щоб розкласти 829-бітне число за допомогою комп’ютерних кластерів, знадобилося майже 2700 процесорних років».
Вузьке місце фон Неймана означає, що час до вирішення зростає експоненціально.
«Підраховано, що з поточною технологією, яка використовує найвідоміший алгоритм (general number field sieve, GNFS), розкладання 2048-бітного ключа RSA займе більше часу, ніж вік Всесвіту», – додали дослідники.
Квантові комп’ютери зможуть вирішити цю проблему протягом значного періоду часу. Звідси потяг до більш складних постквантових алгоритмів, здатних продовжувати захищати шифрування, керований NIST.
Оцінки появи квантових комп’ютерів дуже різняться, але зазвичай говорять про «десятиліття».
Компанія MemComputing фактично хотіла знати, скільки часу знадобиться її запатентована обробка в пам’яті, щоб зламати RSA, і чи можна це зробити за коротший період часу, ніж очікування появи квантових комп’ютерів. Основне дослідження було результатом контракту з Повітряними Силами США на дослідження інновацій малого бізнесу (SBIR).
Використаний підхід полягав у застосуванні емуляції програмного забезпечення, зосередженого на тестових задачах від 30 до 150 біт.
«Результати показали, що схема генерувала відповідні конгруенції для задач тестування до 300 біт, а час, необхідний для факторизації, відповідав поліному другого ступеня за кількістю бітів», – оголосили у MemComputing.
Іншими словами, зростання складності розкладання великих чисел за допомогою обчислень у пам’яті збільшує необхідний час набагато повільніше, ніж експоненціальне збільшення, яке дають класичні комп’ютери.
«Наступним кроком є розширення ефективного діапазону за межі 300 біт, що потребує налаштування дизайну SOG для ще більших проблем факторизації з кінцевою метою реалізації можливостей у специфічній інтегральній схемі (ASIC)», – продовжує компанія.
ASIC – це власний чип. Вони вже широко використовуються для різних застосувань. Виробництво цих чипів займає більше часу та коштує дорожче, ніж класичні комп’ютерні мікросхеми загального призначення, але вони в іншій лізі, ніж розробка квантового комп’ютера.
Зокрема, дослідники сказали:
«Повідомляється про терміни реалізації ASIC платформи MEMCPU. Час ASIC можна легко оцінити, оскільки платформа MEMCPU, будучи емулятором схеми, повертає повну динаміку схеми, включно зі змодельованим часом виконання. Варто зазначити, що на цьому етапі наших досліджень і розробок прогноз для ASIC показує можливість вирішення 2048-бітної проблеми факторизації за десятки хвилин».
Цей висновок, звичайно, є швидше теорією, аніж доказовим фактом. Проте теорія ґрунтується на сукупності фактів, і теоретичні дослідження лежать в основі значної частини сьогоднішньої доказової науки.
Раніше ми повідомляли, що Google випускає ключ безпеки, стійкий до квантових атак.
Підписуйтеся на ProIT у Telegram, щоб не пропустити жодну публікацію!
