Пьер де Ферма

Тема в разделе "WASM.CRYPTO", создана пользователем f13nd, 7 апр 2022.

  1. f13nd

    f13nd Well-Known Member

    Публикаций:
    0
    Регистрация:
    22 июн 2009
    Сообщения:
    1.699
    Уже успели задолбать с новой-революцинной-атакой-на-рса, которая даже иногда к чему-то подходит.
    https://habr.com/ru/company/timeweb/blog/659215/
    (почему-то в статье приведен портерт Рене Декарта, висящий во всех школах, но пусть этот Ришелье будет Ферма).

    Хоть у кого-нибудь этот Ферма на что-то налез? По-моему со времен Данилки Блехенбахера ничего толкового по сабжу не было.
    Код (Text):
    1. #binSignature003F78        8768E733DF3F1382498C4DE496A8E94FDD6155DC9C2D6B411C69938A24F3D796E2FA9E949CEF522D99BCE483254DCC762DA64F566C2D177BFAA5CF66304ECD68FEC870087EB17C1791CB66C76BABAB2A2B66E7E5642208736855C77D030491D192CD7647D17E6F31A116D3F66E023E5E7991731E6E85CE859D756F07B26454BD
    2. #    binModulus017A13    A3848AC40A3E35105747DDA54577EA3F62D1FFDD7A19EEDBB9F0B9FA104E229908609EF6B5BD455A23618D97A851F9702727ADC3E532D93BCB01F562F6C4C792D538D783EF1E495AA0DE4F0F95F2A9C512DD304A36B7385B849C0A33E5C3A587E36FEFC46574DA8356C3C83F3BFE1FDA3624F823DFFE51C510E99EA5B282AC29
    3. #    exp                    3
    4. #    result                0001FFFFFFFFFFFFFFFF00689F80F03734C4EE3F42A45E5FC30C1DC4978316E2E000000000000000000000000000000000000000000000000000000000000000000000E3CDF671000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    5.  
    6. #MOD_BE        AB3B8C61B683EF65A47854710E1F6FA663908121F36C53E15D19F26609C8F0AF4A7FA3FEC40D4EF0C29F4D8C6C5B5E4D05BD4547F196722A98AA66E2A548A02BFE2A56B84F25B2792989D30F0DF1A156F028A3668C29DA2DE7D4049475A6D4114B8DCAAE7D77C182DB459C37D27C5E0A18AC07CA03D6FDCEAE763BAF53CCBD53
    7. #KEY_BE        0002B6405ECC1BDCBD1D00339760A95EC550D57A95389CA3B4026D0D9D19C13BD9C879AE4BAF8AC3039EE981A6757A12B0E87DBD0E3F9C85F2E432EA4EF64B55BC35D47394D0A4B7E27A1F6FF32CF8E2DAEDE33CC74AF443BB60323CA5CAABC17F25F3004DFADE57DD84C913ACFBAB1011D86D8CEB8435AFB11DA0216204ED03
    8. #SEED_BE    2926541A0063B9A6D5F7B3897C16F1E74653CDB66C37979B7F74E3FCA3DAAAB9A757EEB1D396F206D27BDEE6EE6CA1278D6A049CBE472AD8A123466E913D18390E4DBC615F9307BE0AA7ABBD2346EF284DC9A853B86B66007DC1DBFB46722516B4CFBDFFB8F074B898116E4EA6F6B0DE2F766D04069944762CE31F935C6066BB
    9. #EXP        10001
    10.  
    11.  
    12. import gmpy2
    13. data    = 0x0002B6405ECC1BDCBD1D00339760A95EC550D57A95389CA3B4026D0D9D19C13BD9C879AE4BAF8AC3039EE981A6757A12B0E87DBD0E3F9C85F2E432EA4EF64B55BC35D47394D0A4B7E27A1F6FF32CF8E2DAEDE33CC74AF443BB60323CA5CAABC17F25F3004DFADE57DD84C913ACFBAB1011D86D8CEB8435AFB11DA0216204ED03
    14. exp        = 0x10001
    15. modulus    = 0xAB3B8C61B683EF65A47854710E1F6FA663908121F36C53E15D19F26609C8F0AF4A7FA3FEC40D4EF0C29F4D8C6C5B5E4D05BD4547F196722A98AA66E2A548A02BFE2A56B84F25B2792989D30F0DF1A156F028A3668C29DA2DE7D4049475A6D4114B8DCAAE7D77C182DB459C37D27C5E0A18AC07CA03D6FDCEAE763BAF53CCBD53
    16. #outpt    = (data**exp)%modulus
    17. #print("result=" + hex(outpt))
    18. a = gmpy2.isqrt(modulus)
    19. for x in range(0,0x10000000000000000):
    20.     result=(a-x)*(a+x)
    21.     if result==modulus:
    22.         b = x
    23.         break
    24.     if x & 0xFFFFFF == 0:
    25.         print("x=" + hex(x))
    26. if result==modulus:
    27.     print("found!a=" + a + " b=" + b)
    28. else:
    29.     print("not found")
     
  2. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.147
    f13nd,
    Это разве что к говнокоду на петонах разных применимо. В моей реализации, например, SizeInBits (Abs(P - Q)) >= KeySizeInBits / 2 - 99. И во всех нормальных библиотеках там целая пачка дополнительных условий, которым должны удовлетворять сгенеренные праймы.
     
  3. f13nd

    f13nd Well-Known Member

    Публикаций:
    0
    Регистрация:
    22 июн 2009
    Сообщения:
    1.699
    У меня как бы длинная арифметика на ассемблере выписана, но пофигу настолько, что петон. 32 бита с легкостью пробегает без всяких аптемизаций, в 64 бита не верю.
     
    Последнее редактирование: 7 апр 2022
  4. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    247
    Так он, насколько я помню, проверил огромное число ключей этим методом - там сотни тысяч если не больше и нашёл всего несколько с неудачным выбором который позволил перебору состоятся.
    Для нормальной генерации ключей он сам же и оценивает вероятность выдать уязвимый ключ как ничтожный.