Diplomthema Kryptologie Gittermethoden in der Kryptoanalyse

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Das Problem, eine »gute« Gitterbasis zu finden, wird hauptsächlich durch den LLL-Algorithmus gelöst (benannt nach H. W. Lenstra, A. K. Lenstra und L. Lovász). Diese Lösung führt zu effizienten kryptoanalytischen Angriffen auf verschiedene Verschlüsselungsverfahren; neben gitterbasierten Verschlüsselungsverfahren sind auch

• das RSA-Verfahren bei zu kleinem privatem Exponenten,
• Stromchiffren mit dezimierten linearen Zufallsgeneratoren

Einstieg:

1. Vorlesung Kryptologie III.
2. H. Cohen: A Course in Computational Algebraic Number Theory. Springer 1966.

Literatur:

1. Freeze/Hastad/Kannan/Lagarias/Shamir: Reconstructing truncated integer variables satisfying linear congruences. SIAM J. Comput. 17 (1988), 262 - 280.
2. D. Coppersmith: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology 10 (1997), 233 - 260.
3. Chen C.-Y., Ku C.-Y., Yen D. C.: Cryptanalysis of large RSA exponent by using the LLL algorithm. Appl. Math. Comput. 169 (2005), 516 - 525.

Aufgaben: (werden noch genauer spezifiziert)

1. Darstellung des LLL-Algorithmus
2. Aufarbeitung der kryptoanalytischen Anwendung auf RSA und dezimierte lineare Zufallsgeneratoren.
3. Durchrechnen von Beispielen mit Hilfe eines Computeralgebrasystems oder einer selbst programmierten Anwendung und experimentelle Aussagen über die Effizienz.