Newsgroup: it.comp.sicurezza.crittografia
Titolo: XEVRON crackato

Riporto quello che ho scritto su sci.crypt (tradotto):
Ho appena finito il mio piccolo programma.
E' in grado di crackare il "problema della moltiplicazione troncata" in 
un batter d'occhio e non conta sul fatto che i numeri siano 
fattorizzabili (*).
Per esempio, considera questo problema:
idA = 249542840277926802938912332306310470632601156641005608963007
sh = 
9635080685619924420963614732309800860307305040908634380776287680086461773506133177926837421220870343
idA*sh = 
2404365400596590271605425017261434870572498871281685912545969429492634224355824456551590604702512955028155563598102356002074163226558114290542529001530230401401
Rimuoviamo 25+25 cifre. Rimaniamo con
midA = 
1434870572498871281685912545969429492634224355824456551590604702512955028155563598102356002074163226
dove idA ed sh sono due safe/strong prime.
Ho appena crackato una versione un (bel) po' più difficile:
idA = 
269659532882692418682262081495725304483536777013188527470348249542840277926802938912332306310470632601156641005609044747
sh = 
9328036701689980391858119207276854222379512452011455380920402555819202253597461552062322576199442445614661686416707331076963479030264027416015596388825002880278208884588063787299019612976121557161033190942007392861722805946369996324634399196051927923
idA*sh = 
2515394019690330999329276250659844333219720416389851890531745494272254828052661569145283575697473061240435245620358223356397134370903578820829120410644835612050582248364885370551622006450163304216050240234331099192648800814846256137584042624164924339545338398944955722857463040650317930153276137252787749820988427585770405186983094838062370427034671270902732455725770481
midA =
82805266156914528357569747306124043524562035822335639713437090357882082912041064483561205058224836488537055162200645016330421605024023433109919264880081484625613758404262416492433954533839894495572285746304065031793015327613725278
dove midA è ottenuto eliminando 70+70 cifre da idA*sh, e, ancora, idA ed 
sh sono safe/strong prime.
Ritengo che il crittosistema possa essere considerato non solo insicuro, 
ma completamente crackato.
(*) Stavo rispondendo a una persona che ha fatto notare che almeno il 
20% dei valori sh sono deboli (perché contengono molti fattori piccoli) 
e che ha presentato un algoritmo che recupera idA nel 70% dei casi in 
cui sh sia debole. Questo basterebbe per considerare il crittosistema 
totalmente insicuro.
Qualcun altro ha utilizzato con successo LLL, ma non è stato provato con 
problemi di dimensione reale, che io sappia.
--- parte non presente nella versione inglese ---
Per la cronaca, l'ultimo problema (quello grande) ha richiesto 3 minuti 
eseguendo il programma in versione debug e usando una libreria bignum 
compilata in versione debug con tutti i controlli abilitati. Compilando 
codice e libreria in versione release e ottimizzando i meccanismi del 
mio algoritmo, penso di scendere al di sotto dei 10 secondi.
Per ora non sono in grado di dimostrarlo, ma l'algoritmo appare polinomiale.
Non rilascio l'algoritmo perché penso di aver toccato soltanto la punta 
dell'iceberg. Oserei dire che è sprecato per il problema della 
moltiplicazione. Continuerò a lavorarci nei giorni liberi e vedrò che 
succederà.
Kiuhnm
P.S. La soluzione del problema proposto nel cracking context è
idA = 7147847731328124667029312931 (20576 cicli, < 5 s.)
idB = 2161894105293480903739679934 (20123 cicli, < 5 s.)

 idB = 2161894105293480903739679934 (20123 cicli, < 5 s.)
Complimenti !
studieremo la riduzione lattice per vedere se è possibile evitare di 
calcolare XEVRON come una combinazione lineare... altrimenti attualmente 
l'unica è aumentare i troncamenti in modo "enorme" e ottenere sempre e 
cmq una pwd relativamente piccola (in relazione alle grandezze usate). 
Peccato che così facendo svanisca la possibilità di usare XEVRON su 
hardware poco potenti.
ancora complimenti !
p.s.
e pensare che c'è in giro chi pensa che per craccare XEVRON basti fare 
(MidA * MidB) / Sh :-D

 ancora complimenti !
Grazie e buona fortuna.
Kiunnm

 idB = 2161894105293480903739679934 (20123 cicli, < 5 s.)
Complimenti! Anch'io ho cercato di crakkare il sistema, ma senza alcun 
successo...
E.

 successo...
Thanks!
Kiuhnm


Complimenti ;) vivissimi :D
Ora non ci resta che craccare RSA e siamo a cavallo .. ;) io continuo
con i miei studi sui numeri primi ;)
--
[CapoBecchino]
msn: capobecchino |[@]| hotmail |[.]| com
!!! OFFERTA IRRIPETIBILE !!! Muori oggi avrai uno sconto del 50%

 
Se l'algoritmo di Kiuhnm è davvero polinomiale, è solo questione di un
pò di cicli in più IMHO...
@Kiuhnm: non c'è modo di convincerti a metterlo sotto LGPL? :-p
Saluti.

 batter d'occhio e non conta sul fatto che i numeri siano fattorizzabili (*).
Bravo, complimenti! Ottimo lavoro.
Andreas

 @Kiuhnm: non c'è modo di convincerti a metterlo sotto LGPL? :-p
Adesso sto facendo alcune prove (ottimizzazioni, ecc...).
Prometto che più avanti (potrebbere trattarsi di giorni) lo pubblico.
Kiuhnm

 con i miei studi sui numeri primi ;)
Obiettivo un po' ambiziosetto eh? :-)
Kiuhnm

 Bravo, complimenti! Ottimo lavoro.
Una soddisfazione ogni tanto non fa male.
Kiuhnm

 Kiuhnm
--
[CapoBecchino]
msn: capobecchino |[@]| hotmail |[.]| com
SEZIONE DIVERTIMENTO & AFFINI: "Qual è il poliziotto più sfortunato?
Quello che muore al posto di blocco. E quello più fortunato? Blocco!"

 ma completamente crackato.
LOL  :-)
-- 
pinko(at)
people.it

 
"salita sul carro dei vincitori"
STRALOL

 STRALOL
Veramente non ho interesse a salire su nessun carro:
non so niente di crittografia e sono qui solo di passaggio.
Comunque credo che ci siano cervelloni in tutte le università del
mondo a dedicare la loro vita a questi problemi e trovo difficile
riuscire a fare qualcosa di innovativo ed altrettanto vantaggioso
a cui nessuno aveva già pensato.
Detto questo auguro a D. Vantaggiato ed ai suoi colleghi di
riuscire nei loro intenti.
-- 
pinko(at)
people.it