пришел звиздец RSA

Discussion in 'WASM.CRYPTO' started by volodya, Feb 17, 2007.

  1. flankerx

    flankerx New Member

    Blog Posts:
    0
    Joined:
    Jul 2, 2004
    Messages:
    423
    Location:
    Moscow, Russia
    SWR
    давай померяемся успехами -)

    сколько 512-битных ключей RSA ты лично разложил? :)
     
  2. volodya

    volodya wasm.ru

    Blog Posts:
    0
    Joined:
    Apr 22, 2003
    Messages:
    1,169
    SWR тут понаписывал, конечно, просто веселуху. С другой стороны, PageFault первым начал хамить. Поэтому, ребята, оба замолкаем. Хватит тут ругаться. Иначе погремушки отберу.
     
  3. OLS

    OLS New Member

    Blog Posts:
    0
    Joined:
    Jan 8, 2005
    Messages:
    322
    Location:
    Russia
    М-да, весело тут у вас - давненько такого не было

    Вот только объясните мне, непонятливому, зачем для хранения данных использовать асимметричную криптографию ?
     
  4. SWR

    SWR New Member

    Blog Posts:
    0
    Joined:
    May 11, 2006
    Messages:
    226
    Location:
    Russia
    flankerx
    Я не раскладываю большие числа.

    ECk
    T2:T1 ~ log2(N):log2(e)
    Че за формула? Для чего?
    На харде например можно сдлать умножение (32 разряда) за 32 такта (как вшколе в столбик)
    , а можно и за 1 такт.
    Например x1*x2*x3*x4 можно решить за 4 такта, а мона и за 2 (пирамидкой разместить) , а если перелапатить умножители в один многоходовый - то и за 1 такт.
    Так что об точном времени тут говорить нельзя (если конвеер то можно добить
    ся нуля)

    Может просто маркетинг (ща полно бестолковых вещей)
    Использовать можно например для логов, пишется инфа последовательно (прочитать может тока хозяин)

    volodya
    Я и несобирался ругаться (просто в игнор людей с удаффа)
    А в чем виселуха (втом что пишут в нипопад?)?
     
  5. ECk

    ECk Member

    Blog Posts:
    0
    Joined:
    Apr 9, 2004
    Messages:
    454
    Location:
    Russia
    SWR
    Ты собрался за такт делать умножение 512 бит на 512 бит?
    Возведение в степень по модулю ты за такт не сделаешь при таких размерах модуля.
    А формула означает что время на чтение у тебя будет гораздо больше чем время на запись. EFS кстати (виндовская шифрующая файловая система) поступает как все нормальные (данные шифруются симметричной криптографией и ключом FEK - File Encryption Key, который затем закрывается RSA с модулем до 4096 бит).
    Длинные числа никакими "пирамидками" не умножают. Если интересно, на mathworld.wolfram.com посмотри Karatsuba multiplication method.
     
  6. CreatorCray

    CreatorCray Member

    Blog Posts:
    0
    Joined:
    Aug 5, 2006
    Messages:
    201
    ECk
    >> P & Q при выборе являются safeprime (P-1)/2 = prime, (Q-1)/2 = prime.
    Кстати даже MS_STRONG_PROV из CryptoAPI из комплекта Win2003 Ent генерит только unsafe primes
     
  7. SWR

    SWR New Member

    Blog Posts:
    0
    Joined:
    May 11, 2006
    Messages:
    226
    Location:
    Russia
    ECk
    Нет конечно (я же указывал 32 разрада)
    А Karatsuba (вроде русский) как раз позволяет заменить умножение больших на несколько более мелких

    А где она хранит ключи RSA?
     
  8. ECk

    ECk Member

    Blog Posts:
    0
    Joined:
    Apr 9, 2004
    Messages:
    454
    Location:
    Russia
    ключи EFS защищены ключом, созданным на базе пароля пользователя, хранится в виде PKCS #12 в хранилище сертификатов
     
  9. flankerx

    flankerx New Member

    Blog Posts:
    0
    Joined:
    Jul 2, 2004
    Messages:
    423
    Location:
    Moscow, Russia
    Понятно... Ну поделись тогда источником, откуда ты позаимствовал высказанные тут мысли иидеи.. про 128-битный RSA, про факторизацию и т.п.

    А то получается странно: сам не раскладывал, а другим байки всяческие рассказываешь =)
     
  10. SWR

    SWR New Member

    Blog Posts:
    0
    Joined:
    May 11, 2006
    Messages:
    226
    Location:
    Russia
    Я щас нашол способ в 2 раза уменьшить словарь до (90 метров (вместо 800) на все 32х разрядные простые числа)
    + рар жмет еще на 40%

    почти у всех простых чисел есть зеркальные
    например (не попарядку):
    11 - 13
    23 - 29
    43 - 53
    71 - 113
    Есть сами на себя:
    73
    17
    31
    Хотя нашол исключение (пока это 19 - 25) но для перебора это не влияет
    P.S. На больших это тоже работает. проверял на всем наборе 2^32 всего их 203 280 221
    Вроде выборка хорошая
     
  11. crypto

    crypto Active Member

    Blog Posts:
    0
    Joined:
    Dec 13, 2005
    Messages:
    2,533
    SWR
    Смелое утверждение. А где определение зеркальности?
     
  12. SWR

    SWR New Member

    Blog Posts:
    0
    Joined:
    May 11, 2006
    Messages:
    226
    Location:
    Russia
    Переведи в двоичное представление и переверни
    пример:

    101010010011 2707 - простое
    110010010101 3221 - тоже простое

    Есть исключения но их довольно мало (и для перебора невлияет)

    Это я заметил раскладывая числа на блиское двочному представлению

    таже фигня с умножением
    pq = другим pq тоже простым (исключений пока ненашол).


    P.S. могу статистику выложить по простым числам. Нужна?
     
  13. flankerx

    flankerx New Member

    Blog Posts:
    0
    Joined:
    Jul 2, 2004
    Messages:
    423
    Location:
    Moscow, Russia
    Забавно. Если p1*q1 = p2*q2, то p1,q1,p2 и q2 не могут быть простыми. По определению простого числа.
     
  14. SWR

    SWR New Member

    Blog Posts:
    0
    Joined:
    May 11, 2006
    Messages:
    226
    Location:
    Russia
    В смысле если перевернуть ))
     
  15. PageFault

    PageFault New Member

    Blog Posts:
    0
    Joined:
    Mar 5, 2007
    Messages:
    31
    Атаки на unsafe primes для реальных размеров ключей не актуальны (оказываются более трудоемки, чем GNFS). Вот материал на эту тему:
    http://www.rsa.com/rsalabs/node.asp?id=2217
     
  16. crypto

    crypto Active Member

    Blog Posts:
    0
    Joined:
    Dec 13, 2005
    Messages:
    2,533
    SWR
    Первый раз вижу определение в повелительном наклонении.
    Хочу уточнить формулировку теоремы: что означает почти все?
     
  17. SWR

    SWR New Member

    Blog Posts:
    0
    Joined:
    May 11, 2006
    Messages:
    226
    Location:
    Russia
    Это не теорема, а замеченая мной свойтво
    Исключения например 19 - 25
    Просто для сжатия словаря можно вычеркнуть все зеркальные числа


    Вот забацал статистику
    Можно сказать что скопление простых чисел уменьшается
    В маштабе скорее всего по экспоненте, тока вот какой маштаб?
    но график из 1000 точек похож - но не такой резкий.
     
  18. ECk

    ECk Member

    Blog Posts:
    0
    Joined:
    Apr 9, 2004
    Messages:
    454
    Location:
    Russia
    зеркальность не выдерживает элементарной критики:
    Сказано:
    101010010011 2707 - простое
    110010010101 3221 - тоже простое
    Теперь смотрим с точки зрения 16 битного слова
    0000101010010011 2707 - простое
    0000110010010101 3221 - тоже простое
    Зеркальности уже нет.

    Что то мне эти методы напоминают (Ubivits)
     
  19. crypto

    crypto Active Member

    Blog Posts:
    0
    Joined:
    Dec 13, 2005
    Messages:
    2,533
    ECk
    Они не напоминают математику :)
     
  20. SWR

    SWR New Member

    Blog Posts:
    0
    Joined:
    May 11, 2006
    Messages:
    226
    Location:
    Russia
    я говорил не о конкретной записи, а о числе в бинарном виде (пирамидка).

    Просто в модели представлении чилсла (где это я это заметил) доп. нули никак неотрожаются (только расстояния)
    Хотя с точки записи для компа ты прав.