Modul:   MAT076  Neuchatel - St.Gallen - Zurich Seminar in Coding Theory and Cryptography

The ROCA Vulnerability: A Study on Coppersmith's Algorithm and its Applications

Vortrag von Tatjana Bossalini

Datum: 27.09.23  Zeit: 15.15 - 16.00  Raum: Y27H25

The search for strong security and effective algorithms is never-ending in the field of modern cryptosystems. Cryptography is the foundation of trust in the digital era, covering everything from our private communications to financial transactions and essential infrastructure. It enables us to share sensitive information and communicate with confidence, knowing that our data remains confidential and secure. This thesis presents an introduction to Coppersmith’s algorithm. We start by laying the theoretical groundwork for three variants: univariate modular, bivariate integer, and multivariate modular case. Subsequently, we proceed to analyze the diverse range of applications that can be derived from these findings, including but not limited to the use of stereotyped messages, random padding for two messages, factoring with incomplete information, and the Chinese Remaindering with Errors problem. We developed and implemented code examples for each scenario, providing a tangible demonstration of the algorithm’s efficiency. Finally, we discuss the ROCA vulnerability that was found in Estonia and its effects on the nation. This weakness allows an attacker to factorize the RSA modulus and compromise the security of the affected systems. The Estonian example emphasizes the significance of using secure implementation techniques, being careful when choosing random number generators, and being cautious when picking cryptographic libraries.