Newsgroup: it.comp.sicurezza.crittografia
Titolo: Mai più numeri primi !!!  (Chiarimenti sula procedura XEVRON )

Un saluto a tutto il Ng
Sono uno degli inventori della procedura brevettata denominata XEVRON e
spero di fare cosa gradita con un articolo chiarificatore.
Mi rendo conto che probabilmente il testo introduttivo presente al sito
sia davvero "troppo" semplificato e molti di voi l'avranno cestinato
prima di arrivare in fondo. Inoltre l'internet draft è ancora in stato
di sviluppo... Cercherò quindi adesso di colmare le attuali lacune nella
documentazione.
XEVRON è stato reso pubblico il 6 Marzo 2007. Il suo funzionamento è
completamente diverso dagli attuali sistemi di crittografia a chiave
pubblica. Nella procedura non vi è nessuno scambio di password, bensì la
generazione separata e non contestuale della medesima stringa.
Questa generazione avviene tramite l'utilizzo di funzioni unidirezionali
(il troncamento bilaterale su ResA e ResB) che rendono il procedimento
irreversibile (fino a prova contraria) ma che permettono ai valori
residui ( MidA e MidB ) di conservare una residua proprietà associativa
che, nella successiva moltiplicazione con i valori segreti, permette di
ottenere una stringa comune.
Per spiegare meglio il troncamento bilaterale effettuato sui numeri
procedo con un esempio grafico: (font monospaziato aiutami tu :-)
Si parte dalla banale moltiplicazione di A * B e quindi
A*B=C
Chiaramente conoscendo due di questi numeri (e il ruolo che ogni numero
ha avuto nella operazione effettuata) posso conoscerne il terzo.
Consideriamo però A come un numero di 10 cifre e rappresentiamolo
graficamente come (AAAAAAAAAA) e facciamo la stessa cosa per B (BBBBBBBBBB)
Stessa cosa faremo con il numero C rappresentandolo con tante C quante
sono le cifre del risultato.
L'interrogativo è:
Un soggetto che non conosca A, ma che conosca tutte le cifre del numero
B e le sole cifre centrali del numero C, può in qualche modo risalire ad
A ? ( o anche solo ad alcuna delle cifre di A ?)
Esempio esplicativo
Usiamo il carattere X per indicare le cifre sconosciute e rappresentiamo
pertanto le cifre come le conosce l'attaccante ( EVA )
        A=                   XXXXXXXXXX *
        B=                   BBBBBBBBBB =
        ----------------------------------
        C=         XXCCCCCCCCCCCCCCCCXX
In una situazione del genere, dove A è completamente ignoto e C è
parzialmente ignoto nei due caratteri a sinistra e nei due caratteri a
destra, è possibile risalire ad A ( o ad almeno alcune cifre di A) SENZA
effettuare tutte le possibili combinazioni dei valori di X ?
ESEMPIO PRATICO:
TEST DI REVERSIBILITA' numero FG1
Qualora si sia trovata una soluzione per ricavare (anche parzialmente) A
che sia diversa dal provare tutti i possibili valori di X, è possibile
risolvere
la seguente operazione di cui non viene fornita la soluzione ?
elementi noti
A è un numero ignoto composto da 14 cifre
B è un numero noto composto da 14 cifre
C è un numero parzialmente noto composto da 28 cifre di cui 8 ignote, le
prime 4 di sinistra e le prime 4 di destra.
                                 A=                    XXXXXXXXXXXXXX *
                                 B=                    41349255047741 =
                                    ---------------------------------
                                 C=      XXXX61431825915923891854XXXX
è possibile risalire ad A (anche parzialmente) con i dati noti evitando di
provare tutte le possibili combinazioni dei valori di X di destra e/o di
sinistra ?
Empiricamente abbiamo constatato che avendo tutte le cifre di C di
destra, o avendo tutte le cifre di C di sinistra è possibile risalire
alla quasi totalità degli elementi di A in pochissimi tentativi ( da
sinistra è facile... da destra occorre un minimo di fantasia). Ma cosa
succede quando a destra e a sinistra mancano decine di cifre ?
La procedura, lo ammetto, può sembrare bislacca, eppure è alla base di
una procedura crittografica dai risvolti molto importanti. Poichè è vero
che i numeri troncati rendono irreversibile il procedimento ( a quanto
pare ) ma rimane una proprietà associativa residua negli elementi
centrali che trasforma questa moltiplicazione in una operazione ONE-WAY.
Come si nota dai documenti e dai software dimostrativi rilasciati con
relativo sorgente, gli unici elementi che viaggiano in chiaro tra due
soggetti sono: Sh, MidA e MidB. E da questi elementi lo staff di
XorLabs.net non crede sia possibile ricavare idA, idB o il valore comune
generato alla fine senza effettuare un banale brute force sui
troncamenti effettuati (con le conseguenze che tutti sapete).
Il "Tipo 1" è stato rilasciato per esclusive finalità di studio.
Il "Tipo 2" offre una resistenza al bruteforce pari a 2^64.
Il "Tipo 3" offre una resistenza al bruteforce pari a 2^160 e il "Tipo
4" di ben 2^384
Nonostante la procedura sia scalabile all'infinito (aumentando le
lunghezze o anche solo aumentando le basi numeriche, pertanto con un
aggravio minimo per la CPU !, per il momento abbiamo rilasciato questi
soli 4 tipi.
Inutile dire che XEVRON funziona con troncamenti e dimensioni di chiavi
variabili.
Come dimostreranno i software che rilasceremo a breve, conoscendo la
dimensione dei troncamenti e la dimensione in cifre delle chiavi
private, è sempre possibile calcolare con precisione assoluta la zona in
cui in SecA e in SecB saranno presenti dei valori comuni (senza quindi
ulteriori handshake). Per facilità di implementazione abbiamo comunque
deciso di utilizzare per il momento i soli 4 tipi convenzionali.
Oggi ( 7 marzo ) abbiamo rilasciato XEVRON-Password-Maker. Un software
multipiattaforma che permette a due utenti remoti di generare la
medesima password seguendo le specifiche XEVRON-T3.
Il software si appoggia a dei PHP per memorizzare temporaneamente i
valori Sh, MidA e MidB e, come tradizione di XorLabs.net tutto il
software è disponibile corredato di codice sorgente, ivi compresi i php
e la query per creare la tabella di Mysql. Tutto il software è tutelato
dalla licenza Vcube appositamente redatta.
Certi di aver stuzzicato la curiosità dei crittografi italiani (per il
momento) porgiamo distinti saluti.
XorLabs Staff
Daniele Vantaggiato
Gabriele Nardella

pare ) 
e due
Devi avere pazienza, ma da appassionato di crittografia e da persona
che ha letto numerosi testi, non posso accettare il "fino a prova
contraria" e "a quanto pare" :-)
Purtroppo la storia insegna che sono due frasi smontano tante teorie

 sinistra ?
Effettivamente sembra una questione ben più difficile di quelle proposte 
dalla settimana enigmistica.
Il numero C noto non ha nessuna relazione matematica con il prodotto di 
A * B eppure conserva la sua proprietà associativa :-O
IMHO servirebbe qualche approfondimento matematico.
nell'insieme sembra troppo semplice eppure il software per il test 
automatico funziona con qualsiasi valore !!!!
sono curioso di vedere gli sviluppi.


Rispondi-a: crypto(at)
sikurezza.org
A: crypto(at)
sikurezza.org
Se mi sbaglio qualcuno mi corriggera', come diceva uno piu' famoso di me...
partendo da 
http://www.xorlabs.net/XEVRON_internet_draft.txt
 e da
http://www.xorlabs.net/introduzione_XEVRON.pdf
 un paio di osservazioni:
1) la RFC e' abbastanza incomprensibile, suggerisco una riscrittura
completa: potrei aver capito male quello che fate
2) Confermo quanto dice Alessandro (bravo, chi t'avra' insegnato ;-),
e' una rifrittura dello scambio di chiavi alla diffie-hellman (strano
che non venga citato... non voglio nemmeno pensare che sia ignoto agli
autori) solo che al posto di un logaritmo modulare c'e' la presunta non
invertibilita' di una operazione di prodotto in modulo.
3) Purtroppo, la proprieta' che gli autori hanno "scoperto" (e non
dimostrato formalmente, il che me la rende sospetta d'esser vera
numericamente "a meno di casi particolari", in particolare sui carry
della moltiplicazione, ma vado a naso) si puo' riscrivere (mi perdonino
i matematici) come "non e' importante, per il prodotto, il contenuto
delle parti scartate". Questo probabilmente vale sia in avanti che
indietro (per la divisione): gli autori nemmeno si pongono il problema
di dire perche' non sia cosi'. Non ho molta voglia di perdere tempo IO a
fare i conticini per loro, ma ad occhio l'algoritmo nasce gia' rotto.
4) la proprieta' per cui cambiando L'ORDINE il prodotto non cambia e' la
proprieta' commutativa, non associativa ;)
5) gli algoritmi in Europa ed in Italia non godono di protezione
brevettuale (in particolare un'applicazione della MOLTIPLICAZIONE...),
ne' tantomeno vi si possono imporre condizioni di licenza se non vengono
tutelati come segreto industriale. Ma tanto questo e' un problema che si
pone solo per algoritmi interessanti da un punto di vista commerciale :)
6) riguardo alla presunta riduzione dei tempi di calcolo, stiamo
parlando di differenze totalmente irrilevanti, in quanto si tratta solo
dell'overhead di scambio di chiave. I tempi citati dagli autori non sono
ben chiari, ma sicuramente si riferiscono all'uso di RSA per
crittografare testi, non per lo scambio di chiavi. Diffie-Hellman a sua
volta ha tempi assolutamente compatibili con la tecnica suggerita dagli
autori.
Riassumendo:
- Il protocollo di scambio di chiavi e' mal descritto
- Non viene dimostrata la presunta proprieta' numerica su cui si basa
- Non viene data motivazione per la presunta non invertibilita' della
stessa, nemmeno viene analizzata in realta'...
- In ogni caso, anche se l'algoritmo funzionasse, e anche se si
analizzasse la non invertibilita', l'algoritmo non presenta
significativi margini di speedup rispetto all'uso di Diffie-Hellman per
lo scambio di chiavi
Morale (come gia' detto): snake oil.
-- 
Cordiali saluti,
Stefano Zanero
Politecnico di Milano - Dip. Elettronica e Informazione
Via Ponzio, 34/5 I-20133 Milano - ITALY
Tel.    
+39 02 2399-4010
/3660
Fax.    
+39 02 2399-3411
E-mail: zanero(at)
elet.polimi.it
Web:    
www.elet.polimi.it/upload/zanero
________________________________________________________
http://www.sikurezza.org
 - Italian Security Mailing List

 
http://www.xorlabs.net/introduzione_XEVRON.pdf
 un paio di osservazioni:
[CUT]


 ha scritto nel messaggio 
news:45f340ec$0$815$4faf...@reader5.news.tin.it...


 
A questi risponderò quando avrò capito l'esatta natura della sua 
perplessità, ma se legge con attenzione sono tutti casi verificati.
Cordiali saluti.
Gabriele Nardella

 ha scritto nel messaggio 
news:45f59fb1$0$10618$4faf...@reader2.news.tin.it...


 
Come le dicevo prima, quella formula non serve "a rappresentare i due 
fattori" ma solo a predire dai 2 fattori iniziali quanto sarà lungo il 
prodotto in cifre, inoltre applicata a XEVRON (e con questo concludo) 
serve solo per offrire un richiamo successivo ed un valido aiuto nella 
scelta opportuna di h' e k' per verificare che continuino a conservare 
la parziale associatività nella parte centrale.
Nella speranza di aver chiarito meglio le idee che sono alla base di 
XEVRON, porgo i miei distinti saluti.
Gabriele Nardella
- -
Il suddetto procedimento è stato oggetto di studio per mesi ed 
attualmente a parte un attacco che mira al bruteforce del valore finale 
oppure delle informazioni incomplete che passano in chiaro (MidA e 
MidB), non sono stati trovati punti deboli. Si incoraggia chiunque a 
provare a scardinare tutto o parte dello scambio chiavi XEVRON per 
testarne l'effettiva validità. Ricordo inoltre che al sito di 
riferimento 
http://www.xorlabs.net/
 sono disponibili gratuitamente le 
specifiche e PDF esplicativi, i sorgenti in diversi linguaggi, la 
dimostrazione matematica dei fondamenti della procedura e un internet 
draft in continuo aggiornamento che sarà presto inoltrato in inglese 
all'rfc-editor per ottenere una "request for comment" ufficiale non 
appena l'internet draft avrà raggiunto una forma sufficientemente chiara 
e precisa.

 e precisa.
Non capisco, onestamente, perché non abbiate scritto tutta la documentazione
(anche quella preliminare) direttamente in inglese. Avreste evitato di
doverne fare due versioni (giacché la traduzione in italiano non sarebbe
stata di alcuna utilità) e avreste potuto raccogliere commenti da tutta la
comunità di esperti del mondo sin da subito.
Max

 contraria" e "a quanto pare" :-)
sulla dimostrazione che hanno rilasciato cosa ne pensi ?
le mie conoscenze matematiche limitate non mi permettono di approfondire
così tanto l'argomento.
il generatore di password tra due utenti che hanno rilasciato però
funziona bene :-)
magari non sarà sicuro esattamente quanto dicono ma è sempre meglio che
mandarsi la pwd in chiaro su icq :-)

 discussione sul gruppo 'sci.crypt.research'.
e perché? Una volta che finalmente non si parla di come recuperare la 
password di tc, o di come 'proteggere' una cartella.
Non capisco perché dobbiamo rinunciare ad usare l'italiano quando 
possiamo: in Francia non si sognerebbero mai di rinunciare al francese.
Va bene utilizzare la lingua standard di fatto per l'interscambio 
quando c'è necessità, molto meno rinunciare sempre alla propria.
Immagino che l'OP abbia scelto per l'annuncio questo gruppo, oltretutto 
perfettamente IT, ponderando la scelta.
Se invece vogliamo dire che questo gruppo è inadatto al tema...
-- 
Sans

Calma ragazzi, entrambi dite cose giuste. Xor Labs group ha postato 
prima tutta la documentazione in italiano per raccogliere consensi in 
primis tra le menti italiane, e qui po' di orgoglio patriottico non 
guasta, perchè siamo sicuri di avere sulla scena nazionale, grandi 
ricercatori e studiosi; vantare l'Italia come unico posto o almeno uno 
dei pochissimi in cui qualcuno è stato in grado di proporre uno scambio 
chiavi alternativo al Diffie-Helman, che non fa uso in alcun modo dei 
numeri primi ed altrettanto sicuro, sarebbe cosa di non poco conto.
XEVRON, quando è scaduto il periodo di segretezza imposto dal deposito 
brevettuale è stato illustrato ad alcuni professori, Analisti, 
Algebristi etc etc.. di alcune grandi università italiane, nonchè 
notificato a qualche matematico italiano noto anche per le sue 
apparizioni in TV.
Ognuno di questi pure senza sbottonarsi troppo ha mostrato un certo 
interesse per la cosa, qualcuno anche senza risparmiare i complimenti. 
Ma non sono giunte idee efficaci sul piano pratico a scardinare tale 
sistema.
Quindi, premesso che non mancherà occasione di divulgare la cosa anche 
sul panorama internazionale, intanto si cerca di capire se salta fuori 
qualche pecca del sistema "evidente" o anche nascosta. Si effettuano 
tutte le traduzioni del caso e quando sarà il momento se ancora non ci 
saranno rilevanti novità si estende la conoscenza di tale sistema anche 
ai nistri colleghi di altre nazionalità.
In particolare Xor Labs group sarà riconoscente a chi ponendosi con 
atteggiamento costruttivo nei confronti dell'argomento, cercherà di 
scardinare la procedura di scambio chiavi denominata XEVRON (non solo a 
parole)
Attualmente gli autori sono convinti che non sia algebricamente 
possibile in alcun modo tornare indietro dai valori troncati a quelli 
completi.
Si indaga però sulla eventuale possibilità di rappresentare e descrivere 
in formule i numeri troncati come "gruppi abeliani isomorfici".
Nella speranza che quest'ultima informazione possa servire a qualcuno 
per intraprendere studi più seri che non si limitino solo ad un'analisi 
algebrica sommaria.
Cordiali saluti.
Gabriele Nardella

 ha scritto nel messaggio 
news:et63tt$41l$1...@newsreader.mailgate.org...


 effettuare tutte le possibili combinazioni dei valori di X ?
Sia C = y_1 y_2 .......... y_3 y_4
Per ogni (x_1, x_2, x_3, x_4) in [0,9]^4 e in N^4,
   se B divide C e C/B ha il giusto numero di cifre
     C = x_1 x_2 .... x_3 x_4
Ma si puň procedere molto piů efficientemente fattorizzando B.
Per non complicare le cose, faccio un esempio semplice semplice, ma che 
rende l'idea.
Vogliamo trovare A a partire da B e midC:
A = abcd
B = 1746
C = x15198y
Il brute force approach prova tutte le coppie (x,y).
Procediamo invece fattorizzando B.
B = 2*3^2*97
C = x*10^6 + 151980 + y
Se B divide C allora ogni fattore primo di B divide C.
1) 2
2|C ("2 divide C")
C = 0 (mod 2)
x*10^6 + 151980 + y = 0 (mod 2)
0 + 0 + y = 0 (mod 2)
y = 0 (mod 2)
2) 3
3|C
C = 0 (mod 3)
x*10^6 + 151980 + y = 0 (mod 3)
x*1 + 0 + y = 0 (mod 3)
x + y = 0 (mod 3)
3) 97
97|C
C = 0 (mod 97)
x*10^6 + 151980 + y = 0 (mod 97)
x*27 + 78 + y = 0 (mod 97)
Riassumendo:
1) y = 0 (mod 2)
2) x + y = 0 (mod 3)
3) x*27 + 78 + y = 0 (mod 97)
Non č molto difficile trovare la soluzione ora.
Kiuhnm

 
http://www.xorlabs.net/XEVRON_dimostrazione_ITA.pdf
La frase in fondo a pagina 5:
 > "Da cui si evince che in un prodotto esiste una componente centrale
 > dipendente solo dalle componenti centrali dei suoi fattori"
sembra riferirsi al fatto che nel prodotto ab, sviluppato nella formula 
precedente, il termine W^(2h) a_2 b_2 dipende solo dai termini centrali 
a_2 b_2. Sfortunatamente pero' questo termine non rappresenta le cifre 
centrali del prodotto ab. Questo perchè la decomposizione di ogni numero 
rispetto alla base W è unica solo se si impone che i coefficienti (le 
cifre) siano comprese tra 0 e W-1. Ma in questo caso non c'è alcuna 
garanzia che a_2 b_2 sia minore di W^k.
Esempio concreto:
a=15625
b=32000
ab=500000000
a'=15624
b'=32001
a'b'=499983624
come si vede cambiando solamente l'ultima cifra di a e di b si ottengono 
due risultati ab e a'b' che non hanno NESSUNA cifra in comune.
bye bye
E.

 Non è molto difficile trovare la soluzione ora.
Che io sappia non esistono algoritmi per generare un numero che rispetti 
contemporaneamente tutte le seguenti condizioni da Lei ipotizzate... se 
non appunto calcolando a forza bruta.
Dovendo rappresentare informaticamente i passaggi di cui sopra si tratta 
di creare un bruteforce ma diviso in tre loop distinti. Ovvero facciamo 
un bruteforce su Y, quando Y supera la prima condizione proviamo a 
vedere, con un bruteforce su X se supera anche la seconda condizione, 
altrimenti si torna indietro. Quando X e Y superano anche la seconda 
condizione allora si deve controllare se entrambi superano anche la terza.
Se X e Y sono le parti troncate (nel T3 sono 33 cifre in base 32) direi 
che anche avendo decine di fattori primi di B non si aiuta il bruteforce 
di molto, anzi... in termini di cicli/CPU potrebbe risultare più 
semplice fare un bruteforce "semplice" di X e Y e dividere il numero per 
Sh con un algoritmo ottimizzato per le divisioni sui grandi numeri.
Finchè X e Y sono piccolissimi la soluzione può sembrare istantanea ( 
come del resto con RSA finchè sono in gioco numeri piccoli ) ma quando 
le parti troncate diventano molto grandi.....
La proposta di scomporre in fattori Sh è stata avanzata di recente anche 
da alcuni professori universitari ma viste le grandezze in gioco... è 
una proposta che per ora è stata accantonata e bollata come 
"complicazione sul bruteforce classico"
Attualmente il miglior modo per craccare XEVRON consiste nel fare il 
bruteforce dei singoli troncamenti di destra.
Una volta note tutte le cifre di destra è possibile effettuare una 
"moltiplicazione a cruciverba" che permette di trovare le cifre dell'id 
segreta in appena 2 tentativi per cifra ( in media ).
proprio per questo motivo le parti troncate negli scambi XEVRON 
attualmente approvati sono sempre >= al valore della chiave risultante 
dello scambio.
Ringraziandola per l'interesse e la professionalità dimostrata le invio
Distinti Saluti
D.Vantaggiato
www.XorLabs.net

?manu* ha scritto:

PROPRIETA' ASSOCIATIVA Il prodotto di tre o più fattori non cambia se al 
posto di alcuni di essi si sostituisce il loro prodotto.
In questi due casi lei ha usato semplicemente 2 fattori e invece ne 
servono 3 ( cercheremo di rendere più chiara la documentazioni fornita 
nei prossimi giorni)
ovviamente il tutto rimane confermato anche con i numeri da Lei scelti ( 
io ipotizzo per c' il valore casuale 34533 )
rappresento graficamente i troncamenti ( 1 cifra a destra e 1 a 
sinistra) con doppie parentesi
((a' * b')) * c'  = a' * ((b' * c'))
((15624*32001)) * 34533 = 15624 * ((32001 * 34533 ))
9998362 * 34533  = 15624  * 10509053
345273434946 = 164193444072
il valore comune è "34"
Il valore comune, se i troncamenti sono uguali ( a coppie, ovvero se R1 
= R2 e L1 = L2 ) e le dimensioni in cifre di idA e idB sono parimenti 
uguali, si trova, nel prodotto ultimo che gode di proprietà associativa 
parziale, dopo un numero di cifre pari alla lunghezza dell'id segreto. ( 
poi ci sono alcune varianti che però per numeri così piccoli non 
consideriamo)
In questo caso le chiavi segrete ( a' e c' ) erano lunghe 5 cifre e 
quindi la 6 e la 7 cifra del prodotto associativo parziale risultante 
sono in comune.
la quantità di elementi in comune è ugualmente predeterminabile ma 
dipende da più fattori. In linea di massima si può semplificare dicendo 
che la quantità in cifre dei valori comuni è pari alla lunghezza della 
chiave segreta - le cifre dei troncamenti - 1.
Ma queste sono solo regole di carattere generale, le regole per 
calcolare sempre *esattamente* posizione e quantità degli elementi 
comuni (considerando tutti i fattori in gioco, ivi compresi troncamenti 
e chiavi di diverse lunghezze e/o eventuali  riporti possibili) fanno 
attualmente parte esclusivamente del Know-How interno di XorLabs.
XorLabs ha voluto semplificare al massimo per gli sviluppatori 
l'implementazione della procedura XEVRON fornendo appositamente 4 
possibili modalità di generazione. ( Internet Draft qui 
http://www.xorlabs.net/stat/download.php?id=14
 )
Implementando le dimensioni di chiavi e troncamenti come da specifiche 
T1 ad esempio, i programmatori non devono effettuare calcoli complessi, 
devono semplicemente prendere le cifre comprese tra la 46esima e 55esima 
cifra del prodotto associativo parziale risultante. Nient'altro.
I moduli software per le LongMultiplication sono stati rilasciati con 
Licenza V^3 ( 
http://www.xorlabs.net/stat/download.php?id=4
 ) in ben due 
linguaggi di programmazione diversi ( C# e RealBasic ).
I programmatori possono quindi ( nei vincoli abbastanza ampi della 
licenza ) utilizzare quei moduli all'interno dei propri programmi e 
realizzare password sicure con una facilità *mai* vista prima.
Si genera un numero, si fanno due moltiplicazioni con i moduli software 
forniti, e si "tagliano" le stringhe risultanti con una banale 
istruzione software. tutto qui.
Distinti saluti

 non appunto calcolando a forza bruta.
La crittoanalisi sta proseguendo molto velocemente a questo riguardo. 
Basti pensare agli algoritmi LLL, PSLQ (č stato usato per trovare la 
formula per il calcolo dell'n-esima cifra binaria di pi greco), e 
varianti ancora piů efficienti. Tramite l'LLL si cracka addirittura 
l'RSA con esponente 3 (Coppersmith).
Si conoscono anche metodi ad hoc. Si veda per es.
http://portal.acm.org/citation.cfm?id=22184&coll=portal&dl=ACM
"In this paper we describe a polynomial time algorithm for computing the 
values of variables x1, ..., xk when some of their bits and some linear 
relationships between them are known. The algorithm is essentially 
optimal in its use of information in the sense that it can be applied as 
soon as the values of the xi become uniquely determined by the 
constraints. Its cryptanalytic significance is demonstrated by two 
applications: breaking linear congruential generators whose outputs are 
truncated, and breaking Blum's protocol for exchanging secrets."
Per quanto riguarda le congruenze:
http://citeseer.ist.psu.edu/669451.html
Vi sono molte pubblicazioni in proposito.
Il problema puň anche essere visto sotto forma di knapsack: dato un 
insieme di interi, trovare quelli che sommati danno M (o 0 includendo -M).
Per fare un esempio, 1234*x suggerisce di usare l'insieme {1234*2^0, 
1234*2^1, ..., 1234*2^n} dove n dipende dal valore massimo che puň 
assumere logx. Il knapsack risulta anche poco denso quindi risolvibile. 
Infatti il knapsack problem č NP-completo, ma i valori devono essere 
casuali, mentre qui non lo sono.
Ci saranno centinaia di altri attacchi. Io non sono un esperto; ho solo 
studiato un po' di crittografia per hobby.
Kiuhnm

 chiave segreta - le cifre dei troncamenti - 1.
 > Ma queste sono solo regole di carattere generale, le regole per
 > calcolare sempre *esattamente* posizione e quantità degli elementi
 > comuni (considerando tutti i fattori in gioco, ivi compresi troncamenti
 > e chiavi di diverse lunghezze e/o eventuali  riporti possibili) fanno
 > attualmente parte esclusivamente del Know-How interno di XorLabs.
Ma se volete darne una dimostrazione, bisognerà esplicitare queste 
quantità, la frase "sotto determinate ipotesi" non è molto rigorosa.
E.

 
Chiarimento:
Come si evince dalla dimostrazione, per "parte centrale" del prodotto si 
intende qualcosa di un po' diverso dai numeri centrali del prodotto 
calcolato numericamente. Piuttosto si fa riferimento alle sue componenti 
  centrali intese come somme ordinate rispetto alle potenze della base.
Cordiali saluti.
Aspidus

  centrali intese come somme ordinate rispetto alle potenze della base.
Peccato che questa definizione non sia univoca. Lo stesso numero puň 
avere diverse rappresentazioni in questo senso. La risposta di "D. 
Vantaggiato" mi č sembrata piů sensata.
E.