← All research spotlights

Research spotlight · Unit 5

Nadia Heninger

University of California, San Diego

Research field
Applied cryptography and computational number theory

Nadia Heninger studies how cryptographic systems fail in practice when the mathematics is sound but the implementation is not. In 2012 she and her colleagues scanned the whole public IPv4 address space, collected about eleven million distinct RSA moduli from web and secure shell servers, and computed the greatest common divisors of all pairs; about half a per cent of the web servers had keys that shared a prime factor with another key and could be broken at once with Euclid's algorithm. The cause was that small network devices generated their primes before they had gathered enough randomness. The unit presents this study after the section on RSA, as the real-world counterpart of the proof that the system is correct.

In the masterclass

Section 5, after the RSA cryptosystem and its proof, shows how shared prime factors in real public keys were found with nothing more than the gcd.

The research is presented in Unit 5: The Theorems of Fermat, Euler, and Wilson, in a research spotlight box that explains the result at the level of the unit and links it to what you have just learned.

The paper

Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J. A. (2012). Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. Proceedings of the 21st USENIX Security Symposium, 205‑220.

The scientists named here are not contributors to the NT Masterclass, are not affiliated with it, and have not endorsed it. The program presents and explains their published research, with references to the original papers.