On Apr 10, 2010, at 6:11 PM, Guilhem Poirier wrote: > > Hi > > I'm a french student in Master of Mathematics, computers sciences and > application to cryptology in Paris 7 university. > > As part of my degree course, I have to understand and to describe the > method of cryptanalysis of GSM encrypted communication. > > So I have some question about table parameters, I don't understand how > we get the formula > > (1 - h*l^2 / Z)^k = (1 - c)
'c' is the probability that the next chain collides with a previous h chains of length l*k. The probability that the first segment of that new chain (with length l) collides with any segments of the other chains is: h * l^2 / Z where 1/Z is the collision probability of two A5/1 outputs. Deriving the collision probability over the whole length of the chain gives the above formula. > What is the value of Z ? In the Excel sheet > (http://reflextor.com/Rainbow.Tables.xls) we have Z = 2/N, but in the > case where k=1 and c=50%, it contradict the matrix stopping rule of > Hellman's matrix because we have h*l^2 = N/4 and not h*l^2=N. Z is what other papers call 'N'. The matrix stopping rule randomly picks one possible design point. We chose another one (or rather keep it flexible through the 'c' parameter). > I would like to know if it's possible to have more precision about > stopping rule in rainbow tables. > > (sorry for my bad english) > > > _______________________________________________ > A51 mailing list > [email protected] > http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51 _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
