# Tag Info

23

These types of cryptographic primitive can be distinguished by the security goals they fulfill (in the simple protocol of "appending to a message"): Integrity: Can the recipient be confident that the message has not been accidentally modified? Authentication: Can the recipient be confident that the message originates from the sender? Non-repudiation: If ...

17

There is a draft RFC which describes a way to implement deterministic (EC)DSA (with test vectors). In this draft, both $h(m)$ (the hash of the message) and $x$ are used as input to a deterministic PRNG which uses HMAC (that's HMAC-DRBG as specified by NIST); the PRNG output is used to yield $k$. I am not sure your simple multiplication with $x$ would be ...

13

Assuming you are asking about public-key signatures + public-key encryption: Short answer: I recommend sign-then-encrypt, but prepend the recipient's name to the message first. Long answer: When Alice wants to send an authenticated message to Bob, she should sign and encrypt the message. In particular, she prepends Bob's name to the message, signs this ...

12

A second reason that a hash is usually present in RSA signature schemes (apart from being able to sign long messages) is to prevent existential forgery attacks. These look like this: Assume we have the public key $n$, $e$. Choose some random garbage $s$ (smaller than $n$), and calculate $m = s^e \mod n$ (i.e. "RSA encryption"). If you used "text book RSA ...

10

Why is it common practice to create a hash of the message and sign that instead of signing the message directly? Well, the RSA operation can't handle messages longer than the modulus size. That means that if you have a 2048 bit RSA key, you would be unable to directly sign any messages longer than 256 bytes long (and even that would have problems, ...

9

A signature algorithm operates over a sequence of bits -- any sequence of bits. The meaning you may want to attach to these bits is totally none of the business of the signature algorithm. It is supposed to be handled at some other level. Basically you want to attach some meta-data to the signed object, and have that meta-data signed as well. The usual ...

9

DSA stands for "Digital Signature Algorithm" - and is specifically designed to produce digital signatures, not perform encryption. The requirement for public/private keys in this system is for a slightly different purpose - whereas in RSA, a key is needed so anyone can encrypt, in DSA a key is needed so anyone can verify. In RSA, the private key allows ...

9

In addition to the performance problems poncho already mentioned when using RSA signatures without hashing I just want to add on the security warning of poncho: Reordering If you have a message $m>N$ with $N$ being the RSA modulus, then you have to perform at least 2 RSA signatures as $m$ does not longer fit into $Z_N$. Let us assume that it requires ...

9

This is standard mathematical notation and not specific to cryptography. The $\Pi$ symbol means Product in much the same sense $\Sigma$ means Sum. For instance, $\Pi_{i=0}^2{u_i^{m_i}} = u_0^{m_0}u_1^{m_1}u_2^{m_2}$

8

Rabin signatures have a very fast verification algorithm: a simple squaring modulo some integer. RSA signature verification (with a public exponent equal to 3) is also very fast. These signature algorithms are simple to implement and will beat ECDSA for verification speed, even if batch verification is used for ECDSA. The Niederreiter digital signature ...

8

A digital signature scheme has some size on which it works (e.g. what kind of messages can be signed). This message size is usually related to the key size, and smaller than most interesting messages you would want to sign. So we use a hash function, which maps an arbitrary-length message (there is some theoretical upper size limit with most hash functions, ...

8

A pure algorithmic approach does exist, however it only provides a fuzzy bound. It is related to the proof of work / client puzzles I described in this answer. The signer will sign the message using a normal digital signature, and use the message and signature to instantiate a "cryptographic puzzle." A cryptographic puzzle is a moderately hard function ...

8

In this context, "nondeterministic" means that the algorithm to generate the ciphertext (or the signature) takes a random value as one of its inputs, and it can generate many possible ciphertexts (or signatures) based on the random value. ElGamal is nondetermanistic because the encryptor selects a random exponent as a part of encryption method. For public ...

8

Let's first define a few things. Precise definitions are needed because your question is a bit ill-defined, and it seems that you are somewhat cheating. Some definitions Traditionally, we define a signature system as the combination of three algorithms: G: key generation; given a "security parameter" t (e.g. the intended key size), yields a key pair (x, ...

8

Yes. Modern cryptosystems are designed and analysed under the assumption that the key is never used for anything else. If you use your encryption keys for digital signatures, you are violating that assumption, and it is very easy to construct schemes where this violation will compromise security. It is possible to construct schemes that can use the same ...

7

Well, there are no necessary 'reduction in strength', for two reasons: You ask about how many signatures you'd need to recover the private key. Well, even with unrestricted Oracle access to the private operation, there's no known way to recover the private key (or equivalently, factor the modulus) that's more efficient than just ignoring the Oracle and ...

7

In theory, you could "sign" the entire document by encrypting the full document with the private key. This would make the signature roughly the same size as the document, which is impractical. Instead, we sign documents by encrypting a hash of the document using the private key. This makes the signature small, which is much more practical in most cases. ...

7

In their 1998 SAC paper, M'Raihi et al showed how to use hash functions to turn Schnorr signatures (quite similar to (EC)DSA) deterministic, and proved that if the original signature scheme (with randomness) is secure, so is the deterministic one. Bernstein et al's recent EdDSA signature scheme uses the same technique to avoid randomness.

7

RSA is two algorithms, one for asymmetric encryption, the other for digital signatures. For asymmetric encryption, the main competitors of RSA would be: The Rabin cryptosystem ElGamal NTRUEncrypt Diffie-Hellman key exchange (in practice, key exchange is almost as good as asymmetric encryption, since most usages of asymmetric encryption are for sending a ...

7

One rationale for avoiding randomized schemes in general, and in MACs in particular, is that the random in such schemes tends to increases the size of cryptograms or reduce the size of the payload. An example is scheme 2 in ISO/IEC 9796-2 RSA signature with message recovery, where the size of the random/salt field is directly antagonist with the amount of ...

7

Using exponential Elgamal as the encryption function, Define the list of candidates: e.g., Alice, Bob, Carol Voters submit an encryption of their vote: e.g., to voter for Alice: $v=\langle\mathsf{Enc}(1),\mathsf{Enc}(0),\mathsf{Enc}(0)\rangle$ Use an OR-proof (Fig 2) to show each ciphertext encrypts a 0 or a 1: e.g., $\langle \pi_1, \pi_2, \pi_3 \rangle$ ...

7

Yes. Any good standard digital signature algorithm will be secure in this setting. Digital signature algorithms are designed to be secure against chosen-message attacks, where the attacker can choose any set of messages and learn the signatures on those messages; the security of the signature scheme means that this doesn't help the attacker at all. This ...

7

Most signature schemes actually incorporate a one-way function (hash) in the algorithm. Partly this is necessary to be able to sign an arbitrarily large message at all, partly this is necessary to avoid some kinds of forgery attacks on the signature scheme (often it is easy to find a "signature" which is valid, but due to the one-way function it is not easy ...

7

If you compare DSA with SHA-256 and a 2048 bit group modulus $p$, to RSA with SHA-256, a 2048 bit modulus $n$ and public exponent $e = 65537$, on you will at least perform the following operations: DSA $g^{u_1}y^{u_2}$ - 2*256 squares $\mod p$, up to on average 2*128 multiplications $\mod p$, depending on implementation optimizations. RSA $s^e$ - 16 ...

7

For your application: "I need the (underpowered 8-bit) slave to be able to tell if a command issued is really trustable", RSA signature with low public exponent ($e=3$), or Rabin (an analog with $e=2$), is likely the most appropriate, assuming you can't trust the slaves to keep a key secret, which is the only realistic assumption unless that slave uses ...

7

I hope I got your point and try to answer your question. Actually, if I understand you right, then what you call an attack actually means an adversary acting in a specific attack model. To clarify this, we need to review the security models for digital signature schemes and when we have discussed this we can clarify issues. Basically, we have to discuss ...

6

This has more to do with how Microsoft decided to implemented their certificate inspection GUI, than about the actual fields of the certificate. Most signature algorithm identifiers present in contemporary certificates specify both the public key algorithm (RSA in this case) and the digest algorithm (SHA-1 in this case). The identifier "sha1RSA" is most ...

6

IMO implementing RSA yourself is a bad idea. While textbook signing is pretty easy, if you have access to a BigInteger class, you also need to get the padding right. In some use-cases timing attacks are also a problem. But if you want to go that route, PKCS #1 is the standard you need to implement. It details how the padding should look like. The text-book ...

6

It's shockingly simple. It's a file. It has public keys in it. The traditional PGP Key Ring is a sequential file with a sequential list of keys in it. It's not even a database. Slightly more advanced key rings, such as those used in Key Servers actually use a database.

6

It very much depends on the asymmetric cryptosystem used, and its parameters. With RSA using small public exponent (which is typical), the cost of verifying a certificate (knowing the signer's public key) is dominated by a few (typically $17$ or $2$) modular multiplications (for $e=2^{16}+1$ or $e=3$) with arguments of the size of the public modulus. With ...

Only top voted, non community-wiki answers of a minimum length are eligible