Бинг говорит что RSA мертв

Тема в разделе "WASM.CRYPTO", создана пользователем sl0n, 28 окт 2023.

  1. sl0n

    sl0n Мамонт дзена **

    Публикаций:
    0
    Регистрация:
    26 сен 2003
    Сообщения:
    692
    Я помню, что мы раньше обсуждали с вами два компьютера: обычный компьютер с процессором Intel Core i7-9700K и квантовый компьютер IBM Quantum System One. Вы хотите знать, сколько времени займет взлом 2048-битного ключа RSA на обоих из них по времени, алгоритмы выберу на свое усмотрение.
    Для обычного компьютера я буду использовать алгоритм решета числового поля, который является одним из самых эффективных классических алгоритмов факторизации. Этот алгоритм имеет субэкспоненциальную сложность [math]O(e^{\sqrt{\log(N)\cdot \log (\log(N))}})[/math], где [math]N[/math] - число, которое нужно факторизовать. Для квантового компьютера я буду использовать алгоритм Шора, который является самым известным квантовым алгоритмом факторизации. Этот алгоритм имеет полиномиальную сложность [math]O(\log^{3}(N))[/math], где [math]N[/math] - число, которое нужно факторизовать.
    Для того, чтобы оценить время работы этих алгоритмов для 2048-битного числа, нам нужно знать скорость компьютеров в операциях в секунду. По данным , процессор Intel Core i7-9700K может выполнить около 240 миллиардов операций в секунду. По данным , квантовый компьютер IBM Quantum System One может выполнить около 1.12 квадриллиона операций в секунду.
    Тогда мы можем оценить время работы каждого алгоритма для 2048-битного числа следующим образом:
    • Для решета числового поля на обычном компьютере мы можем использовать формулу [math]O(e^{\sqrt{\log(N)\cdot \log(\log(N))}})[/math], где [math]N = 2^{2048}[/math]. Тогда количество операций будет равно[math] e^{\sqrt{2048 \cdot \log_{2}(2048)}}=e^{\sqrt{2048 \cdot 11}} ≈e^{150}≈ {\color{Red}{10^{94}}}[/math]. Делим это число на скорость процессора и получаем время работы: [math]\frac{\displaystyle 10^{94} }{\displaystyle 240000000000} ≈ 4\cdot 10^{82}[/math] секунд.
    • Для алгоритма Шора на квантовом компьютере мы можем использовать формулу [math]O(\log^{3}(N))[/math], где [math]N = 2^{2048}[/math]. Тогда количество операций будет равно [math](\log_{2}(2^{2048}))^{3} = (2048\cdot \log_{2}(2))^{3} = 2048^{3} ≈ 8\cdot 10^{9}[/math]. Делим это число на скорость компьютера и получаем время работы: [math]\frac{\displaystyle 8\cdot 10^{9}}{\displaystyle 1120000000000} ≈ 0.007[/math] секунды.
    Таким образом, мы видим, что алгоритм Шора на квантовом компьютере работает примерно в 6×1084 раз быстрее, чем решето числового поля на обычном компьютере для взлома 2048-битного ключа RSA. Однако, это только теоретическая оценка, которая не учитывает возможные ошибки, шумы, переключения контекста и другие факторы, которые могут повлиять на реальную производительность алгоритмов. Кроме того, эта оценка зависит от выбора конкретных моделей компьютеров и алгоритмов, и может измениться при других условиях.

    Для того, чтобы оценить время работы алгоритмов факторизации для 64-килобитного числа, нам нужно использовать те же формулы и параметры компьютеров, что и для 2048-битного числа. Единственное отличие - это размер числа [math]N[/math], который теперь равен 265536. Тогда мы можем оценить время работы каждого алгоритма следующим образом:
    • Для решета числового поля на обычном компьютере мы можем использовать формулу [math]O(e^{\sqrt{\log(N)\cdot \log(\log(N))}})[/math], где [math]N = 2^{65536}[/math]. Тогда количество операций будет равно [math]e^{\sqrt{65536 \cdot \log_{2}(65536)}}=e^{\sqrt{65536 \cdot 16}}=e^{1024} ≈ {\color{Red}{10^{10000}}}[/math]. Делим это число на скорость процессора и получаем время работы: [math]\frac{\displaystyle 10^{10000}}{\displaystyle 240000000000} ≈ 4\cdot 10^{9988}[/math] секунд.
    • Для алгоритма Шора на квантовом компьютере мы можем использовать формулу [math]O(\log^{3}(N))[/math], где [math]N = 2^{65536}[/math]. Тогда количество операций будет равно [math](\log_{2}(2^{65536}))^{3} = (65536\cdot \log_{2}(2))^{3} = 65536^{3} ≈ 3\cdot 10^{14}[/math]. Делим это число на скорость компьютера и получаем время работы: [math]\frac{\displaystyle 3\cdot 10^{14}}{\displaystyle 1120000000000} ≈ 0.3[/math] секунды.
    Таким образом, мы видим, что алгоритм Шора на квантовом компьютере работает примерно в 109990 раз быстрее, чем решето числового поля на обычном компьютере для взлома 64-килобитного ключа RSA. Однако, это только теоретическая оценка, которая не учитывает возможные ошибки, шумы, переключения контекста и другие факторы, которые могут повлиять на реальную производительность алгоритмов. Кроме того, эта оценка зависит от выбора конкретных моделей компьютеров и алгоритмов, и может измениться при других условиях.

    Знающие люди по квантовы объясните, что там за квантовые ошибки и как с ними борются. Правильно ли все бинг посчитал?
     
  2. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.343
    Квантовня не дает точных ответов. Только вероятность, что точный ответ внутри заданного тобой диапазона.
     
  3. Application

    Application Active Member

    Публикаций:
    1
    Регистрация:
    15 окт 2022
    Сообщения:
    110
  4. TrashGen

    TrashGen ТрещГен

    Публикаций:
    0
    Регистрация:
    15 мар 2011
    Сообщения:
    1.173
    Адрес:
    подполье
    А чо мы будем готовить жрать пока это там всё триллион секунд ламаеццо?,)
     
  5. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.146
  6. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.741
  7. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    377
    спросите у бигна сколько надо Q-бит для того самого взлома
    потом спросите какие сейчас есть в реале Q-PC и думаю все станет ясно
    и да, еще цену спросите
     
  8. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    569
    Как эти квантовые калькуляторы вообще работают?
    Как ЭВМ работают, я понимаю, понимаю и элементарный уровень, уровень логических элементов, транзисторов, электрический полей в них. А вот как эти тупые кубиты... что-то там вращается, как-то вычисляется. Типа в бочку насыпали транзисторов, диодов, сопротивлений и всё это электролитом залили и это как-то заработало(читал в каком-то фантастическом рассказе). Главное, как эти кубиты выполняют довольно сложный код по взлому не слишком простого алгоритма, тут я вообще в осадке.
     
  9. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    377
    а еще кубитам вооще пофиг на пространство - один кубит может общаться с другим что находиться за сотни миллионов световых лет
    получается теория ипштейна - гуано полное? он же бил себя в грудину что макс скорость в мире = скорость света
     
  10. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.343
    Не может. Квантовая запутанность это вообще про другое и никакие законы там не нарушаются.
     
  11. sl0n

    sl0n Мамонт дзена **

    Публикаций:
    0
    Регистрация:
    26 сен 2003
    Сообщения:
    692
    Ну так я и спрашивал это 65 кубитный айбиэм так считает, против какого-то топового десктопа
     
  12. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    377
    там все законы физики нарушаются
    учен↨е вообще в панике
     
  13. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    449
    Если вкрации, то это как бы аналоговые вычислительные машины, которые базированы на квантовых эффектах.
    Главный квантовый так сказать эффект который тут интересен - это "расщепление" квантовых состояний в суперпозиции.
    Тут можно немного отойти к истории вопроса и вспомнить например про https://ru.wikipedia.org/wiki/Формулировка_квантовой_теории_через_интегралы_по_траекториям - фишка в том, что фотон проходящий через щелевой эксперимент даже вот с формальной матанской точки зрения путешествует по всем возможным путям и вероятностный результат который экспериментатор в конце концов измерит определяется суммами вероятностей всех путей. Здесь уже прослеживается важный момент который главную роль в квантовой криптографии играет - частица как будто бы распараллелилась и из разных своих вариантов дала общую картину (здесь же можно увидеть уши многомировой интерпретации Эверетта).
    Так вот квантовый прибор оперирует кубитами как аналогами битов (физически это спины каких то частиц там) и там подбираются такая конструкция и смысл физического эксперимента что они действительно будут соответствовать битам в битовых операциях (очень ограниченного толка, но подходящего для взлома RSA прям идеально).
    Так вот такие приборы считают все возможные комбинации бит в этом процессе одновременно! Здесь нет перебора по всем комбинациям, потому что сразу за O(1) перебираются все комбинации. Ну и конечно главная заумная хитрость, что каким то заумным способом там делается такой прикол, что итоговая комбинация _вероятнее всего_ будет именно той которая крякнет RSA-шифр. Опять таки это не 100% как и всё в квантовом мире, но если 1000 раз повторить этот O(1), то с вероятностью 99% в каком то измерении проскочит правильный ответ. А его проверить уже тривиально и легко на классическом компуктере.
    P.S.
    Я бы поэтому сказал еще так, что если верить в многомировую интерпретацию, то квантовый взлом RSA - это когда мы в изначальной вселенной запускаем расчёт, он расходится в разных вариантах для данного куска мультивселенной внутри этого чипа по бесчисленному сонму вариантов этого чипа в триллиардах триллионов (и т.п.) вселенных считающих разные переборы шифра, но у квантовых эффектов есть способность "вытащить" из этих вселенных полезный результат с очень хорошей вероятностью которая сугубо практична. Это за счёт вот этих вот квантовых сцеплений и прочей квантовой мистики. Ну дай бог дай бог.

    Ну и еще проще говоря - квантовый компуктер способен делать брутфорс некоторых задач за O(1).
     
    Последнее редактирование: 29 окт 2023
  14. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.146
    aa_dav, ну-это всё в реалиях розовых фэнтези, конечно, работает.. в наших же Бренных км-ка катит лишь на спортлото :grin: и ещё вот нехороший Вопрос хочу задать: а аким дикобразом можно получить отдельный фотон/электрон.. вот технически это как? :):blush2:
     
  15. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    569
    aa_dav, понятно.:scratch_one-s_head:
    Да нихрена не понятно!!! Что такое аналоговый компьютер я ещё понимаю, но вообще непонятно как натягивают алгоритм на эти дурацкие кубиты. И ещё, а можно ли задачу о 19 ферзях натянуть на эти кубиты, и будут ли это быстро работать? Хотя всё равно не понятно, тут уже высший матан, а у меня с ним плоховато.:mda:
    Но зато понятно, что этот квантовый калькулятор, как и всякая аналоговая ВТ сильно специализирована, тут даже нет смысла делать для широкого употребления, + реально многие до конца эту вундервафлю не понимают, и сильно это всё распиарено. Лучше бы оптоэлектронику создавали, 3д процессор из миллионы ядер, частота сотни ГГц, штука для взлома весьма прекрасна, как и для млрд других задач. А взломы, взломы лучше делать методом воровства пароля.
     
  16. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.146
    у аналоговой машины решение задачи == её мин энергетическому состоянию. в плане классификации, км-ки можно отнести к АМ, но в реале это лишь генераторы случайных чисел и не более того/
    впрочем, уж дико дорогая лотто машина получается, а вот грандиозные успехи в разложение чисел..
     
  17. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    449
    Вот чтобы понять как именно натягивают на кубиты нужно лет пять отучится на факультете с глубоким изучением квантовой физики и потом еще полгода изучать конкретику этого алгоритма Шора.
    Это к сожалению уже слишком заумно. Настолько, что сами ученые предлагают способы этот алгоритм улучшить, а потом ломают копья на тему того работает это улучшение или всё ломает. Была с год назад такая история.
    Но вот если его описание по шагам посмотреть: https://ru.wikipedia.org/wiki/Алгоритм_Шора
    то один из первых шагов это:
    а один из последних шагов это:
    Классический компьютер, как я выше говорил, просто проверят, что то состояние которые измерил прибор действительно ли соответствует желаемому решению (оно вероятностно и лишь тяготеет к правильному ответу). Проверить является ли разложение простого числа на множители верным намного проще и линейно по сложности в отличие от задачи нахождения этого разложения.
    А суть и мякотка всего - что квантовое вычисление "идёт по всем путям", "считает сразу все возможные ответы в мультивселенной" отталкиваясь от "суперпозиции всех возможных битовых состояний входа" и вот это вот всё.
     
  18. SilverStorm

    SilverStorm Member

    Публикаций:
    0
    Регистрация:
    7 дек 2010
    Сообщения:
    116
  19. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    143
    Не надо проверять - простое число нельзя разложить на множители по определению.
    Разве что в перпендикулярных вселенных...
     
  20. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    449
    Описка конечно же. Хотел написать на простые множители.