https://nsucrypto.nsu.ru/archive/2021/round/2/task/4/#data
Ideea principală a exercițiului: Găsiți cheia secretă $k$, având acces la $Enc(x, d) = Enc(x^d \bmod n), n = 1060105447831$.
voi presupune $0 < k < n.$
$Enc$ este un hash normal, returnează aceeași ieșire ca și intrarea corespunzătoare.
Vreau să găsesc o coliziune astfel încât $hash(k, 1) = hash(x, d)$, asta ar însemna că am găsit $k = x^d \bmod n.$
Prima mea idee a fost să caut generatorul grupului ciclic al $Z_{1060105447831}$, dar am aflat că 2 și 3 și nimic din primele 20000 de numere nu a funcționat. Aș folosi generatorul pentru a verifica dacă există coliziuni pentru $k$. Știu $2^{40} > n$. De asemenea, ar ajuta să folosiți generatorul pentru a calcula logaritmul discret și a găsi valoarea lui k mai rapid. Vreau să-l testez, dar se pare că problema a fost creată având în vedere verificarea manuală.
Un atac de ziua de naștere nu funcționează pentru un hash de 128 de biți dacă vreau o probabilitate și o eficiență bune.
De asemenea, am încercat să obțin valoarea hash a valorilor mici Enc(2,1), Enc(3,1) ... Enc(10, 1) pentru a vedea dacă hash-ul are vreo relație ascunsă între ieșirile sale.
În plus, $\phi(n)$ are o factorizare frumoasă a numerelor mici.
Voi adăuga orice detalii noi importante.
Ce valori ar trebui alese pentru a ajuta la găsirea k? Contează ele? Generatoarele nu sunt utile, nu pot aplica algoritmi mai rapidi pentru exponențiarea modulară, deoarece tot ce primesc este un șir de 128 de biți. Tot ce pot face este să verific dacă un număr sau puterea unui număr are o codificare egală cu cea a numărului secret $k$
