Authenticating Signatures in RSA
In the RSA system, the sender of a message can use their private key to digitally sign it, while the recipient can verify the signature using the sender's public key.
When a user wants to send a signed message, they attach a digital signature to it. Upon receiving the message, the recipient can confirm that the signature is indeed authentic and originates from the sender.
The RSA encryption system is a robust solution for authenticating digital signatures.
How Does It Work?
In RSA, each user has a public key, which is openly available, and a private key, which is kept secret and known only to the user.
For example, consider two users, A and B, with the following public keys: $ K_A $ and $ K_B $.
$$ K_A = (n_A, e_A) $$
$$ K_B = (n_B, e_B) $$
Each public key consists of two numerical values $ (n, e) $, and these keys are accessible to anyone.
Each user also possesses a private key, which remains confidential: $ d_A $ for user A and $ d_B $ for user B.
The sender (A) uses their private key to sign the message, and the recipient (B) uses the sender's public key to verify the signature.
1] Writing a Signed Message
User A (the sender) creates the message \( M \).
They then generate a digital signature \( F \).
This signature \( F \) is a numerical representation of \( M \), typically produced by applying a hash function to the message:
$$ F = \text{hash}(M) $$
Note: The hash function ensures that any alterations to the message during transmission will invalidate the original signature.
Next, user A encrypts the signature using their private key \( d_A \), which only they possess:
$$ F_c = F^{d_A} \mod n_A $$
They then send the message, along with the encrypted signature, to user B.
2] Verifying the Signed Message
User B (the recipient) receives the message \( M_1 \) and the encrypted signature \( F_c \) from the sender.
To verify the signature, user B decrypts \( F_c \) using the sender's public key \( e_A \):
$$ F_c^{e_A} \mod n_A = (F^{d_A})^{e_A} \mod n_A $$
Because RSA ensures that \( d_A \cdot e_A \equiv 1 \mod \phi(n_A) \), the operation simplifies to:
$$ F_c^{e_A} \mod n_A = F $$
Now, user B has successfully retrieved the original signature \( F \).
To confirm its validity, user B computes a hash \( H \) from the received message \( M \) using the same hash function:
$$ H = \text{hash}(M) $$
User B then compares \( F \) with \( H \):
- If \( F \) (the decrypted signature) matches \( H \) (the hash of the message), the signature is valid, and the message has not been tampered with.
- If \( F \neq H \), the message has either been altered or the signature is invalid.
In essence, the hash function serves as a "digital fingerprint" for the message.
The encrypted signature \( F_c \) ensures that this fingerprint is both authentic and tied to the sender.
Note: By decrypting \( F_c \) and comparing it with the locally computed hash, the recipient verifies the message’s integrity and authenticity. This ensures the message genuinely comes from the sender and remains unaltered.
A Practical Example
Here’s a practical example of how RSA digital signatures work, showing the process of sending a message from User A to User B.
User A has the following keys:
- A’s public key: \( (n_A = 77, e_A = 13) \)
- A’s private key: \( d_A = 37 \)
Note: The public key was created using two prime numbers: \( p = 7 \) and \( q = 11 \).
$$ n_A = p \cdot q = 7 \cdot 11 = 77 $$
Euler’s totient function for \( n_A \) is:
$$ \phi(n_A) = (p-1) \cdot (q-1) = 6 \cdot 10 = 60 $$
A value \( e_A \) is chosen such that it is coprime with \( \phi(n_A) \):
$$ e_A = 13 $$
The private key \( d_A \) satisfies this equation:
$$ d_A \cdot e_A \equiv 1 \mod \phi(n_A) $$
Using the extended Euclidean algorithm, we find:
$$ d_A = 37 $$
1] User A Signs the Message
User A writes the message:
$$ M = 5 $$
They then generate a digital signature \( F \) using a hash function:
For simplicity, in this example, the hash function returns the message value itself (real-world systems use secure hash functions like SHA-256):
$$ F = \text{hash}(M) = 5 $$
Next, User A encrypts the signature \( F \) using their private key \( d_A = 37 \):
$$ F_c = F^{d_A} \mod n_A $$
$$ F_c = 5^{37} \mod 77 $$
$$ F_c = 47 $$
Finally, User A sends the message \( M = 5 \) and the encrypted signature \( F_c = 47 \) to User B.
Note: To compute \( 5^{37} \mod 77 \), we use the method of successive squaring:
- \( 5^1 \mod 77 = 5 \)
- \( 5^2 \mod 77 = 25 \)
- \( 5^4 = (5^2)^2 \mod 77 = 25^2 \mod 77 = 625 \mod 77 = 9 \)
- \( 5^8 = (5^4)^2 \mod 77 = 9^2 \mod 77 = 81 \mod 77 = 4 \)
- \( 5^{16} = (5^8)^2 \mod 77 = 4^2 \mod 77 = 16 \)
- \( 5^{32} = (5^{16})^2 \mod 77 = 16^2 \mod 77 = 256 \mod 77 = 25 \)
Using these values:
$$ 5^{37} = 5^{32} \cdot 5^4 \cdot 5^1 $$
We apply modular reduction at each step:
$$ 5^{37} \mod 77 = (5^{32} \cdot 5^4 \cdot 5^1) \mod 77 $$
Substituting the modular results:
$$ 5^{32} \mod 77 = 25, \, 5^4 \mod 77 = 9, \, 5^1 \mod 77 = 5 $$
$$ 5^{37} \mod 77 = (25 \cdot 9 \cdot 5) \mod 77 $$
$$ 5^{37} \mod 77 = 1125 \mod 77 $$
$$ 5^{37} \mod 77 = 47 $$
This method makes the calculations much simpler, as \( 1125 \div 77 = 14 \) with a remainder \( r = 47 \).
2] User B Verifies the Signature
User B receives the message \( M = 5 \) and the encrypted signature \( F_c = 47 \).
To verify the signature, User B decrypts \( F_c \) using A’s public key \( (n_A = 77, e_A = 13) \):
$$ F = F_c^{e_A} \mod n_A $$
$$ F = 47^{13} \mod 77 $$
$$ F = 5 $$
User B then computes the hash of the received message:
$$ H = \text{hash}(M) = 5 $$
Finally, User B compares \( F \) (the decrypted signature) with \( H \) (the hash of the message):
Since \( F = H \), the signature is valid.
This example uses small numbers for educational purposes. In practice, much larger numbers are used to ensure a high level of security.
Note: To compute \( 47^{13} \mod 77 \), modular exponentiation is applied step by step:
- \( 47^1 \mod 77 = 47 \)
- \( 47^2 \mod 77 = (47 \cdot 47) \mod 77 = 2209 \mod 77 = 34 \)
- \( 47^4 \mod 77 = (34 \cdot 34) \mod 77 = 1156 \mod 77 = 4 \)
- \( 47^8 \mod 77 = (4 \cdot 4) \mod 77 = 16 \)
Using these results:
$$ 47^{13} = 47^{8} \cdot 47^{4} \cdot 47^{1} $$
$$ 47^{13} \mod 77 = (16 \cdot 4 \cdot 47) \mod 77 $$
Substituting the modular results:
$$ 47^{13} \mod 77 = 3008 \mod 77 $$
$$ 47^{13} \mod 77 = 5 $$
The result is \( 5 \), as \( 3008 \div 77 = 39 \) with a remainder \( r = 5 \).
The Hash Function
A hash function processes a message of any length and produces a fixed-length output, known as a digest.
Key properties of a reliable hash function include:
- Deterministic: The same input always generates the same hash.
- Non-reversible: It is computationally infeasible to reconstruct the original input from the hash.
- Collision-resistant: It is difficult to find two different inputs that produce the same hash.
- Avalanche effect: A small change in the input drastically changes the hash.
A commonly used cryptographic hash function is SHA-256 (Secure Hash Algorithm 256-bit), part of the SHA-2 family.
For example, the message:
M="This is an example."
Has the following hash digest in hexadecimal when processed with **SHA-256**:
7a580dd696f5b5b6324a350b4a4cf3a6e4b43e672dc5f1b9dd84af7f3d9964c0
If the message changes even slightly, such as:
M="This is an example?"
The new hash will be entirely different:
30c916eec612587b60b0d770c9312a67d73d7efab39456970d03e4faaddbfb79
Each digest uniquely identifies the input message and reflects even the smallest changes in the original message.
Other hash functions include:
- MD5, now considered obsolete for cryptographic use due to its vulnerability to collisions.
- SHA-1, which is also no longer secure for modern cryptographic purposes.
- SHA-3, the latest member of the SHA family.
These functions are widely used in cryptography, digital signatures, authentication, and file checksums.
And so on...
