|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima TDima TПогуглил немного: оказывается RSA c 32-битным ключом это пара десятков строк кода ))) Пошел писать. Строк мало, а в 32 бита вписаться проблематично :( Есть проблемы с генерацией ключей.какие проблемы то? гдет тема была с генерацией простых чисел фигня только выйдет, взламывается на ура тупым перебором ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 00:15 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Победил разрядность, черновик без тюнинга производительности Код: plaintext 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.
Далее шифрование Код: plaintext 1.
и расшифровка Код: plaintext 1.
где Код: plaintext 1. 2. 3.
Тут еще один вопрос: я не совсем понимаю про допустимую разрядность шифруемого. Т.к. в итоге происходит "% n", то могу ли я ожидать что все значения до n (0 <= x < n) будут корректно зашифрованы и расшифрованы? Планирую двухбайтными блоками шифровать, плюс флаг для указания что один байт зашифрован, т.е. шифруемые значения 0 <= x <= 0x100FF. Поэтому ограничил 0x100000 <= n <= 0xFFFFFF. Т.е. минимальный n почти в 16 раз больше максимального шифруемого. Тесты погоняю, но ключей множество, все комбинации не проверить. Хотелось бы найти какое-то мат.доказательство. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 09:25 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima T Тут еще один вопрос: я не совсем понимаю про допустимую разрядность шифруемого. Т.к. в итоге происходит "% n", то могу ли я ожидать что все значения до n (0 <= x < n) будут корректно зашифрованы и расшифрованы? не все, ограничение из теоремы Эйлера m, p1, p2 - должны быть взаимнопросты ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 09:33 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
kealon(Ruslan)Dima T Тут еще один вопрос: я не совсем понимаю про допустимую разрядность шифруемого. Т.к. в итоге происходит "% n", то могу ли я ожидать что все значения до n (0 <= x < n) будут корректно зашифрованы и расшифрованы? не все, ограничение из теоремы Эйлера m, p1, p2 - должны быть взаимнопросты В смысле для pow_mod(base, exp, n) взаимнопросты exp и n, т.к. специально генерятся, а base тоже должно быть взимнопростое к exp и n? ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 09:38 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima T Код: plaintext 1. 2. 3. 4. 5. 6. 7.
вот это нехорошо, гугли расширенный алгоритм Евклида ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 09:40 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima Tkealon(Ruslan)пропущено... не все, ограничение из теоремы Эйлера m, p1, p2 - должны быть взаимнопросты В смысле для pow_mod(base, exp, n) взаимнопросты exp и n, т.к. специально генерятся, а base тоже должно быть взимнопростое к exp и n?не к експоненте, а к p и q ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 09:46 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
kealon(Ruslan)Dima Tпропущено... В смысле для pow_mod(base, exp, n) взаимнопросты exp и n, т.к. специально генерятся, а base тоже должно быть взимнопростое к exp и n?не к експоненте, а к p и q Добавил тупой перебор Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8.
Не срабатывает, хотя вот например значения Код: plaintext 1. 2.
Как понимаю должно сглючить на каждом кратном 1823, т.е. 3646, 5469, 7292, 9115 и т.д. но работает. Оставим этот вопрос открытым, пока просто добавлю эту проверку в генерацию ключей. kealon(Ruslan)вот это нехорошо, гугли расширенный алгоритм Евклида Евклида загуглил, спасибо за подсказку, а то хотел свой велосипед изобретать. kealon(Ruslan)фигня только выйдет, взламывается на ура тупым перебором Думаю прежде чем тюнинг устраивать надо перебор запустить: генерить ключи и писать в какой-нибудь std::map, посмотреть как быстро будет увеличиваться количество уникальных комбинаций, как часто повторы случаются. Если их относительно немного получится, например миллиард, то можно сложить их в табличку и по открытому ключу получать закрытый. Написал, посмотрел код: Код: plaintext 1.
Для начала разрядность n и e надо повысить. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 10:32 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima TДумаю прежде чем тюнинг устраивать надо перебор запустить: генерить ключи и писать в какой-нибудь std::map, посмотреть как быстро будет увеличиваться количество уникальных комбинаций, как часто повторы случаются. Если их относительно немного получится, например миллиард, то можно сложить их в табличку и по открытому ключу получать закрытый. Написал, посмотрел код: Код: plaintext 1.
Для начала разрядность n и e надо повысить.Зачем??? просто n разложить на множители и дальше расчёт ключей тривиален - вот и весь "взлом" ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 11:46 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
kealon(Ruslan)просто n разложить на множители и дальше расчёт ключей тривиален - вот и весь "взлом" Точно. На перебор всех простых от 2 до sqrt(n) надо меньше секунды. Потом немного перебора с подбором d. Все равно допилю, без исходников сложно понять что это за алгоритм. А в случае необходимости всегда можно перейти на полноценный RSA. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 14:04 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
kealon(Ruslan)Dima T Код: plaintext 1. 2. 3. 4. 5. 6. 7.
вот это нехорошо, гугли расширенный алгоритм Евклида Алгоритм нагуглил , только как его тут применить не понимаю. Алгоритм Евклида можно расширить так, что он не только даст НОД(a,b)=d, но и найдет целые числа x и y, такие что ax + by = d. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 14:11 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Вроде нашел как https://foxford.ru/wiki/informatika/rasshirennyy-algoritm-evklida Одним из применений расширенного алгоритма Евклида является нахождение обратного элемента в кольце вычетов по модулю.... ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 14:18 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima TЭлементарно: если кто-то назовется Алисой, то при этом реальная Алиса зайти не сможет, поэтому она позвонит и скажет: "ваша корявая прога не работает". Вопрос не во входе, вопрос в регистрации нового пользователя. В системе ещё нет Алисы. Как Алиса докажет, что это она Алиса, а не Хрен-с-горы, который ею представился час назад? ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 14:39 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima TВроде нашел как https://foxford.ru/wiki/informatika/rasshirennyy-algoritm-evklida Одним из применений расширенного алгоритма Евклида является нахождение обратного элемента в кольце вычетов по модулю.... не помню откуда брал, нерекурсивный вариант: Код: pascal 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. 34. 35.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 15:22 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dimitry SibiryakovDima TЭлементарно: если кто-то назовется Алисой, то при этом реальная Алиса зайти не сможет, поэтому она позвонит и скажет: "ваша корявая прога не работает". Вопрос не во входе, вопрос в регистрации нового пользователя. В системе ещё нет Алисы. Как Алиса докажет, что это она Алиса, а не Хрен-с-горы, который ею представился час назад? Это-то тут при чем? Тут каждый сам решает как при регистрации убедиться что пользователь тот за кого себя выдает. Эта проблема не этого топика, но она мне известна, как-то ее тоже надо будет решать, как один из вариантов вводить спец.учетку(и) админа: юзер саморегается, но изначально получает права писать только админам, передает админам инфу о себе, на основании полученной инфы админ дает серверу команду подтверждения или удаления новичка. В общем это тема для отдельного топика. Суть моей проблемы в том чтобы никто не смог писать от лица уже имеющейся учетки. Например тебе в вацап напишут с неизвестного номера - ничего страшного, главное чтобы левые люди не писали с известных тебе номеров. Т.е. получатель изначально знает от кого принимать сообщения. Я эту проблему решаю. Например резервное копирование: есть получатель "backup", ему сообщил что слать файлы могут "proga1", "proga2" и "proga3". От этих учеток принимает, остальным пишет "Извините, а вы кто?" ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 15:33 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
kealon(Ruslan)не помню откуда брал, нерекурсивный вариант: Спасибо. А то в инете только с рекурсией. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 15:36 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima Tkealon(Ruslan)не помню откуда брал, нерекурсивный вариант: Спасибо. А то в инете только с рекурсией.та нет, мусорка просто та ещё тынц ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 15:37 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
kealon(Ruslan)Dima Tпропущено... Спасибо. А то в инете только с рекурсией.та нет, мусорка просто та ещё тынц Я уже твой переписал Код: plaintext 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.
Вроде работает ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 16:05 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Затестил перебор. За полчаса нагенерил 7 млн. пар ключей, количество уникальных остановилось на 3`607`581 и даже по одному не добавляется. Можно ломать таблицей ключей ))) Понаблюдаю еще пару часов. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 17:53 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
kealon(Ruslan)Dima Tпропущено... Строк мало, а в 32 бита вписаться проблематично :( Есть проблемы с генерацией ключей.какие проблемы то? гдет тема была с генерацией простых чисел фигня только выйдет, взламывается на ура тупым перебором Тест Миллера-рабина применяется. Для чисел которые во много раз больше чем мы генерили несколько лет назад. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 18:04 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
maytonТест Миллера-рабина применяется. Для чисел которые во много раз больше чем мы генерили несколько лет назад.этот тест для проверки простоты числа используется, когда ищут пару для ключа. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 18:34 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Dima TЗатестил перебор. За полчаса нагенерил 7 млн. пар ключей, количество уникальных остановилось на 3`607`581 и даже по одному не добавляется. Можно ломать таблицей ключей ))) Понаблюдаю еще пару часов. Полтора часа прошло, 27 млн. обработано, а уникальных те же 3`607`581. Все понятно, вырубаю. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.12.2018, 19:28 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Оказывается Тест Миллера — Рабина иногда имеет ложноположительные срабатывания Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел. Наткнулся на is_prime(233 * 1103) дает true, я на его основе делаю пару ключей, естественно они не рабочие. Как с этим бороться? ... |
|||
:
Нравится:
Не нравится:
|
|||
30.12.2018, 10:35 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
Да. Это нормально. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.12.2018, 11:26 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
А все-таки, ключ - это одно число, или система чисел? ... |
|||
:
Нравится:
Не нравится:
|
|||
30.12.2018, 13:48 |
|
Авторизация без сервера
|
|||
---|---|---|---|
#18+
С точки зрения криптографии ключ - это просто массив битов. Но для нашего (человеческого восприятия) мы можем его представлять в виде - Целого десятичного числа: 12345678 - Двоично десятичного (binhex) Например: 00 FF AB C1 - Base64 - кодированного представления (система счисления с основанием 64) Но есть формы генерации ключа когда он должен удовлетворять каким-то требованиям Разложимость на небольшое число простых множителей - это просто один из частных случаев. Для симметричной криптографии (например шифр DES) например ключ это просто массив из 56 битов. Для тройного ДЕС-а - соотвествтенно бутерброд из трех ключей 3*56. И формулы там - другие. Но в большинстве случаев это просто очень хороший случайный поток битов. Без повторов и авто-корреляций. Есть формулы отображающие пароль в ключ. Но они все соотв. имею слабые места зависящие от длины пароля. Выше Дима привёл замечание к методу Раввина-Миллера. Од даёт ложные сообщения о том что число простое. Но это допустимо. Во первых у него - ошеломительная скорость по сравнению с традиционными методами. Во вторых он параметризируется числом раундов. (Здесь я точно не помню надо почиать). Ну вобщем в беря во внимание длинну целых чисел с коротыми он работает - его предсказание простоты вполне себе подходит для практических задач. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.12.2018, 14:02 |
|
|
start [/forum/topic.php?fid=16&msg=39754978&tid=1340007]: |
0ms |
get settings: |
10ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
171ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
65ms |
get tp. blocked users: |
1ms |
others: | 249ms |
total: | 528ms |
0 / 0 |