У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.
Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.
Максимально дубовая реализация монтгомери вместе с делением по Лемиру улучшила мой результат с 27,223 до 21,820 . Даже обидно как-то, получается раньше я вообще не в ту сторону смотрел. Но теперь до первых мест рукой подать, скорее всего можно те же вызовы _mullo_epi32 в два раза реже делать (у меня на 1 mulmod 3 simd умножения, из которых только два полноценное, и одно урезанное), или от бранча для переполнения вычитания как-то отказаться, его обработка съедает четверть всего времени. Теоретически можно оптимально распланировать умножения по битам степени, и вместо маскировки делать их только тогда когда нужно, это тоже может дать до трети всего времени (умножаем только на половину всех битов).
Да, проверяю по 4 числа одновременно. Главное заранее отсекать большую часть работы (5/6) проверкой на делимость на маленькие делители, довольно красиво сделано, но видимо можно сделать лучше, я использовал для больших libdivide_u32_do_vec256, а для маленьких (2,3,5,7) сообразил трюк с _mm256_shuffle_epi8. Тоже в восторге от результатов первой тройки. Ах да, еще нужно чтение через mmap организовать, в справке от сайта есть пример.
Все так говорят (на один символ отправка 8 байт если между ними меньше ~20ms), пробежал по коду и не вижу ничего противоречащего этому. Тестить правда лень, если хотите оспорить — wireshark/tcpdump вам в помощь.
подмешивается немного мусора
Действительно в прошлом году появился патч и опция в конфиге, мне интересно, а в вашем дистрибутиве есть эта опция? (проще всего проверить man ssh_config; /Obf)
Презентация про ssh, тут статья. Текст об этом на хабре, но я не рекомендую ни комментарии ни статью: там какая-то отсебятина про visual feedback.
Но в таком случае происходит утечка данных не только о тайминге нажатий, но и о количестве клавиш, что соответствует длине пароля
Вместе с таймингом утекает и длина пароля, ответных пакетов со стороны сервера не нужно.
В комментариях тоже какая-то дичь, например: (проблема не в комментарии или в комментаторе, а в том что его никто не поправил, так и висит).
в SSH автоматически включается Nagel's и передаваемые символы начинают группироваться и объединяться, что портит хакерам весь праздник
/* Informs that the current session is interactive. Sets IP flags for that. */
void
ssh_packet_set_interactive(struct ssh *ssh, int interactive, int qos_interactive, int qos_bulk)
{
...
set_nodelay(state->connection_in);
...
}
/* disable nagle on socket */
void
set_nodelay(int fd)
{
...
if (setsockopt(fd, IPPROTO_TCP, TCP_NODELAY, &opt, sizeof opt) == -1)
error("setsockopt TCP_NODELAY: %.100s", strerror(errno));
}
Статья про анализ серверного "пинга" со стороны собеседника в IM.
Напишу на тот случай если кто-то не понимает какую конкретно безопасность обеспечивает E2EE и для/от кого. Для любого мессенджера с моментальной доставкой сообщений и без серьёзного "замусоривания" траффика легко понять кто с кем общается используя глобальное наблюдение (без MitM) и элементарные корреляции.
Пусть пользователь A, B живут в стране, где некие вредоносные агенты Е установили специальное оборудование сохраняющее метаданные всего оконечного трафика на всех провайдерах связи. Пусть агенты E знают A, но не знают B, про B известно что он один из множества U.
Теперь каждый раз когда A пишет сообщение B, он инициирует обмен сетевым трафиком с серверами напрямую (Telegram), через peer-to-peer сеть(Tor), либо даже с использованием туннеля с дополнительным шифрованием ( Wireguard или OpenVPN). Но во всех популярных любительских сценариях использования (за редким исключением вроде i2p) размеры пакетов меняются крайне предсказуемо, а то и не меняются вовсе. Теперь E, зная паттерны трафика нового сообщения (а в случае push уведомлений можно опираться и на ip-подсеть как на показатель пуша), запоминает текущее время.
Затем это сообщение должно прийти B, где ситуации повторится. Так как множество людей из U могут получить подобный трафик случайно, E может лишь ограничить размер множества U - даже для довольно таки большого окна доставки в минуты (типично для пуш-уведомлений) с каждым сообщением размер U будет сокращаться в разы, если не в десятки. Для однозначного установления B потребуется около 27 бит информации (|U|~=1.4e8), что вполне себе достижимо при регулярном общении. Даже если утекать будут малые доли бита (т.е. агенты E очень не уверены в том что произошло общение), из того что нам их нужно собрать буквально десятки, при достаточном количестве сообщений легко вычислить весь граф общения.
Эту картину не меняет даже вменяемый false-positive (пусть например фоном запущенный ютуб раз в 15 секунд даёт картину похожую на сообщение, тогда мы должны учесть шанс того что A ничего не отправлял). В таком случае мы не выкидываем кандидатов из U, а честно обновляем ожидания по Байесу. Если проделать подобное в итоге получатся что граф общения оказывается (ребро между вершинами если они общаются) равен попарной временной корреляции "интересного" трафика относительно U.
Подправив параметры можно узнать например на какие каналы в youtube вы подписаны не залезая в шифрованный трафик, достаточно посмотреть корреляцию жирного потока на сервера гугла с расписанием публикации новых видео, (если вы конечно открываете их сразу по уведомлению).
Да, это вычислительно сложная задача, но явно не сложнее подсчета условного PageRank-a для поискового индекса с MapReduce, естественно считать в лоб (O(|U|^2)) нельзя.
Слайды про утечку пользователя по паролю при наборе его используя SSH (не совсем в тему, но идея похожая)
Определение местоположения пользователя популярных "защищенных" мессенджеров
Тут исследователи не пользуются глобальным мониторингом траффика, смотрят только на раундтрипы оповещения о доставке.
P.S. Задумался над тем что бы комментарий до статьи добить, но об подобном на хабре уже писали еще в 2011 (в контексте Tor, Tarzan и Morphmix).
Еще я сомнительным способом генерировал случайное целое, uniform_uint64() % (HI-LO) + LO В районе 10^18 там уже значительный перекос в пользу меньших чисел.
Было бы любопытно узнать, как график ведёт себя на бесконечности
Прогнал Монте-Карло на равномерных неупорядоченных парах, (это не точно учтёт пары где x=y, но так как их немного, погрешность должна быть небольшой).
Просто взял p:=cnt_good/cnt_iters; estimate:=81*10^{d-2}*p/2;
Скорость симуляции получилась около 5 миллиардов итераций в секунду, что не впечатляет. Пришлось немного попотеть что бы правильно работать с 36-значными числами.
@cuda.jit
def cuda_run_core(A, oA, oB, B):
B0 = B // BASE
pos = cuda.grid(1)
if pos + 1 < A.size:
b_lo = A[pos]
b_hi = A[pos + 1]
for b in range(b_lo, b_hi):
if b % BASE == 0:
continue
rb = rev(b)
a0 = uint64(math.ceil(rb * 1.0 * B / b))
for a in range(a0, a0 + BASE):
if not (B0 <= a < B):
continue
ra = rev(a)
err = uint64(a * b - rb * B)
if err == ra:
oA[pos] = a
oB[pos] = b
if err > B:
break
Проверяет все до m=12 за минуту на видюшке. Посмотрим что будет с m=14 через пару часов.
Hidden text
@cuda.jit(device=True)
def cuda_rev(x):
r = uint64(0)
while x > 0:
r = r * BASE + x % BASE
x = x // BASE
return uint64(r)
def run_cuda(d):
# 10 -> 0.638
# 11 -> 6.601
# 12 -> 68.787
# 13 -> 775.907
num = 2**18
A = np.linspace(pow(BASE, d - 1), pow(BASE, d), num).astype(np.uint64)
oA, oB = np.zeros_like(A), np.zeros_like(A)
threadsperblock = 2**9
blockspergrid = (A.size - 1 + (threadsperblock - 1)) // threadsperblock
A, oA, oB = cuda.to_device(A), cuda.to_device(oA), cuda.to_device(oB)
cuda_run_core[blockspergrid, threadsperblock](A, oA, oB, uint64(pow(BASE, d)))
A, oA, oB = A.copy_to_host(), oA.copy_to_host(), oB.copy_to_host()
for x, y in zip(oA, oB):
if x:
print(x, '*', y, '=', rev(y), rev(x))
def main():
for d in range(8, 16):
t0 = time.perf_counter()
run_cuda(d)
t1 = time.perf_counter()
print(f'{d} -> {t1-t0:.3f}')
Эксперты компании по отслеживанию космического мусора LeoLabs говорят, что обломки будут находиться на орбите еще долго, и возникнет «потенциальный риск столкновения с большинством спутников на низкой околоземной орбите в течение следующих нескольких лет или десятилетий».
Очень сомнительное ограничение в 56 на путь, так-то змейка на карте в 60x60 что-то порядка 1700 дает. В мире плюсов аллокацию из библиотеки можно избежать output iterator-ом, там такое на шаблонах бесплатно, в го так не выйдет.
Ого. Ходил еще школьником на его курс по питону 14-15 лет назад, жалко не имел подходящий mindset для этих занятий в то время. Вроде бы делали рисовалку на pygame. Действительно многому научил.
Помню через несколько лет уже в МФТИ сокурсники удивлялись этому факту когда мы учили курс по ОСям по его учебнику.
Поздравляю победителей!
У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.
Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.
Максимально дубовая реализация монтгомери вместе с делением по Лемиру улучшила мой результат с
27,223до21,820. Даже обидно как-то, получается раньше я вообще не в ту сторону смотрел. Но теперь до первых мест рукой подать, скорее всего можно те же вызовы_mullo_epi32в два раза реже делать (у меня на 1 mulmod 3 simd умножения, из которых только два полноценное, и одно урезанное), или от бранча для переполнения вычитания как-то отказаться, его обработка съедает четверть всего времени. Теоретически можно оптимально распланировать умножения по битам степени, и вместо маскировки делать их только тогда когда нужно, это тоже может дать до трети всего времени (умножаем только на половину всех битов).Да, проверяю по 4 числа одновременно. Главное заранее отсекать большую часть работы (5/6) проверкой на делимость на маленькие делители, довольно красиво сделано, но видимо можно сделать лучше, я использовал для больших libdivide_u32_do_vec256, а для маленьких (2,3,5,7) сообразил трюк с _mm256_shuffle_epi8. Тоже в восторге от результатов первой тройки. Ах да, еще нужно чтение через mmap организовать, в справке от сайта есть пример.
О, я примерно тем же путём шел когда решал https://highload.fun/tasks/10
Правда у меня в итоге векторизованная где-то в 2 раза быстрее не векторизованной, но и другие трюки использовал. Обязательно поделитесь результатом.
Все так говорят (на один символ отправка 8 байт если между ними меньше ~20ms), пробежал по коду и не вижу ничего противоречащего этому. Тестить правда лень, если хотите оспорить — wireshark/tcpdump вам в помощь.
Действительно в прошлом году появился патч и опция в конфиге, мне интересно, а в вашем дистрибутиве есть эта опция? (проще всего проверить
man ssh_config; /Obf)Презентация про ssh, тут статья. Текст об этом на хабре, но я не рекомендую ни комментарии ни статью: там какая-то отсебятина про visual feedback.
Вместе с таймингом утекает и длина пароля, ответных пакетов со стороны сервера не нужно.
В комментариях тоже какая-то дичь, например: (проблема не в комментарии или в комментаторе, а в том что его никто не поправил, так и висит).
Статья про анализ серверного "пинга" со стороны собеседника в IM.
Напишу на тот случай если кто-то не понимает какую конкретно безопасность обеспечивает E2EE и для/от кого. Для любого мессенджера с моментальной доставкой сообщений и без серьёзного "замусоривания" траффика легко понять кто с кем общается используя глобальное наблюдение (без MitM) и элементарные корреляции.
Пусть пользователь A, B живут в стране, где некие
вредоносныеагенты Е установили специальное оборудование сохраняющее метаданные всего оконечного трафика на всех провайдерах связи. Пусть агенты E знают A, но не знают B, про B известно что он один из множества U.Теперь каждый раз когда A пишет сообщение B, он инициирует обмен сетевым трафиком с серверами напрямую (Telegram), через peer-to-peer сеть(Tor), либо даже с использованием туннеля с дополнительным шифрованием ( Wireguard или OpenVPN). Но во всех популярных любительских сценариях использования (за редким исключением вроде i2p) размеры пакетов меняются крайне предсказуемо, а то и не меняются вовсе. Теперь E, зная паттерны трафика нового сообщения (а в случае push уведомлений можно опираться и на ip-подсеть как на показатель пуша), запоминает текущее время.
Затем это сообщение должно прийти B, где ситуации повторится. Так как множество людей из U могут получить подобный трафик случайно, E может лишь ограничить размер множества U - даже для довольно таки большого окна доставки в минуты (типично для пуш-уведомлений) с каждым сообщением размер U будет сокращаться в разы, если не в десятки. Для однозначного установления B потребуется около 27 бит информации (
|U|~=1.4e8), что вполне себе достижимо при регулярном общении. Даже если утекать будут малые доли бита (т.е. агенты E очень не уверены в том что произошло общение), из того что нам их нужно собрать буквально десятки, при достаточном количестве сообщений легко вычислить весь граф общения.Эту картину не меняет даже вменяемый false-positive (пусть например фоном запущенный ютуб раз в 15 секунд даёт картину похожую на сообщение, тогда мы должны учесть шанс того что A ничего не отправлял). В таком случае мы не выкидываем кандидатов из U, а честно обновляем ожидания по Байесу. Если проделать подобное в итоге получатся что граф общения оказывается (ребро между вершинами если они общаются) равен попарной временной корреляции "интересного" трафика относительно U.
Подправив параметры можно узнать например на какие каналы в youtube вы подписаны не залезая в шифрованный трафик, достаточно посмотреть корреляцию жирного потока на сервера гугла с расписанием публикации новых видео, (если вы конечно открываете их сразу по уведомлению).
Да, это вычислительно сложная задача, но явно не сложнее подсчета условного PageRank-a для поискового индекса с MapReduce, естественно считать в лоб (O(|U|^2)) нельзя.
Слайды про утечку пользователя по паролю при наборе его используя SSH (не совсем в тему, но идея похожая)
Определение местоположения пользователя популярных "защищенных" мессенджеров
Тут исследователи не пользуются глобальным мониторингом траффика, смотрят только на раундтрипы оповещения о доставке.
P.S.
Задумался над тем что бы комментарий до статьи добить, но об подобном на хабре уже писали еще в 2011 (в контексте Tor, Tarzan и Morphmix).
Еще я сомнительным способом генерировал случайное целое,
uniform_uint64() % (HI-LO) + LOВ районе 10^18 там уже значительный перекос в пользу меньших чисел.Прогнал Монте-Карло на равномерных неупорядоченных парах, (это не точно учтёт пары где
x=y, но так как их немного, погрешность должна быть небольшой).Просто взял
p:=cnt_good/cnt_iters; estimate:=81*10^{d-2}*p/2;Скорость симуляции получилась около 5 миллиардов итераций в секунду, что не впечатляет. Пришлось немного попотеть что бы правильно работать с 36-значными числами.
Monte-Carlo
Относительная точность падает при уменьшении p, поэтому оценку для d=18 получилось посчитать с точностью
±0.3%Hidden text
Попробовал ваш алгоритм на видяшке, работает 4.5 секунды для
n=6.Заодно и осилил
n=7Лобовой подсчет без каких-либо алгоритмов на видяшке работает 4 секунды! (задача с парами). Если не лень ждать 16 часов сможете узнать ответ для n=7.
Hidden text
Ничего не нашлось, а пятнадцать нужно 16 часов ждать. Расширил пространство на несколько порядков, вдруг пригодится потомкам.
Другие основания, из не указанного выше
Проверяет все до
m=12за минуту на видюшке. Посмотрим что будет сm=14через пару часов.Hidden text
Чет медленно. Сейчас сделаю побыстрее.
WTF! В каком это месте он рекурсивный? В целом почти все алгоритмы поиска кратчайшего пути нерекурсивные.
Визуализация показала обширное облако обломков после уничтожения советского спутника
Очень сомнительное ограничение в 56 на путь, так-то змейка на карте в 60x60 что-то порядка 1700 дает. В мире плюсов аллокацию из библиотеки можно избежать output iterator-ом, там такое на шаблонах бесплатно, в го так не выйдет.
А где про это можно почитать на русском?
Ого. Ходил еще школьником на его курс по питону 14-15 лет назад, жалко не имел подходящий mindset для этих занятий в то время. Вроде бы делали рисовалку на pygame. Действительно многому научил.
Помню через несколько лет уже в МФТИ сокурсники удивлялись этому факту когда мы учили курс по ОСям по его учебнику.