Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I came across with cryptosystem whose decryption method is: $\ m = c^2 \bmod n $. It's exact opposite of Rabin's, where's the same formula is used for encryption.
What is the name of this cryptosystem?
How does the encryption function in this system work?
I doubt this is an encryption scheme, except in the limited sense of that in code obfuscation. If indeed this is the decryption part of an encryption scheme, that's a very weak one: it is a symmetric encryption scheme which decryption key is $n$, and two distinct plaintext/ciphertext pairs are typically enough to recover that key. Often $n=\gcd({c_0}^2-m_0,{c_1}^2-m_1)$ (though sometime, pulling out small factors or a third pair is necessary).
This cryptosystem seems to be a simplified variant of Rabin signature. As any signature scheme, it aims at integrity and proof of origin of the message, not at protecting the confidentiality of the message.
Like in RSA, security relies on the difficulty of factoring $n$, which distinct prime factors $p$ and $q$ are the secret key. $m$ is the message to sign, assumed to have internal redundancy. Or better (true Rabin signature) $m$ is a full-domain hash of the message. Further, somewhat $m$ has to be made a square modulo $n$ (or equivalently, modulo $p$ and modulo $q$). $c$ is the signature. Schematically, verification is computing $c^2\bmod n$, and comparing it against $m$. Calling that decryption (as the question does) is an error in terminology.
There are several methods for generating $p$ and $q$; then for adjusting $m$, computing $c$ (which is signing, not encrypting), and checking $m$ against the result. One is described in algorithms 11.29 and 11.30 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography. Be sure to ignore the section 11.3.5 (which describes ISO/IEC 9796(-1) padding, dated and insecure).
If the rationale is that making a cryptogram $c$ leading to an $m$ that makes sense is hard without the factorization of $n$, again that's not a cipher or encryption, and $m\gets c^2\bmod n$ is not decryption. The proper name is Rabin signature with total message recovery, and $m\gets c^2\bmod n$ is signature verification and message recovery (and lacking validation of redundancy in $m$). This is standardized by ISO/IEC 9796-2 (with proper padding) including with exponent $2$.
Well clearly if the decryption process is squaring modulo $n$, the encryption process must be taking a square root modulo $n$, i.e., the encryption of a message $m$ is any square root of $m$ modulo $n$. Which particular square root is taken (if there are more than one) is immaterial since they will by definition all yield back $m$ when squared.
How to compute modular square roots depends on what the parameters look like, especially the modulus. If the prime factorisation of the modulus is known, one can use Tonelli-Shanks to compute a square root modulo each prime power factor, and combine with the Chinese theorem.
