Programma di criptazione/decriptazione (Parte 2)

[M1n021]

Il topic, come si evince dal titolo, vuole essere una continuazione (si spera più serena e ragionata) della seguente discussione chiusa un po' di tempo fa: https://forum.tomshw.it/threads/programma-di-criptazione-decriptazione.932244/

Il fatto che il metodo ideato da @piergiac-1, stando alle sue sperimentazioni, sembrasse funzionare, mi ha incuriosito, e quindi ho deciso di approfondire la questione cercando di capire cosa avvenisse matematicamente dietro le quinte, in modo da poter giungere alla fine ad una sua dimostrazione o confutazione.

---

Il primo passo è stato quello di inquadrare meglio e formalizzare il metodo proposto dall'autore, che più o meno dovrebbe essere il seguente.
Sia p un numero primo e siano e1 > e2 e b degli interi positivi. Sia poi z = p^[(e1+e2)/2] (dove le parentesi quadre indicano in questo caso la divisione intera), mentre p1 e p2 sono due generici numeri primi appartenenti rispettivamente agli intervalli [p^e1 + 1 ; p^e1 + 2^b] e [p^e2 + 1 ; p^e2 + 2^b] . Si afferma che determinati valori di p, e1, e2 e b individuano una famiglia di semiprimi s = p1*p2 (costituiti cioè dal prodotto di due primi prelevati da ciascuno dei suddetti due intervalli) per cui la formula MCD(s , s mod z) fornisce la fattorizzazione del semiprimo (restituendo il MCD o p1 o p2 ). Fine.

---

Non starò qui a tediarvi con tutti i passaggi, mi limito quindi a dire che, ragionando matematicamente su quanto appena scritto, ho dedotto che il suddetto MCD non può restituire il maggiore dei due numeri primi (ossia p1), quindi qualora il metodo fosse corretto dovrà per forza essere

a) MCD(s , s mod z) = MCD(p1*p2 , p1*p2 mod z) = p2

Inoltre dalla a) si deduce che p1*p2 mod z deve essere un multiplo di p2 , che in matematichese si può scrivere come

b) (p1*p2 mod z) mod p2 = 0

In seguito, facendo alcuni test su uno degli esempi numerici forniti dall'autore, mi sono reso conto che la proprietà b) non riguarda esclusivamente i numeri primi, ma sussiste per ogni coppia di numeri prelevata dai due intervalli; inoltre essa persiste anche oltre i limiti degli intervalli da lui fissati.
Alla fine, ragionando su questi presupposti, credo di aver capito cosa avviene matematicamente dietro le quinte:

Spoiler: Dimostrazione matematica

Dove la 14) dovrebbe essere proprio la proprietà riscontrata sperimentalmente dall'autore.

Per chiarire il senso della mia dimostrazione provo a fare un esempio numerico relativo alla 14).
Innanzitutto scegliamo due valori qualsiasi a e b (con a>b), per esempio a=8361 e b=207 . Il massimo valore della chiave c sarà c_max = a-1 = 8360 = 2^3*5*11*19; gli altri valori assumibili dalla chiave c sono i divisori di a-1 maggiori di b , come per esempio c_1 = 2^2*5*19 = 380 o c_2 = 5*11*19 = 1045 .
A questo punto siamo in grado di definire precisamente gli intervalli da cui prelevare i numeri primi, ossia [a ; a+i] e [b ; b+j) , con i e j definiti rispettivamente dalla 5) e dalla 6) (da cui si può notare che j dipende da i ). Volendo però si può semplificare il tutto riducendo gli intervalli a [a ; a+m] e [b ; b+m] , con m ricavabile dalla 8), da cui peraltro si deduce che al diminuire della chiave c diminuisce anche m ; quindi il massimo valore di m , e di conseguenza gli intervalli più ampi, si ottengono per c = c_max , e facendo i conti nel nostro caso si ottiene m=33 .
Quindi in definitiva la formula MCD(A*B , A*B mod c_max) = B sarà valida per tutti i numeri primi A e B prelevati rispettivamente dagli intervalli [8361 ; 8361+33] e [207 ; 207+33] .

---

In seguito poi si potrà anche approfondire la parte del metodo sviluppato dall'autore più legata alla crittografia, ma per il momento mi vorrei soffermare sulla parte più matematica, anche perché mi sembra di ricordare che c'erano alcuni utenti interessati alla questione.
Ovviamente eventuali osservazioni o correzioni relative alla dimostrazione matematica sono ben accette.

 

[BAT]

In seguito poi si potrà anche approfondire la parte del metodo sviluppato dall'autore più legata alla crittografia

in linea generale quella parte non va bene: la "(de)cifratura" la fa in 3 soli passi:

---

a = s mod chiave dove s è il semiprimo, con s=x*y con x,y primi, e appare "chiave magica"
b = s - a
p = MCD(a,b) dove s dovrebbe essere primo

innazitutto la chiave nel codice non è definita, non ci sono istruzioni che la esplicitino né funzioni che la calcolino, ma su questo ci torno dopo. Con questa premessa la chiave è arbitraria, dal punto di vista matematico potrebbe perfino coincidere con uno tra x ed y (o essere chiave>s), in tal caso se sostituisci x (o y) alla chiave ottieni

a = 0
b = s
p = MCD(0,s) = s

cioè s si fattorizza in sé stesso

---

l'obiezione sarebbe che la chiave non va scelta così, e allora come? va calcolata, e qui casca l'asino;
spulciando Internet tra i 1000 thread che ha aperto l'autore, la chiave magica se la calcola a parte e (parole sue) richiede anche giorni di lavoro per il PC ma come! non doveva essere O(1) l'algoritmo?
Per tacer del fatto che MCD non è certo O(1) e che in generale un MCD non restituisce affatto un numero primo!

Alla fin della fiera esce fuori che la "chiave" prima se la "calcola" con tempi noti solo a lui, gli esce fuori un numero magico buono SOLO per un certo intervallo, LO INSERISCE HARD-CODED nel codice e poi "decifri"!
Se cambi il semiprimo/intervallo), a seconda di quanto è grande ci vuole un'altra chiave, da ricalcolare (con giorni di lavoro...) come sopra.
Quindi cosa fa? calcola a parte e mette in un file di testo tutte le chiavi secondo lui possibili (in chiaro, ma è un dettaglio) incommentabile! Fai prima ad andare in vacanza per 6 mesi e lasciare porte e finestre spalancate a chiunque passi di là.
Non va bene letteralmente nulla di nulla, né matematicamente, né nei tempi né dal punto di vista sw, né della sicurezza.
Ma poi: per proteggere gli archivi di dati non si usa mica la cifratura asimmetrica!

Ma che non funzioni te lo dice la precedente discussione:

• gli hanno dato da fattorizzare un semiprimo e non c'è riuscito, bastava quello;
• gli hanno fornito 2 primi da moltiplicare e poi fattorizzare, invece di usare quelli li ha cambiati

Che un dilettante prenda una cantonata ci sta, le non-risposte perniciose che fornisce rendono impossibile discuterci.

Vai nel sito dell'autore a questa pagina: https://www.gc57crypto.net/presentazione-gc57eal
cito testualmente:

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.

Spoiler: bit e byte

byte da 6 bit, byte da 7 bit...

 

[M1n021]

@BAT scusa, ma sei completamente off-topic, dal tuo post si evince che se hai letto il mio messaggio iniziale, allora lo hai fatto con molta superficialità.

Avevo chiesto di tralasciare per il momento la parte sulla crittografia e di soffermarci su quella matematica, in modo da analizzare razionalmente il metodo complessivo proposto dall'autore, il quale si compone appunto di una parte più matematica (ossia la proprietà su cui si basa il metodo) e di una più legata alla crittografia (scelta delle chiavi pubblica e privata, sicurezza, efficienza, ...). Questo è l'unico modo per giungere ad una sentenza definitiva sul metodo.

Detto ciò, che l'autore non sia molto capace a spiegarsi e che abbia preso alcuni strafalcioni, nessuno lo mette in dubbio, ma il punto è un altro: lui ha sperimentalmente riscontrato una proprietà matematica, che dai test da lui fatti sembra effettivamente funzionare. Ora davanti a ciò c'è poco da divagare, nel senso che quella proprietà o la si dimostra (e quindi era corretta) o la si confuta (e quindi era sbagliata). Spinto da pura curiosità, questo è quello che ho fatto, e alla fine, anche se non proprio nei termini descritti dall'autore, sono riuscito a dimostrarla e a delinearne precisamente i contorni.

in linea generale quella parte non va bene: la "(de)cifratura" la fa in 3 soli passi:

a = s mod chiave dove s è il semiprimo, con s=x*y con x,y primi, e appare "chiave magica"
b = s - a
p = MCD(a,b) dove s dovrebbe essere primo

Per favore lasciate stare tutto quello che è stato scritto in passato, il metodo reale utilizzato dall'autore è quello che ho formalizzato nel post iniziale, ossia:

Il primo passo è stato quello di inquadrare meglio e formalizzare il metodo proposto dall'autore, che più o meno dovrebbe essere il seguente.
Sia p un numero primo e siano e1 > e2 e b degli interi positivi. Sia poi z = p^[(e1+e2)/2] (dove le parentesi quadre indicano in questo caso la divisione intera), mentre p1 e p2 sono due generici numeri primi appartenenti rispettivamente agli intervalli [p^e1 + 1 ; p^e1 + 2^b] e [p^e2 + 1 ; p^e2 + 2^b] . Si afferma che determinati valori di p, e1, e2 e b individuano una famiglia di semiprimi s = p1*p2 (costituiti cioè dal prodotto di due primi prelevati da ciascuno dei suddetti due intervalli) per cui la formula MCD(s , s mod z) fornisce la fattorizzazione del semiprimo (restituendo il MCD o p1 o p2 ). Fine.

Dove il tutto è stato riscontrato dall'autore solo sperimentalmente andando per tentativi e test.

 

[DispatchCode]

Io quando riesco ad avere del tempo da dedicare al tuo primo post, me lo leggo con calma. Mi sa quando sarò più tranquillo, con la testa senza task di lavoro

 

[BAT]

ma sei completamente off-topic, dal tuo post si evince che se hai letto il mio messaggio iniziale, allora lo hai fatto con molta superficialità.

hai ragione solo su una cosa: ho letto con troppa superficialità e ho dato per scontato che la parte matematica fosse giusta, invece non lo è.

Mentre tu devi dimostrare in generale, a me basta trovare un controesempio che nega la tesi per confutarla del tutto.
Nella formalizzazione che hai fatto (sulla cui correttezza non mi pronuncio) basta porre:

• p=3 (primo)
• e1, e2, b interi positivi con e1>e2 --> e1=2, e2=1, b=1 --> z=3
• di conseguenza intervalli disgiunti A=[10, 11], B=[4, 5] --> p1=11 unica scelta per A, p2=5 unica scelta per b
• --> s = 55 unico semiprimo possibile
• s mod z --> 55 mod 3 = 1, perché 55:3=18 con resto 1
• MCD(s, s mod z) = MCD(55, 1) = 1 --> niente fattorizzazione

obbiettare che il controesempio è patologico è inutile: la tesi è falsa in generale, l'esistenza di un singolo controesempio significa che ce ne sono infiniti altri;
tesi falsa in generale non esclude che esitano particolari valori che la verificano, che è ciò che ha fatto l'autore: usare numeri (pre)calcolati ad arte.

Ed ecco perché ero perfettamente in-topic: se usi valori particolari, la fattorizzazione a scopo di cifratura è troppo debole, infatti i primi coinvolti risultano avere una struttura calcolata che rende il metodo attaccabile.

 

[M1n021]

Mentre tu devi dimostrare in generale, a me basta trovare un controesempio che nega la tesi per confutarla del tutto.
[...]
obbiettare che il controesempio è patologico è inutile: la tesi è falsa in generale, l'esistenza di un singolo controesempio significa che ce ne sono infiniti altri;

Partiamo dal fatto che la seguente

Sia p un numero primo e siano e1 > e2 e b degli interi positivi. Sia poi z = p^[(e1+e2)/2] (dove le parentesi quadre indicano in questo caso la divisione intera), mentre p1 e p2 sono due generici numeri primi appartenenti rispettivamente agli intervalli [p^e1 + 1 ; p^e1 + 2^b] e [p^e2 + 1 ; p^e2 + 2^b] . Si afferma che determinati valori di p, e1, e2 e b individuano una famiglia di semiprimi s = p1*p2 (costituiti cioè dal prodotto di due primi prelevati da ciascuno dei suddetti due intervalli) per cui la formula MCD(s , s mod z) fornisce la fattorizzazione del semiprimo (restituendo il MCD o p1 o p2 ). Fine.

è una formalizzazione sì mia, ma sul metodo dell'autore, mentre la mia trattazione è quella sotto spoiler.
Fatte le dovute precisazioni, ti faccio notare che non hai confutato niente, in quanto la tesi afferma esplicitamente che la proprietà vale solo per "determinati valori di p, e1, e2 e b". Logicamente parlando, il giusto controesempio per confutare la tesi sarebbe quello di identificare degli intervalli per cui la formula MCD(s , s mod z) = p2 funziona per alcuni dei primi prelevati dai due intervalli, ma non per altri.
Poi sull'utilità o meno di questa proprietà matematica in ambito crittografico se ne può (e se ne dovrà) discutere, ma ridurre tutto a

numeri (pre)calcolati ad arte

mi sembra un approccio molto superficiale e logicamente inconsistente.
Poi vedo che insisti con queste fughe in avanti, ignorando il mio invito a stabilire prima la correttezza o meno di questa proprietà matematica e della mia dimostrazione. A tal proposito sarei curioso di sapere quali sarebbero gli errori matematici che avrei commesso.

hai ragione solo su una cosa ho letto con troppa superficialità e ho dato per scontato che la parte matematica fosse giusta, invece non lo è.

Riprova, magari la terza sarà la volta buona!

 

[BAT]

la tesi afferma esplicitamente che la proprietà vale solo per "determinati valori di

e io cosa avevo detto? rileggi sopra

la tesi è falsa in generale, l'esistenza di un singolo controesempio significa che ce ne sono infiniti altri;
tesi falsa in generale non esclude che esitano particolari valori che la verificano, che è ciò che ha fatto l'autore: usare numeri (pre)calcolati ad arte.

quindi è perfettamente inutile domandarmi un controesempio di una cosa su cui già concordo

mi sembra un approccio molto superficiale e logicamente inconsistente.

superficiale e inconsistente è estrapolare la seconda metà della frase ignorando la parte che ti ho evidenziato in rosso: ok, diciamo che in qualche caso funziona... ma per "dimostrare" vengono usati dei numeri specifici, questo non è dimostrare, puoi portare 1 miliardo di miliardi di esempi "buoni" che tutti insieme non fanno una dimostrazione

ignorando il mio invito a stabilire prima la correttezza o meno di questa proprietà matematica e della mia dimostrazione

stabilire la correttezza di quella che tu chiami dimostrazione sarebbe compito di un matematico professionista, non mio: se tu pretendi di aver dimostrato qualcosa a me lo vieni a chiedere? io vedo solo un mucchio di lettere, quando e se avrò tempo potrei anche guardarla ma non sposta di un millimetro il mio pensiero sulla questione