# Tag Info

This is a) no attack on the security model, but an attack in the security model of EUF-CMA, and b) a generic attack on any signature scheme that signs the hash of a message instead of the message itself (as done in RSA-FDH). The idea is that if you can find a collision for the used hash function $H$, i.e., two messages $m_1, m_2$ such that $H(m_1) = H(... 3 HMAC (and any other MAC) are totally different from Digital Signatures (RSA, DSA, ECDSA, EdDSA). MACs require a shared secret key that both the communicating parties have. The same secret is used to create the MAC as is used to verify it. Anyone with the shared secret key can create a MAC, and anyone with the shared secret key can verify a MAC. Digital ... 3 If$x^2\equiv1\mod{n}$, it means that$(x+1)(x-1)\equiv0\mod n$. In other words,$(x+1)(x-1)=k\cdot n=k\cdot p\cdot q$for some$k\in\mathbb{N}$. And there you go: if$x\neq\pm 1\mod n$, neither$x+1$nor$x-1$equals$p\cdot q$and must contain either of the primes in their factorization (plus perhaps some factor of$k$). Hence,$\gcd(x+1,n)\in\{p,q\}$. 2 You have$x^2 \equiv 1 \pmod n$and$x \neq \pm 1 \pmod n$now we can write$x^2 -1 = 0 + n\cdot k$for some$k \in \mathbb{Z}$. that is$(x-1)(x+1) = n \cdot k$. So if you take$\gcd(x+1, n)$and$\gcd(x-1,n)$then one of them must be larger than 1. Otherwise we have to$(x-1)(x+1) = k$which fails since the equality. 2 To give an example with less maths, suppose that I come to you and ask you to sign the message "Josiah's favourite number is 747895723190543. Weird I know." You think that is a bit odd, but harmless so you do so. Unbeknown to you, the hash of that message is also the hash of "Please pay Josiah the sum of 87476 United States dollars." Because the hash ... 1 The proposed system seems to be as follows: At generation, Alice selects odd$e>2$and random large primes$p$and$q$with$\gcd(p-1,e)=1=\gcd(q-1,e)$; computes$n\gets p\,q$; chooses random$s_0$in$[1,n)$; and publishes$(n,e,s_0)$. She computes and keep secret$\lambda(n)\gets(p-1)(q-1)/\gcd(p-1,q-1)$and$d\gets e^{-1}\bmod\lambda(n)\$. For ...