# Tag Info

### 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, ...
• 142k
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$...
• 142k
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-...
• 46.1k

### 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 ...
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 ...
• 142k

### 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 ...
• 148k

• 1,779
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, ...
• 142k
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.
• 22.7k
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$ ...
• 148k
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$, ...
• 142k

### 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 ...
• 93.2k
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 ...
• 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 ...
• 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 ...
• 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 ...
• 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$...
• 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 ...
• 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 ...
• 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 ...
• 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.
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 ...
• 24.9k

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