A List by Author: Petr ©venda

home page:

The Million-Key Question - Investigating the Origins of RSA Public Keys

by Petr ©venda, Matus Nemec, Peter Sekan, Rudolf Kvasnovsky, David Formanek, David Komarek, Václav Matyá¹, August 2016, 83 pages.

FIMU-RS-2016-03. Available as Postscript, PDF.


Can bits of an RSA public key leak information about design and implementation choices such as the prime generation algorithm? We analysed over 60 million freshly generated key pairs from 22 open- and closed-source libraries and from 16 different smartcards, revealing significant leakage. The bias introduced by different choices is sufficiently large to classify a probable library or smartcard with high accuracy based only on the values of public keys. Such a classification can be used to decrease the anonymity set of users of anonymous mailers or operators of linked Tor hidden services, to quickly detect keys from the same vulnerable library or to verify a claim of use of secure hardware by a remote party. The classification of the key origins of more than 10 million RSA-based IPv4 TLS keys and 1.4 million PGP keys also provides an independent estimation of the libraries that are most commonly used to generate the keys found on the Internet. Our broad inspection provides a sanity check and deep insight regarding which of the recommendations for RSA key pair generation are followed in practice, including closed-source libraries and smartcards. The inspection was not limited only to public part of a RSA keypair – the properties of private key were inspected including factorization of p-1 and p+1 for large number of 512-bit RSA keys followed by discussion of relevant factorization attacks.

On Secrecy Amplification Protocols - Extended Version

by Radim O¹»ádal, Petr ©venda, Václav Matyá¹, A full version of the paper presented at conference WISTP 2015 June 2015, 34 pages.

FIMU-RS-2015-01. Available as Postscript, PDF.


We review most important secrecy amplification protocols that are suitable for ad-hoc networks of devices with limited resources, providing additional resistance against various attacks on used cryptographic keys without necessity for asymmetric cryptography. We discuss and evaluate different designs as well as approaches to create new protocols. A special focus is given to suitability of these protocols with respect to different underlying key distribution schemes and also to open issues. This technical report provides details of our research that will be presented at the 9th WISTP International Conference on Information Security Theory and Practice (WISTP`2015), where a subset of this technical report will be published in this conference proceedings.

Key Distribution and Secrecy Amplification in Wireless Sensor Networks

by Petr ©venda, Václav Matyá¹, November 2007, 63 pages.

FIMU-RS-2007-05. Available as Postscript, PDF.


This report targets the area of wireless sensor networks, and in particular their security. Probabilistic key pre-distribution schemes were developed to deal with limited memory of a single node and high number of potential neighbours. We present a new idea of group support for authenticated key exchange that substantially increases the resilience of an underlaying probabilistic key pre-distribution scheme against the threat of node capturing. We also propose a new method for automatic protocol generation which utilizes Evolutionary Algorithms (EA). The approach is verified on the automatic generation of secrecy amplification protocols for wireless sensor networks. All human-designed secrecy amplification protocols proposed so far were re-invented by the method. A new protocol with better fraction of secure links was evolved. An alternative construction of secrecy amplification protocol was designed which exhibits only linear (instead of exponential) increase of needed messages when the number of communication neighbours is growing. As a message transmission is a battery expensive operation, this more efficient protocol can significantly save this resource.