1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What's the public and secret key in this supposed encryption scheme? If $n$ is public then the scheme could be called "broken". $\endgroup$ – Maeher Dec 17 '19 at 7:59
  • $\begingroup$ Unfortunately no, found it as part of a system I have analyzed. The numbers are quite big, $\ 10^{300} $. $\endgroup$ – Georg D Dec 17 '19 at 8:00
  • 3
    $\begingroup$ If $n$ is public then the "decryption" equation can be evaluated by anyone. So this "encryption" scheme, however it works exactly, gives no confidentiality whatsoever. I don't there's a name for such an obviously broken construction. $\endgroup$ – Maeher Dec 17 '19 at 8:24
  • $\begingroup$ @Maeher Yes, the n is the public key. The difficulty is in composing a message is the size of numbers. $\endgroup$ – Georg D Dec 17 '19 at 8:35
  • 1
    $\begingroup$ Please indicate where you came across this cryptosystem... And please do provide specific titles to your questions so we can tell questions apart. $\endgroup$ – Maarten Bodewes Dec 17 '19 at 11:23
3
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Saying thanks for effort of @fgrieu, I shall ensure you that the formula given does role the decryption of message content and isn't a signature. $\endgroup$ – Georg D Dec 17 '19 at 14:19
  • 1
    $\begingroup$ @Georg D: If it is decryption of an encryption scheme, that's one with unconventional goals, or insecure, for reasons in the first paragraph of the answer. If the context is a real application other than code obfuscation, I beg to know which. If this is hypothetical, finding $c$ from $m$ is easy with the factorization of $n$ into distinct primes: solve modulo each factor using Tonelli-Shanks, then use the CRT. $\endgroup$ – fgrieu Dec 17 '19 at 14:53
  • 1
    $\begingroup$ I don't think you need anything additionally to the public key, if this was a public key encryption scheme: If everyone can encrypt, you need the exponent in addition to the modulus to be public (the one to calculate square roots). And from that everyone can factor the modulus. The strength of this system can be described as "if the adversary doesn't know algebra...". $\endgroup$ – tylo Dec 17 '19 at 16:47
  • $\begingroup$ @tylo, do you think that it's trivial to compose a new message even the range of the public key $\ n$ is $\ 10^{300} $? $\endgroup$ – Georg D Dec 17 '19 at 18:00
  • 1
    $\begingroup$ @GeorgD If it is encryption, it is trivial: Everyone, including the adversary, knows the public key. That is the entire concept. And if the 'decryption' is like you state, then the information necessary to encrypt reveals the factorization of $n$. $\endgroup$ – tylo Dec 18 '19 at 1:39
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Are there a chance to encrypt a message when the factorisation of $\ n$ is unknown? $\endgroup$ – Georg D Dec 18 '19 at 2:56
  • $\begingroup$ @Georg No. In fact it is known that computing square roots modulo $n$ is as difficult as factoring $n$; yhat's what the security of Rabin encryption relies on. $\endgroup$ – fkraiem Dec 18 '19 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.