Ускорение проверки цифровых подписей

Я понимаю, что загрузка и проверка blockchain занимает много времени.
Что касается проверки, я считаю, что большая часть времени тратится проверки цифровых подписей.
Кто-нибудь смотрело на пакетной проверке подписей ECDSA?
Вот отправная точка: http://cse.iitkgp.ac.in/~abhij/publications/AfricaCrypt12-ECDSA-bv.pdf

PS: После беглой проверки, я не нашел реализацию этих algotirthms.

Удар. Нам нужна математика доска.

Клиент не использует "быстрый" возможно осуществление. Он просто использует стандартную OpenSSL реализацию эллиптической кривой.

Должны сбалансировать скорость против безопасности.

Идея пакетной системы звучит круто, хотя. Похоже, что он работает только тогда, когда тот же открытый ключ используется для всех подписей?

Цитата: TierNolan 22 января 2014 года, 2:30:46 PM

Идея пакетной системы звучит круто, хотя. Похоже, что он работает только тогда, когда тот же открытый ключ используется для всех подписей?

См уравнение 3 наивным Алгоритм, так как точка кривой умножение с отмеченной точкой Р выполняется только один раз за партию подписей, которые она предлагает по крайней мере, около 2х с ускорением в любом случае.

Цитата: prezbo 22 января 2014 года, 4:57:20 PM

Они имеют проблему, что подпись (R, S), который является 2 целых чисел (по модулю р).

Вам нужно проверить

сумма (R) = сумма (и * G) + сумма (v * Q)

или

сумма (R) = сумма (и) * G + сумма (v * Q)

Проблема заключается в том, что вы не имеете R. параметр г х-коорд из R.

R означает у ^ 2 = г ^ 3 + а * R + B по модулю р

Это дает 2 г для каждого значения г.

Они предлагают пытаются все перестановки.

Если вы делаете партию 4, что дает 16 попыток найти R.

сумма (и) * G => 3 целое число, добавляет и точка умножить
сумма (v * Q) => 4 точки умножает и 3 точка добавляет

Каждый R догадка требует 3 очка добавляют и 8 на среднее средства 24 пункта добавляет.

Это также требует квадратный корень шаг.

Всего
5 точек умножает
27 пункт добавляет

Нормальный:
8 точек умножает
1 пункт добавить

Метод пакетного имеет 3 меньше размножается, но более 19 добавляет.

Что такое относительное время добавляет и размножается?

Цитата: TierNolan 22 января 2014 года, 5:44:41 PM

Что такое относительное время добавляет и размножается?

Использование двойной и добавьте один умножение с п требует O (журнал (п)) дополнения. Я не думаю, что есть более эффективные методы.

Добавление еще немного к г-значений для определения точки на кривой будет очень элегантное решение, то рассмотреть, если это обеспечивает значительное улучшение.

Цитата: prezbo 22 января 2014 года, 6:08:23 PM

Использование двойной и добавьте один умножение с п требует O (журнал (п)) дополнения. Я не думаю, что есть более эффективные методы.

Это log2? Если да, то умножьте "расходы" 128 добавляет?

котировка

Добавление еще немного к г-значений для определения точки на кривой будет очень элегантное решение, то рассмотреть, если это обеспечивает значительное улучшение.

Время пропорционально количеству уникальных открытых ключей. Для Bitcoin, все транзакции будут иметь различные открытые ключи, так что скорость вверх не больше 2X.

Соответствующая часть введения:

"В этой статье мы предлагаем три алгоритма для проверки оригинальных подписей ECDSA в пакетах. Наши алгоритмы применяются ко всем случаям подписей ECDSA разделяющих одни и те же параметры кривой, хотя мы получаем хорошие цифры SpeedUp, когда все подписи в партии из того же подписавшего.
Наши алгоритмы эффективны только для небольших объемов партий

Цитата: TierNolan 22 января 2014 года, 7:23:01 PM

Цитата: prezbo 22 января 2014 года, 6:08:23 PM

Это log2? Если да, то умножьте "расходы" 128 добавляет?

Да, это было бы двоичный логарифм.

Цитата: TierNolan 22 января 2014 года, 7:23:01 PM

Это правильно, вопрос в том, является ли это достаточно, чтобы возиться с ним.

Цитата: prezbo 22 января 2014 года, 7:28:01 PM

Это правильно, вопрос в том, является ли это достаточно, чтобы возиться с ним.

Я не думаю, что это будет главным приоритетом. Обычай Bitcoin кривого кода дает гораздо больший эффект без использования потенциально небезопасный метода.

Цитата: prezbo 22 января 2014 года, 4:57:20 PM

К сожалению, чтобы вернуться к этому вопросу ... Глядя на уравнение (3), это относится к ситуации, в которых можно повторно использовать адреса, поведение мы недавно имели нить о (это не рекомендуется). Это делает меня подозрительным

Цитата: deuteragenie 22 января 2014 года, 7:23:54 PM

Соответствующая часть введения:
"В этой статье мы предлагаем три алгоритма для проверки оригинальных подписей ECDSA в пакетах. Наши алгоритмы применяются ко всем случаям подписей ECDSA разделяющих одни и те же параметры кривой, хотя мы получаем хорошие цифры SpeedUp, когда все подписи в партии из того же подписавшего.
Наши алгоритмы эффективны только для небольших объемов партий

Так я понять это ускорение путем признания подписей конкретного ключа в пределах одного блока?

Цитата: Altoidnerd 22 января 2014 года, 8:49:27 PM

Цитата: prezbo 22 января 2014 года, 4:57:20 PM

Повторное использование адреса обеспечат дополнительный прирост скорости, но 2x будет гарантирован даже с уникальными адресами.

Было бы хорошо, если бы была реализация этого доступна где-то, чтобы попытаться выяснить, что может быть фактическая скорость вверх, как это не представляется возможным, по современной архитектуре процессора, чтобы определить скорость до путем подсчета числа добавляет / мулов. К сожалению, я не был в состоянии определить реализацию.

Цитата: TierNolan 22 января 2014 года, 7:41:34 PM

Обычай Bitcoin кривого кода дает гораздо больший эффект без использования потенциально небезопасный метода.

Является ли это так пользовательский код, который СИП используется в текущей реализации?

Почему вы говорите, что техника является потенциально "небезопасный" ? Это будет использоваться только для проверки подписей на blockchain, как это может быть "небезопасный" ?
Проверка подписи может быть полностью протестирована на эталонную реализацию (OpenSSL и сип), поэтому вероятность неправильной проверки подписей (либо объявлять их действительными, если они не являются, или наоборот) является очень низким.

Цитата: Altoidnerd 22 января 2014 года, 8:49:27 PM

Так я понять это ускорение путем признания подписей конкретного ключа в пределах одного блока?

Тест подписи требует 2 точки умножений. Одним из них является умножение точки генерации (G), а другой с помощью открытого ключа (Q).

Предполагая, что вы проверяете 4 подписи, обычно проверьте:

R1 = a1 * G + b1 * Q
R2 = а2 * G + b2 * Q
R 3 = а3 * G + b3 + Q
R 4 = а4 * G + b4 + Q

Это может быть упрощено до

(R1 + R2 + R3 + R4) = (a1 + a2 + a3 + a4) * G + (b1 + b2 + b3 + b4) + Q

Добавление точки и нормальное целое число, сложение является (относительно) очень быстро. Это уменьшает количество размножается до 2, независимо от того, сколько подписей.

Однако, если Q отличается для каждой подписи (разные открытого ключа), то вы можете только уменьшить сложность (a1 + a2 + a3 + a4) * G. Итак, в лучшем случае половина размножается устраняются в этом случае.

Цитата: deuteragenie 23 января 2014 года, 8:58:31 AM

Почему вы говорите, что техника является потенциально "небезопасный" ? Это будет использоваться только для проверки подписей на blockchain, как это может быть "небезопасный" ?
Проверка подписи может быть полностью протестирована на эталонную реализацию (OpenSSL и сип), поэтому вероятность неправильной проверки подписей (либо объявлять их действительными, если они не являются, или наоборот) является очень низким.

Метод, безусловно, передать действительные подписи.

Я был обеспокоен тем, что может быть способом подписать недействительные подписи каким-то образом.

Из Google, авторы представили систему, которая использует "Randomisers", Это говорит о том, что их первоначальная схема имела некоторый потенциал (или фактическую) слабость.

проверить

А = В
С = Д

слабее, что просто проверка

А + С = В + D,

Будет ли это работать?

Он основан на "Хитрость Шамира",

Единственные операции ЕС являются двойными и добавить. Это позволяет создать умножение.

а = а0 + а1 * 2 ^ 1 + а2 * 2 ^ 2 + .... ан-1 * 2 ^ (п-1)

который может быть упрощена

а = а0 + 2 * (a1 + 2 * (a2 + 2 * (... ан-1)))

аО затем может быть выражено как

аО = а0 * G + 2 * (а1 * G + 2 * (а2 * G + 2 * (.... ан-1 + G)))

Это стандартное двойное и добавить правило. Вы начинаете с MSB и работать в обратном направлении.

Я буду считать 3 битовые числа, которые не должны уменьшить аргумент.

аО = а0 * G + 2 * (а1 * G + 2 * (а2 * С))
Ьо = b0 * Q + 2 * (b1 * Q + 2 * (b2 * Q))

Ag + Ьо = а0 * G + 2 * (а1 * G + 2 * (а2 * G)) + b0 * Q + 2 * (b1 * Q + 2 * (b2 * Q))

перестраивать
аО + Ьо = (a0 * G + b0 * Q) + 2 * (а1 * G + 2 * (а2 * G)) + 2 * (b1 * Q + 2 * (b2 * Q))

Коэффициент на 2
Ag + Ьо = (а0 * G + b0 + Q) + 2 * (а1 * G + 2 * (а2 + G) + b1 * Q + 2 * (b2 * Q))

перестраивать
Ag + Ьо = (а0 * G + b0 + Q) + 2 * ((а1 * G + b1 * Q) + 2 * (а2 + G) + 2 * (b2 * Q))

Коэффициент на 2
Ag + Ьо = (а0 * G + b0 + Q) + 2 * ((а1 * G + b1 * Q) + 2 * (a2 * G + b2 * Q))

Эффект в том, что вы можете справиться суммой 2 продуктов с таким же числом удвоений как единое удвоение.

Примечание: умножить на a0, b1 и т.д. на самом деле не размножается, поскольку они одиночные битовые числа. Вы умножить на 1 или 0.

Во всяком случае, для пакетного режима, который, кажется, чтобы дать эквивалентный импульс.

R1 = a1 * G + b1 * Q
R2 = а2 * G + b2 * Q
R 3 = а3 * G + b3 + Q
R 4 = а4 * G + b4 + Q

превращается в

R1 + R2 + R3 + R4 = a1 * G + b1 * q1 + а2 * G + b2 * Q2 + а3 * G + b3 * Q3 + а4 * G + b4 * В4

Даже с различными открытыми ключами вы можете получить повышение в скорости.

Я не уверен, почему вы определили Q_К в конечной стадии.

Кроме того, я считаю, что это алгебра хорошо, но я не уверен, компьютер сможет
переставить блок, как это на самом деле в результате чего скорость вверх.

Нам нужен анализ конкретного языка компьютера или просто тест, чтобы увидеть, если что-нибудь случится быстрее.

Цитата: Altoidnerd 23 января 2014 года, 7:29:53 PM

Я не уверен, почему вы определили Q_К в конечной стадии.

У меня был пойти на кодирование Это.

Результаты находятся

Надувной замок: 2,5 мс на проверить

Наивная Реализация: 3,3 проверить

Пакетные: 1.0ms в проверить

Это 2.5X быстрее. Если оно сочеталось с внутренними уловок, которые Надувной замок делать, то, возможно, было бы скорость 4-5X Надувной замка.

Результаты партии показывают, что Calcs EC то, что занимает время, поэтому сырое время ЕС ограничено.

Это означает, что рандомизации вещь может быть возможно.

Это экономит много размножается, но он делает это, делая много добавляет.

Я также вычислить R напрямую, так что не придется сделать несколько попыток, чтобы найти решение.

Вау! Впечатляет, как быстро вы сделали это!

- Я полагаю, что добавление может быть ускорено в баунти замок, потому что параметр «A» равно нулю для кривой BC.
- Эта часть кода интересно:

для (Int J = 255; J >= 0; j--) {
         сумма = sum.twice ();
         для (INT I = 0; я < Len; я ++) {
            если (u2.TESTBIT (к)) {
               Сумма = sum.add (Q);
            }
         }
      }

Я не знаю, сколько «если» и «TESTBIT» стоимость метода, но теоретически они могут быть заменены символическим выражением оценщиком, за счет обхода дерева и несколько указателей. Не уверен, что будет самым быстрым.

- Я не уверен, является ли «атака» на пакетной проверке применяется к использованию подписных проверок в blockchain в контексте нашей эры. Предположительно, можно применить партия проверить до, скажем, последние 1000 блоков, а затем перейти к отдельным проверкам.

Цитата: deuteragenie 23 января 2014, 10:20:07 PM

Вау! Впечатляет, как быстро вы сделали это!

Спасибо, но это в основном то, что бодрый библиотека замка имеет библиотеку точки ЕС, построенную в.

Кроме того, формула просто "работал", Я ожидал, час или два отладки, по крайней мере.

котировка

- Я полагаю, что добавление может быть ускорено в баунти замок, потому что параметр «A» равно нулю для кривой BC.

Не знаю. Похоже, что добавление фактически не зависит от параметров кривых, удачливым.

котировка

- Эта часть кода интересно:

для (Int J = 255; J >= 0; j--) {
         сумма = sum.twice ();
         для (INT I = 0; я < Len; я ++) {
            если (u2.TESTBIT (к)) {
               Сумма = sum.add (Q);
            }
         }
      }

Я не знаю, сколько «если» и «TESTBIT» стоимость метода, но теоретически они могут быть заменены символическим выражением оценщиком, за счет обхода дерева и несколько указателей. Не уверен, что будет самым быстрым.

Java не действительно указатели, как это. Тем не менее, я думаю, что Calcs ЕС, вероятно, является ограничивающим фактором, так что не имеет значения.

Тест бит, вероятно, реализован в виде поиска массива + битовой маски.

котировка

- Я не уверен, является ли «атака» на пакетной проверке применяется к использованию подписных проверок в blockchain в контексте нашей эры. Предположительно, можно применить партия проверить до, скажем, последние 1000 блоков, а затем перейти к отдельным проверкам.

Не знаю. Существует документ, который говорит о том, защищая его с помощью случайных чисел.

Вы умножать u1 (I) и u2 (I) константой. Это означает, что вы должны умножить R (I) по той же постоянной, хотя, так что означает, что LHS имеет больше Calcs тоже.

22 января 2014, 11:29:05 AM	# 1
deuteragenie Сообщений: 36 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Взлом Биткоин адресов. 500 Биткоинов взломаны в "мозговом кошельке" с паролем "bitcoin is awesome" Адрес кошелька: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE Приватный ключ: 5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6e подробнее... Всем кто хочет заработать Биткоины без вложений - рекомендую сайт http://bitcoin-zarabotat.ru Я понимаю, что загрузка и проверка blockchain занимает много времени. Что касается проверки, я считаю, что большая часть времени тратится проверки цифровых подписей. Кто-нибудь смотрело на пакетной проверке подписей ECDSA? Вот отправная точка: http://cse.iitkgp.ac.in/~abhij/publications/AfricaCrypt12-ECDSA-bv.pdf PS: После беглой проверки, я не нашел реализацию этих algotirthms.

22 января 2014, 1:26:50 PM	# 2
Altoidnerd Сообщения: 406 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Получил 1806 Биткоинов Реальная история. Удар. Нам нужна математика доска.

22 января 2014, 2:30:46 PM	# 3
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Клиент не использует "быстрый" возможно осуществление. Он просто использует стандартную OpenSSL реализацию эллиптической кривой. Должны сбалансировать скорость против безопасности. Идея пакетной системы звучит круто, хотя. Похоже, что он работает только тогда, когда тот же открытый ключ используется для всех подписей?

22 января 2014, 4:57:20 PM	# 4
prezbo Сообщения: 430 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: TierNolan 22 января 2014 года, 2:30:46 PM Идея пакетной системы звучит круто, хотя. Похоже, что он работает только тогда, когда тот же открытый ключ используется для всех подписей? См уравнение 3 наивным Алгоритм, так как точка кривой умножение с отмеченной точкой Р выполняется только один раз за партию подписей, которые она предлагает по крайней мере, около 2х с ускорением в любом случае.

22 января 2014, 5:44:41 PM	# 5
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: prezbo 22 января 2014 года, 4:57:20 PM См уравнение 3 наивным Алгоритм, так как точка кривой умножение с отмеченной точкой Р выполняется только один раз за партию подписей, которые она предлагает по крайней мере, около 2х с ускорением в любом случае. Они имеют проблему, что подпись (R, S), который является 2 целых чисел (по модулю р). Вам нужно проверить сумма (R) = сумма (и * G) + сумма (v * Q) или сумма (R) = сумма (и) * G + сумма (v * Q) Проблема заключается в том, что вы не имеете R. параметр г х-коорд из R. R означает у ^ 2 = г ^ 3 + а * R + B по модулю р Это дает 2 г для каждого значения г. Они предлагают пытаются все перестановки. Если вы делаете партию 4, что дает 16 попыток найти R. сумма (и) * G => 3 целое число, добавляет и точка умножить сумма (v * Q) => 4 точки умножает и 3 точка добавляет Каждый R догадка требует 3 очка добавляют и 8 на среднее средства 24 пункта добавляет. Это также требует квадратный корень шаг. Всего 5 точек умножает 27 пункт добавляет Нормальный: 8 точек умножает 1 пункт добавить Метод пакетного имеет 3 меньше размножается, но более 19 добавляет. Что такое относительное время добавляет и размножается?

22 января 2014, 6:08:23 PM	# 6
prezbo Сообщения: 430 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: TierNolan 22 января 2014 года, 5:44:41 PM Что такое относительное время добавляет и размножается? Использование двойной и добавьте один умножение с п требует O (журнал (п)) дополнения. Я не думаю, что есть более эффективные методы. Добавление еще немного к г-значений для определения точки на кривой будет очень элегантное решение, то рассмотреть, если это обеспечивает значительное улучшение.

22 января 2014, 7:23:01 PM	# 7
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: prezbo 22 января 2014 года, 6:08:23 PM Использование двойной и добавьте один умножение с п требует O (журнал (п)) дополнения. Я не думаю, что есть более эффективные методы. Это log2? Если да, то умножьте "расходы" 128 добавляет? котировка Добавление еще немного к г-значений для определения точки на кривой будет очень элегантное решение, то рассмотреть, если это обеспечивает значительное улучшение. Время пропорционально количеству уникальных открытых ключей. Для Bitcoin, все транзакции будут иметь различные открытые ключи, так что скорость вверх не больше 2X.

22 января 2014, 7:23:54 PM	# 8
deuteragenie Сообщений: 36 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Соответствующая часть введения: "В этой статье мы предлагаем три алгоритма для проверки оригинальных подписей ECDSA в пакетах. Наши алгоритмы применяются ко всем случаям подписей ECDSA разделяющих одни и те же параметры кривой, хотя мы получаем хорошие цифры SpeedUp, когда все подписи в партии из того же подписавшего. Наши алгоритмы эффективны только для небольших объемов партий

22 января 2014, 7:28:01 PM	# 9
prezbo Сообщения: 430 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: TierNolan 22 января 2014 года, 7:23:01 PM Цитата: prezbo 22 января 2014 года, 6:08:23 PM Использование двойной и добавьте один умножение с п требует O (журнал (п)) дополнения. Я не думаю, что есть более эффективные методы. Это log2? Если да, то умножьте "расходы" 128 добавляет? Да, это было бы двоичный логарифм. Цитата: TierNolan 22 января 2014 года, 7:23:01 PM Время пропорционально количеству уникальных открытых ключей. Для Bitcoin, все транзакции будут иметь различные открытые ключи, так что скорость вверх не больше 2X. Это правильно, вопрос в том, является ли это достаточно, чтобы возиться с ним.

22 января 2014, 7:41:34 PM	# 10
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: prezbo 22 января 2014 года, 7:28:01 PM Это правильно, вопрос в том, является ли это достаточно, чтобы возиться с ним. Я не думаю, что это будет главным приоритетом. Обычай Bitcoin кривого кода дает гораздо больший эффект без использования потенциально небезопасный метода.

22 января 2014, 8:49:27 PM	# 11
Altoidnerd Сообщения: 406 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: prezbo 22 января 2014 года, 4:57:20 PM См уравнение 3 наивным Алгоритм, так как точка кривой умножение с отмеченной точкой Р выполняется только один раз за партию подписей, которые она предлагает по крайней мере, около 2х с ускорением в любом случае. К сожалению, чтобы вернуться к этому вопросу ... Глядя на уравнение (3), это относится к ситуации, в которых можно повторно использовать адреса, поведение мы недавно имели нить о (это не рекомендуется). Это делает меня подозрительным Цитата: deuteragenie 22 января 2014 года, 7:23:54 PM Соответствующая часть введения: "В этой статье мы предлагаем три алгоритма для проверки оригинальных подписей ECDSA в пакетах. Наши алгоритмы применяются ко всем случаям подписей ECDSA разделяющих одни и те же параметры кривой, хотя мы получаем хорошие цифры SpeedUp, когда все подписи в партии из того же подписавшего. Наши алгоритмы эффективны только для небольших объемов партий Так я понять это ускорение путем признания подписей конкретного ключа в пределах одного блока?

22 января 2014, 10:20:41 PM	# 12
prezbo Сообщения: 430 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: Altoidnerd 22 января 2014 года, 8:49:27 PM Цитата: prezbo 22 января 2014 года, 4:57:20 PM См уравнение 3 наивным Алгоритм, так как точка кривой умножение с отмеченной точкой Р выполняется только один раз за партию подписей, которые она предлагает по крайней мере, около 2х с ускорением в любом случае. К сожалению, чтобы вернуться к этому вопросу ... Глядя на уравнение (3), это относится к ситуации, в которых можно повторно использовать адреса, поведение мы недавно имели нить о (это не рекомендуется). Это делает меня подозрительным Повторное использование адреса обеспечат дополнительный прирост скорости, но 2x будет гарантирован даже с уникальными адресами.

23 января 2014, 8:58:31 AM	# 13
deuteragenie Сообщений: 36 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Было бы хорошо, если бы была реализация этого доступна где-то, чтобы попытаться выяснить, что может быть фактическая скорость вверх, как это не представляется возможным, по современной архитектуре процессора, чтобы определить скорость до путем подсчета числа добавляет / мулов. К сожалению, я не был в состоянии определить реализацию. Цитата: TierNolan 22 января 2014 года, 7:41:34 PM Обычай Bitcoin кривого кода дает гораздо больший эффект без использования потенциально небезопасный метода. Является ли это так пользовательский код, который СИП используется в текущей реализации? Почему вы говорите, что техника является потенциально "небезопасный" ? Это будет использоваться только для проверки подписей на blockchain, как это может быть "небезопасный" ? Проверка подписи может быть полностью протестирована на эталонную реализацию (OpenSSL и сип), поэтому вероятность неправильной проверки подписей (либо объявлять их действительными, если они не являются, или наоборот) является очень низким.

23 января 2014, 9:48:50 AM	# 14
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: Altoidnerd 22 января 2014 года, 8:49:27 PM Так я понять это ускорение путем признания подписей конкретного ключа в пределах одного блока? Тест подписи требует 2 точки умножений. Одним из них является умножение точки генерации (G), а другой с помощью открытого ключа (Q). Предполагая, что вы проверяете 4 подписи, обычно проверьте: R1 = a1 * G + b1 * Q R2 = а2 * G + b2 * Q R 3 = а3 * G + b3 + Q R 4 = а4 * G + b4 + Q Это может быть упрощено до (R1 + R2 + R3 + R4) = (a1 + a2 + a3 + a4) * G + (b1 + b2 + b3 + b4) + Q Добавление точки и нормальное целое число, сложение является (относительно) очень быстро. Это уменьшает количество размножается до 2, независимо от того, сколько подписей. Однако, если Q отличается для каждой подписи (разные открытого ключа), то вы можете только уменьшить сложность (a1 + a2 + a3 + a4) * G. Итак, в лучшем случае половина размножается устраняются в этом случае.

23 января 2014, 9:51:57 AM	# 15
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: deuteragenie 23 января 2014 года, 8:58:31 AM Почему вы говорите, что техника является потенциально "небезопасный" ? Это будет использоваться только для проверки подписей на blockchain, как это может быть "небезопасный" ? Проверка подписи может быть полностью протестирована на эталонную реализацию (OpenSSL и сип), поэтому вероятность неправильной проверки подписей (либо объявлять их действительными, если они не являются, или наоборот) является очень низким. Метод, безусловно, передать действительные подписи. Я был обеспокоен тем, что может быть способом подписать недействительные подписи каким-то образом. Из Google, авторы представили систему, которая использует "Randomisers", Это говорит о том, что их первоначальная схема имела некоторый потенциал (или фактическую) слабость. проверить А = В С = Д слабее, что просто проверка А + С = В + D,

23 января 2014, 5:37:35 PM	# 16
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Будет ли это работать? Он основан на "Хитрость Шамира", Единственные операции ЕС являются двойными и добавить. Это позволяет создать умножение. а = а0 + а1 * 2 ^ 1 + а2 * 2 ^ 2 + .... ан-1 * 2 ^ (п-1) который может быть упрощена а = а0 + 2 * (a1 + 2 * (a2 + 2 * (... ан-1))) аО затем может быть выражено как аО = а0 * G + 2 * (а1 * G + 2 * (а2 * G + 2 * (.... ан-1 + G))) Это стандартное двойное и добавить правило. Вы начинаете с MSB и работать в обратном направлении. Я буду считать 3 битовые числа, которые не должны уменьшить аргумент. аО = а0 * G + 2 * (а1 * G + 2 * (а2 * С)) Ьо = b0 * Q + 2 * (b1 * Q + 2 * (b2 * Q)) Ag + Ьо = а0 * G + 2 * (а1 * G + 2 * (а2 * G)) + b0 * Q + 2 * (b1 * Q + 2 * (b2 * Q)) перестраивать аО + Ьо = (a0 * G + *b0 Q*) + 2 (а1 * G + 2 * (а2 * G)) + 2 * (b1 * Q + 2 * (b2 * Q)) Коэффициент на 2 Ag + Ьо = (а0 * G + b0 + Q) + 2 * (*а1 G + 2 * (а2 + G) + b1 * Q + 2 * (b2 * Q)*) перестраивать Ag + Ьо = (а0 G + b0 + Q) + 2 * ((а1 * G + *b1 Q*) + 2 (а2 + G) + 2 * (b2 * Q)) Коэффициент на 2 Ag + Ьо = (а0 * G + b0 + Q) + 2 * ((а1 * G + b1 * Q) + 2 * (*a2 G + b2 * Q*)) Эффект в том, что вы можете справиться суммой 2 продуктов с таким же числом удвоений как единое удвоение. Примечание: умножить на a0, b1 и т.д. на самом деле не размножается, поскольку они одиночные битовые числа. Вы умножить на 1 или 0. Во всяком случае, для пакетного режима, который, кажется, чтобы дать эквивалентный импульс. R1 = a1 G + b1 * Q R2 = а2 * G + b2 * Q R 3 = а3 * G + b3 + Q R 4 = а4 * G + b4 + Q превращается в R1 + R2 + R3 + R4 = a1 * G + b1 * q1 + а2 * G + b2 * Q2 + а3 * G + b3 * Q3 + а4 * G + b4 * В4 Даже с различными открытыми ключами вы можете получить повышение в скорости.

23 января 2014, 7:29:53 PM	# 17
Altoidnerd Сообщения: 406 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Я не уверен, почему вы определили Q_К в конечной стадии. Кроме того, я считаю, что это алгебра хорошо, но я не уверен, компьютер сможет переставить блок, как это на самом деле в результате чего скорость вверх. Нам нужен анализ конкретного языка компьютера или просто тест, чтобы увидеть, если что-нибудь случится быстрее.

23 января 2014, 9:56:46 PM	# 18
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: Altoidnerd 23 января 2014 года, 7:29:53 PM Я не уверен, почему вы определили Q_К в конечной стадии. У меня был пойти на кодирование Это. Результаты находятся Надувной замок: 2,5 мс на проверить Наивная Реализация: 3,3 проверить Пакетные: 1.0ms в проверить Это 2.5X быстрее. Если оно сочеталось с внутренними уловок, которые Надувной замок делать, то, возможно, было бы скорость 4-5X Надувной замка. Результаты партии показывают, что Calcs EC то, что занимает время, поэтому сырое время ЕС ограничено. Это означает, что рандомизации вещь может быть возможно. Это экономит много размножается, но он делает это, делая много добавляет. Я также вычислить R напрямую, так что не придется сделать несколько попыток, чтобы найти решение.

23 января 2014, 10:20:07 PM	# 19
deuteragenie Сообщений: 36 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Вау! Впечатляет, как быстро вы сделали это! - Я полагаю, что добавление может быть ускорено в баунти замок, потому что параметр «A» равно нулю для кривой BC. - Эта часть кода интересно: для (Int J = 255; J >= 0; j--) { сумма = sum.twice (); для (INT I = 0; я < Len; я ++) { если (u2.TESTBIT (к)) { Сумма = sum.add (Q); } } } Я не знаю, сколько «если» и «TESTBIT» стоимость метода, но теоретически они могут быть заменены символическим выражением оценщиком, за счет обхода дерева и несколько указателей. Не уверен, что будет самым быстрым. - Я не уверен, является ли «атака» на пакетной проверке применяется к использованию подписных проверок в blockchain в контексте нашей эры. Предположительно, можно применить партия проверить до, скажем, последние 1000 блоков, а затем перейти к отдельным проверкам.

23 января 2014, 10:38:05 PM	# 20
TierNolan Сообщения: 1148 Цитировать по имени цитировать ответ	Re: Ускорение проверки цифровых подписей Цитата: deuteragenie 23 января 2014, 10:20:07 PM Вау! Впечатляет, как быстро вы сделали это! Спасибо, но это в основном то, что бодрый библиотека замка имеет библиотеку точки ЕС, построенную в. Кроме того, формула просто "работал", Я ожидал, час или два отладки, по крайней мере. котировка - Я полагаю, что добавление может быть ускорено в баунти замок, потому что параметр «A» равно нулю для кривой BC. Не знаю. Похоже, что добавление фактически не зависит от параметров кривых, удачливым. котировка - Эта часть кода интересно: для (Int J = 255; J >= 0; j--) { сумма = sum.twice (); для (INT I = 0; я < Len; я ++) { если (u2.TESTBIT (к)) { Сумма = sum.add (Q); } } } Я не знаю, сколько «если» и «TESTBIT» стоимость метода, но теоретически они могут быть заменены символическим выражением оценщиком, за счет обхода дерева и несколько указателей. Не уверен, что будет самым быстрым. Java не действительно указатели, как это. Тем не менее, я думаю, что Calcs ЕС, вероятно, является ограничивающим фактором, так что не имеет значения. Тест бит, вероятно, реализован в виде поиска массива + битовой маски. котировка - Я не уверен, является ли «атака» на пакетной проверке применяется к использованию подписных проверок в blockchain в контексте нашей эры. Предположительно, можно применить партия проверить до, скажем, последние 1000 блоков, а затем перейти к отдельным проверкам. Не знаю. Существует документ, который говорит о том, защищая его с помощью случайных чисел. Вы умножать u1 (I) и u2 (I) константой. Это означает, что вы должны умножить R (I) по той же постоянной, хотя, так что означает, что LHS имеет больше Calcs тоже.

Заголовок