Table of contents
1.
Introduction
2.
Semantic Security
2.1.
Symmetric Cryptography
2.2.
Asymmetric Cryptography
3.
RSA Algorithm
3.1.
Vulnerabilities
4.
Semantic Security of RSA
5.
Frequently Asked Questions
5.1.
How does the semantic security of RSA is achieved?
5.2.
What exactly is RSA system security?
5.3.
What are RSA's vulnerabilities?
5.4.
Why makes RSA so challenging to crack?
6.
Conclusion
Last Updated: Mar 27, 2024

What is Semantic Security of RSA?

Author Rashi
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

One’s goal in cryptography is to create a public key system that is secure against the ability to recover the private key and can decrypt messages without knowing the key, also known as total break, and partial break respectively. We also want the adversary to be unable to distinguish between any given ciphertexts. A semantically secure cryptosystem is one in which only a small amount of information about the plaintext can be extracted from the ciphertext. So, in this article, we will go through what semantic security means, what is the RSA algorithm and what is the semantic security of RSA.

Semantic Security of RSA

Semantic Security

A semantically secure cryptosystem is one in which only a small amount of information about the plaintext can be extracted from the ciphertext.

Semantic Security

Symmetric Cryptography

A malicious user must not be able to deduce any information about a plaintext out of its ciphertext in the case of symmetric-key cryptosystems. When given two plaintexts of equal length and their respective ciphertexts, a malicious user cannot determine which ciphertext belongs to which.

Asymmetric Cryptography

An asymmetric key encryption algorithm cryptosystem must make it impossible for a computationally constrained malicious user to derive meaningful data from a text (i.e., plaintext) when provided only its ciphertext and the corresponding public encryption key for semantic security. Semantic security only considers the case of a "passive" attacker, that is, one who generates and observes ciphertexts using the public key and plaintexts. In contrast to other security definitions, semantic security does not take into account the case of chosen ciphertext attack (CCA), in which an attacker can request the decryption of selected ciphertexts, and many semantically secure encryption strategies are demonstrably insecure against CCA.

RSA Algorithm

The RSA algorithm is a public key encryption technique that is widely regarded as the most secure method of encryption. Rivest, Shamir, and Adleman invented it in 1978, hence the name RSA algorithm.

RSA Algorithm

The RSA algorithm has the following characteristics:

  • The RSA algorithm is a well-known exponentiation in a finite set over integers that includes prime numbers.
     
  • This method's integers are sufficiently large to make it difficult to solve.
     
  • This algorithm uses two types of keys: private keys and public keys.
     

For detailed information on RSA Algorithm, and its working, prefer the linked blogs.

Vulnerabilities

M stands for plaintext message.

N = p*q = prime number 1 * prime number 2.

When using low encryption exponents (e.g., e=3) and small M values (i.e., m< n(1/e)), the result of Me is strictly less than the modulus n. Ciphertexts can be easily decrypted in this case by taking the root of the ciphertext over the integers.

As RSA encryption is just a deterministic encryption algorithm (i.e., it lacks a random component), an intruder can effectively launch a chosen plaintext attack against the cryptosystem by encrypting likely plaintexts with the public key and comparing their results to the ciphertext. As previously stated, RSA without padding is not semantically secure. As a result, we will go over how to achieve semantic security of RSA further down.

Semantic Security of RSA

Semantic Security of RSA

We have assumed up to this point in the text that a malicious user attempting to break a cryptosystem is trying to find the secret key (in the case of a secret key cryptosystem) or the private key (in the case of a public-key cryptosystem). If an attacker can do so, the system is entirely broken. However, a malicious user's goal may be less ambitious. Even if the attacker cannot locate the secret or private key, he may be able to obtain more information than we would prefer. To be sure that the cryptosystem is "semantically secure," we must consider the more modest goals that a malicious user may have.

  • Total Break: In the case of a public key cryptosystem, the malicious user can determine the user's private key or secret key (in the case of a secret-key cryptosystem). As a result, he can decrypt any ciphertext encrypted with the given key.
     
  • Partial Break: The malicious user can decrypt a previously unknown ciphertext with a non-zero probability (without knowing the key). Alternatively, given the ciphertext, the malicious user can deduce specific information about the plaintext.
     
  • Distinguishability of Ciphertexts: The adversary can distinguish between encryptions of two given plaintexts or between encryption of both a given plaintext and a random string with a probability greater than 1/2.
     

The following experiment is commonly used to define indistinguishability under Chosen Plaintext Attack (IND-CPA):

  • Running Gen(1n) generates a random pair (pk, sk).
     
  • The public key pk is given to a probabilistic polynomial time-bounded adversary, who can use it to generate any number of ciphertexts (within the polynomial bounds).
     
  • The adversary generates two equal-length messages m0 and m1 and sends them, along with the public key, to a challenge oracle.
     
  • The challenge oracle chooses one of the texts by flipping a coin (selecting a random bit b ∈ {0, 1}), encrypts the message mb with the public key, and returns the adversary the resulting challenging ciphertext c.
     

Because the malicious user in the preceding game possesses the public encryption key, a semantically secure encryption scheme must be probabilistic, with a component of randomness; otherwise, the malicious user could calculate the deterministic encryption of m0 and m1 and keep comparing these encryptions with the retrieved ciphertext c to think the oracle's choice successfully. This guarantees the semantic security of RSA.

Frequently Asked Questions

How does the semantic security of RSA is achieved?

RSA can be made semantically secure (under more stringent assumptions) by employing random encryption padding schemes.

What exactly is RSA system security?

The RSA algorithm (Rivest-Shamir-Adleman) is the foundation of a cryptosystem, a collection of cryptographic algorithms used for specific security services or purposes and widely used to secure sensitive data.

What are RSA's vulnerabilities?

Weak parameters can be difficult, if not impossible, to detect, and their poor performance forces developers to take dangerous shortcuts.

Why makes RSA so challenging to crack?

The size of the key is essential. The greater the number of bits in a key (essentially how long it is), the more difficult it is to crack using brute-forcing and factoring attacks.

Conclusion

In this blog, we have learned about what semantic security means, what is the RSA algorithm and what is the semantic security of RSA.

You can refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Recommended Readings:

Happy Learning!

Live masterclass