Trusted platforms have been proposed as a promising approach to enhance the security of general-purpose computing systems. However, for many resource-constrained embedded systems, the size and cost overheads of a separate Trusted Platform Module (TPM) chip are not acceptable. One alternative is to use a software-based TPM (SW-TPM), which implements TPM functions using software that executes in a protected execution domain on the embedded processor itself. However, since many embedded systems have limited processing capabilities and are battery-powered, it is also important to ensure that the computational and energy requirements for SW-TPMs are acceptable. In this work, we perform an evaluation of the energy and execution time overheads for a SW-TPM implementation on a Sharp Zaurus PDA. We characterize the execution time and energy required by each TPM command through actual measurements on the target platform. In addition, we also evaluate the overheads of using SW-TPM in the context of various end applications, including trusted boot of the Linux operating system (OS), secure file storage, secure VoIP client, and secure web browser. Furthermore, we observe that for most TPM commands, the overheads are primarily due to the use of 2048-bit RSA operations that are performed within SW-TPM. In order to alleviate SW-TPM overheads, we evaluate the use of Elliptic Curve Cryptography (ECC) as a replacement for the RSA algorithm specified in the Trusted Computing Group (TCG) standards. Our experiments indicate that this optimization can significantly reduce SW-TPM overheads (an average of 6.51X execution time reduction and 6.75X energy consumption reduction for individual TPM commands, and an average of 10.25X execution time reduction and 10.75X energy consumption reduction for applications). Our work demonstrates that ECC-based SW-TPMs are a viable approach to realizing the benefits of trusted computing in resource-constrained embedded systems.