Lecture Notes: Digital Signatures

Software Engineering Projects

  • Some groups are nearly finished with their software engineering projects.
  • Others are lagging behind, with one group having made very little progress.
  • Dom and Darby's project is progressing well with main functionality nearing completion and focus shifting to polishing.
  • Another group's project has evolved into a self-help tool rather than a strict healthcare application, including features like nutrition tracking, appointment management, and medication tracking.

ElGamal Cryptosystem Assignment

  • The next assignment involves ElGamal cryptosystem decryption.
  • Students will be given a ciphertext to decrypt, but without needing to perform cryptanalysis.
  • First generate a private key composed of: a prime number p, a primitive element Alpha, an exponent a, and a public key \Beta = Alpha^a.
  • p and Alpha are provided; students must send the public key to receive the ciphertext.
  • The task is decryption, not breaking the cipher.

Digital Signature Schemes

  • The lecture transitions from public key cryptosystems to digital signature schemes.
  • Cryptosystems ensure confidentiality, while signature schemes ensure integrity and authenticity.
  • Integrity/authenticity verifies the sender's identity and confirms that the message wasn't altered in transit.
  • Digital signature schemes provide a way to sign messages electronically.

Digital Signatures vs. Ordinary Signatures

  • Both serve the same basic purpose, but differ significantly.
  • Ordinary signatures are assumed unique to a person and do not change based on the signed content.
  • Digital signatures must be bound to the message to prevent misuse, making them valid only for that specific message.

Integrity Concerns

  • Relying solely on the "from" address (e.g., email) is insufficient as it can be easily forged.
  • Spoofing, where calls or emails appear to originate from a trusted source, is easily achievable.
  • Attaching a static signature (e.g., in emails) doesn't provide security and isn't a digital signature.
  • Real-life signatures are a function of the person alone, while digital signatures depend on both the person and the message.
  • A minor change in content should result in a different digital signature.

Verifying Signatures

  • Real-life signature verification often relies on intimate knowledge of the person's signature.
  • Digital signatures should be verifiable using a public algorithm, not private knowledge.
  • Banks use sample signatures for verification, but this won't work for digital signatures, as each signature must be unique to the message.
  • A publicly verifiable algorithm is essential for digital signatures.

Cloning Problem

  • Copying signatures is easier in the digital world than physically cutting and pasting them from documents.
  • Digital signature depends on a particular message, any signature lifted from the original message won't be validated on the newer (different) message.
  • Reusing a signed digital message can cause problems; e.g., copying and resending a previous announcement.
  • Signed messages that are copied still verify and extra care to precent reuse is needed.
  • Using secure timestamps in all messages is one technique to prevent reuse.

Formal Definition of a Signature Scheme

  • A signature scheme comprises five components:
    • P: Plain text space (set of all possible messages).
    • A: Set of all possible signatures.
    • \mathcal{K}: Key space (set of possible keys, including private and public elements).
    • S: Signing algorithms (collection of algorithms).
    • V: Verification algorithms (collection of algorithms).
  • For a specific key k \in \mathcal{K}, there's a signing algorithm \text{sig}k and a verification algorithm \text{ver}k.
  • Signing algorithm \text{sig}k takes a plain text message as input and outputs a signature: \text{sig}k: P \rightarrow A.
  • Verification algorithm \text{ver}k outputs true or false based on the validity of the signature for the message: \text{ver}k: P \times A \rightarrow {\text{true, false}}.
  • For correctness, for each message x \in P and signature y \in A, \text{ver}k(x, y) should return true if and only if y = \text{sig}k(x).
  • Alice computes \text{sig}_k(x) = y, appends y to the message x, and sends the pair (x, y) to Bob.
  • Bob executes \text{ver}_k(x, y) to verify the signature, declaring the message authentic if true.
  • The verification algorithm must be public for anyone to verify, while the signing function must be private to ensure only Alice can create her signatures.

Security of Digital Signature Schemes

  • A secure scheme prevents others from posing as Alice and creating her signature.
  • Oscar cannot know Alice's signing function, which is private.
  • Oscar can check possible signatures, as verification is public.
  • No digital signature scheme can provide unconditional security because there's always a way to brute force.
  • The goal is to have signature schemes that are computationally secure.

Combining Confidentiality and Integrity

  • To ensure both secrecy and authenticity, combine digital signature schemes with public key cryptography.
  • Two paradigms: sign-then-encrypt and encrypt-then-sign.

Sign-Then-Encrypt

  • Alice computes signature y on message x using the signing function.
  • Alice encrypts the pair (x, y) using Bob's public key to get z = E_{\text{Bob}}(x, y).
  • Alice transmits z to Bob.
  • Bob decrypts z using his private key to get (x, y).
  • Bob uses Alice's verification algorithm to check if it is actually equal to true.

Encrypt-Then-Sign

  • Alice encrypts message x using Bob's public key to get z.
  • Then, she signs encrypted message z to create signature y = \text{Sig}_{\text{Alice}}(z).
  • Alice sends the pair (z, y) to Bob.
  • Bob verifies the signature using Alice's public verification function.
  • If verified, Bob decrypts the encrypted message z with his private key to obtain plaintext x.

Comparison of Methods

  • Sign-then-encrypt is preferred:
    • If Oscar intercepts the transmission and replaces Alica's message he will need to provide his signature as well, and Bob will use Oscar's verification function to verify the communication came from Oscar.
    • If encrypt-then-sign this cant be achieved since you cant separate the components when they both are encrypted. This improves security.
  • When both confidentiality and integrity are desired, make sure to first sign and then encrypt.

Building Digital Signature Schemes

  • Digital signature schemes can be built using public key cryptosystems that satisfy extra conditions.
  • The public key cryptosystem must be endomorphic meaning that the encryption same as the:
    • Plaintext space and ciphertext space must be same.
  • And two extra conditions:
    • Dk(Ek(x)) = x
    • Ek(Dk(x)) = x
  • If both conditions are met, D sub k and E sub k are inverses of functionally inverse
  • Those are the only two extra condition that is needed.
  • The decryption algorithm is used as the signing algorithm.

RSA Signature Scheme

  • RSA cryptosystem satisfies the required conditions

RSA Cryptosystem Recap

  • n is the product of two primes, p and q.
  • Plain text and Ciphertext space are Z_n.
  • Choose a such that \text{GCD}(a, \phi(n)) = 1.
  • Compute b such that b = a^{-1} \mod \phi(n).
  • Key consists of five elements: (n, p, q, a, b).
    • n and b public.
    • p, q, and a private.
  • Satisfies endomorphic requirement.
  • Encrypting after decrypting yields the original message.
  • RSA signature scheme involves turning RSA cryptosystem into the signing key using the decryption component.

Signing Algorithm

  • Given key (n, p, q, a, b), signature on message x is computed using a signing algorithm that's the same as the decryption algorithm because only that is known:

    \text{SIG}(x) = x^a \mod n = y

  • The integrity portion is sent over channel: (x, y)

Verification Algorithm

  • Verifies that the signature is the decryption message

    \text{Verify} = x \equiv y^b \mod n

  • Checking on encrypted y (using public key aliases) is equal to x

Security of RSA Signature Scheme

  • Forging is easy on a random message, and therefore Oscar can forge Alice's signature
  • Verification Algorithm is simply to encrypt using the Public Key Alice
  • This not is considered as a serious problem because Oscar does not have control over what the message says, so he is able to send messages to Bob and convince him that is actually coming from Alice's signatures.

ElGamal Signature Scheme

  • In ElGamal what is the prime P.

ElGamal Signature Scheme vs. RSA

  • ElGamal differs from RSA: ElGamal is the plain text space with Zp star and ElGamal cryptosystem is Zp star cross and that is not endomorphic system.
  • Elgamal will be studied in the next class.