What's is the simplest possible example of using cryptography to sign a message? I am interested in explaining to a total layman the basics of how a network can know that you are authorized without having to compromise your private key.  

Using an example consisting of simple primes that anyone could understand, what is the best way to illustrate this?
It will be a bit of a journey to get to the answer for your question, but check out Khan Academy's crypto series: https://www.khanacademy.org/computing/computer-science/cryptography
They do a nice job of explaining how all the maths work with pretty small numbers. Even colors, which is an awesome analogy.