Mobile users are increasing fast in numbers, new types of services and applications become available, and new mobile systems (e.g., for intelligent transportation) emerge. Meanwhile, the need for securing communication in such large scale, highly dynamic systems grows. But the organizational complexity and operational costs make traditional security solutions hard to deploy at the rate new mobile applications are rolled out. The challenge that lies ahead is how to provide versatile security compatible with the large deployed mobile networking infrastructure. We propose a novel approach to establish cryptographic keys. Our basic observation is that users are often very mobile and, as they interact with the infrastructure, each of them can leave a unique trace behind. Unlike many works that seek to identify structure in the mobility of a population, we leverage the inherent randomness of the mobility of individuals (and thus the randomness of mobile-infrastructure interactions) to establish shared secret keys between each mobile node and the infrastructure. With an underlying readily available source of uncertainty, such keys can be generated as needed, on the fly, to enhance the system and user security in many ways. We find that with no or little change to existing mobile communication systems, users can generate a common secret with the infrastructure at a rate of roughly $0.1$ bits per second.