Rabin cryptosystem
E836301
The Rabin cryptosystem is a public-key encryption scheme based on the hardness of integer factorization, notable for its provable security equivalence to factoring and its similarity to RSA.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
encryption scheme
ⓘ
public-key cryptosystem ⓘ |
| advantageOverRSA | tighter reduction to factoring ⓘ |
| basedOn | integer factorization problem ⓘ |
| category |
number-theoretic cryptosystem
ⓘ
trapdoor one-way function based scheme ⓘ |
| ciphertextComputation | c ≡ m^2 mod n ⓘ |
| ciphertextSpace | integers modulo n ⓘ |
| contrastWith | RSA where security equivalence to factoring is not proven ⓘ |
| decryptionAmbiguity | 4-to-1 mapping from plaintexts to ciphertexts ⓘ |
| decryptionComplexity | polynomial time in log n given factors ⓘ |
| decryptionStep |
compute square roots of c modulo p and q
ⓘ
use Chinese Remainder Theorem to combine roots ⓘ |
| definedOver | Blum integers NERFINISHED ⓘ |
| disadvantageComparedToRSA | decryption yields four candidates ⓘ |
| encryptionComplexity | polynomial time in log n ⓘ |
| encryptionDeterministic | true ⓘ |
| hasIssue | multiple possible plaintexts per ciphertext ⓘ |
| hasProperty | encryption is as hard as factoring in the worst case ⓘ |
| hasSecurityProperty | provable security equivalence to integer factorization ⓘ |
| influenced | design of provably secure public-key schemes ⓘ |
| introducedBy | Michael O. Rabin NERFINISHED ⓘ |
| introducedInYear | 1979 ⓘ |
| keyGenerationStep |
choose large primes p and q
ⓘ
compute n = p·q ⓘ |
| mathematicalTool |
Chinese Remainder Theorem
NERFINISHED
ⓘ
modular arithmetic ⓘ |
| modulusProperty |
n = p·q where p ≡ 3 (mod 4)
ⓘ
n = p·q where q ≡ 3 (mod 4) ⓘ |
| namedAfter | Michael O. Rabin NERFINISHED ⓘ |
| plaintextSpace | integers modulo n ⓘ |
| privateKey | (p, q) ⓘ |
| privateKeyComponent |
prime factor p of n
ⓘ
prime factor q of n ⓘ |
| provableEquivalence | breaking scheme is equivalent to factoring n ⓘ |
| publicKey | n ⓘ |
| publicKeyComponent | modulus n ⓘ |
| requires | Blum integer modulus ⓘ |
| requiresAssumption | difficulty of factoring large composite integers ⓘ |
| requiresForPracticalUse | CCA-secure padding or transformation ⓘ |
| requiresForUniqueness |
redundancy in plaintext
ⓘ
structured padding scheme ⓘ |
| securityReducesTo | factoring the modulus n ⓘ |
| similarTo | RSA cryptosystem NERFINISHED ⓘ |
| trapdoorFunction | modular squaring with factorization trapdoor ⓘ |
| usedIn | theoretical cryptography ⓘ |
| usesOperation | modular squaring ⓘ |
| vulnerableTo | chosen-ciphertext attacks without proper padding ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
Michael O. Rabin