# Tag Info

11

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. Huh? I see two problems with the above statement; "Encryption"; using the word encryption implies that there's a way somehow to decrypt it. However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the ...

9

This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit). First, I assume that when writing $Pr[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both $x$ and $y$. Now, the claim is that there exists a subset of $x$ values of a large enough size'' so that for every $x$ in ...

5

I suppose that you address the question to a signature scheme, in which the signature is still the pair $(r,s)$ with $r=g^k \bmod p$ as the exponentiated nonce and $$s = H(m)\cdot x + k \mod q,$$ where $h = H(m)$ depends solely on the message $m$ being signed. Here $x$ denotes the secret signing key and $q$ the order of the generator $g$ of a prime ...

4

Well, there are indeed differences between the two standards, as you can see below: key pair generation X9.31 requires that $p-1$, $p+1$, $q-1$, $q+1$ all have prime factors between $2^{100}$ and $2^{120}$, and that $p$ and $q$ differ in at least one of the first 100 bits. These requirements are there to frustrate suboptimal factoring methods, ...

3

Comments already pointed out, that encryption and signing are not the same and should not be exchanged deliberately. Of course in practice specifically for RSA, not PKE in general, and only in the textbook variant (no padding), encrypt/decrypt are bascally the same operations as sign/verify: For all of them, you just do modular exponentiations; and the ...

3

$s_1, ..., s_N \stackrel{\$}{\leftarrow} S$means coordinate-wise sampling:$s_1 \stackrel{\$}{\leftarrow} S$ $s_2 \stackrel{\$}{\leftarrow} S$...$s_N \stackrel{\$}{\leftarrow} S$

1

An analogy might not be that helpful but an example for example with RSA signatures. RSA Signatures work like this: s = m^d mod N where s is the signature, m the message and d the private key. (See example below. Verification works like this: m' = s^e mod N where s is still the signature and e is the publicly known and trusted public key. If m' = m ...

1

Ok, here's a toy example (which really doesn't work) of a simple signature scheme, which you can use as an analogy of a real system: Suppose the signer Alice picks three integers $b, c, p$, and computes $a = b \times c \bmod p$. She then publishes $a, b, p$ as her public key, and keeps $c, p$ as her private key. Then, when Alice wants to sign a message $M$...

1

To decode from a public-key encoded message, you need the secret private key. Anyone else cannot do it. For the mathematical details how this is possible, you need to analyse the respective asymmetric cryptographic algorithms. There are several different asymmetrical encryption algorithms, including RSA and ElGamal, see the Wikipedia links for an ...

1

In principle, a signature can always be used in lieu of a MAC. You use a MAC when you want the legitimate recipient of a message to be able to verify its authenticity. With a signature, everyone, including of course the legitimate recipient, can verify the authenticity of a message. The reason we use MACs at all, instead of just using signatures all the ...

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