Hot answers tagged signature
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 ...
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 ...
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
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 ...
7
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, ...
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
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
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
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 ...
6
In principle, the answer is no, with an asterisk. Signature schemes are equivalent to one-way functions under black-box reductions. Public-key encryption scheme implies the existence of key agreement.
Impagliazzo & Rudich famously proved that there is no black-box reduction from one-way functions to key agreement. That means there is no ...
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
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 ...
6
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 ...
6
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, ...
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
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 ...
6
No it's not useful to use slow hashing in such a situation.
The relevant attacks against the hash in a digital signature are second pre-images and sometimes collisions. Assuming the hash-function is secure, then there is no way to find collisions with less work than $2^{n/2}$, and second pre-images with less work than $2^{n}$. There is no weak part the ...
6
No.
The challenge for RSA-155 (which is 512 bits) was broken in 1999. This took 6 months on pretty advanced hardware to break at the time, which works out to 8000 MIPS years. It should be much less today.
FYI, RSA 768 took just under 3 years.
6
This is secure, and a lot of systems actually do signatures this way (for example, PGP). One reason to do this for performance. Signing a hash is much faster than signing your whole message. It is also non-trivial to hash large messages since signature functions usually operate on a bounded size input.
An attacker will have just as much difficulty forging a ...
5
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 ...
5
That is not a bad method of doing a license key; an attacker would certainly be unable to generate a signature that would validate with his computer's window product key.
On the other hand, this approach may be overkill. The easiest way to attack this system would be to modify the program to skip (or ignore) the signature validation; hackers have both the ...
5
Normally, the salt length is part of the signature parameters, i.e. the things which tell you that the signature is indeed of type RSA-PSS, what hash function is used and what mask generation function is used.
Many protocols use ASN.1 to encode such parameters (e.g. CMS, the offspring of PKCS#7 and basis for signed emails with S/MIME). PKCS#1 defines (in ...
5
I recommend you use Rabin signatures. Rabin signatures without batch verification are likely to be faster than most other signatures with batch verification.
Moreover, read Dan Bernstein's work. He has shown how to make Rabin signatures even faster. For standard Rabin signatures, verification requires approximately one modular multiplication modulo n ...
5
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 ...
5
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 ...
5
If the CA issued something with a CSR as the dominant part of the To-Be-Signed field, it wouldn't be a X.509 certificate and hardly any existing software would know what to do with it. I guess the original CSR could be added as an extension, though.
Therefore, I suppose you are really asking why the X.509 certificate format wasn't originally specified to ...
5
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 ...
5
The "signed on date" field of any signature message format is only trustworthy if you trust the signer to not
modify the software to include an arbitrary date (or use a software which allows setting the date) or
change his computer's system date.
So, if the signer wants to use this field to prove that this was signed at some time (specially, before some ...
5
PSS is harder to implement because it uses randomness -- randomness is hard on many embedded systems like smart cards.
The most proclaimed advantage of PSS is that it has a "security proof" with, apparently, a rather tight reduction (see this page for some references). Security proofs are not an easy subject; the proof for OAEP (the encryption padding which ...
5
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
