Comments 6
Если бы такая проверка существовала в коде, то задача была бы уже нерешаемой.
Неправда ваша, если взять например M=p-1, то вариантов для pow(M,c,p) всего два: 1 и p-1, шанс угадать 50%.
Сразу докину, на случай если напишите что это частный случай и его тоже надо добавить в список на проверку, после чего задача станет нерешаемой.
При
M=0xc5b5e9966f601b7f42b309cc4e44e85541b7a054a9b84a6d8c7c5b5060405c5edd77c0da5ced7d88b5c62b140e403023f503c31cb0c05dc32ac82cc22e5b0b5fc73ade705533ba1193014ec33e46dd554abe6473aad9d9d84577f10d51f481cd77a35aaa02fb9f4bb3a9f79a735609bd503ca9fbeecb0262afabe95dc97757537b9c4044da87a9e3d8542ba2698d5ea1f4beab6db0da1d55dfa0f337ea63db4e2d827761a3dbe9e8617a015ccb259682fc2f9302831c59d91bc8b0d17703acd97b2714a124515cdd430ce70f5535ee0a6d114715c7650ca2e4d255ce29afa51249a3f5d6fe0caee3efa1dfe91c3807dba8fd5fcaac7727349dc16676b5374f5
в примерно 1/4 всех случаев генерации c
shared_secret=pow(M,c,p)=0x44439c18056825bb05d5cb7b42826860d7ee43b81ac7f2ecee439adff0a3b5bb9b3faa782cef07aecaf37ff57b7569e04917c149f12409f60f0c60686b10effa7a2d06517cf1dc3f8f4c23a83bc2273c9f742ebec1f37e230acdff697690c19819f0ff09212f0c479a6f3b495fbf7a0b1fe4e87b28143b7e4c6c12432b4b43ee02dbbb14ebd8d672dd0252a9a54e43f395581cd6f9aca116611b1109f6feaf88ea3a45424ef9638ea8d11dc6ca8b9adc0631000336d465ddd7074f22f71884427bd209a70deeecd5404aa10ce560c3f1f685e80c6f14865f4cb7a7684ce0cbacb471ba85fd20c53fcf1c8c4da6af1443a5cc925d09463a9f644ce795c6fd2df4
плюс задачка на подумать, как я получил эти значения.
Да я больше чем уверен, что таких "частных" случаев там еще больше чем достаточно...
Однажды попадалась интересная задача на CTF, где нужно было ввести число, которое одновременно должно было бы быть и простым и не простым числом. Я решить не смог. Там одна из проверок была "библиотечной" функцией, т.е. гарантированно реализована правильно, а вторая уже самописная реализация одного из алгоритмов сита для проверки простого числа, которая тоже имела некоторые "частные случаи" и в некоторых случаях ошибочно считала простым числом. Естественно речь шла о простых числах достаточной длины.
Хм. А вы действительно правы, спасибо! Интересное поведение) Вот поэтому я и не считаю себя достаточно разбирающимся в криптографии. Значит есть еще вариант решения этого CTF, но с 50% вероятностью.
Увлекательная криптография. Часть 1