М.Двач / Криптоанархия

Этого треда уже нет.
Это копия, сохраненная 11 мая 2020 года.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.

1,3 Мб, 3264x2448
Тупых вопросов тред Купрум 15 ноя 2017, 13:11 38048 В конец треда | Веб

Криптач умер? Да здравствует Криптач. Аноны, куда вы все пропали? Почему меньше одного поста в час? Может, стоит возрадить криптач?

Ответы381673817040312

Купрум 2 15 ноя 2017, 14:41 2 38051

Как я понимаю, этого треда будет недостаточно. Поэтому тут я также периодически буду писать переводы к некоторым интересующим меня вещам, касающимся криптографии.

Ответы38214

3 15 ноя 2017, 16:04 3 38053

Тут слишком много школьников задающих тупые вопросы по кругу.

Ответы3806338071

4 16 ноя 2017, 10:04 4 38063

>>38053
Может тогда создать faq, нет?

Ответы38072

Купрум 5 16 ноя 2017, 15:39 5 38071

>>38053
Пусть читают фак или пишут итт.

Купрум 6 16 ноя 2017, 15:40 6 38072

>>38063
Он есть. На нулевой в закреплённом треде.

7 25 ноя 2017, 13:09 7 38167

>>38048 (OP)
все съебались в даркнет

Ответы38196

8 25 ноя 2017, 19:01 8 38170

>>38048 (OP)
У школьников учёба. Какой крпитач?

9 27 ноя 2017, 17:50 9 38196

>>38167
ссылочку запили пожалуйста

10 28 ноя 2017, 15:27 10 38210

Раз уж тупых вопросов тред, то можно ли увидеть все скрытые доступные по ссылке видео на чужом ютуб канале?

11 29 ноя 2017, 02:12 11 38214

>>38051
Здесь криптографию никогда и не обсуждали, в ней никто ничего не смыслит из местных. Как в /s не обсуждают кодинг. Это доска для трепа о прайваси, законах, софте с т.з. пользователей и т.п.

12 19 июня 2018, 17:40 12 40312

>>38048 (OP)
Каким алгоритмом
можно найти примитивный корень по модулю простого числа,
если оно пиздатющее?

Ответы4031340326

13 19 июня 2018, 18:00 13 40313

>>40312
Алгоритмом Сосницкого.

Ответы40314

14 19 июня 2018, 19:43 14 40314

>>40313
>Алгоритмом Сосницкого
Это троллинг такой, или что?
Сразу же, сходу, нашёл какую-то теорему от математика Сосницкого: https://dxdy.ru/topic52676.html

В схемах ElGamal и Diffie-Hellman нужно первым делом - сгенерировать пару p и g.
При этом g - является первообразным корнем по модулю простого числа p.
Как найти g? Есть что-то типа JavaScript генератора?
Я нашёл только ECDH - на эллиптических кривых: http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html
Там изначально заданы координаты генераторной точки G, в самой эллиптической кривой.

Выбираешь кривую, задаётся генераторная точка G,
затем генерируешь число (приватный ключ),
и умножаешь генераторную точку на число - получаешь публичный ключ (точка с двумя координатами).
После обмена ими - рассчитывается общая точка, которая и может быть общим ключём шифрования
(если её координаты, конвертнуть в HEX, например)...

Но кривые эти - надо чтобы были и у Алисы и у Боба, к тому же нужно задать конкретную кривую.
А вот если просто числа брать, без эллиптических кривых,
то быстрое возведение в степень по модулю не так уж много места занимает и не требует всяких скриптов.
К тому же эти функции можно быстро написать.
Вот здесь: https://8gwifi.org/DHFunctions.jsp я вижу нечто наподобие PGP DH,
но тут тоже задаются изначально, параметры p и g.
То, что p - это простое число, и оно может быть большим, так есть алгоритм Миллера-Рабина.
Вопрос в том, как получить g при определённом, сгенерированном p.

Ответы4031540326

15 19 июня 2018, 22:06 15 40315

>>40314
Вот так и надо было с самого начала спрашивать. Прочитал за тебя википедию, вот какой-то алгоритм: https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots
Попробуй.

Ответы40316

16 20 июня 2018, 00:15 16 40316

>>40315
>https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots
Там что надо факторизовать φ(p)?.. Равное (p-1).
А если оно, порядка 10^616 (2048 бит ~ 2^2048)?

Есть что-нибудь попроще?

Ответы4031940326

17 20 июня 2018, 07:16 17 40319

>>40316
Во-первых, факторизовать его может быть и не очень сложно, тут как повезет. Во-вторых, я ничего об этом не знаю, но скорее всего в википедии приведен самый лучший из известных алгоритмов. В-третьих, обычно в качестве g берут какое-то маленькое число, например 2. Поботай еще вот этот вопрос, который я тебе только что нагуглил за минуту: https://crypto.stackexchange.com/questions/12961/diffie-hellman-parameter-check-when-g-2-must-p-mod-24-11

Ответы40320

18 21 июня 2018, 02:05 18 40320

>>40319
Много букв на английском, и цифры другие.
Вот какой-то алгоритм нашёл на си++:
http://www.cyberforum.ru/turbo-pascal/thread273061.html
Как его в JS - не знаю.

И вот ещё: http://kaf401.rloc.ru/Criptfiles/primroots.htm
Тут наглядно видно, что первообразные корни - дают
равномерное распределение остатков по разным степеням,
а другие числа - нет.
Только как их искать - не пойму нифига, даже с кода, что выше.

Ответы40326

43 Кб, 707x614
19 21 июня 2018, 17:59 19 40326

>>40320>>40316>>40314>>40312
Глядя на этом сайте: http://kaf401.rloc.ru/Criptfiles/primroots.htm
на повторяющиеся числа 6 и 10
для разных первообразных корней по модулям простых чисел 7 и 11 - сделал следующий вывод:

1. Если p - простое, φ(p) = p-1.
2. Поскольку p - нечётное, то p-1 = φ(p) - чётное, оно делится на 2.
Делим, и получаем некое x = φ(p)/2 = (p-1)/2.
3. Дальше, для всех a, взаимно-простых с p, вычисляем a^x (mod p), и проверяем...
Если a^x (mod p) ≢ 1 и a^x (mod p) ≡ φ(p), вернуть a - это первообразный корень.
Пикрелейтед.

Примечательно то, что для непростого числа 9, факторизуемого как 3×3,
также можно видеть повторяющееся число 8 у корней 2 и 5.
Однако, φ(9) = 8, φ(9)/2 = 8/2 = 4,
при этом 2 - взаимно простое с 9,
однако 2^4 mod 9 === 7 !== 8,
и этот алгоритм для нечётных составных - не прокатит.

Чтобы найти генератор для нечётного составного, насколько я понял, надо от d отнять ещё одну единицу.

Ответы4032740329

14 Кб, 480x471
20 21 июня 2018, 18:30 20 40327

>>40326
>φ(9) = 8
Вообще-то при p = 9 (составное, 3×3),
φ(9) = 6, при этом x = φ(9)/2 = 6/2 = 3,
и при a = 2 (взаимно-простое с p):
a^x mod p = 2^3 mod 9 = 8 = (p-1).

Только вот чтобы найти φ(n), при составном нечётном n - надо факторизовать это n.

Ответы40329

21 21 июня 2018, 22:25 21 40329

>>40326
>Если a^x (mod p) ≢ 1 и a^x (mod p) ≡ φ(p), вернуть a - это первообразный корень.
Для первых чисел - сойдёт, а вот для следующих...

>http://kaf401.rloc.ru/Criptfiles/primroots.htm
6 - взаимно простое с 7;
и 6^3 mod 7 !== 1 = 6 = φ(7), но 6 - не первообразный корень.
То же самое и с числом 10 при p=11:
gcd(10, 11) = 1, и они взаимно-просты.
Проверил тут: http://www.alcula.com/calculators/math/gcd/ введя "10, 11".
Дальше...
a^φ(p)/2 mod p = 10^10/2 mod 11 = 10^5 mod 11 !== 1 = 10 = φ(11), но 10 - тоже не первообразный корень.

Надо, походу ещё, при переборе - отсеять a по условияю "a mod φ(p) === 0".
А затем уж, наверняка, можно будет и рандомные числа брать
например, от 2 до p, c неким определённым интервалом для поиска, скажем 1000 перебираемых a.

>>40327
Вот, допустим, я факторизовал число 5624351580503521 = 163×167×173×179×181×191×193
Дальше что?
http://e-maxx.ru/algo/euler_function тут ничего не понятно,
с этими индексами вверху и внизу - возле каждого простого числа в каноничном разлжении n.
Какие-то минусы и дроби пиздатые.
φ(n) = n⋅(1 - 1/p1)⋅(1 - 1/p2)⋅...⋅(1-1/pk) Это как считать???
Там такие длинные десятичные дроби получаются, если единицу на простое число поделить...
С индексом a вверху p - тоже ничего непонятно...

Ответы40331

22 22 июня 2018, 04:45 22 40331

>>40329
>a mod φ(p)
Там ещё брутфорсом надо либо единицы искать, либо φ(p).

Вот таблица для числа 31:
n = 31
φ(31) = 30
φ(n)/2 = 15
n-1 = 30
Количество первообразных корней: φ(φ(n)) 8
φ(φ(n)/2) = 8

a^x mod c; c = 31
a\x123456789101112131415161718192021222324252627282930
1111111111111111111111111111111
2248161248161248161248161248161248161
+3392719261617202925138241030282241251514112618237211
4416281416281416281416281416281416281
55251525152515251525152515251525152515251
6653025261653025261653025261653025261653025261+
77182145428108252016199171821454281082520161991
8821641821641821641821641821641821641
99191620258102845142187191916202581028451421871
101078182522014165194928110781825220141651949281
11112829964131923524162114302032222527181282671510171+
12122023282622491525214171830191183529722166102714131+
13131427106162272953811193018174212515924226282320121+
141410167581918425922820114101675819184259228201
15158272301623429115827230162342911582723016234291-
16168421168421168421168421168421168421
17171015726812182725222320301421162452319134692928111+
181814410251697252882019118144102516972528820191
191920828527916251041418119208285279162510414181
202028292541819857161014120282925418198571610141
21217231862111415512422283010248132529201716261927931+
22221915206821282751721373091216112523103426142918241+
23232154308291627123215430829162712321543082916271-
24241829142643102325111612930713217527282186201519221+
252551255125512551255125512551255125512551
26262530561262530561262530561262530561262530561-
27271629830415223127162983041522312716298304152231-
282894195161420225188710128941951614202251887101
29294231630227815129423163022781512942316302278151-
30301301301301301301301301301301301301301301301

Справа - первообразные корни отмечены знаком плюс. Их всего 8, как рассчитано и рассчитано выше.
Там где знак минус - это какие-то полукорни. Число a в степени φ(n)/2 для них равно 30, и это φ(31), но эти тридцадки - повторяются.
Также, есть и по нескольку единиц, в ряду. У первообразных корней - же числа не повторяются.
Возможно можно как-то найти φ(31), либо единицы, без перебора и факторизации φ(n)...
Ведь если оно большое, то не то что перебирать - факторизовать его сложно.
Я уже вижу некую закономерность, но через факторизацию числа 30.
30 = 2×3×5, и
6^(3×1) mod 31 = 6^(3×3) mod 31 = 6^(3×5) mod 31 = 6^(3×7) mod 31 = 6^(3×9) mod 31 = 30
6^(3×2) mod 31 = 6^(3×4) mod 31 = 6^(3×6) mod 31 = 6^(3×8) mod 31 = 6^(3×10) mod 31 = 1

23^(5×1) mod 31 = 23^(5×3) mod 31 = 23^(5×5) mod 31 = 30
23^(5×2) mod 31 = 23^(5×4) mod 31 = 23^(5×6) mod 31 = 1

26^(3×1) mod 31 = 26^(3×3) mod 31 = 26^(3×5) mod 31 = 26^(3×7) mod 31 = 26^(3×9) mod 31 = 30
26^(3×2) mod 31 = 26^(3×4) mod 31 = 26^(3×6) mod 31 = 26^(3×8) mod 31 = 26^(3×10) mod 31 = 1

27^(5×1) mod 31 = 27^(5×3) mod 31 = 27^(5×5) mod 31 = 30
27^(5×2) mod 31 = 27^(5×4) mod 31 = 27^(5×6) mod 31 = 1
29 - то же, что и выше.

А вот во 2-й степени - тридцаток не нахожу.

Вопрос: возможно ли без факторизации φ(n) и прямого перебора - с поиском φ(n) и 1, как-то отсеять не первообразные корни?

22 22 июня 2018, 04:45 22 40331

>>40329
>a mod φ(p)
Там ещё брутфорсом надо либо единицы искать, либо φ(p).

Вот таблица для числа 31:
n = 31
φ(31) = 30
φ(n)/2 = 15
n-1 = 30
Количество первообразных корней: φ(φ(n)) 8
φ(φ(n)/2) = 8

a^x mod c; c = 31
a\x123456789101112131415161718192021222324252627282930
1111111111111111111111111111111
2248161248161248161248161248161248161
+3392719261617202925138241030282241251514112618237211
4416281416281416281416281416281416281
55251525152515251525152515251525152515251
6653025261653025261653025261653025261653025261+
77182145428108252016199171821454281082520161991
8821641821641821641821641821641821641
99191620258102845142187191916202581028451421871
101078182522014165194928110781825220141651949281
11112829964131923524162114302032222527181282671510171+
12122023282622491525214171830191183529722166102714131+
13131427106162272953811193018174212515924226282320121+
141410167581918425922820114101675819184259228201
15158272301623429115827230162342911582723016234291-
16168421168421168421168421168421168421
17171015726812182725222320301421162452319134692928111+
181814410251697252882019118144102516972528820191
191920828527916251041418119208285279162510414181
202028292541819857161014120282925418198571610141
21217231862111415512422283010248132529201716261927931+
22221915206821282751721373091216112523103426142918241+
23232154308291627123215430829162712321543082916271-
24241829142643102325111612930713217527282186201519221+
252551255125512551255125512551255125512551
26262530561262530561262530561262530561262530561-
27271629830415223127162983041522312716298304152231-
282894195161420225188710128941951614202251887101
29294231630227815129423163022781512942316302278151-
30301301301301301301301301301301301301301301301

Справа - первообразные корни отмечены знаком плюс. Их всего 8, как рассчитано и рассчитано выше.
Там где знак минус - это какие-то полукорни. Число a в степени φ(n)/2 для них равно 30, и это φ(31), но эти тридцадки - повторяются.
Также, есть и по нескольку единиц, в ряду. У первообразных корней - же числа не повторяются.
Возможно можно как-то найти φ(31), либо единицы, без перебора и факторизации φ(n)...
Ведь если оно большое, то не то что перебирать - факторизовать его сложно.
Я уже вижу некую закономерность, но через факторизацию числа 30.
30 = 2×3×5, и
6^(3×1) mod 31 = 6^(3×3) mod 31 = 6^(3×5) mod 31 = 6^(3×7) mod 31 = 6^(3×9) mod 31 = 30
6^(3×2) mod 31 = 6^(3×4) mod 31 = 6^(3×6) mod 31 = 6^(3×8) mod 31 = 6^(3×10) mod 31 = 1

23^(5×1) mod 31 = 23^(5×3) mod 31 = 23^(5×5) mod 31 = 30
23^(5×2) mod 31 = 23^(5×4) mod 31 = 23^(5×6) mod 31 = 1

26^(3×1) mod 31 = 26^(3×3) mod 31 = 26^(3×5) mod 31 = 26^(3×7) mod 31 = 26^(3×9) mod 31 = 30
26^(3×2) mod 31 = 26^(3×4) mod 31 = 26^(3×6) mod 31 = 26^(3×8) mod 31 = 26^(3×10) mod 31 = 1

27^(5×1) mod 31 = 27^(5×3) mod 31 = 27^(5×5) mod 31 = 30
27^(5×2) mod 31 = 27^(5×4) mod 31 = 27^(5×6) mod 31 = 1
29 - то же, что и выше.

А вот во 2-й степени - тридцаток не нахожу.

Вопрос: возможно ли без факторизации φ(n) и прямого перебора - с поиском φ(n) и 1, как-то отсеять не первообразные корни?

Показать весь текст

Тред утонул или удален.
Это копия, сохраненная 11 мая 2020 года.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.

« /crypt/В начало тредаВеб-версияНастройки

/a//b//mu//s//vg/Все доски

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.gq, m2ch.cf, m2ch.fapp.in, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion