[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

Risposte
ramath
Salve,
la cosa mi ha incuriosito, per cui ho dato un'occhita al codice ed eseguito alcune ricerce ed anche delle prove, e posso tranquillamente affermare che si tratta di una buffonata: la teoria dei numeri e la crittografia avanzata sono una cosa seria, non è roba per dilettanti anche se dotati di buona volontà.

Durante la ricerca ho trovato il sito web dell'autore (https://www.gc57crypto.net/) dove "spiega" a parole come funzionerebbe. Purtroppo è fin troppo evidente che non abbia la minima preparazione né matematica né di teoria elementare della complessità computazionale.
Arriva ad affermare che la fattorizzazione di semiprimi (un semiprimo è un intero prodotto di 2 numeri primi non necessariamente distinti) sia eseguita in tempo O(1), una cosa che definire ridicola è perfino riduttivo: è matematicamente dimostrato che la fattorizzazione di interi è un problema di complessità esponenziale per computer deterministici, mentre in linea teorica su computer quantistici è polinomiale.
Il tutto si poggerebbe su una fantomatica "chiave" una specie di numero magico che permetterebbe la scomposizione del semiprimo che dovrebbe servire come cifratore di dati. Tale chiave è prodotta con calcoli arbitrari e senza nessuna giustificazione teorica.
Oltre alle dimostrazioni matematiche sono assenti le dimostrazioni formali di terminazione, correttezza e completezza dell'algoritmo.

A parte questo, semplicemente non funziona: dato in input un sempiprimo generico la fattorizzazione è errata (su piccoli semiprimi è immediatamente evidente anche con carta e penna che non può funzionare). Figuriamoci su semiprimi risultato di un prodotto fra grandi primi casuali.

Successive ricerche online mi hanno riportato a link su diversi forum:
https://www.iprogrammatori.it/forum-programmazione/python/nessuna-domanda-t52004.html
https://www.inforge.net/forum/threads/sicurezza-informatica-e-le-nuove-sfide.618601/
https://forum.tomshw.it/threads/programma-di-criptazione-decriptazione.932244/
l'autore elude o non risponde alle domande e quando lo fa le risposte sono al limite dell'assurdo, demenziali e irritanti. Nessuna dimostrazione solo "fidatevi funziona": ma non funziona...
Si trova perfino il link a un suo libro in vendita su Amazon, non ti consiglio di sprecare i meno di 3 euro che costa, meglio un buon caffé o un gelato

gabriella127
Ok, c'è qualcosa che non funziona sul sito, grazie a te! Ho cancellato i messaggi che mi avevi indicato.

AlgoGC57
Grazie della risposta @ramath, veramente completa. Anch'io la penso come te ma vorrei anche capire se esistono un paio di passaggi matematici formali da indicare (da parte di un marematico) che dimostrino quanto siano assurde le formulate usate.

P.S. @ramath per caso avevi partecipato con altro nick nella discussione su tomshw?

AlgoGC57
@gabriella127... a chi stai rispondendo??

gabriella127
"AlgoGC57":
@gabriella127... a chi stai rispondendo??


Rispondevo a ramath, c'è stato un disguido tecnico, ramath ha modificato il suo messaggio, ma inveceè è stato postato tre volte, e ne ho cancellati due che mi ha indicato.

AlgoGC57
Ok Gabriella.

Spero che qualche esperto di matematica (!) del forum mi possa dare qualche indicazione precisa

ramath
"AlgoGC57":
vorrei anche capire se esistono un paio di passaggi matematici formali da indicare (da parte di un marematico) che dimostrino quanto siano assurde le formulate usate.

P.S. @ramath per caso avevi partecipato con altro nick nella discussione su tomshw?

In realtà te l'ho già dato: è dimostrato che il problema della fattorizzazione di interi richiede un numero di passi esponenziale, la fattorizzazione di un semiprimo è un sottocaso del problema generale, quindi è esso stesso esponenziale.
Viceversa l'autore dice che bastano 3 istruzioni per risolverlo, il che è assurdo: in una delle dette istruzioni c'è una fantomatica "chiave magica" che lo permette: se fosse vero il calcolo di tale chiave richiederebbe tempo esponenziale; l'ultima istruzione è un MCD(a,b) dove a e b sono interi, non può garantire che il risultato sia un numero primo.

P.S
non partecipo ad altri forum di matematica, non ne ho il tempo

AlgoGC57
"ramath":
In realtà te l'ho già dato: è dimostrato che il problema della fattorizzazione di interi richiede un numero di passi esponenziale, la fattorizzazione di un semiprimo è un sottocaso del problema generale, quindi è esso stesso esponenziale.


Sì, ti ho ringraziato per la tua risposta e ne sono convinto anche io, ma vorrei fare l'avvocato del diavolo e andare un po' oltre.

Per assurdo, è possibile che in quel caso (dei semiprimi costruiti in quel modo) ci sia qualcosa che, attraverso calcoli con complessità minore, porti al risultato? No? Perché?

una fantomatica "chiave magica"


se fosse vero il calcolo di tale chiave richiederebbe tempo esponenziale


un MCD(a,b) dove a e b sono interi, non può garantire che il risultato sia un numero primo.


Tutto vero ma ...

non partecipo ad altri forum di matematica, non ne ho il tempo


Ok

interrupt_gate
Ciao,

Mi sono iscritto apposta per commentare qui, prima di girovagare per il forum. :)

Ho trovato "interessante" il topic...
Ho alcune considerazioni, iniziando a precisare di non essere un matematico (ma un informatico, prettamente mi occupo di codice in C).

Ho dato uno sguardo al sito linkato dall'utente e difficilmente una persona che sa quello che sta scrivendo può fare un'uscita come [1]:


Questo processo si completa in un tempo costante, inferiore a un secondo ([inline]O(1)[/inline]), indipendentemente dalla grandezza dei numeri coinvolti.


Già un'uscita come questa a mio avviso mette già in dubbio il contenuto, visto che si propone come un algoritmo rivoluzionario.

Non penso l'autore conosca il significato di[inline]O(1)[/inline] e dubito a questo punto riesca a fornire degli esempi (per esempio, quando si verifica un accesso in [inline]O(1)[/inline]).

Sembra che l'autore stia sostenendo a mio avviso "visto che ci impiega meno di 1s, allora è[inline]O(1)[/inline]". Quindi mi viene da pensare... se fosse stato in 5s, sarebbe stato [inline]O(5)[/inline]? :roll:

Non so se avevi fatto caso a questa parte del contenuto, AlgoGC57.

E poi ancora [2]:

Quando si parla di Byte e bit è facile cadere nella incomprensione più totale. Il Byte è un carattere o un simbolo rappresentato in bit: per esempio ‘!’ è un Byte e viene rappresentato con 6 bit 100001 e il suo codice decimale è 33. ‘a’ è un Byte e viene rappresentato con 7 bit 1100001 e il suo codice decimale è 97. ‘©’ è un Byte e viene rappresentato con 8 bit 10101001 e il suo codice decimale è 169.


"il byte è un carattere o un simbolo"... :?:
Il byte è 1 byte, è una sequenza di 8 bit. Il dato viene rappresentato come 8-bit, il modo in cui li interpreti fa parte di una codifica, che l'autore nemmeno cita (sarebbe stato molto più chiaro farlo); mi riferisco per esempio a ASCII, ISO Latin-1, UTF-8, UTF-16....

Il carattere 'a' occupa 1-byte, non occupa 6-bit perchè ci sono due leading zeroes...

Ma continuando a leggere, chissà quante altre inesattezze si trovano.

- [1] https://www.gc57crypto.net/nuova-pagina
- [2] https://www.gc57crypto.net/presentazione-gc57eal

ramath
"AlgoGC57":
Per assurdo, è possibile che in quel caso (dei semiprimi costruiti in quel modo) ci sia qualcosa che, attraverso calcoli con complessità minore, porti al risultato? No? Perché?

No, non è possibile e se ci fosse, la cifratura sarebbe inutile!

Se per "costruiti in quel modo" intendi che i semiprimi non siano casuali o meglio, che i 2 numeri primi che li enerano non siano casuali, ma "prodotti" con una specie di formula o con un qualche calcolo per diminuire la complessità, significa che invertendo il procedimento si possono ricavare attraverso la stessa foruula che li produce. Quanto minore è la complessità, meno generale è l'algoritmo e tanto più debole è la cifratura; invece la sicurezza della cifratura mediante prodotto fra 2 primi sta nell'estrema difficoltà della fattorizzazione.

Comunque AlgoGC57 gradirei un po' di correttezza: il tuo nick mi fa fortemente sospettare che non ti sei "imbattuto casualmente" in quel progetto, ma che tu stesso ne sia l'autore. Non che cambino di conseguenza le mie risposte.

axpgn
[ot]Da profano vi vorrei chiedere questo: nei vari metodi di cifratura che utilizzano la difficoltà di fattorizzare un semiprimo enorme, questo semiprimo è sempre lo stesso? Ne vengono utilizzati diversi? È sempre lo stesso ma viene aggiornato di tanto in tanto?
EDIT: riflettendoci un attimo deve essere sempre lo stesso in una determinata versione dello specifico algoritmo altrimenti i due corrispondenti non si capirebbero :D[/ot]

AlgoGC57
Grazie anche a te.

Avevo notato tutto quello che scrivi e tanti lo hanno contestato in altri forum. Sicuramente il tizio ha un sacco di carenze in tanti fronti (matematica informatica logica), fa un sacco di confusione su cognizioni di base e molte volte non sa quello che dice.

Ma quello che voglio sapere è se è andato a abbattere per caso un una soluzione al problema fattorizzazione (ne dubito fortemente) o è tutta una buffonata (a prescindere dai suoi strafalcioni).

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.

ramath
"AlgoGC57":

Ma quello che voglio sapere è se è andato a abbattere per caso un una soluzione al problema fattorizzazione (ne dubito fortemente) o è tutta una buffonata (a prescindere dai suoi strafalcioni).

è una buffonata: nelle 3 istruzioni che compongono la fattorizzazione, una è MCD(a,b) che ha un suo costo computazionale e che non è O(1); e questa e la cosa meno grave!

"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!
inoltre non può esistere nessun intero chiamato "chiave" che possa aiutare a fattorizzare indipendentemente dal semiprimo in input, questa è teoria dei numeri non geometria, dove esiste il numero $\pi$ buono per tutti i cerchi!

AlgoGC57
No ramath, ti assicuro che non sono io l'autore di tutto ciò, ho usato solo un nick casuale, sono corretto.

Mi sono imbattuto nella discussione su tomshw e ho cercato di capire se la cosa è contestabile a parte i generici discorsi sul fatto che ne verrebbe sconvolto il mondo della sicurezza informatica e della cifratura.

Mi sono fatto l'idea che il metodo parta sempre dalle soluzioni (ovvero lui parte sempre da p e q) e che in qualche modo ci ritorni (in maniera fallace). Ho anche apprezzato il giudizio di chi (su inforge) ha contestato le modalità di formazione del semiprimo (mi riferisco alla questione dell'entropia, se l'hai letta).

Credo anche io sia una buffonata.

Comunque, se vuoi dare un'occhiata a qualche altra discussione, ne esiste anche un'altra su

http://www.pierotofy.it/pages/extras/fo ... iptazione/

ramath
"AlgoGC57":

Mi sono fatto l'idea che il metodo parta sempre dalle soluzioni (ovvero lui parte sempre da p e q) e che in qualche modo ci ritorni (in maniera fallace). Ho anche apprezzato il giudizio di chi (su inforge) ha contestato le modalità di formazione del semiprimo (mi riferisco alla questione dell'entropia, se l'hai letta).

Basta molto meno:
1) un utente gli ha proposto un semiprimo da fattorizzare e la risposta ovviamente non è arrivata.
2) un altro utente ha proposto 2 primi da moltiplicare per ottenere un seminprimo (quindi in pratica la soluzione si poteva controllare) e invece di usare quelli li ha cambiati con calcoli non meglio specificati

Ma poi basta guardare il codice: il "miracoloso algoritmo" di fattorizzazione ha solo 3 istruzioni

a = s mod k dove $s$ è il semiprimo e $k$ la fantascientifica "chiave"
b = s - a
p = MCD(a,b)

$k$ non è definita (non c'è alcuna istruzione che la esplicita) e data la sua arbitrarietà potrebbe coincidere con uno dei semiprimi da trovare! in questo caso si verifica che
a = 0
b = s
p = MCD(0,s) = s
cioè il sempirpimo si fattorizza in sé stesso una cosa ridicola dato che a detta dell'autore p sarebbe primo ma coincide con un semiprimo (che no è un numero primo);
inoltre MCD non è "gratis", ha un costo computazionale, ciò rende automaticamente falsa l'affermazione di complessità costante o O(1)
MCD(a,b) in generale non produce un numero primo, se lo fa occorre dimostrarlo (dov'è la dimostrazione?)
ma anche se lo fosse non c'è nessuna garanzia che sia uno dei primi che hanno generato s (ancora: dov'è la dimostrazione?)

"AlgoGC57":
se vuoi dare un'occhiata a qualche altra discussione, ne esiste anche un'altra su

http://www.pierotofy.it/pages/extras/fo ... iptazione/

non l'ho letta, mi sono bastate le altre e già a un'occhiata superficiale le risposte del presunto genio sono dello stesso tenore, oltre a gridare al complotto

AlgoGC57
Grazie per il tuo tempo. Concordo su tutto quelli che hai detto, in particolare sulla definizione misteriosa di k

AlgoGC57

sivepofo
Scusate se mi intrometto ma sull'altro forum nella discussione che gli è stata chiusa il nostro soggettone afferma

### 2. **Divisibilità e fattorizzazione**
- I numeri come $2^n$ sono facilmente **divisibili per $2$**. Questo significa che hanno una struttura molto semplice dal punto di vista della divisibilità: saranno sempre divisibili per $2$, per $4$, per $8$, ecc.
- Invece, i numeri come $13^n$ sono molto più **difficili da scomporre** e hanno una struttura aritmetica più complicata. Ad esempio, $13^n$ non è divisibile per molti numeri (a parte $13$), e questo li rende più "irregolari" nella fattorizzazione.

Quasi si prendono a botte e si infamano per $O(1)$, ma nessuno si è accorto della perla (che dico diamante!)
Letto questo mi sono fermato e penso di aver risparmiato ore di vita.

Studiare un minimo i numeri primi e le potenze credo sia obbligatorio!

AlgoGC57
Ciao, il discorso si ricollega al seguente thread

https://www.matematicamente.it/forum/vi ... 9#p8681897

sivepofo
Se una persona, non importa chi, non si accorge che

Con $p$ primo e $n\in\mathbb{N}$

$\sigma_0(p^n)=n+1$

ed in particolare

$\sigma_0(2^n)=\sigma_0(13^n)$

o in altre parole

il numero di divisori di $2^n$ è uguale al numero di divisori di $13^n$
quello che segue a voler essere bastardi si interpreta solo come numerologia

In realtà non sono così bastardo e leggendo tra le righe interpreto come:
$2^n$ a causa di come sono fatte le attuali macchine calcolatrici ammette delle scorciatoie
quando si tratta di dividerlo. Rimane sempre il problema di come riconoscere che il numero
dato sia una potenza di $2$.

Tornando ad essere bastardo per la legge del contrappasso la persona in questione
finirà nel girone infernale dove hanno un IBM 1401 ed un demone senza farsene accorgere
gli sposterà di continuo la levetta che commuta da sistema decimale a sistema LSD.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.