ЭЦП с короткой подписью

Тема в разделе "WASM.CRYPTO", создана пользователем scf, 14 дек 2011.

  1. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    Существуют ли надежные алгоритмы ЭЦП, генерирующие короткую (меньше 256 бит) подпись?
    Алгоритмы, которые я смотрел (RSA/DSA/Эль-Гамаль) генерируют подпись с длиной не меньше длины ключа.
     
  2. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    Все подписи строятся на вычислительно задачах, а это следующие задачи:
    1. FACTOR - факторизация
    2. RSAP - проблема RSA
    3. SQRTP - нахождение корня
    4. DLP - логарифмирование
    5. GDLP - обобщенное DLP
    6. DHP - Диффи-Хеллман
    7. GDHP - думаю понятно что
    8. KSP - рюкзак (постоянно модифицируется и взламывается)
    9. CTP - на базе кодирования

    Во всех выше перечисленных задачах, должны использоваться достаточно большие модули, что-бы
    алгоритмы решения этих задач не смогли сработать за приемлемое время.
    Что касается вопроса, последнее время появилось много работ на криптосистемы, построенных на
    помехоустойчивых кодах, как следствие есть и алгоритмы подписи, попробуйте поискать именно
    в этом направлении.
     
  3. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    Спасибо!
    Я еще нашел white-box cryptography - тоже может быть интересно.
     
  4. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    А может для Вашей модели угроз достаточно MAC (например, HMAC) ?
     
  5. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    Это не подпись)
     
  6. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    h0t
    Создаем ключ для AES - это будет приватный ключ
    Внедряем этот ключ в алгоритм дешифрования AES - это будет публичный ключ. По концепции, из полученного алгоритма невозможно извлечь ключ.

    Для подписывания сообщения считается хеш и шифруется приватным ключом.
    Для проверки любой желающий может дешифровать хеш публичным алгоритмом дешифрования.

    Чем не подпись? :)
     
  7. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    OLS
    К сожалению нет - в моем случае проверяющая сторона untrusted, так что ей секретный ключ знать нельзя
     
  8. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    К сожалению тут и оно что можно.
     
  9. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    h0t
    Я что-то не понимаю в концепции? идея whitebox в этом же и состоит - по известному алгоритму и ключу получить такой шифрующий этим ключом алгоритм, из которого невозможно за разумное время извлечь этот ключ?
     
  10. T800

    T800 Member

    Публикаций:
    0
    Регистрация:
    7 дек 2006
    Сообщения:
    293
    Адрес:
    Moscow
    scf
    А чем вас не устраивают 1024 бита RSA ?
    Почему вы считаете 1024 бита слишком расточительными?
     
  11. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    T800
    Идея в том, чтобы сделать генератор серийников, устойчивый к взлому.
    Как это обычно делается? берется незащищенный ключ с кодом приложения и уникальным номером и подписывается каким-нибудь алгоритмом.
    В итоге мы получаем "ключевые файлы" с устрашающим wall of text.

    Другой пример - Microsoft product key. Он представляет из себя 32 бита данных (код продукта и номер) + 80-битную подпись - в итоге мы имеем 25 символов ключа. Это уже допустимо, но 80 бит RSA ломается, и существующие кейгены ключей для винды это наглядно доказывают.
    Подробности тут если кому интересно: http://www.licenturion.com/xp/fully-licensed-wpa.txt

    Сильно смущает то, что с точки зрения blackbox 32 бит для валидации ключа более чем достаточно, и в итоге можно генерить приличные красивые серийники длиной в 14-15 символов. НО - проверять, разумеется, только на сервере, т.к. для простых алгоритмов по алгоритму проверки ключа очень легко написать кейген.

    Так что исходный вопрос можно сформулировать так: существует ли не обратимый за полиномиальное время алгоритм шифрования, работающий с блоком данных 64 бита?
     
  12. T800

    T800 Member

    Публикаций:
    0
    Регистрация:
    7 дек 2006
    Сообщения:
    293
    Адрес:
    Moscow
    scf
    Последние 6 лет "ключевые файлы" принято формировать в виде файлов, а не строки из буковок. И к этому обстоятельству юзвери уже привыкли.
    Так что ваши аргументы про 64 бита кажутся не обоснованными.
     
  13. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    T800
    Не суть важно - буковки снаружи или внутри :)

    Ключевые файлы зло - т.к. придется каждой домохозяйке объяснять, что с ними делать, а не каждая домохозяйка сможет самостоятельно открыть диск Ц в проводнике...

    Так что лучший вариант - серийник достаточной длины, что его можно было бы на крайняк переписать на бумажку и ввести.
     
  14. T800

    T800 Member

    Публикаций:
    0
    Регистрация:
    7 дек 2006
    Сообщения:
    293
    Адрес:
    Moscow
    scf
    Какой вы консерватор то.
    Уже все домохозяйки привыкли копировать X.509 в буфер.
    Кстати, в "котейнер" RSA 1024 бит (PKCS#1 v1.5) можно положить 117 байт полезной информации, а не только 16..32 байт хеш-суммы. Так что задумайтесь.
     
  15. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    scf
    Короткая цифровая подпись.. я видел алгоритм BLS-signature (Boneh-Lynn-Shacham-2001)..
    BLS в основе своей использует криптографию на эллиптических кривых, в качестве ЭЦП выступает точка на элл-й кривой.
    Если взять модуль эллип-й кривой в 160 бит, то ЭЦП будет 161 бит...
     
  16. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    386
    gorodon
    Спасибо, сейчас заценим :)
    http://libeccio.dia.unisa.it/projects/jpbc/download.html
    Java - найдется всё (С)