Diskussion:Merkles Puzzle

Absatz Sicherheit: Im Text steht "Dafür braucht er m*2^n Versuche". Das ist nach meinem Verständnis aber der worst-case für den Angreifer. Er kann den Schlüssel auch beim ersten mal haben. Im Mittel vermutlich nach der halben Anzahl möglicher Schlüssel. Korrekt wäre dann "Dafür braucht er maximal m*2^n Versuche, im Mittel m/2*2^n Versuche"? Der GAU für Alice und Bob wäre wenn bei einem frühen Versuch der Schlüssel erraten würde. Daraus folgt auch die polynomiale Forderung. Der Aufwand muss für den Angreifer so hoch sein, dass er es erst gar nicht versucht. Richtig? Wenn das jemand bestätigt würde ich es auch versuchen einzufügen. --MaPae (Diskussion) 16:53, 3. Mär. 2015 (CET)

Im Mittel muss der Angreifer $m/2$ Chiffrate entziffern, bis er das richtige hat, und für jedes braucht er im Mittel $2^{n}/2$ Versuche, um den Schlüssel zu finden, insgesamt also $m\cdot 2^{n}/4$ Versuche.--Megatherium (Diskussion) 12:30, 13. Jul. 2021 (CEST)