RSA Signatures

Cryptography · Axiom Academy

Digital signatures using RSA: Proving authenticity and integrity through public-key cryptography 1. The Basic Idea: Reversing RSA In RSA encryption, we encrypt with the public key and decrypt with the private key. For signatures, we reverse this process : Signing: "Encrypt" the message hash with your private key to create a signature Verification: Anyone can "decrypt" the signature with your public key to verify authenticity This works because only you possess the private key, so only you can create valid signatures. But anyone with your public key can verify them. 2. Signing and Verification Formulas Given RSA parameters: modulus n , public exponent e , private exponent d , and a cryptographic hash function H . Apply private key operation: σ = h d mod n The signature σ is sent along with message m Compute the hash of received message: h = H(m) Apply public key operation to signature: h' = σ e mod n Accept if h' ≡ h (mod n) , reject otherwise 3. Why We Hash the Message First We don't sign the message directly. Instead, we sign its hash. This is crucial for several reasons: Efficiency: RSA operations are slow. Messages can be gigabytes, but hashes are fixed-size (e.g., 256 bits) Security: Signing raw messages directly enables certain mathematical attacks Message size: The message must be smaller than n . Hashing ensures this constraint is met Standardization: Hash outputs have uniform properties regardless of message content 4. PKCS#1 v1.5 Signature Padding

This is the written version of the interactive lesson above. See the full Cryptography course.