Regarding the overall speed and power consumption, cryptographic applications in embedded environments like PDAs or mobile communication devices can benefit from specially designed cryptosystems with fixed parameters. In this contribution, we propose a highly efficient algorithm for a hyperelliptic curve cryptosystem (HECC) of genus two, well suited for these applications on constrained devices. This work presents a major improvement of HECC arithmetic for certain non-supersingular curves defined over fields of characteristic two. We optimized the group doubling operation and managed to speed up the whole cryptosystem by approximately 27% compared to the previously known most efficient case. Furthermore, an actual implementation of the new formulae on an embedded processor shows its practical relevance. A scalar multiplication can be performed in approximately 50ms on an 80MHz embedded device.