[C++] Generazioni chiavi RSA
Salve a tutti, devo creare un programma che tramite la codifica RSA sia in grado di cifrare e decifrare dei file di testo.
Apro questo topic per chiedervi un consiglio riguardo la generazione delle chiavi RSA, in particolare quando devo effettuare il prodotto tra i due numeri primi p e q.. dato che tale prodotto potrebbe essere un numero veramente grande, è molto probabile che per certi valori vada in overflow; perciò stavo pensando di mettere i due numeri primi in due variabili di tipo int e il prodotto in un tipo di variabile più grande, ad esempio long long int.. ma anche così non sono sicuro che il prodotto di due primi molto grandi non vada in overflow.. secondo voi come potrei fare??
Apro questo topic per chiedervi un consiglio riguardo la generazione delle chiavi RSA, in particolare quando devo effettuare il prodotto tra i due numeri primi p e q.. dato che tale prodotto potrebbe essere un numero veramente grande, è molto probabile che per certi valori vada in overflow; perciò stavo pensando di mettere i due numeri primi in due variabili di tipo int e il prodotto in un tipo di variabile più grande, ad esempio long long int.. ma anche così non sono sicuro che il prodotto di due primi molto grandi non vada in overflow.. secondo voi come potrei fare??
Risposte
Se non vuoi creare una classe bignum, magari ottimizzata per i tuoi scopi, usane una già creata come per esempio gnu mp (o anche sul sito di wiki). Ce ne sono altre, ma questa è la più consciuta.
Crearne una non è difficilissimo soprattutto se a te sono sufficiente 100-200 cifre al massimo (insomma roba da cavarsela con 8-12 int64_t) e non hai particolare necessità di performance.
Crearne una non è difficilissimo soprattutto se a te sono sufficiente 100-200 cifre al massimo (insomma roba da cavarsela con 8-12 int64_t) e non hai particolare necessità di performance.
quindi in questo caso non dovrei avere problemi di overflow giusto??
A meno che tu non riempia tutta la memoria direi che non dovresti avere problemi. Ma per quale ragione devi implementare una codifica RSA? In genere non è consigliato implementarli se non si sa quel che si fa. Gnu Mp inoltre non è implementata per scopi crittografici seri, ma per calcoli scientifici che richiedono precisioni superiori al normale o un numero di cifra molto molto grande. Per esempio openSSH non la usa e ne implementa una sua. Il problema è sostanzialmente che un non-tecnico potrebbe non essere a conoscenza di particolari attacchi che potrebbero far fallire il tuo codice indipendentemente dalla correttezza formale del tuo codice.
Detto questo non dovresti usare int, long & co. quando hai bisogno di gestire bene la memoria. È consigliabile usare i tipi int32_t, uint32_t, int64_t, uint64_t e similari contenuti in cstdint. Inoltre in un unsigned int (che supponiamo di 32bit) puoi memorizzare appena 8-9 cifre decimali; stai davvero pensando di implementare un sistema RSA che utilizza interi così piccoli?
Detto questo non dovresti usare int, long & co. quando hai bisogno di gestire bene la memoria. È consigliabile usare i tipi int32_t, uint32_t, int64_t, uint64_t e similari contenuti in cstdint. Inoltre in un unsigned int (che supponiamo di 32bit) puoi memorizzare appena 8-9 cifre decimali; stai davvero pensando di implementare un sistema RSA che utilizza interi così piccoli?
Niente di particolare.. è un progettino che sto facendo per un esame di programmazione, nulla di serio quindi, la mia unica preoccupazione è fare in modo che non vada in overflow a fronte di una moltiplicazione tra numeri enormi e che non crashi in sede d'esame xD
Per il resto mi basta far vedere al prof che ho capito come funziona la codifica e la decodifica, non tanto il fatto di fare un programma particolarmente utile o sofisticato..
Per il resto mi basta far vedere al prof che ho capito come funziona la codifica e la decodifica, non tanto il fatto di fare un programma particolarmente utile o sofisticato..
Se è solo per quello allora puoi probabilmente limitarti ad usare uint32_t e uint64_t. O anche lavorare sempre con gli uint64_t ma controllando che i primi non siano maggiori di UINT32_MAX prima di fare tutte le moltiplicazioni.
ok grazie mille per l'aiuto!
ultima cosa: come posso fare per determinare d tale che sia (d*e)%f(r) = 1 ?
grazie!
ultima cosa: come posso fare per determinare d tale che sia (d*e)%f(r) = 1 ?
grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo