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

 

[M1n021]

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

Ma sei sicuro di aver capito di cosa si stia parlando?
L'autore ha scoperto sperimentalmente una proprietà matematica per cui la formula MCD(s , s mod z) = p2 risulta valida per ogni coppia di numeri primi prelevati da due determinati intervalli. La cosa mi ha incuriosito, ci ho ragionato un bel po' e alla fine l'ho dimostrata, nel senso che ho definito precisamente gli estremi dei due intervalli e ho dimostrato matematicamente che vale per ogni coppia di numeri primi da essi prelevata. Quindi la dimostrazione ci sta... per chi vuole vederla...

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

Ma che stai dicendo? Non nel senso che non sono d'accordo, ma nel senso che non ho proprio capito che significa quello che hai scritto...
Comunque, giusto per capirci, ti chiedo un paio di cose.

1) Se una tesi afferma che una certa proprietà si verifica solo in determinati casi, e in quei determinati casi effettivamente la proprietà è verificata, perché mai continuare a ripetere che la tesi è falsa in generale!? E' logica di base...

2) Continui a ripetere questo "numeri (pre)calcolati ad arte", ma precisamente a che ti riferisci? Lo hai capito vero che il metodo proposto dall'autore non è un algoritmo di fattorizzazione per generici semiprimi? La suddetta proprietà matematica serve per identificare delle famiglie di semiprimi che verranno poi utilizzate in ambito crittografico (sul come e sulla sicurezza se ne discuterà in seguito) . Ed è di questa pura proprietà matematica, slegata da qualsiasi applicazione crittografica, che parla il mio post iniziale... se poi leggendolo pensi a cose che non ho mai scritto non è certo colpa mia...
Spero che le incomprensioni nascano da questo fraintendimento, perché altrimenti davvero non capisco quello che stai dicendo...

 

[BAT]

Ma che stai dicendo? Non nel senso che non sono d'accordo, ma nel senso che non ho proprio capito che significa quello che hai scritto.

è una frase chiarissima: significa che ci possono essere valori (uno, pochi, tanti è ininfluente) per cui invece è vera. Per quale motivo è vera in certi casi? perché i primi/pseudoprimi che entrano in gioco non sono casuali ma sono prodotti in un certo modo.
Che sia vera in tutti i casi in cui "prelevi" primi da quei 2 intervalli, tu dici di averlo dimostrato... mah! qualche teorico dei numeri te l'ha validata? anche Fermat disse di aver dimostrato il suo "ultimo teorema" invece non aveva dimostrato nulla (circa 350 anni dopo si è rivelato vero, ma non nelle poche righe che millantò il grande matematico: la dimostrazione oggi c'è, ma non era la sua, sempre che sia esistita).

Ora che ci penso, nominando Fermat, mi viene in mente per associazione di idee che c'è un metodo di fatorizzazione chiamato appunto "Fattorizzazione di Fermat" che usa gli intervalli (più o meno); funziona abbstanza bene per numeri relativamente grandi (ma non troppo) i cui fattori siano "vicini" alla radice quadrata del numero. Quindi in particolare vale per i semiprimi e sono abbastanza convinto che l'idea degli intervalli da cui pescare primi è da lì che provenga.

Spero che le incomprensioni nascano da questo fraintendimento, perché altrimenti davvero non capisco quello che stai dicendo

le incomprensioni nascono da una sola cosa: ti ostini a voler ignorare il fatto che i numeri in gioco sono generati algoritmicamente; quello che tu dici essere irrilevante invece è esattamente il nocciolo della questione.

Possiamo trascurare il fatto che dal punto di vista crittografico quello che fa non va bene. Ma cosa fa l'autore?
Non ha fatto nessuna scoperta: genera numeri primi con molte cifre partendo da interi relativamente "piccoli" e poi usando pseudoprimi forniti da una funzione in Python e/o compie una serie di manipolazioni aritmetiche (elevamenti a potenza per esempio) su di essi.
E' da lì che derivano gli intervalli grandi (non c'è bisogno di ricavarli con ulteriori "dimostrazioni") ed è questo che intendo per "pre-calcolati ad arte": hanno una struttura precisa che li rende calcolabili e che determina gli intervalli d'uso; ma "strutturandoli" non può fattorizzare altro che ciò che decide lui.
Per quanto riguarda gli intercvalli in cui il metodo dovrebbe funzionare, è l'autore stesso che ne dà la dimensione: intervalli con numeri di alcuni centinaia di cifre dove, a detta sua, fattorizzi qualsiasi semiprimo usando le sue "chiavi". Io però sto ancora aspettando la fattorizzazione di questo semiprimo, che rientra perfettamente negli intervalli definiti: dov'è la fattorizzazione? E' il controesempio che il metodo non funziona su tutti i semiprimi da tot cifre, ma solo su quelli ottentui da primi "con struttura". Difatti, l'autore si è guardato bene dal rispondere, ha fatto semplicemente finta di nulla: perché? Semplice: perché non lo può fattorizzare!
Quindi di cosa stiamo parlando? un metodo che fattorizza solo quello che ti pare non serve a niente.

Questo è quanto.

La parte sotto spoiler cerco di guardarla quando ho tempo

 

[M1n021]

Che sia vera in tutti i casi in cui "prelevi" primi da quei 2 intervalli, tu dici di averlo dimostrato... mah! qualche teorico dei numeri te l'ha validata?

Da dove deriva quel "mah" se la parte sotto spoiler non l'hai nemmeno letta?
Poi, nonostante non sia né un "informatico" né un "matematico", ho la presunzione che ragionando e utilizzando la logica si possa dire la propria in qualsiasi campo, senza alcun complesso di inferiorità verso gli "esperti" o presunti tali. Questa è una filosofia di vita generale, in ogni caso relativamente alla dimostrazione (che si basa su matematica e logica di base, per cui non penso ci sia bisogno di scomodare un "teorico dei numeri") non sto escludendo categoricamente che non possa aver commesso qualche errore (anche se ne dubito), quindi se qualcuno me lo fa notare mi fa solo un favore.

Io però sto ancora aspettando la fattorizzazione di questo semiprimo, che rientra perfettamente negli intervalli definiti: dov'è la fattorizzazione?

Ma leggi quello che scrivo?

Lo hai capito vero che il metodo proposto dall'autore non è un algoritmo di fattorizzazione per generici semiprimi?

Poi che caspita significa che il semiprimo "rientra negli intervalli definiti"? Sono i numeri primi che compongono il semiprimo a dover rientrare nei due intervalli affinché la formula funzioni...

le incomprensioni nascono da una sola cosa: ti ostini a voler ignorare il fatto che i numeri in gioco sono generati algoritmicamente; quello che tu dici essere irrilevante invece è esattamente il nocciolo della questione.

Certo che sei duro di comprendonio... lascia stare tutto quello che ha detto l'autore in passato e lascia stare la crittografia, e limitati a quello che ti dico io...
Si sta parlando di una proprietà matematica per cui la formula MCD(s , s mod z) = p2 vale per tutti i semiprimi s = p1*p2 ottenuti dal prodotto di due generici numeri primi prelevati da due determinati intervalli. Fine.
Con la precisazione che l'autore ha ottenuto questi intervalli (non completi) in modo sperimentale e andando per tentativi, io invece nella dimostrazione mostro come calcolare questi intervalli in modo preciso e diretto.
Poi sul come l'autore utilizzi queste famiglie di semiprimi in ambito crittografico è un'altra storia; anche io ho alcune riserve al riguardo dal punto di vista della sicurezza e dell'utilità, ma ne parliamo in seguito.
Cioè più chiaro di così si muore...

---

P.S.
Per caso lo hai letto l'esempio numerico basato sulla mia dimostrazione che ho riportato alla fine del post iniziale?

 

[BAT]

che caspita significa che il semiprimo "rientra negli intervalli definiti"?

non è riferito agli intervalli dei primi che moltiplichi, ma all'intervallo numerico che contiene il semiprimo ottenuti per moltiplicazione; per capirsi, se moltiplichi 2 primi da 300 cifre, ottieni un semiprimo da 600 cifre. Sono dimensioni date dall'autore, mica da me.

Per farti stare tranquillo sulla mia presunta incapacità di comprensione, ti faccio il disegnino, ecco io capito questo, giusto no?
p e q sono i semiprimi che chiamo "strutturati", A è l'intervallo numerico che contiene p, e B è quello che contiene q, disgiunti, tutti e 2 "belli grossi" nel senso che contengono un'enormità di numeri, e, tanto per fissare le idee, sono numeri da 300 e passa cifre


In questi enormi intervalli ci saranno primi con "struttura"; moltiplicando tali primi ottieni semiprimi per cui esiste la chiave z che li fattorizza; che ne fattorizzi uno, alcuno o tutti non mi interessa; ma A e B sono intervalli numerici giganteschi, com'è possibile che contengano solo primi "strutturati"? (in realtà pesudoprimi restituiti da una funzione Python...).
Ci saranno altri numeri primi che una struttura non ce l'hanno (oppure ce l'hanno ma è diversa da quella con cui sono generati p e q); come diavolo puoi credere/pretendere che la chiave z nel modulo fattorizzi pure semiprimi generati con quelli? deve essere veramente magica se ne basta una, sempre quella, sempre la stessa, per domarli tutti, manco fosse il Signore degli Anelli.
Assurdo no? Questa non è matematica, è fantascienza.

Se sei convinto che esista, fammi vedere come fattorizzi il semiprimo dell'altra discussione: il programma dell'autore ce l'hai, quella che dici essere la dimostrazione pure, quindi hai il metodo e i limiti per trovare la chiave e tutti gli indici e i numeri (a, b, c, i, j, k, m) di cui parli nella dimostrazione, ossia sulla carta sei in gradissimo di generare gli intervalli giusti, basti che li fai grandi a sufficienza e avrai gli intervalli che servono, a forza di allargarli ci dovranno pur rientrare i primi che fattorizzano il numero proposto, ti pare?

Da dove deriva quel "mah" se la parte sotto spoiler non l'hai nemmeno letta?

perché è fatica sprecata, se pure dimostrasse qualcosa, dimostra una cosa noiosa e non interressante;
guardandola alla buona, vedo diverse cose che mi lasciano perplesso:

• intanto per 1), 2) e 3) bastava dire a>c>b (c>kb con k intero significa che c è maggiore di qualsiasi multiplo di b, ma solo fino a un certo punto, dovendo essere a>c)
• c=a-1 è il massimo valore per cui è vera 3), ma è falso che massimizza k, semmai lo minimizza (è un dettaglio comunque)
• 4) vale per qualunque combinazione a,b,c (con b<c, che è vero)
• dopo è un delirio: passi pure la 5), ma la 6) è una scelta per j assolutamente pessima: stabilisci che j è intero e per definirlo usi una frazione! con quella scelta j non è intero per la maggior parte delle volte (per i=0 j è intero, unico caso che mi piace); se i e c sono entrambi pari j non è intero; se i e c sono entrambi dispari j non è intero; ogni volta che i+1 non è un divisore esatto j non è intero, se è un divisore esatto "troppo grande" al risultato della divisione se sottrai b rende j negativo... mah!
• sempre allo stesso punto non si capisce cosa dovrebbe dire "limite superiore per entrambi" (i e j)
• 7) e 8) sono nebulosi, appaiono un'uguagliana dove al posto della j c'è i e al posto del < c'è l'uguale, suppongo a "ugiagliare" i valori di i e j per trovare il "limite superiore" per entrambi, dopodiché si trova la soluzione ed un valore m che nel resto della dimostrazione non viene neanche usato
• ad ogni modo, in generale j non è affatto un intero, ma lo è solo in particolari casi, per cui tutti i calcoli successivi semplicemente non si possono fare

Secondo me è da sistemare parecchio prima di essere accettabile.

 

[M1n021]

Ci saranno altri numeri primi che una struttura non ce l'hanno (oppure ce l'hanno ma è diversa da quella con cui sono generati p e q); come diavolo puoi credere/pretendere che la chiave z nel modulo fattorizzi pure semiprimi generati con quelli? deve essere veramente magica se ne basta una, sempre quella, sempre la stessa, per domarli tutti, manco fosse il Signore degli Anelli.
Assurdo no? Questa non è matematica, è fantascienza.

perché è fatica sprecata, se pure dimostrasse qualcosa, dimostra una cosa noiosa e non interressante;

Non mi sembra che le due affermazioni vadano molto d'accordo fra di loro!
Non so bene cosa intendi con "strutturati", comunque il senso della proprietà matematica che ho dimostrato è proprio quello che la "chiave" riesce a fattorizzare qualsiasi semiprimo ottenuto dal prodotto di due generici numeri primi prelevati dai due intervalli.

Se sei convinto che esista, fammi vedere come fattorizzi il semiprimo dell'altra discussione: il programma dell'autore ce l'hai, quella che dici essere la dimostrazione pure, quindi hai il metodo e i limiti per trovare la chiave e tutti gli indici e i numeri (a, b, c, i, j, k, m) di cui parli nella dimostrazione, ossia sulla carta sei in gradissimo di generare gli intervalli giusti, basti che li fai grandi a sufficienza e avrai gli intervalli che servono, a forza di allargarli ci dovranno pur rientrare i primi che fattorizzano il numero proposto, ti pare?

Non penso sia così facile beccare gli intervalli giusti, bisognerebbe rifletterci meglio dal punto di vista matematico; quindi non è un test così immediato da fare come invece vorresti farlo passare...
Inoltre non ho mai utilizzato il programma dell'autore, anche perché non conosco il python. Comunque non appena avrò implementato la radice intera (quella dell'altro topic) nella mia libreria sui big_int, e potrò quindi calcolare la 8), posso provarci; o ancora meglio posso fare un test con un altro semiprimo RSA la cui fattorizzazione è già nota e vedere se il metodo funziona scegliendo valori di a e b più piccoli dei due primi in questione.

---

intanto per 1), 2) e 3) bastava dire a>c>b (c>kb con k intero significa che c è maggiore di qualsiasi multiplo di b, ma solo fino a un certo punto, dovendo essere a>c)

Non basta dire che a>c>b , la 3) per esempio è indispensabile per la 10) .

c=a-1 è il massimo valore per cui è vera 3), ma è falso che massimizza k, semmai lo minimizza (è un dettaglio comunque)

Lo massimizza, in quanto k = [c/b] (dove le parentesi quadre stanno ad indicare la divisione intera).

4) vale per qualunque combinazione a,b,c (con b<c, che è vero)

a = 25 , b = 11 , c = 19 ... non mi sembra che 25*11 mod 19 faccia 11 .

dopo è un delirio: passi pure la 5), ma la 6) è una scelta per j assolutamente pessima: stabilisci che j è intero e per definirlo usi una frazione! con quella scelta j non è intero per la maggior parte delle volte (per i=0 j è intero, unico caso che mi piace); se i e c sono entrambi pari j non è intero; se i e c sono entrambi dispari j non è intero; ogni volta che i+1 non è un divisore esatto j non è intero, se è un divisore esatto "troppo grande" al risultato della divisione se sottrai b rende j negativo... mah!

i e j sono due interi, quindi è ovvio che in relazione alla 6) ti devi riferire alla parte intera; per esempio j < 5.13 significa che j può assumere i valori 0 , 1 , 2 , 3 , 4 , 5 , mentre j < 4 significa che j può assumere i valori 0 , 1 , 2 , 3 .
Inoltre il secondo membro della 6) non può mai essere negativo, infatti per i = i_max = k-1 si ottiene j < c/k - b , e dalla 2) si evince
che c/k > b .

7) e 8) sono nebulosi, appaiono un'uguagliana dove al posto della j c'è i e al posto del < c'è l'uguale, suppongo a "ugiagliare" i valori di i e j per trovare il "limite superiore" per entrambi, dopodiché si trova la soluzione ed un valore m che nel resto della dimostrazione non viene neanche usato

m rappresenta il massimo valore che possono assumere i e j affinché risultano verificate sia la 5) che la 6) .
Sì, m non viene utilizzato nel resto della dimostrazione, ma risulta molto utile nella determinazione pratica degli intervalli, come puoi notare dall'esempio numerico riportato alla fine del post iniziale. A tal proposito, lo hai letto?

ad ogni modo, in generale j non è affatto un intero, ma lo è solo in particolari casi, per cui tutti i calcoli successivi semplicemente non si possono fare

Ma che dici?! j è un intero per definizione... prima della 5) e 6) ho scritto esplicitamente "Introduciamo i due interi non negativi".

Secondo me è da sistemare parecchio prima di essere accettabile.

Non voglio escludere categoricamente che non possa aver commesso qualche errore, ma tra le obiezioni che mi hai mosso ti rendi conto che non ne hai azzeccata una?!

 

[BAT]

Non so bene cosa intendi con "strutturati"

già spiegato nell'altro post

comunque il senso della proprietà matematica che ho dimostrato è proprio quello che la "chiave" riesce a fattorizzare qualsiasi semiprimo ottenuto dal prodotto di due generici numeri primi prelevati dai due intervalli

in tal caso temo che gli intervalli saranno stretti stretti e non si possano allargare

Inoltre non ho mai utilizzato il programma dell'autore, anche perché non conosco il python

non è un problema perché non c'è nulla da analizzare: la fase di decifrazione è esclusivamente costituita dalle 3 istruzioni che ti ho messo in neretto nel mio primo post, non c'è nient'altro, me lo ha detto l'autore stesso nell'altra discussione. E difatti nel codice NON trovi il calcolo della chiave... quella viene messa nelle prove un'istruzione prima come una costante.

bisognerebbe rifletterci meglio dal punto di vista matematico; quindi non è un test così immediato da fare come invece vorresti farlo passare...

era ironico il commento

a = 25 , b = 11 , c = 19 ... non mi sembra che 25*11 mod 19 faccia 11 .

e cosa c'entra?
la premessa che fai è che a mod c = 1 quindi è ovvio che ab mod c = b, se dividi a per c e hai resto 1 è ovvio che se raddoppi il dividendo raddoppi il resto, se triplichi il dividendo triplichi il resto... fino ad arrivavare al massimo a c-1, e dato che b<c la cosa è vera, è la una normale proprietà del resto. Il senso del commento è che si poteva omettere, non che sia sbagliato.

Sì, m non viene utilizzato nel resto della dimostrazione

non serve, quindi non usarlo nella dimostrazione, la appesantisci solamente, usalo solo per controllare i test

ma risulta molto utile nella determinazione pratica degli intervalli, come puoi notare dall'esempio numerico riportato alla fine del post iniziale. A tal proposito, lo hai letto?

nel pochissimo tempo che ho ho guardato solo la dimostrazione, ho visto visto solo che gli intervalli sono piccoli e quindi contengono solo primi. Cosa credi che non abbia nulla da fare? tu a questa roba ci lavori a tempo pieno da almeno un mese, io è già tanto se riesco a connettermi per qualche minuto al giorno

I passaggi dal 9 all'11 non li ho guardati proprio essendomi fermatomi su j che poteva (per me) non essere intero. Sui calcoli successivi non ho dubbi che siano corretti.
Ma perrché noin sottoponi direttamente la questione su qualche blog/sito/forum/gruppo dove ci trovi gente che in un modo o nell'altro fa matematica per mestiere? Ti darebbero un parere molto più mirato e magari qualche suggerimento su come migliorare o procedere.
La matematica elementare di teoria dei numeri, per uqnato apparentemente semplice, è piena di trappole, un sguardo di uno del campo ti sarebbe di grande aiuto.