[Algoritmi] Controllo algoritmo fattorizzazione

[AlgoGC57]

Ciao a tutti, oggi mi sono imbattuto in questo progetto/algoritmo

https://github.com/Claugo/GC57crypto

https://github.com/Claugo/GC57_cassaforte

Non ho le cognizioni per capire se è un algoritmo rivoluzionario o no.
Potete commentare e darmi una mano per capire? Soprattutto dal punto di vista matematico.

Grazie

[ramath]

La prima cosa sensata che leggo sulla questione, lo avevo detto da subito che era una buffonata: https://forum.tomshw.it/threads/program ... st-8722585

[sivepofo]

Seconda conferma al fatto che non vale la pena di perderci troppo tempo.
Nella pagina "esempi sui numeri" nel sito del nostro programmatore "fai date" (sic) l'esempio del semiprimo 10000bit non mi pare corretto, alla fine il $MCD$ risulta $=1$.

Sempre ammesso che io sia ancora capace di fare copia incolla...

P.S. proseguendo nemmeno direi che se

$S=411376139330301510538742295729271098078875701297578574742561717$
$Int(sqrt(S))=20282409603651670423947251286016$

sia corretto
il risultato dovrebbe essere

$20282409603651670423947251288233$

Questo volendo essere onesti potrebbe anche andare perché non precisa la precisione con la quale lavora ed io ho dovuto fare delle assunzioni...

[ramath]

Purtroppo hai ragione, il "soggetto" che ha fatto il programma pare che si sia alleato con uno che vuol fare il matematico e ha addiritutra aperto un topic su questo forum, come ci ha fatto notare l'utente che ha aperto questa discussione ed è collegata a quella di Toms che avevo linkata prima. La discussione qui non se l'è filata nessuna, su Toms invece gliel'hanno chiusa, poi riaperta (non si capisce perché), e dopo la riapertura il "matematico" ha fatto una figuraccia epica accusando i moderatori del forum e offendendo gli utenti... morale della favola alla fine la discussione l'hanno chiusa definitivamente e hanno bannato il "matematico".

Certa gente non capisce le cose più semplici: uno che non sa programmare dice di aver fatto una scoperta clamorosa di matematica (ma non sa niente di matematica) sfuggita a tutti i più grandi geni matematici degli ultimi diciamo 200 anni; e lui che gli dà retta, ma un po' di sale in zucca santo cielo!
Ma quanto ci vuole a capire che è impossibile? e se pure fosse, con quale logica la vai a chiedere su un forum? per quanto ci siano persone molto competenti qui su matematicamente.it una presunta nuova scoperta di matematica, per essere convalidata va sottoposta all'esame di almeno 2 commissioni scientifiche che la revisionano.

Su Internet è pieno di questa gente

[sivepofo]

"ramath":
Su Internet è pieno di questa gente

Si, e c'è pure una scala per misurare questi soggetti.
Da quello che ho potuto vedere tutte e due le persone marcano un buon punteggio

[utente__medio11]

"ramath":Purtroppo hai ragione, il "soggetto" che ha fatto il programma pare che si sia alleato con uno che vuol fare il matematico e ha addiritutra aperto un topic su questo forum

L'utente sono io e il topic in questione, e in particolare la "dimostrazione", è questa; dalla lettura dei post precedenti a quello linkato si può capire la genesi del problema e il percorso che mi ha portato a quella dimostrazione.

Poi personalmente non ho mai detto di aver fatto chissà quale grande scoperta, ho semplicemente cercato di capire cosa avvenisse matematicamente dietro le quinte del metodo crittografico in questione, visto che nell'altro forum giustamente si pretendeva dall'autore una dimostrazione matematica della proprietà da lui riscontrata sperimentalmente. Inoltre ho sempre detto che trovo quella "dimostrazione" (se così si può chiamare) piuttosto semplice e che la sua comprensione non richiede chissà quali conoscenze matematiche.
Infine non ho mai escluso in modo categorico che non possa aver commesso qualche errore, quindi se qualcuno vuole confutarla si accomodi pure.

Fatte le dovute premesse, spiego ai lettori quello che è successo nell'altro forum:
[ot]Un utente crea un thread in cui afferma di aver fatto una scoperta rivoluzionaria in campo crittografico, ma in poco tempo degenera completamente e viene chiuso, sia per colpa dell'autore (che non si esprime correttamente e utilizza toni eccessivamente entusiastici) sia dall'altra parte per colpa di una serie di utenti e moderatori (che, infastiditi dall'atteggiamento dell'op, si accaniscono eccessivamente nei suoi confronti, soffermandosi sulle cose obiettivamente sbagliate e ignorando quelle che invece potevano risultare interessanti).
A quel punto, incuriosito dal fatto che effettivamente la proprietà matematica su cui si basava il metodo sembrava funzionare, ho contattato l'utente in questione e gli ho posto alcune domande per inquadrare meglio il problema dal punto di vista matematico, e avere quindi tutti gli elementi per ragionarci un po'.
Poi, dopo qualche tempo, creo un topic in cui dico che penso di aver trovato una spiegazione matematica a quei riscontri sperimentali, posto la mia dimostrazione e chiedo di dividere la discussione in due parti, di cui una prima finalizzata a ragionare sulla parte più matematica, e una seconda parte più legata all'ambito della crittografia. Lo scopo era quello di giungere in modo pacato e argomentato ad una sentenza definitiva sulla proprietà matematica e sul suo eventuale utilizzo in ambito crittografico.
Ma il thread è diventato ben presto un proliferare di accuse varie con toni da tifoseria, di obiezioni senza senso alla mia dimostrazione (tutte sistematicamente smontate), e di critiche off-topic alle cose scritte dall'autore del metodo nel suo primo post ormai chiuso (e a tal proposito fa sorridere il fatto che ciò sia avvenuto senza che l'autore avesse ancora nemmeno preso parte al thread, oltre al fatto che ciò sia stato fatto proprio dagli stessi moderatori che, dopo aver chiuso l'altro topic in fretta e furia, hanno utilizzato il mio per continuare ad accanirsi sulle cose presenti nel primo, ignorando per non so quanto tempo le cose che scrivevo).
Per chi volesse rendersi conto del grado di faziosità, ipocrisia ed ignoranza con cui mi sono dovuto misurare, lascio il link alla discussione: https://forum.tomshw.it/threads/program ... -2.933380/ (ovviamente questo è il mio punto di vista, e magari leggendola altri concorderanno con gli amici qui presenti che ci hanno allietato con queste tre pagine di nulla cosmico)[/ot]

Poi, visto che qualche post fa parlavate di esempi numerici, e visto che ci troviamo nella sezione di informatica, riporto di seguito un codice in C++ (postato anche sull'altro forum) che fornisce esempi numerici basati sulla mia dimostrazione:

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

bool is_prime(const unsigned int n)
{
    if(!(n % 2))
    {
        return false;
    }
    for(unsigned int i = 3; i <= n / i; i += 2)
    {
        if(!(n % i))
        {
            return false;
        }
    }
    return true;
}

unsigned int mcd_euclide(unsigned int a, unsigned int b)
{
    while(b)
    {
        unsigned int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    unsigned int a = 72609;
    unsigned int b = 1289;

    if(b && a > b)
    {
        vector<unsigned int> v_c;
        vector<unsigned int> v_m;
        for(unsigned int i = a - 1; i > b; --i)
        {
            if(a % i == 1)
            {
                v_c.push_back(i);
                v_m.push_back(ceil((sqrt((b - 1) * (b - 1) + 4 * i) - b - 1) / 2 - 1));
            }
        }

        vector<unsigned int> v_A;
        vector<unsigned int> v_B;
        for(unsigned int i = 0; i <= v_m[0]; ++i)
        {
            if(is_prime(a + i))
            {
                v_A.push_back(a + i);
            }
            if(is_prime(b + i))
            {
                v_B.push_back(b + i);
            }
        }

        cout << "\n a = " << a << "\n b = " << b << "\n";
        for(unsigned int i = 0, j_A, j_B; i < v_c.size(); ++i)
        {
            cout << "\n " << i + 1 << ")\n c = " << v_c[i] << "  =>  m = " << v_m[i];
            cout << "\n [" << a << ";" << a + v_m[i] << "] => A =";
            for(j_A = 0; j_A < v_A.size() && v_A[j_A] <= a + v_m[i]; cout << " " << v_A[j_A++]);
            cout << "\n [" << b << ";" << b + v_m[i] << "] => B =";
            for(j_B = 0; j_B < v_B.size() && v_B[j_B] <= b + v_m[i]; cout << " " << v_B[j_B++]);
            if(j_A && j_B)
            {
                for(unsigned k_A = 0; k_A < j_A; ++k_A)
                {
                    for(unsigned k_B = 0; k_B < j_B; ++k_B)
                    {
                        if(mcd_euclide(v_A[k_A] * v_B[k_B], v_A[k_A] * v_B[k_B] % v_c[i]) != v_B[k_B])
                        {
                            return -1;
                        }
                    }
                }
                cout << "\n MCD(A*B ,(A*B) mod c) = B -> OK";
            }
            cout << "\n";
        }
    }
}

Per due generici valori di [inline]a[/inline] e [inline]b[/inline] (con [inline]a>b>0[/inline] ) il programma calcola tutti i possibili valori di [inline]c[/inline], e per ogni [inline]c[/inline] calcola l'estensione [inline]m[/inline] degli intervalli, definisce gli intervalli stessi e mostra l'elenco dei primi [inline]A[/inline] e [inline]B[/inline] appartenenti ai suddetti intervalli. Inoltre se per un dato valore di [inline]c[/inline] entrambi gli intervalli comprendono almeno un numero primo, allora viene testata la formula

[inline]MCD(A*B ,(A*B) mod c) = B[/inline]

per ogni possibile combinazione di numeri primi prelevati dai due intervalli, e nel caso in cui non fosse verificata il programma si interrompe ritornando [inline]-1[/inline].

Il codice l'ho scritto velocemente, quindi non mi sono soffermato più di tanto sull'ottimizzazione, inoltre se riscontrate qualche bug fatemelo sapere.
Di seguito l'output per [inline]a=72609[/inline] e [inline]b=1289[/inline] :

 a = 72609
 b = 1289

 1)
 c = 72608  =>  m = 53
 [72609;72662] => A = 72613 72617 72623 72643 72647 72649 72661
 [1289;1342] => B = 1289 1291 1297 1301 1303 1307 1319 1321 1327
 MCD(A*B ,(A*B) mod c) = B -> OK

 2)
 c = 36304  =>  m = 26
 [72609;72635] => A = 72613 72617 72623
 [1289;1315] => B = 1289 1291 1297 1301 1303 1307
 MCD(A*B ,(A*B) mod c) = B -> OK

 3)
 c = 18152  =>  m = 12
 [72609;72621] => A = 72613 72617
 [1289;1301] => B = 1289 1291 1297 1301
 MCD(A*B ,(A*B) mod c) = B -> OK

 4)
 c = 9076  =>  m = 6
 [72609;72615] => A = 72613
 [1289;1295] => B = 1289 1291
 MCD(A*B ,(A*B) mod c) = B -> OK

 5)
 c = 4538  =>  m = 2
 [72609;72611] => A =
 [1289;1291] => B = 1289 1291

 6)
 c = 2269  =>  m = 0
 [72609;72609] => A =
 [1289;1289] => B = 1289

Process returned 0 (0x0)   execution time : 0.038 s

[utente__medio11]

"ramath":pare che si sia alleato con uno che vuol fare il matematico e ha addiritutra aperto un topic su questo forum

"ramath":Su Internet è pieno di questa gente

"sivepofo":Si, e c'è pure una scala per misurare questi soggetti.
Da quello che ho potuto vedere tutte e due le persone marcano un buon punteggio

Prima mi tirate in ballo e poi fate finta di nulla?
Mi sono anche palesato per darvi modo di sbertucciarmi di persona, ma forse dopo 3 pagine così pregne di contenuti non avete più molto da dire...

[sivepofo]

Ne abbiamo, stai tranquillo, è che non siamo interessati alle tue manfrine (e ti stò citando)

[utente__medio11]

"sivepofo":Ne abbiamo, stai tranquillo, è che non siamo interessati alle tue manfrine (e ti stò citando)

"Ne abbiamo"? Come mai parli anche per gli "altri"?
E poi in cosa mi avresti citato?

In ogni caso se avete qualcosa da dire, fatelo, altrimenti i malpensanti potrebbero pensare che la vostra sia solo una scusa per nascondere il fatto che non sappiate come replicare senza dire altre sciocchezze!


P.S.
"stò" si scrive senza accento.

[ramath]

"utente__medio":Prima mi tirate in ballo e poi fate finta di nulla?
Mi sono anche palesato per darvi modo di sbertucciarmi di persona, ma forse dopo 3 pagine così pregne di contenuti non avete più molto da dire...

per quale motivo dovrei mettermi a discutere o a litigare sul nulla?
la mia opinione sul cosiddetto "algoritmo crittografico" l'ho già espressa a inizio del post
tu puoi pensare di aver dimostrato quello che vuoi ma dal punto di vista della crittografia, che è l'unica cosa che mi interesserebbe, hai fatto uno sforzo inutile. Vatti a leggere come funziona RSA, che è pure considerata superata, e ti accorgerai che la matematica che ci sta dietro non è per niente banale o facile. E la crittografia moderna usa concetti ancora più avanzati.

[utente__medio11]

"ramath":per quale motivo dovrei mettermi a discutere o a litigare sul nulla?

Peccato siate stati voi a riempire tre pagine di "nulla", e se non mi aveste tirato tirato in ballo non mi sarei mai sognato di intervenire in quest'inutile topic.

"ramath":tu puoi pensare di aver dimostrato quello che vuoi ma dal punto di vista della crittografia, che è l'unica cosa che mi interesserebbe, hai fatto uno sforzo inutile.

Io mi sono limitato a soddisfare la mia curiosità di capire cosa avvenisse matematicamente dietro le quinte. e una volta fatto ho pensato di condividere la spiegazione aprendo una discussione sull'altro forum, dove peraltro in molti in un precedente topic avevano chiesto all'autore del metodo una dimostrazione matematica (che egli non ha potuto fornire in quanto aveva riscontrato questa proprietà matematica solo sperimentalmente).
Ma il mio gesto, invece di essere apprezzato, è stato solo avversato con obiezioni alla mia dimostrazione che definire ridicole è dir poco...

"ramath":la mia opinione sul cosiddetto "algoritmo crittografico" l'ho già espressa a inizio del post

Come già detto non sono un esperto di sicurezza informatica, mi sono limitato a dimostrare la correttezza di una "proprietà" matematica... e non sono certo il difensore del metodo crittografico dell'autore, su cui peraltro io stesso ho espresso alcune riserve nell'altro forum.
Ma detto ciò, al momento nessuno mi ha ancora spiegato in modo logico e argomentato perché mai l'utilizzo della suddetta proprietà in ambito crittografico, benché non introduca magari nulla di rivoluzionario, sia di per sé sbagliato. Quindi se vuoi farlo tu, accomodati!


P.S.
Anche il titolo stesso di questa discussione è profondamente fuorviante.

[ramath]

"utente__medio":
P.S.
Anche il titolo stesso di questa discussione è profondamente fuorviante.

e quindi? mica l'ho aperta io questa discussione, l'ha aperto quello che fa finta di non essere l'autore del metodo stesso, evidentemente pensa di essere molto furbo ma si vede benissimo che è lui

"utente__medio":
Peccato siate stati voi a riempire tre pagine di "nulla", e se non mi aveste tirato tirato in ballo non mi sarei mai sognato di intervenire in quest'inutile topic.

ti avrei tirato in ballo? io non ho fatto né nomi né riferimenti, la cosa curiosa è che tu ti sia accorto di questa discussione "per caso", ma non stiamoci a prendere in giro, te l'ha segnalata lo stesso utente che l'ha aperta, il "programmatore".

"utente__medio":
al momento nessuno mi ha ancora spiegato in modo logico e argomentato perché mai l'utilizzo della suddetta proprietà in ambito crittografico, benché non introduca magari nulla di rivoluzionario, sia di per sé sbagliato. Quindi se vuoi farlo tu, accomodati!

l'hanno spiegato un sacco di volte sia su quel forum che su altri, solo che voi (intendo né tu né il programmatore) non riuscite proprio a capirlo: i numeri primi che si usano (direi usavano) sono casuali, non si possono generare con le normali librerie dei linguaggi di programmazione, e sono selezionati con criteri che rendono il semiprimo risultante "praticamente inattaccabile" agli algoritmi di fattorizzazione (tali algoritmi potrebbero in realtà fattorizzarlo, ma solo in tempi blblici).
Ve l'ha detto l'ultima volta il tizio che hai insultato (facendo oltretutto una figura veramente pessima visto che non poteva spiare niente) quando ha parlato di entropia dell'informazione al programmatore, ve l'ha detto anche un programmatore esperto su un altro forum ancora; sai cos'è l'entropia di un semiprimo? quando moltiplichi i 2 numeri primi che lo compongono la sequenza di cifre non ha nessuna regolarità, né nelle cifre decimali, né nella sequenza di bit che lo rappresentano. Adesso vai ad aprire il file di testo col semiprimo che ha postato il programmatore e dimmi se ti sembra casuale. Bisogna essere veramente idioti per riuscire a non capire che è tutto meno che casuale con tutte le sequenze che si ripetono, si vede addirittura a occhio. Quella è la debolezza ovvia a chiunque ne capisca qualcosa.
E poi la password che dovrebbe decifrare, a parte che non si capisce da dove arriva, è tutto tranne che sicura, a giudicare dai pochi esempi che ho visti anche con numeri piccoli ci possono essere migliaia di numeri che possono funzionare da password

[utente__medio11]

"ramath":ti avrei tirato in ballo?

Direi proprio di sì:

"ramath":Purtroppo hai ragione, il "soggetto" che ha fatto il programma pare che si sia alleato con uno che vuol fare il matematico e ha addiritutra aperto un topic su questo forum, come ci ha fatto notare l'utente che ha aperto questa discussione ed è collegata a quella di Toms che avevo linkata prima. La discussione qui non se l'è filata nessuna, su Toms invece gliel'hanno chiusa, poi riaperta (non si capisce perché), e dopo la riapertura il "matematico" ha fatto una figuraccia epica accusando i moderatori del forum e offendendo gli utenti... morale della favola alla fine la discussione l'hanno chiusa definitivamente e hanno bannato il "matematico".

[...]

Su Internet è pieno di questa gente

"ramath":la cosa curiosa è che tu ti sia accorto di questa discussione "per caso", ma non stiamoci a prendere in giro, te l'ha segnalata lo stesso utente che l'ha aperta, il "programmatore".

Non me l'ha segnalata nessuno, frequento questo forum e questa sezione da tempo... prima che mi coinvolgeste non sono intervenuto semplicemente perché come già detto ritenevo questo topic indegno di qualsiasi risposta.

"ramath":l'hanno spiegato un sacco di volte sia su quel forum che su altri, solo che voi (intendo né tu né il programmatore) non riuscite proprio a capirlo: i numeri primi che si usano (direi usavano) sono casuali, non si possono generare con le normali librerie dei linguaggi di programmazione, e sono selezionati con criteri che rendono il semiprimo risultante "praticamente inattaccabile" agli algoritmi di fattorizzazione (tali algoritmi potrebbero in realtà fattorizzarlo, ma solo in tempi blblici).
Ve l'ha detto l'ultima volta il tizio che hai insultato (facendo oltretutto una figura veramente pessima visto che non poteva spiare niente) quando ha parlato di entropia dell'informazione al programmatore, ve l'ha detto anche un programmatore esperto su un altro forum ancora; sai cos'è l'entropia di un semiprimo? quando moltiplichi i 2 numeri primi che lo compongono la sequenza di cifre non ha nessuna regolarità, né nelle cifre decimali, né nella sequenza di bit che lo rappresentano. Adesso vai ad aprire il file di testo col semiprimo che ha postato il programmatore e dimmi se ti sembra casuale. Bisogna essere veramente idioti per riuscire a non capire che è tutto meno che casuale con tutte le sequenze che si ripetono, si vede addirittura a occhio. Quella è la debolezza ovvia a chiunque ne capisca qualcosa.
E poi la password che dovrebbe decifrare, a parte che non si capisce da dove arriva, è tutto tranne che sicura, a giudicare dai pochi esempi che ho visti anche con numeri piccoli ci possono essere migliaia di numeri che possono funzionare da password

Innanzitutto non capisco perché continui a parlare al plurale e dai per scontato che io conosco vita, morte e miracoli dell'autore del metodo... perché mai dovrei essere a conoscenza di tutte le discussioni che ha aperto in internet nel tempo!? E anche i riferimenti che fai ai suoi programmi sono perfettamente inutili, in quanto, non conoscendo il python, non ho mai letto il suo codice.
Poi quello che hai scritto a mio modo di vedere non ha molto senso né a livello sintattico né a livello semantico... per esempio che intendi con "numeri primi casuali" e "entropia di un semiprimo"!?
E poi, invece di ripetere in modo astratto che mi avrebbero già risposto, argomenta in modo chiaro perché mai l'utilizzo di quella proprietà in ambito crittografico sia di per sé sbagliato (e bada bene che la mia domanda è sincera e non sto affatto escludendo tale possibilità). Però ti prego, non mettere di nuovo in mezzo il codice dell'autore, ma rifatti direttamente all'applicazione della formula 10) della mia "dimostrazione".



P.S.

"ramath":tu puoi pensare di aver dimostrato quello che vuoi ma dal punto di vista della crittografia, che è l'unica cosa che mi interesserebbe, hai fatto uno sforzo inutile.

Ora dici che non te ne frega, ma guarda che scrivevi prima:

"ramath":[quote="AlgoGC57"]La parte matematica è quella che lui non dimostra e vorrei tanto sapere da un matematico quali sono gli strafalcioni che fa in quell'ambito e che fanno cadere tutto il suo pseudo algoritmo.

la mancanza di dimostrazioni è esattamente ciò che fa cadere tutto![/quote]

[AlgoGC57]

Scrivo solo per ribadire che io NON sono l'autore del presunto metodo. Volevo solo una spiegazione da matematici ma in questo forum non mi pare ce ne siano tanti.
La polemica non mi interessa, se ilvthread finisce in flame io non lo seguo più, potete chiuderlo.

[apatriarca]

Chiudo la discussione perché a questo punto mi sembra sia solo polemica e insulti.