Got it working. I can confirm it works with the tutorial - I received the token.
It was an issue with my shell. I packed the commands in a bash script and there was no issue.
The PUBLIC_KEY indeed should have the \n included, and not do line breaks which my shell did automatically, since the command was the same. I mistakenly thought, it was just a way to display \n.
Thanks for your help @peter!