Tag Info

Hot answers tagged signature

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

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

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

Actually, it does appear to be feasible to construct such a public key, with the caveats that: the public exponent $e$ will be large. While this is legal, most public keys have a small $e$ the modulus may be more vulnerable than usual to a specific (normally nonoptimal) factorization method. However, how vulnerable it is can be controlled. (Note: I'll ...

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

6

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

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

For many signature schemes, having two signatures using the same randomness for two different hash values allows recovery of the private key. This is used in many security proofs by showing that an adversary that forges a valid signature can be coerced through replaying into producing two signatures of this form. As a consequence, an forger can be twisted ...

5

Digital signatures are used to solve this type of problem. That is, a way for $A$ to sign the message for $B$ so that $B$ is highly confident that $A$ signed the message in question. There are lots of signature schemes out there, such as RSA signing, DSA, and others. A MAC is not strictly a digital signature, but has a subset of that functionality and may ...

5

Yes, this looks fine. I assume $A$ and $B_i$ are trusted parties. The protocol as I understand it looks like this: $A$, $B_1$,…,$B_n$ agree on a secret key k. $A$ broadcasts messages ($m_1$,MAC($m_1$,$k$)), … , ($m_j$,MAC($m_j$,$k$) which $B_1$,…,$B_n$ receive and authenticate. I assume $A$ and $B_i$ are trusted parties, so no $B_i$ will itself ...

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

4

Yes, this is possible. Here's one simple scheme: The scheme. We fix an upper bound $B$ for the maximum allowed value of the counter. Let $H$ be a cryptographic hash function and $\text{Sig}(\cdot)$ be an ordinary signature scheme (e.g., a RSA signature). Use $H^k(x)$ to the $k$-fold iteration of $H$ on $x$, e.g., $H^2(x)=H(H(x))$. The signature $S(n)$ ...

3

If he chooses $s$ at random, then the scheme will be stateless but will fail after using the same $s$ twice, which should happen after giving approximately $\:$$\Theta$$\big(\hspace{-0.05 in}$ $2^{H/2}$$\hspace{-0.01 in}\big)\:$ signatures. If he chooses $s$ by applying a PRF to $g(m)$, then the scheme will be deterministic and stateless, but can be ...

3

From these three, ECDSA is faster - it does arithmetic with smaller numbers, and is thus faster. (RSA verification is faster than ECDSA, even though it uses larger numbers, because it computes a exponentiation by a small number.) Still, elliptic curve Schnorr signature should be around 5-10% faster than ECDSA (or even more in a side-channel resistant ...

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

3

First and foremost: it is a bad idea to invent a method to sign or encrypt with RSA (or any crypto). Standards like PKCS#1 or ISO/IEC 9796-2 are here for that purpose, and even these occasionally have more or less subtle flaws. Given comments, I'll assume that the question is about an RSA encryption scheme enciphering message $M$ into $(M||S)^e\bmod N$, and ...

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 Since you asked in general "Are there any other obvious flaws/issues I'm missing", I would recommend that you would take a critical look at the whole update process flow. I would not consider the quality of the PRNG at your server as an obvious weak point, as long as it is reasonably strong, since on servers you have quite a bit of choice of reasonably good ... 3 Well, lets go through the issues: It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone Nope, not quite. You also need the message being signed. And, with that, it doesn't give you the unique public key; it does allow you to narrow it down to two possibilities (assuming you're using a ... 3 An RSA signature is a sequence of bytes of the same size of the modulus. If the key uses a 1024-bit modulus$n$, then the signature value is, numerically, an integer in the$1..n-1$range, and the PKCS#1 standard specifies that this integer should be encoded as a sequence of bytes of the same length as would be needed to encode the modulus, i.e. 128 bytes ... 3 Why the CFS signature is affected Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme. In the Niederreiter PKE scheme, a public key is$H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes. A plaintext is a decodable error; for example, we set$S = \{\vec{e} \in ...

3

Short Answer: NO, it is not safe, do NOT do this. Longer Answer: You are true that you can use your RSA keypair for both operations. This approach is used in many applications and scenarios. There are Web Services or Single Sign-On implementations, which enforce you to use the same key pair for both operations. X.509 certificates do not allow you (by ...

2

I don't think there is a pure-cryptography solution to this. Suppose you built a chip, and it time-stamped whatever message you wanted, using an internal atomic clock. For the sake of argument, let's say that it's unhackable, and totally tamper-proof. Well, there's still a loophole. Put the chip on a spacecraft and speed it up to 99% the speed of light for ...

2

Have you considered using symmetric key crypto (MAC) instead ? Elliptic Curve Crypto or even regular (but costly) modular arithmetic might be overkill in your case. As I understand it you would be able to precharge MAC keys into your master and slaves before deployment and you would be set. You can even generate a different key for each so that the ...

2

There is no meaningful distinction between these two things. Consider this scheme: Hash the object. Sign the hash. Now, does this scheme sign the hash or the full object? Step 2 signs the hash. But the scheme signs the full object. So which is it?

2

After looking through some papers, I feel qualified to answer my question, for the record. The scheme works and I've found no evidence that it has been broken. A good review is given in "A survey of ring signature" by L. Wang, which contains a section on linkable signatures. The technique used in Liu's 2004 paper from the question makes O(n)-long ...

2

I suppose this is a terminology question. "A digital signature scheme which can sign many documents with one private key" means something like this: There are some sets $M$ (the "message space", often the set of bitstrings of any length, or some useful subset thereof), $K_{pub}$, $K_{priv}$ (the public and private "key spaces") and $S$ (the signature ...

2

BLS signatures are $\:2\hspace{-0.04 in}\cdot\hspace{-0.03 in}k\:$ bits long, where $k$ is the security parameter, and the probability of a forgery is $\hspace{.01 in}\epsilon$. Pseudorandom MACs (such as HMAC) can be truncated to $L\hspace{.01 in}$ bits, and the probability of forgery (by someone who is outside of the system) will be \$\: \frac{\text{# of ...

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