I have read that difficulty in breaking many algorithms are based either on Factorization or discrete logarithm. I am reading about schemes that are similar to RSA which make use of integer factorization and Schnorr scheme, which is based on discrete logarithm problem.

My idea is to create signature based on any of these schemes. I am using this on embedded system, where the limitations are

  1. Less computing power as compared to Laptop/Desktop
  2. Amount of data sent between parties is less; may be 128 bits of messages
  3. Data allowed for signature is also less; usually 64 to 128 bits

Considering this which ones is relatively difficult for the attacker?

  • 4
    $\begingroup$ I know no secure signature scheme within your constraints. But if both signer and verifier share a secret, they can use a MAC instead of a signature. MACs fit your constraints, but the verifier can forge them, so it doesn't work well with more than two parties. $\endgroup$ Commented Jan 26, 2014 at 10:20
  • 2
    $\begingroup$ Are you using "signature" in its standard meaning, that is a value computed from data and a private key, allowing anyone knowing the corresponding public key to ascertain the integrity of the data without any secret information? Or some other meaning, perhaps that of Message Authentication Code? $\endgroup$
    – fgrieu
    Commented Jan 26, 2014 at 12:21
  • $\begingroup$ Asymmetric cryptography with 64 or 128 bit is not possible, as far as we know. The main reason is that our trapdoor functions don't widen the gap between function evaluation and finding the trapdoor fast enough. For example, factoring and DLOG with 128 bit integers are really easy. $\endgroup$
    – tylo
    Commented Jan 27, 2014 at 13:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.