# Tag Info

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

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

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

You got tripped up by the fact that there are two different group operations in play here, and they don't play nice with each other. This is implicit in the notation, and it's easy to get tripped up, because the notation expresses both operations in the same way -- but they are not the same. This is arguably a pitfall in the notation: the assumption is ...

5

This sounds like a fair exchange protocol where what is exchanged is a digital signature. Per this paper, these are impossible without trusted third parties. With a trusted third party, they are possible. Indeed people have proposed schemes that do what you describe again relying on a third party in the case of failure.

5

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

4

It looks like your main question is determining why $k{_{E}}^{-1} = 2$, correct? As mentioned in the comments to the question, this is because it is the modular multiplicative inverse. The multiplicative inverse is a number, $x^{-1}$, such that $x·x^{-1}=1$. However, since we are in modulo 19, we want to find $x^{-1}$ such that $x·x^{-1}\equiv1 \bmod 19$. ...

4

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

4

Your question appears to be "why do we use the terminology 'encoding' when talking about what we do as a part of the signature operation". Well, we don't (at least, I don't, and I don't remember hearing that terminology from someone else). As for RSA, well, the terminology you use is moderately irrelevant (as long as you do the cryptographical operations ...

4

Digital Signatures, hashes and MACs can do similar jobs. They allow someone sending a message to a check value along with the message. They allow someone receiving the message to verify that the message corresponds to the check value. However, a hash is an unkeyed operation; anyone can compute the hash of the message. So, while they provide protection ...

4

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

4

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

4

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

4

Some signature algorithms are deterministic (you always get the same signature for the same private key and input), others are not. In the case of RSA, as specified by PKCS#1, the "old-style" (aka "v1.5") signatures are deterministic, while the "new-style" ("PSS") signatures are not (padding includes some random bytes). In Java, the "NONEwithRSA" mechanism ...

3

I'm still a newbie in the field, but trying to learn something about it I ran into these two papers that you surely know, in case not I'll point them out: Blind signatures for untraceable payments, Chaum Provably secure blind signatures schemes, Pointcheval By the way if you look at the introduction of the second title it seems what your looking for. ...

3

Yes. There has been extensive research on this question: there is even a community of cryptographers who work on building voting schemes of this sort (see end-to-end auditable voting system). I'll give you some advice based upon the experience from that field. Don't design your own. Don't try to design your own. There has been extensive research into ...

3

I see a few issues with this approach: First, since you're signing the ciphertext and sending the signature in plain, anyone who has your public key can verify that you did, in fact, sign that message, even if they won't be able to actually decrypt it. This may or may not be something you want. More importantly, anyone who intercepts the message can strip ...

3

Actually, if everyone uses a different salt whenever they "sign", and if the RSA_sign operation doesn't involve a hash (in general, real signature operations do, I don't know about your variant), it turns out not to be secure, and in fact, the password can be recovered fairly easily if the attacker hears enough signatures based on the same password. Here's ...

3

The core of the problem is finding a near first pre-image on the function $A = aB$ on an elliptic curve, where $A$ is the public key, and $a$ the private key¹. For a normal hash function you $2^m$ operations to fix $m$ specific bits.² In particular a full pre-image takes $2^n$ hash function calls. A full pre-image on $A = aB$ is equivalent to solving ...

3

I don't have any experience with this myself, but Tom Ritter talked about this on twitter: Matthew Green: Out of curiosity: do you happen to know offhand how much it costs to factor a 512-bit RSA key on EC2? Tom Ritter: My personal costs are \$120-\$150 with my setup. You can probably do it cheaper, heard reports of \\$75. He also published a ...

3

"Efﬁcient, Compromise Resilient and Append-only Cryptographic Schemes for Secure Audit Logging" (PDF) gives a publicly verifiable approach that allows fine-grained verification, but it is in the Random Oracle Model. The Simple Method: The verifier and logger start with a seed for a forward-secure pseudo-random number generator. To denote a valid ending ...

2

Such certificates are basically just an implementation of digital signatures. One certificate is used to sign the data using a private key, and a corresponding verification certificate is given to the user along with the signature and the data. The user uses the verification certificate to verify that the file matches its signature. You can't reverse ...

2

It's a statement made by the signer, just like if I say that this message was written on 19 June 2012. Its value is context-dependent. Just like with a pen and paper, you can post-date or pre-date anything. In general, there's no such thing as verified time. Over the years, there are many people who have tried to create trusted time services, but they've ...

2

There is another advantage that certs provide that has nothing to do with trust issues. Certs are a pretty-much universally-recognised public-key bit-bagging format that's portable to pretty much everything, while there's no such equivalent for raw public keys. By placing your public key in a certificate, you're converting it into an interoperable form that ...

2

PKCS#1, "the" RSA standard, describes how a signature should be encoded, and it is a sequence of bytes with big-endian unsigned encoding, always of the size of the modulus. This means that for a 2048-bit modulus, all signatures have length exactly 256 bytes, never more, never less. PKCS#1 is the most widely used standard, but there are other standards in ...

2

If you can store the private key with some pre-computed work, then you can pick almost any public key you want. So in a way, it depends on the implementation. Here's a diagram of how Ed25519 works, note how keys are generated: (Image source.) A more detailed description (that is simpler than the actual paper) of the process is in these slides (slides 9 ...

2

The answer is either "no" or "it depends". Generally speaking, RSA-PSS is more robust, in the sense that you don't have to take as many extra precautions in order to use it securely. RSA-PKCS#1-v1.5 is OTOH more widely supported by pre-exisiting software, but you sometimes have to patch the way it is used in order to prevent exploits. For instance, if you ...

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