Don't like this style? Click here to change it! blue.css
Overview: We set up the basic RSA digital signature scheme. The goal is an unforgeable tag/signature that can be validated by anyone with access to the public key but only made by someone with the private key.
What's the goal? I want to have a verifiable "signature" on a document, so that only one person in the world could generate that signature but anyone that knows that person could look at it and confirm that it is valid.
This is done by the public-key version of a message authentication code. Think about what is unique to a particular person: their private key of course. We want to use their private key to generate a signature (like a tag) on a message. Now anyone with access to their public-key, the message, and their signature should be able to verify the signature. Also no adversary should be able to forge another message and signature that would verify with the same public key.
Just like in the MAC world, a digital signature scheme fails when someone can forge a signature without having the private key.
Our first (straw-man) stab at a signature on a message goes like this:
So you'll note that this is the exact complement of encryption, we use the private key to make a noisy result which can only be undone using the public key.
The scheme is secure if no one can generate another \((m', \sigma')\) pair that people could verify.
Sign the following message: "I solemnly swear to learn applied cryptography. Even though there are not enough graded assignments to incentivize the needed hours I will: 1) work problems 2) ask questions 3) ponder start-ups 4) think in a paranoid fashion 5) get it done without excuse" You'll need a 2048-bit RSA public/private key pair ( ssh-keygen -t rsa -m PEM will do the job). Get the message into integer format, confirm that it is smaller than your modulus. Publish \(m^d \mod{n}\) and \((n,e)\) into our slack channel. Pick someone else's signature and verify it.
Overview: Now let's look at some weaknesses that we can start to exploit to make forgeries.
Gibberish Signature: Now, take someone's public key, and generate a random "fake signature" (any random number \(\sigma' \in \mathbb{Z}_n^{*}\)) then reverse a message \(m' := \sigma'^{e} \mod{n}\). Now if you publish \(m', \sigma'\) we will verify that the person who published that public key signed your gibberish message too.
Trick them twice, they'll say anthing: The next weakness of the school-book DS scheme is that \(\sigma_1 \cdot \sigma_2 \) is a valid signature for \(m_1 \cdot m_2\). So if you can trick them with what looks like noise, then you can create a signature on any message you want.
Find a "factorization" of a message: Take the message: "I, the undersigned, do solemnly swear to pick boogers, eat them, and wipe any excess on my shirt." Convert it to an integer, \(m\). Now take your own public-key, \(n\), and pick a random number \(m_1 \in \mathbb{Z}_n^{*}\). Compute an \(m_2\) such that \(m_1 \cdot m_2\) is the malicious message. Now sign the two noise messages \(m_1, m_2\) and confirm that their product is your own signature on the the booger message.
Overview: These are very important and subtle weaknesses in RSA that you have to be aware of if you deploy it.
I want to point out two weaknesses in the RSA scheme that impact our choices as implementers:
The take home is that padding must be carefully done so that we don't know the higher order bits when an exponent is too small.
The primitive RSA signature has the above weaknesses and so it's not quite good enough. The world invented "probabilistic signature schemes" which add salts into the process (and use a Fiestel-like construction to recover the salt).
Let's look at the RSA-PSS signature as laid out: here.
This is the diagram:
Pull it off?