Talk:Rabin signature algorithm

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Mid-importance).

This article is not correctly written. The Rabin cryptosystem is the first secure signature scheme in history. Rabin literally invented the use of hash functions for signature security in his signature scheme and all others follow their hash-and-sign paradigm. — Preceding unsigned comment added by 88.254.4.93 (talk) 17:09, 30 December 2020 (UTC)[reply]

Quadratic Residue d - Notation issue in the source

Thank you for your edits and clean up, @Taylor_Riastradh_Campbell. I have a concern about the source you used where my [Clarify] question was. The article currently reads:

 Let  $d=(b/2){\bmod {n}}$ . If  $c+d^{2}$  is a quadratic nonresidue modulo  $n$ , the signer starts over...

The source cited for that sentence is Rabin TR-212, page 10. However, on page 10, Rabin does not include that statement. He says:

 By analysis of Section 2, this congruence is solvable if and only if  $m=c+d^{2}$  is a [quadratic residue] mod  $P$  and mod  $Q$ .

Rabin's paper is ambiguous on the meaning of $d$ here. In Section 2, he uses $d=b/2{\bmod {p}}$ where $p$ is any prime, then later he applies that result to both secret key primes $P$ and $Q$ . To untangle this notation issue, the wikipedia article uses $d_{p}$ and $d_{q}$ . Using the wikipedia notation, Rabin's statement now reads:

 ...if and only if  $m_{p}=c+{d_{p}}^{2}$  and  $m_{q}=c+{d_{q}}^{2}$  are [quadratic residues] mod  $P$  and mod  $Q$ , respectively.

It's not clear to me whether that statement with clarified notation is equivalent to the one on the current wikipedia article, in the first quote. Phlosioneer (talk) 05:33, 3 September 2024 (UTC)[reply]

c+d^{2}

is a quadratic residue modulo

n=p\cdot q

if and only if it is a quadratic residue modulo

p

and

q

at the same time. So the criterion is equivalent.

The variables

d_{p}

and

d_{q}

serve mainly for cheaper computation (they're half the size) and could be replaced by

d

. I don't remember why I introduced them at the time I rewrote this article some years ago. Maybe it would be better to just say

d

everywhere. Taylor Riastradh Campbell (talk) 10:12, 3 September 2024 (UTC)[reply]