powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинные сдвиги
25 сообщений из 50, страница 2 из 2
Длинные сдвиги
    #39603374
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
д0кХДля RSA за счет создания уязвимости.

Сила RSA не в медленном делении, а в большом количестве простых чисел в промежутке от p до
q. При его брутфорсе вообще деление не используется.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39603393
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov, попробуй:
1. Выровнять начало массива на размер cache line (обычно 128 байт)
2. Оперировать четырьмя регистрами (rax, rdx, rbx, rcx) над разными частями сдвигаемого массива
3. Использовать инструкцию сдвига SHRD m64,r64,1
Быстрее этого справятся только инструкции из расширенных наборов MMX/SSE
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39603400
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovТогда вопрос: есть ли трюк, позволяющий найти остаток от деления двух
длинных чисел быстрее, чем за M-N вычитаний, где M и N - число бит в делимом и делителе
соответственно? можно заменить операцию нахождения остатка на 2 умножения и 1 вычитание

асимптотически будет быстрее, чем реализация через вычитание столбиком (O(N^2))


Код: plaintext
1.
2.
3.
4.
5.
6.
7.
15  mod 7 = 1

Q  = 100 / 7 = 14
15 * Q = 210   |удаляем последний разряд| -> 21

умножаем на 7 ->     141 |удаляем последний разряд| -> 14
наш остаток:   15 - 14 = 1         

по умножению уже точно есть алгоритмы до O(N*ln(N)) включительно
вычитание O(N)
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39603412
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тьфу

15 * Q = 210 |удаляем 2 последних разряда| -> 2

умножаем на 7 -> 14
наш остаток: 15 - 14 = 1
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39603438
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)асимптотически будет быстрее, чем реализация через вычитание столбиком (O(N^2))

Почему (O(N^2))?

b111111 mod b100 = 111111 - 100000 - 10000 - 1000 - 100 = 11.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39603546
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

а у тебя есть команда которая, например, при 512-битном ключе сразу разницу находит?

это вычитание даёт O1(N/32), и сделать их нужно в общем случае (2N-N) раз
вот и выходит O(N^2)
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39603817
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)Q = 100 / 7 = 14

Насколько я понимаю, чтобы не напороться на ошибки округления, надо брать "100" с большим
запасом: не меньше чем квадрат делителя. А это автоматически приводит к удвоению
разрядности "15 * Q". Надо будет потестить...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39603892
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

ага, по идее так, не проверял
т.е. если если модуль 512-битный, то множитель нужен 2*512 битный

возможно стоит дробную часть не отсекать, там как раз остаток от деления, но не весь

210 -> 10 -> 10*7 = 070 -> 1
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39604196
Вася Уткин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry SibiryakovСреди intrinsic-ов (или подобных трюков) есть возможность быстрых сдвигов нескольких
последовательных целых? Что-нибудь быстрее, чем цикл из
Код: sql
1.
arr[i+1] = arr[i+1] >> 1 | arr[i] << 31



PS: В старом добром ассемблере DEC была идеально подходящая для этого команда сдвига через
флаг переноса...

Пробовал _mm_slli_si128() + _mm_slli_epi64() + _mm_srli_epi64() + _mm_or_si128() ?
Если сдвиг больше, чем на 64 бита, то 2 инструкции, а если меньше, то 4 инструкции.
http://coliru.stacked-crooked.com/a/a9dbd34a8940082b
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39604564
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39604798
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери

ну раз пошла такая пьянка :)
по тынцуОсновное свойство: наибольший общий делитель {\displaystyle m} m и {\displaystyle n} n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6 ; он делится на все общие делители этих чисел: 1, 2, 3, 6.
Следствие 1: множество общих делителей {\displaystyle m} m и {\displaystyle n} n совпадает с множеством делителей НОД(m, n).
Следствие 2: множество общих кратных {\displaystyle m} m и {\displaystyle n} n совпадает с множеством кратных НОК(m, n).
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39604955
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери от же, ещё чуть-чуть и мы бы его переоткрыли
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39605098
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери от же, ещё чуть-чуть и мы бы его переоткрыли

Напомню новую вводную
Dimitry Sibiryakov найти остаток от деления двух
длинных чисел быстрее, чем за M-N вычитаний,
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39605150
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери от же, ещё чуть-чуть и мы бы его переоткрыливажно не путать открытия с откупориваниями (с)
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39605195
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
д0kХ,

авторнайти остаток от деления двух
длинных чисел быстрее, чем за M-N длинных вычитаний,
уже нашли 21203765
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39605746
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)д0kХ,

авторнайти остаток от деления двух
длинных чисел быстрее, чем за M-N длинных вычитаний,
уже нашли 21203765

У меня есть сомнения в истинной этой серебрянности этой пули
авторОднако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при однократном вычислении произведения двух чисел представляется неразумным.



анекдот
К уже переодевшемуся в спортивный костюм
и с довольной рожей наслаждаюшемуся сигаретой Иосифу
возле вагона поезда Москва - Одесса подходят цыгане
и предлагают купить богатый золотой перстень за 40 долларов.
Йося долго торгуется и они сходятся на 30 .
Йося дает им сотку, получает сдачу полтинник и двадцатку.
Йося уезжает в Одессу с фальшивым кольцом и настоящими долларами,
А довольные цигане остаются с фальшивой соткой.

...
Рейтинг: 0 / 0
Длинные сдвиги
    #39605862
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
д0kХУ меня есть сомнения в истинной этой серебрянности этой пули
авторОднако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при однократном вычислении произведения двух чисел представляется неразумным.
всё нормально, алгоритм из разряда немного поднапрячься зато сразу долететь
что для RSA и нужно
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39605875
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)всё нормально, алгоритм из разряда немного поднапрячься зато сразу долететь
что для RSA и нужно

Обычно RSA наоборот используют чисто для разовых вещей типа зашифровать сессионный ключ,
подписать документ и т.п.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39605949
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

в RSA взятие модуля составляет половину алгоритма и выполняется в цикле, вынеси получение n' из основного цикла и используй в цикле уже готовое
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39606088
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)в RSA взятие модуля составляет половину алгоритма и выполняется в цикле

А, ну да, на приватной стороне. На публичной с e=3 достаточно одного-двух.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39606623
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как же я не люблю баги в компиляторах...
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
#include <stdio.h>
#include <intrin.h>

static void Add(uintptr_t* Source, uintptr_t* Dest, size_t n)
{
	unsigned char Carry = 0;
	for (size_t i = 0; i < n; i++)
	{
#ifdef __x86_64__
		Carry = _addcarry_u64(Carry, Source[i], *Dest, Dest);
#else
		Carry = _addcarry_u32(Carry, Source[i], *Dest, Dest);
#endif
		Dest++;
	}
	while (Carry != 0)
	{
#ifdef __x86_64__
		Carry = _addcarry_u64(Carry, 0, *Dest, Dest);
#else
		Carry = _addcarry_u32(Carry, 0, *Dest, Dest);
#endif
		Dest++;
	}
}

int main()
{
   uintptr_t a[] = { -1, -1, -1, -1, 0 };
   uintptr_t b[] = { 1, 0, 0, 0, 0 };
   Add(b, a, 4);
   printf("%x %x %x %x %x\n", a[0], a[1], a[2], a[3], a[4]);
}


TDM-GCC 5.1 с -О[1-3] выдаёт "0 ffffffff ffffffff ffffffff 0" вместо правильного "0 0 0 0
1" (MS VC - результат правильный).

Может кто-нибудь проверить на версии 5.3 или выше?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39606649
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovМожет кто-нибудь проверить на версии 5.3 или выше?5.3.0 - полет нормальный.
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39607341
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakovkealon(Ruslan)в RSA взятие модуля составляет половину алгоритма и выполняется в цикле

А, ну да, на приватной стороне. На публичной с e=3 достаточно одного-двух.
e=3 плохой выбор https://en.wikipedia.org/wiki/Coppersmith's_attack
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39607519
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

тут что то фиксили
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67317
...
Рейтинг: 0 / 0
Длинные сдвиги
    #39607526
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
эти интрисики появились в 5.0, новенькие баги

AFAIK gcc надо использовать стабильные ветки
https://gcc.gnu.org/develop.html#timeline
-4.8.5
-4.9.4
-5.5
-6.4
7 - экспериментальная пока - было много принципиальных изменений по оптимизатору
...
Рейтинг: 0 / 0
25 сообщений из 50, страница 2 из 2
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинные сдвиги
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]