Add unicode handling to the signing and verifying logic

We're seeing a few errors in prod related to this.

@ormsbee @jbau