On Using Fast Exponentiation Algorithm in PDAs (or: How Secure is the Discrete Logarithm Problem Assumption in PDAs?)

Personal Digital Assistants (PDAs) are the miniature of normal size PCs, with a very limited computational power. In this paper, we investigate the security of PDAs when they are used to perform some cryptographic applications. In our context, we investigate the computation y = g' (mod p), for a prime p, which is believed to be secure in the sense of the Discrete Logarithm Problem (DLP) assumption. To be more precise, knowing only p, g and y, it is hard to derive x. We note that this computation is the most important operation in most cryptographic algorithms. However, due to the limited computational power of PDAs, such computation requires some amount of time (and battery life). We show that by observing one of these parameters, we can reduce the hard problem of DLP to be predictable, and hence it is not secure. We also show how to securely generate these kind of computations with PDAs by employing some different techniques, so that they will not reveal any additional information to a passive eaves-dropper. In contrast to previous works, we do not assume that the attacker can take the full control of the PDA. This assumption is only applicable to a smart card whenever it is used in a malicious smart card reader.