Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Rabin cryptosystem
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Algorithm== Like all asymmetric cryptosystems, the Rabin system uses a key pair: a [[public key]] for encryption and a [[private key]] for decryption. The public key is published for anyone to use, while the private key remains known only to the recipient of the message. ===Key generation=== The keys for the Rabin cryptosystem are generated as follows: # Choose two large distinct [[prime numbers]] <math>p</math> and <math>q</math> such that <math>p \equiv 3 \bmod{4}</math> and <math>q \equiv 3 \bmod{4}</math>. # Compute <math>n = p q</math>. Then <math>n</math> is the public key and the pair <math>(p,q)</math> is the private key. ===Encryption=== A message <math>M</math> can be encrypted by first converting it to a number <math>m < n</math> using a reversible mapping, then computing <math>c = m^2 \bmod{n}</math>. The ciphertext is <math>c</math>. ===Decryption=== The message <math>m</math> can be recovered from the ciphertext <math>c</math> by taking its square root modulo <math>n</math> as follows. # Compute the square root of <math>c</math> modulo <math>p</math> and <math>q</math> using these formulas: #: <math>\begin{align} m_p &= c^{\frac{1}{4}(p+1)} \bmod{p} \\ m_q &= c^{\frac{1}{4}(q+1)} \bmod{q} \end{align}</math> # Use the [[extended Euclidean algorithm]] to find <math>y_p</math> and <math>y_q</math> such that <math>y_p \cdot p + y_q \cdot q = 1</math>. # Use the [[Chinese remainder theorem]] to find the four square roots of <math>c</math> modulo <math>n</math>: #: <math>\begin{align} r_1 &= \left( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p \right) \bmod{n} \\ r_2 &= n - r_1 \\ r_3 &= \left( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p \right) \bmod{n} \\ r_4 &= n - r_3 \end{align}</math> One of these four values is the original plaintext <math>m</math>, although which of the four is the correct one cannot be determined without additional information. ====Computing square roots==== We can show that the formulas in step 1 above actually produce the square roots of <math>c</math> as follows. For the first formula, we want to prove that <math>m_p^2 \equiv c \bmod{p}</math>. Since <math>p \equiv 3 \bmod{4},</math> the exponent <math display="inline">\frac{1}{4}(p+1)</math> is an integer. The proof is trivial if <math>c \equiv 0 \bmod{p}</math>, so we may assume that <math>p</math> does not divide <math>c</math>. Note that <math>c \equiv m^2 \bmod{pq}</math> implies that <math>c \equiv m^2 \bmod{p}</math>, so c is a [[quadratic residue]] modulo <math>p</math>. Then : <math>m_p^2 \equiv c^{\frac{1}{2}(p+1)} \equiv c\cdot c^{\frac{1}{2}(p-1)} \equiv c \cdot 1 \mod p</math> The last step is justified by [[Euler's criterion]]. ===Example=== As an example, take <math>p = 7</math> and <math>q = 11</math>, then <math>n=77</math>. Take <math>m = 20</math> as our plaintext. The ciphertext is thus <math>c = m^2 \bmod{n} = 400 \bmod{77} = 15</math>. Decryption proceeds as follows: # Compute <math>m_p = c^{\frac{1}{4}(p+1)} \bmod{p} = 15^2 \bmod{7} = 1</math> and <math>m_q = c^{\frac{1}{4}(q+1)} \bmod{q} = 15^3 \bmod{11} = 9</math>. # Use the extended Euclidean algorithm to compute <math>y_p = -3</math> and <math>y_q = 2</math>. We can confirm that <math>y_p \cdot p + y_q \cdot q = (-3 \cdot 7) + (2 \cdot 11) = 1</math>. # Compute the four plaintext candidates: #: <math>\begin{align} r_1 &= (-3 \cdot 7 \cdot 9 + 2 \cdot 11 \cdot 1) \bmod{77} = 64 \\ r_2 &= 77 - 64 = 13 \\ r_3 &= (-3 \cdot 7 \cdot 9 - 2 \cdot 11 \cdot 1) \bmod{77} = \mathbf{20} \\ r_4 &= 77 - 20 = 57 \end{align}</math> and we see that <math>r_3</math> is the desired plaintext. Note that all four candidates are square roots of 15 mod 77. That is, for each candidate, <math>r_i^2 \bmod{77} = 15</math>, so each <math>r_i</math> encrypts to the same value, 15.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)