IT-Sicherheit, 10th Edition

Faktorisierungsangriff

Faktorisierung

Bei diesem Angriff werden Algorithmen eingesetzt, die die Primfaktorzer legung einer natürlichen Zahl berechnen. Eines dieser Verfahren ist das der Fermat’schen Faktorisierung. Es führt besonders schnell zum Ziel, wenn sich die beiden Primzahlen p und q, deren Produkt n ist, nur wenig von $\sqrt{n}$unterscheiden. Der Algorithmus beruht auf dem Satz, dass es für eine natürliche Zahl n, die Produkt zweier Primzahlen p und q ist, zwei natürliche Zahlen a und b gibt, so dass gilt:

$n=a^2-b^2=\underset{=p}{\underbrace{\left(a+b\right)}}\cdot \underset{=q}{\underbrace{\left(a-b\right)}}=p\cdot q.$

Die Idee des Algorithmus besteht nun darin, nach Zahlen a und b zu suchen, die die obige Gleichung erfüllen. Man beginnt mit $a=\overline{)\sqrt{n}}+\overline{)1}$und erhöht a schrittweise um ...