Re: Rabin vs. RSA/ElGamal

Mike Amling wrote:
I'm quite hazy on this, but isn't Rabin susceptible to a kind of
chosen ciphertext attack in that if I can get you to extract square
roots for me modulo your modulus, I can factor your modulus?

Depends how you use it. If you use "raw Rabin" (e.g., without hashing or
proper padding), then yes, it is insecure. But then, so is "raw RSA".
So this is not an advantage or disadvantage of RSA; it is just a fact
that no matter which public-key encryption scheme you use, you have to
apply hashing, padding, or some other mechanism to turn a raw trapdoor
permutation into a full-blown public-key encryption scheme.

Many textbooks are thoroughly confused on this point, because they fail
to distinguish between a primitive (a trapdoor permutation, like squaring
or cubing modulo N -- a building block, not something it makes sense to
use on its own) vs a public-key encryption scheme (something that does
make sense to use on its own, and that provides the security goals that
you'd expect an application to need).
.

Relevant Pages

  • Re: Is there any COBOL program for verify the SSN?
    ... Modulus 11 is NOT the same as Modulo 11. ... The Luhn algorithm or Luhn formula, also known as the "modulus 10" or "mod 10" algorithm, is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. ...
    (comp.lang.cobol)
  • Re: [QUIZ] Modular Arithmetic (#179)
    ... one less than the modulus. ... we must use the appropriate congruent value modulo 24. ... While most operations will be straightforward, modular division is a ... def coerce ...
    (comp.lang.ruby)
  • Re: RSA Private Key representation
    ... Use the secret exponent to factor the modulus. ... factor the modulus if we have the public key and the private key ... Modulo n, we have four square roots of one, 1, -1, and two ... if we can find a non-trivial square root of one modulo n, ...
    (sci.crypt)
  • Re: How do I do this problem without a calculator?
    ... in response to what Chip Eastham wrote: ... You might want Euler's generalization of Fermat's Little Thm. ... to find the reduced nonnegative residue mod 22), the modulus ... would be to consider the computation modulo 2 and again ...
    (sci.math)
  • Re: Summation, modulo and decimal
    ... >I'm trying to use the modulo (modulus, mod, %) to do the following: ... >The problem is that modulo is only def. ... It not worked because before it shift the ... >digit to the left the number is added to the previous value, so, I used ...
    (sci.math)