Dickson, LUC, RSA and Williams : a study on four polynomial-type public-key cryptosystems

In this work we focus on four public-key cryptosystems, namely the Dickson, LUC, RSA and Williams cryptosystem. All of these cryptosystems are of polynomial-type, i.e. polynomials build the foundation of en- and decryption. After discussing the cryptosystems and their mathematical backgrounds in detail, we give insights on relevant cryptanalyses. We also focus on the implementability of the cryptosystems, where we address relevant algorithms and give insights on how to implement them efficiently. In particular we present and apply, besides standard and simple to implement algorithms, heuristic approaches to improve the computational performance. For the Dickson and LUC system, for example, we apply an algorithm by P.L. Montgomery to evaluate Lucas sequences and also Dickson polynomials more efficiently. For the Williams system we discuss and apply an evaluation strategy, which improves the performance of en- and decryption to almost the level of the LUC system. Further, we also observe the impact of applying commonly used techniques (e.g. Montgomery's reduction, Chinese remainder theorem) on the performance of the cryptosystems. Finally, we conclude this work by a thorough study on the computational performance of the cryptosystems.Diese Dissertation behandelt die vier public-key Kryptosysteme Dickson, LUC, RSA und Williams. Alle dieser Kryptosysteme sind polynom-basiert, d.h. die Ver- und Entschlüsselungsfunktionen basieren auf Polynomen. Nach einer eingehenden Diskussion der theoretischen Grundlagen der Kryptosysteme wird deren Sicherheit betrachtet und relevante Kryptoanalysen aufgezeigt. Ferner wird detailliert auf die Implementierbarkeit der Systeme eingegangen und es werden relevante Algorithmen besprochen. Im Besonderen präsentieren und wenden wir, neben Standardalgorithmen, heuristische Algorithmen an, die die Performanz der Systeme verbessern. Zum Beispiel verwenden wir für das Dickson und LUC System einen Algorithmus von P.L. Montgomery, mit dem die Auswertung von Lucas Folgen und Dickson Polynomen effizienter durchgeführt werden kann. Für das Williams System diskutieren wir eine Auswertungsstrategie, welche die Performanz der Ver- und Entschlüsselung auf das Niveau des LUC Systems verbessert. Des Weiteren untersuchen wir auch die Anwendung von häufig verwendeten Techniken wie z.B. Montgomery Reduction und Chinesischem Restsatz. Eine detaillierte Studie der Performanz der Kryptosysteme schließt diese Dissertation ab.Günther BrandnerAbweichender Titel laut Übersetzung der Verfasserin/des VerfassersKlagenfurt, Alpen-Adria-Univ., Diss., 2011KB2011 26OeBB(VLID)240914