# Tag Info

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

6

Well, one reason to hash the data before signing it is because RSA can handle only so much data; we might want to sign messages longer than that. For example, suppose we are using a 2k RSA key; that means that the RSA operation can handle messages up to 2047 bits; or 255 bytes. We often want to sign messages longer than 255 bytes. By hashing the message ...

5

If we note $|m|$ the number of bits in the bytestring coding the message $m$, the first padding considered is $m\mapsto \tilde m=257\cdot2^{|m|}+m$, and the signature is $m\mapsto\tilde S(m)=S(\tilde m)=\tilde m^d\bmod N$, where $S$ is the textbook/naked RSA signing $m\mapsto m^d\bmod N$. Notice that for any $m$ small enough that $m^2$ can be signed, we can ...

3

Look at it this way; consider the value of: $(2^{1019} - N * 2^{34} / 3)^3$ Using the binomial expansion, we see that it equal to: $(2^{1019})^3 - 3 * (2^{1019})^2 * N * 2^{34}/3 + 3 * 2^{1019} * (N * 2^{34} / 3)^2 - (N * 2^{34} / 3)^3$ or (simplifying): $2^{3057} - N * 2^{2072} + G$ where $G = N^2/3 * 2^{1087} - N^3/27 * 2^{102} < 2^{2072}$ for the ...

2

Considering the padding as an addition, padded message passed to sign is $m\cdot 2^{16}+0101$, $0101$ in hexadecimal, assuming padding is done on the lower bytes (for higher bytes the logic is just the same). Being $e$ the private exponent, and $m^2$ computed in the size of $m$, $(m\cdot 2^{16}+0101)^e \pmod m$ is very different from $(m^2\cdot ... 1 Given a set of (unhashed) Lamport signatures using the same key, an attacker can trivially forge a signature for any message whose$k$-th bit, for each$k$, is equal to the$k$-th bit of at least one of the signed messages. For example, let's say I know the Lamport signatures for the following 16-bit messages using the same key:$$m_1 = 0001111101110001 ... 1 I assume that the deadline for the homework is passed, so I will provide an answer: Let us assume that we have the public key$y=g^x \pmod p$and the private key to be$x$. Computing an ElGamal signature for a message$m \in Z_p^*$amounts to: choosing$k\in Z_p^*r\equiv g^k \pmod ps\equiv (m-xk)k^{-1} \pmod{p-1}$which is equivalent to$m\equiv ...

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