Skip to main content
5 votes

Is this a good choice of a digital signature scheme?

Rabin-Williams signature verification with 3072 bit keys is much faster than EdDSA signature verification of comparable security (when done in software). How much depends on care of coding, hardware, ...
fgrieu's user avatar
  • 142k
5 votes
Accepted

Decryption in Rabin

Note: It is assumed familiarity with finite ring $\mathbb Z_w$, polynomial ring, and standard notation; see final section. Decrypting in the Rabin cryptosystem of the question involves solving for $m$...
fgrieu's user avatar
  • 142k
4 votes
Accepted

Does Rabin function lose its one-way property if squaring mod a prime?

Would [$f_N(x)=x^2\bmod N$] lose the one-way property if $N$ is prime and not a product of two primes? Yes, thanks to the Tonelli-Shanks algorithm (special cases here). [Is] Rabin function still one-...
SEJPM's user avatar
  • 46.1k
3 votes

Breaking hashless variant of the Rabin Signature system with chosen message attack

You heard incorrectly. Rabin signatures as proposed in his 1979 paper include (randomized) hashing of the message, which completely prevents the attack given reasonable choices of hash function. The ...
Daira-Emma Hopwood's user avatar
3 votes
Accepted

Identify the cryptosystem where $\ m = c^2 \bmod n$?

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 ...
fgrieu's user avatar
  • 142k
3 votes

Why is the Rabin mapping not a permutation over $\mathbb{Z}_N^*$

Why is the Rabin mapping: $f_i(x_i)=x_i^2 \bmod N_i$ not a Permutation over $\mathbb{Z}_N^*$? Because it maps distinct inputs to the same output. For example, $f_i(1) = f_i(N_i - 1)$, with both ...
poncho's user avatar
  • 148k
3 votes

Rabin encryption when M is not Disjoint to n

The definition of the Rabin cryptosystem in the question likely is similar to: Setup: choose $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod 4$ ; compute and publish public modulus $n=...
fgrieu's user avatar
  • 142k
2 votes
Accepted

Get $a$ such that quadratic residue has a solution (Rabin)

The equation $a = x^2 \bmod N$ has at most $4$ solutions $x$. There are solutions if $a$ is a square modulo both $p$ and $q$. This can be checked by computing the Legendre of symbol of $x$ modulo $...
user94293's user avatar
  • 1,779
2 votes
Accepted

Estimate Security level of the Rabin Signature

With proper choice of key and padding, the most efficient purely cryptographic known attack on Rabin signature and RSA (encryption and signature) is the same: factoring the public modulus. Therefore, ...
fgrieu's user avatar
  • 142k
2 votes
Accepted

Rabin: how discover P and Q?

The intended users know, in fact choose $p,q.$ The attackers aren't supposed to know. Once you know $p,q,$ you use the Chinese Remainder Theorem for efficient computations.
kodlu's user avatar
  • 22.7k
2 votes
Accepted

Rabin cryptosystem - How many solutions?

How much will we have solutions? Assuming: $p, q, r, ..., z$ are distinct odd primes $b$ is relatively prime to $n$ There exists at least one solution Then, yes, there will be precisely $2^k$ ...
poncho's user avatar
  • 148k
2 votes
Accepted

How to decrypt Rabin message when p=q and you have the roots from Tonelli-Shanks

We are given $n>4$ and ciphertext $c\in(0,n)$ for textbook Rabin encryption. We want to solve for $x\in[0,n)$ the equation $x^2\bmod n=c$. We found that $n$ is a square, computed $p=\sqrt n$, ...
fgrieu's user avatar
  • 142k
2 votes

Is digital signature without schema possible?

In principle what you describe seems to be a full domain hash (FDH) scheme, which is known to be secure for RSA. Furthermore, you'd be choosing the wrong hash as you generally need a collision free ...
Maarten Bodewes's user avatar
  • 93.2k
2 votes
Accepted

Clarification regarding Rabin Cryptosystem being CPA (Chosen Plaintext Attack) secure

Do I understand correctly that the textbook Rabin encryption scheme, where there is no random padding, is not CPA secure? Yes, textbook Rabin encryption is not CPA secure for the modern meaning of ...
fgrieu's user avatar
  • 142k
1 vote

Rabin Cryptosystem: Chosen-Ciphertext Attack

I'll assume this is not homework. It's actually quite simple: Pick a random value $r$ Compute $s = r^2 \bmod n$, and submit $s$ to the Rabin decryptor Since $s$ is a Quadratic Residue, the Rabin ...
poncho's user avatar
  • 148k
1 vote

Rabin-Williams signature and it's reduction to factorization

I'm still piecing things together, so bear with me as this may be revised. Access to a signature oracle is either a zero-knowledge resource or breaks the random oracle model for $H_k$. To see this we ...
Daniel S's user avatar
  • 24.1k
1 vote
Accepted

Forging Rabin signature

I'll assume a system as follows $N=p\,q$ is the public product of two large secret primes, chosen about uniformly randomly and independently, thus distinct (with overwhelming odds). Such $N$ is ...
fgrieu's user avatar
  • 142k
1 vote

Identify the cryptosystem where $\ m = c^2 \bmod n$?

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$...
fkraiem's user avatar
  • 8,152
1 vote
Accepted

rabin decryption

Rabin decryption (or rather, one step of that before selection of the solution then padding removal) is solving the equation $c=m^2\bmod(p\;q)$, searching for $0\le m<p\;q$ given $c$ and distinct ...
fgrieu's user avatar
  • 142k
1 vote

Rabin cryptosystem decryption when p=q

As fkraiem already pointed out, Rabin's requires $p\neq q$, otherwise your ring is not isomorphic to the direct product $\mathbb{Z}_p \times \mathbb{Z}_q$. And then the decryption doesn't work as ...
tylo's user avatar
  • 12.7k
1 vote

Rabin cryptosystem decryption when p=q

Rabin, like RSA, requires $p\ne q$. Basically, this is because the rings $\mathbf{Z}_{pq}$ (for $p\ne q$) and $\mathbf{Z}_{p^2}$ have fundamental differences. Crucially, $\mathbf{Z}_{pq}$ is ...
fkraiem's user avatar
  • 8,152
1 vote

Get $a$ such that quadratic residue has a solution (Rabin)

There is also a nice formula giving solutions for quadratic residues modulo $n$: $$x=a^{\frac{(p-1)(q-1)+4}{8}}\mod n.$$ As usual, it is sufficient to verify it modulo $p$ and modulo $q$ separately.
Alexey Ustinov's user avatar
1 vote

Decrypting an RSA message given $a^2 \equiv 1 \pmod n$

Consider two numbers $a$ and $b$ that square to the same value modulo $n$ and don't just differ by the sign. $$a^2 \equiv b^2 \pmod n2$$ $$(a-b)(a+b) \equiv 0 \pmod n$$ Neither of the factors on ...
CodesInChaos's user avatar
  • 24.9k

Only top scored, non community-wiki answers of a minimum length are eligible