How can you ensure that the person receiving your message knows that you wrote it?

You've been asked out on a date, and you want to send a message telling them that you'd love to go, however a jealous lover isn't so happy about this.

When you send your message saying yes, your jealous lover intercepts the message and corrupts it so it now says no!

We can protect against these attacks by cryptographically signing the message.

Imagine you write a message $m$. You encrypt this message with your friend's public key: $c = m^{e_{0}} \mod N_{0}$.

To sign this message, you calculate the hash of the message: $H(m)$ and "encrypt" this with your private key: $S = H(m)^{d_{1}} \mod N_{1}$.

In real cryptosystems, it's best practice to use separate keys for encrypting and signing messages.

Your friend can decrypt the message using their private key: $m = c^{d_{0}} \mod N_{0}$. Using your public key they calculate $s = S^{e_{1}} \mod N_{1}$.

Now by computing $H(m)$ and comparing it to $s$: assert H(m) == s, they can ensure that the message you sent them, is the message that they received! As long as your private key is safe, no one else could have signed this message!

Sign the flag crypto{Immut4ble_m3ssag1ng} using your private key and the SHA256 hash function.

The output of the hash function needs to be converted into a number that can be used with RSA math. Remember the helpful bytes_to_long() function that can be imported from Crypto.Util.number.

Challenge files:
  - private.key