# Tag Info

4

I am given $p = 4916335901$, $q = 88903$ and am asked to show these are prime To check whether a given integer $n$ is prime you have to check whether it is only divisible by $1$ and $n$, i.e., that it is not a composite integer. If you are given such an integer you can either factor the given integer, use primality tests to check for primality or in ...

4

There are two ways to solve a discrete log problem over $Z^*/p$, that is, given $g$ and $h$, find $x$ with $h \equiv g^x \bmod p$: If the point $g$ generates a subgroup of size $q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover $x$ in $O( \sqrt{q})$ time. Use the Number Field Sieve algorithm to attack the discrete log problem in ...

2

In a sense, you are correct in not understanding where the equations in DSA and ElGamal signatures come from. To a certain extent, they are just (distinct) choices from a family of equations that all seem to work, and all for the same-ish reasons. See e.g. Meta-ElGamal signature schemes by Patrick Horster, Holger Petersen, Markus Michels, ...

2

The fundamental difference between RSA-groups and prime order groups is that in RSA groups the multiplicative order of the group is unknown (without knowledge of the factorization). This allows much easier constructions for unforgeable signatures (although hashing and padding are required to ensure existential unforgeability). With knowledge of the group ...

1

What you need to know is that all equations in this context are, implicitly, understood to be modulo n. That information alone should answer all of your questions, starting with the equation k = (z1 - z2) / (s1 - s2) (modulo N), which hence means k = ((z1-z2) * modular_inverse_mod_n(s1-s2)) % n, where I tried to copy your modulus (%) operator. Specifically: ...

1

While no SHA1 collisions have been found, there are some attacks: ~$2^{60}$ collision attack. Estimated to cost around \$1-2 million currently in the cloud. Possibly economical soon, especially with specialized hardware. Intractable preimage attacks like$2^{151}$against reduced round variant,$2^{159}$against full hash. (Cf.$2^{160}$brute force on any ... 1 In the case of emails your solution is not really practical. The problem is that the sender of an email uses the public key whereas the receiver should have the secret key. This means that whenever somebody wants to send you an email (and therefore generate a new key) you have to be online or you have to provide a set of pre-computed key pairs. If multiple ... 1 With my new idea I seem to solve the problem and answer my question, so I'll go ahead and post it as the answer. I choose the new$m'$as$m'=t+m$with$t>0$. Now the verification works like this:$v'=g^{m'w} y^{rw}=g^{m'w+xrw}=g^{tw+mw+xrw}=g^{tw} \cdot g^k=r' \mod q$So my new$r'=g^{tw}r=g^{ts^{-1}}r\$ This means I can create a legit signature to any ...

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