Logaritmo discreto, ma in una situazione particolare
Buongiorno a tutti,
scrivo questo post per chiedere lumi su un problema di crittografia nel quale mi sono imbattuto.
Una precisazione è doverosa: non ho una particolare formazione matematica, per cui purtroppo mi perdo facilmente quando le cose si fanno complicate!
Durante lo studio di un programma per pc, mi sono trovato di fronte ad una formula che, dopo averla rimaneggiata, semplificata e riscritta, ha assunto questa forma:
$ R=x^(C_1) mod C_2 $
con C1 e C2 costanti.
Ciò che vorrei ottenere è un procedimento per calcolare "x" essendo noti C1, C2 ed R.
Dopo una ricerca su internet ho scoperto che la formula indicata è alla base di alcuni moderni sistemi di crittografia, e che il suo inverso è noto come "logaritmo discreto", per il quale a oggi non sono noti algoritmi di calcolo efficienti.
Questi sono i punti fermi. I dubbi:
1) Tutti i testi che ho trovato su Internet indicano che non esistono algoritmi per ricavare C1 dati x, C2 e R. Nel mio caso C1 è noto, come C2 ed R. Ciò che mi occorre calcolare è x. Cambia qualcosa?
2) In tutti i testi che ho letto si fa riferimento al fatto che C1 di solito è un numero primo. Nella formula in cui mi sono imbattuto io né C1 né C2 (che, ricordo, nell'applicazione in esame sono costanti) sono primi.
3) Questo è il punto meno rigoroso, ma è anche quello per cui, nonostante tutto, continuo a spaccarmi la testa: ho ragione di credere che un metodo per calcolare x partendo da C1, C2 ed R (diverso dall'andare per tentativi) effettivamente esista!
Detto questo, vorrei fare un paio di precisazioni:
1) Non sto cercando di penetrare nei sistemi missilistici di nessuno stato, nè nei server di nessuna banca o cose simili.
2) Mi diverto a studiare le protezioni dei software, e per la cronaca questa formula si trova in un programma di cui possiedo una regolare licenza
Un grazie a chiunque vorrà aiutarmi a togliermi questo problema dalla testa!
Ciao
Roberto
scrivo questo post per chiedere lumi su un problema di crittografia nel quale mi sono imbattuto.
Una precisazione è doverosa: non ho una particolare formazione matematica, per cui purtroppo mi perdo facilmente quando le cose si fanno complicate!
Durante lo studio di un programma per pc, mi sono trovato di fronte ad una formula che, dopo averla rimaneggiata, semplificata e riscritta, ha assunto questa forma:
$ R=x^(C_1) mod C_2 $
con C1 e C2 costanti.
Ciò che vorrei ottenere è un procedimento per calcolare "x" essendo noti C1, C2 ed R.
Dopo una ricerca su internet ho scoperto che la formula indicata è alla base di alcuni moderni sistemi di crittografia, e che il suo inverso è noto come "logaritmo discreto", per il quale a oggi non sono noti algoritmi di calcolo efficienti.
Questi sono i punti fermi. I dubbi:
1) Tutti i testi che ho trovato su Internet indicano che non esistono algoritmi per ricavare C1 dati x, C2 e R. Nel mio caso C1 è noto, come C2 ed R. Ciò che mi occorre calcolare è x. Cambia qualcosa?
2) In tutti i testi che ho letto si fa riferimento al fatto che C1 di solito è un numero primo. Nella formula in cui mi sono imbattuto io né C1 né C2 (che, ricordo, nell'applicazione in esame sono costanti) sono primi.
3) Questo è il punto meno rigoroso, ma è anche quello per cui, nonostante tutto, continuo a spaccarmi la testa: ho ragione di credere che un metodo per calcolare x partendo da C1, C2 ed R (diverso dall'andare per tentativi) effettivamente esista!
Detto questo, vorrei fare un paio di precisazioni:
1) Non sto cercando di penetrare nei sistemi missilistici di nessuno stato, nè nei server di nessuna banca o cose simili.
2) Mi diverto a studiare le protezioni dei software, e per la cronaca questa formula si trova in un programma di cui possiedo una regolare licenza
Un grazie a chiunque vorrà aiutarmi a togliermi questo problema dalla testa!
Ciao
Roberto
Risposte
È impossibile trovare un unico valore della $x$, perché i numeri naturali sono infiniti, mentre i valori di $R$ sono solo $c_2$. Ti faccio un esempio con numeri molto semplici:
$R=1$
$c_1=2$
$c_2=3$
In questo caso ci sono infiniti valori della $x$ che verificano l'equazione: $x=2, x=5, x=7, x=11, x=13, ...$
$R=1$
$c_1=2$
$c_2=3$
In questo caso ci sono infiniti valori della $x$ che verificano l'equazione: $x=2, x=5, x=7, x=11, x=13, ...$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo