Tu atbildi augstāk redzamajam komentāram. Atcelt

Gravatar bubu

2004. gada 3. septembrī, plkst. 09:45

Tajā pdfā ir nekorekts pierādījums. Viņi nepareizu sākuma vekotru paņēmuši bija. Īstajam MD5 vēl nekas nav pierādīts.

Gravatar ns

2004. gada 3. septembrī, plkst. 10:35

neviens nav teicis, ka md5 nevar būt šāda problēma. respektīvi nav pierādīts ne tiešais, ne apgrieztais, tādēļ šāda lieta ne tā ka ļoti izbrīnītu...

Gravatar Kaklz

2004. gada 3. septembrī, plkst. 10:44

Teorētiski jau jebkurai hash funkcijai tiek pieļautas kolīzijas - jautājums ir tikai cik liela ir varbūtība, ka kolīzija gadīsies?

Gravatar ledusledus

2004. gada 3. septembrī, plkst. 10:54

vot, vot - kaa jau kaklz teica. peec Dirihlee principa, ja mums ir hasha rezultaats uz n bitiem, tad njemot visas n bitu mesaages + veel vienu mees dabuusim vismaz vienu koliiziju. Alelujah!

Gravatar aiks

2004. gada 3. septembrī, plkst. 11:01

viss loģiski, pilnīgi unikāls hash varētu būt tikai tieši tāda paša garuma vai grāks kā saturs, kurš tiek hašots; ar galvu padomaajot, tur nav nekas jauns vai nebijis.

Gravatar laacz

2004. gada 3. septembrī, plkst. 11:03

Ja nemaldos, runa ir par to, ka līdz šim tā bija teorija - uzģenerēt divus dažādus sūdasūdus ar identisku MD5 var, bet tīšām to izdarīt ir nejēgā grūti.

Un te nu cilvēki, ja nemaldos, ir to izdarījuši apzināti :) Protams, ja es visu saprotu.

Neviens jau nestrīdās par to, vai MD5 ir unikāla čeksumma, vai nav (pēdējais ir pareizais vairants). Runa, kā jau minēju, ir par to, ka šāda čeksumma vairs nav kritērijs, uz kuru varētu paļauties.

Gravatar ulzha

2004. gada 3. septembrī, plkst. 11:17

Jap, par to tiešām springtne ir. Ātrais lasāmgabals, ko ar to iesākt, atradās šitāds, nepretendējot uz pilnību: http://citeseer.ist.psu.edu/cache/papers/cs/23311/http:zSzzSzdenis.ijs.sizSzstudentszSzpubzSzcsitrcek.pdf/minimising-the-risk-of.pdf

Gravatar Noname

2004. gada 3. septembrī, plkst. 11:20

abet SHA-1 tak veel ir OK ?

Gravatar Arturs

2004. gada 3. septembrī, plkst. 14:11

Patīk man šie komentāri par to ka nav pierādīta ne kolīziju esamība, ne neesamība atsevišķām hash funkcijām. Manuprāt, Dirihlē principu, ar kura palīdzību katrai hash funkcijai var pierādīt, ka tā rada kolīzijas, māca skolas matemātikā 5. klasē.

Gravatar fxz

2004. gada 3. septembrī, plkst. 14:39

tad jau gan skolas tagad advanceejushaas. manos laikos veel neko taadu nemaacija ;)

Gravatar Arturs

2004. gada 3. septembrī, plkst. 15:02

fxz, aha - es ne*iju skolā tajā dienā, kad mācīja urtu "", tapēc tagad tādu nemāku.

Gravatar ulzha

2004. gada 3. septembrī, plkst. 15:03

Arturs, nevis kolīziju esamība vai neesamība, bet tiešām algoritma kolīziju atrašanai esamība vai neesamība. Saproties, cilvēki tic, ka viņas ir ļoti grūti atrodamas, bet matemātiski pierādīts tas nav, un reku daži parāda, cik ļoti nav.

Gravatar Arturs

2004. gada 3. septembrī, plkst. 15:26

Algoritms kolīziju atrašanai? Lūdzu:

for i=1 to 2^HashFunction.bitCount+1 for j=1 to 2^HashFunction.bitCount+1 if (i <> j) and (hash(i) == hash(j)) output(i, j)

Gravatar Arturs

2004. gada 3. septembrī, plkst. 15:27

Cita lieta ir, ka varbūt polinomiāla laika algoritms neeksistē, bet nu augstāk minētais jau arī ir algoritms.

Gravatar ulzha

2004. gada 3. septembrī, plkst. 15:43

Nuja. Neprecīzi izteicos. Bet tajos rakstos jau figurē 2 ^ daudz_mazāk, un par to arī bēda.

Gravatar Kirils

2004. gada 3. septembrī, plkst. 19:21

tas gadijumaa nebija rakstiits jau MD5 specifikaacijaa?

btw, adresee no 19. komenta raxtiits, ka ar shito SSL sertifikaatus gaazt nevar, bet var gaazt digitaalos parakstus.

tagad, njemot veeraa, ka cilveeku rakstiitaa valoda nav kompakts storage format (tb ir ljoti viegli kompreseeejama), no kaa izriet, ka nepietiek ar random burtu virkni, lai dabuutu jaunu message textu, ko paraxtiit ar to pashu paraxtu. veel mazaaka iespeejamiiba.

Gravatar daka

2004. gada 4. septembrī, plkst. 10:05

man jau liekas, ka 2+2=4 un 3+1=4 !!! :) Arī "A" + "B" = "C" + "@" , vai ne? Tās ir manas speciāli radītās kolīzijas! :))))

Gravatar ulzha

2004. gada 6. septembrī, plkst. 11:59

Kirils, ko nu izdomāji... Doma it kā pareiza, bet ne jau "kompakts storage format" ir īstais vārds. Toties manā ielinkotajā pdfā (un droši vien arī MD5 specifikācijā) ir minēts, ka jis apstrādā doto virkni pa blokiem, no kā tiešām izriet, ka pietiek kolīzēt daļu ziņojuma, piemēram, lietotājam neredzamu HTML komentāru, un vakars klāt. Tas laikam nozīmē, ka e-dokumentu sistēmas būs jādizainē tuvu plaintextam... Ļoti jauki, return to innocence.