Untersuchung der Gruppen GL(s,Zn) und SL(s,Zn) zur Nutzung in der Kryptographie

Abstract

Einige Veröffentlichungen erweitern das RSA-Verfahren, indem sie es auf Matrizen aus der Gruppe GL(s, Zn) anwenden. Diese Verfahren verwenden jedoch zum Teil nur spezielle Matrizen aus GL(s,Zn) und operieren nicht auf der ganzen Gruppe GL(s, Zn). Der Grund für dieses Vorgehen liegt darin, dass es in GL(s, Zn) Matrizen gibt, für die das RSA-Verfahren leicht zu brechen ist. Diese Arbeit untersucht die Sicherheit des RSA-Verfahrens, wenn das RSA-Verfahren auf der ganzen Gruppe GL(s, Zn) oder der ganzen Gruppe SL(s, Zn) operiert. Da die Sicherheit des RSA-Verfahrens eng mit der Schwierigkeit des diskreten Logarithmusproblems in der jeweiligen Gruppe zusammenhängt, wird in dieser Arbeit auch das diskrete Logarithmusproblem in den Gruppen GL(s, Zp)\SL(s, Zp) und SL(s, Zp) betrachtet. Dazu erfolgt eine Klassifikation der Matrizen aus den Gruppen GL(s, Zp)\SL(s, Zp) und SL(s, Zp), so dass differenzierte Aussagen über die Komplexität des diskreten Logarithmusproblems in den einzelnen Klassen getroffen werden können. Darüber hinaus erfolgt eine Klassifikation der Matrizen der Gruppe GL(s,Zn), so dass die Sicherheit des RSA-Verfahrens in den einzelnen Klassen differenziert beschreibbar wird. Es wird gezeigt, für welche Matrizen das diskrete Logarithmusproblem und das diskrete Wurzelproblem effizient lösbar ist und für welche Matrizen sich die Probleme auf die zugrunde liegende Gruppe Zn zurückführen lassen. Basierend auf dieser Untersuchung der Matrizeneigenschaften bestimmter Klassen werden zwei neue Faktorisierungsverfahren vorgestellt.