Tag Info

Hot answers tagged

21

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 ...


16

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 ...


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 ...


12

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 ...


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

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

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. 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

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

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

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

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

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 ...


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 ...


6

There isn't a simple answer, as speed of batching depends on a number of parameters. First, the speed of the signature and the speed of the batching is largely independent. If you have two signature algorithms S1 and S2 that both permit batching technique B1, then generally they will both permit batching technique B2. If S1 is faster than S2 for individual ...


6

I'm surprised that Daniel J. Bernstein's EdDSA has not been mentioned. High-speed high-security signatures Even faster batch verification. The software performs a batch of 64 separate signature verifications (verifying 64 signatures of 64 messages under 64 public keys) in only 8.55 million cycles, i.e., under 134000 cycles per signature. The ...


6

For the first part of your question: Yes, if Mallory manages to publish is own public key under Alice's name, then there is really nothing to stop him. This problem is addressed with public key infrastuctures and public key certificates. That is, for Bob to believe that the public key is Alice's key, Mallory would need to have a trusted third party attest, ...


6

I'm considering switching to ECDSA, would this require less space with the same level of encryption? The answer to that question is yes, both ECDSA signatures and public keys are much smaller than RSA signatures and public keys of similar security levels. If you compare a 192-bit ECDSA curve compared to a 1k RSA key (which are roughly the same security ...



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