The International Stamped Time Server (ISTS) broadcasts a time stamp integrity-protected with RSA-4096 public key (n, e). But mere days after it starts operation, hackers announce they pwned it by rigging the RSA cryptoengine, and publish a valid stamp for year 9999 as a proof. You wrote the key generator and supervised key insertion in the cryptoengine, and are the target of suspicion. Find how the hackers proceeded, and the fastest they could do.
ISTS radioes a 512-byte s changing every minute. Users compute r = s^3 mod n (with big-endian convention), split r into t || h with t 448-byte and h 64-byte, and check that h = SHA512(t). Time t starts with the UTC date in ASCII as 2018-07-31 12:25. t further contains the date and time in a variety of other scales (TAI, GPS, religious and national calendars..) with all bits precisely defined. That's a simple form of RSA signature with message recovery, and public exponent 3.
ISTS computes s from t using a third-party cryptoengine, which you initialized with a private key (n, e, d) you generated. The cryptoengine is battery-powered, communicates thru optical fiber, and is housed in a Tempest safe; you checked that before key insertion, sealed the safe, which stayed that way.
After key setup the device's specification is that it accepts t (a little in advance), computes h = SHA512(t), s = (t || h)^d mod n, then checks s^3 mod n = t || SHA512(t) before s is output, all in constant time.
On top of that, s^3 mod n = t || SHA512(t) and t are re-cheked before broadcast, and s is released when the UTC minute changes as determined by a stable atomic clock. Every communication on the optical fiber after key insertion was logged, and checks, with t of correct content.
