In digital signature schemes, what the security advantage of using Elliptic Curve over Integer Factorization and Discrete Logarithm schemes?
121354
What is the benefit of using elliptic curves over the standard finite field, when the cyclic subgroup we consider of the EC's  solution group is just isomorphic to some integer residue class of prime order? Is it because the group operation is more complex?
67074
I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the meanwhile?  Edit: Lets assume an appropriate padding strategy. Also, I'm asking both about security of signatures and security of data encryption.
67958
The algorithm purposed to play a fair game of heads or tails over the phone given  claims that knowing the four solutions to  $$ x^2 \equiv a^2 \pmod n$$ would allow us to factor $n$ where $n$ is a product of two unknown primes $p,q$ and $\gcd(a, n) = 1$. However, I am not seeing why this would be true. Can someone please explain?
41201
There seems to be sources like , this , and some  that discuss elliptic curves in general and how they're used.  But what I'd like to know is why these particular curves are so important in cryptography as opposed to, let's say, any other polynomial degree $\gt$ 2 which you can then mod over some group.  It seems like once a modulus is applied then other function types should be acceptable as well.  It seems even less intuitive when just looking at the bubble vs curve as here:    Since there are other curves (let's say anything from a sin wave to the $x^3 + x$ or even just some unusually shaped contour) that could do the job.  It seems like they would provide much more surface area to get a larger space in $\mathbb{Z}_p$ or really just more possible combinations of connecting lines from some arbitrary $P$ and $Q$ to get $R$ as opposed to something as restrictive (on the graph) as beginning from some bubble (which would seem to unnecessarily reduce the possible combinations) and then use a modulus to implement the discrete logarithm problem.  Sorry if this seems a little naive of a question, I'm trying to write an implementation right now and just to understand it fully even if that means asking something that is taken for granted.  Perhaps just walking through a simple example (most of the ones I've searched are anything but), just a few sentences, would be rather helpful, from "A wants to talk to B" all the way up to "now E can't listen in between A and B".  EDIT:  So it seems like this is the version of elliptic curves over a finite field:    Yes that looks pretty random.  But I'm still not really seeing why they are the only equations that have cryptographic significance.  It's difficult to imagine that if you simply took some other higher degree equation and applied modulus (to place within a group), then it seems like it would make sense that you'd get something that's also comparatively random.
105838
Key derivation functions, such as HKDF (standardized in ), are meant to stretch some initial keying material having enough entropy, like a Diffie-Hellman shared value, into one or more strong cryptographic secret keys.   Password-hashing schemes, such as the  winner , are meant to hash usually low-entropy passwords with the goal of making the hash digest inversion as costly as possible for an adversary with respect to CPU and memory consumption, as well as parallelization.  Is it exact to consider that password-hashing schemes are actually key derivation functions specialized for low-entropy inputs? Or is there any other essential difference of theoretical nature between these two types of cryptographic schemes?
28378
From what I understand, based on the article , the public key is generated by performing $n$ tangent plus mirroring operations from the point $G$ over the elliptic curve, where $G$ is defined in  and $n$ is a natural number that directly relates to the private key.   As I know the public key and the seed value $G$, I could start a process computing $$G + G, G + G + G, \dots$$ and comparing those results with the public key value until it matches.   If your answer would be that this process is very slow: if this process is slow, the same applies to computing the public key from the private key (because the operations are the same except for the check operation). So, how it is possible to compute the public key in a very fast way?
69235
I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on mathematical facts, others are just instinctive approximations (such as square roots).  Don't such 'tricks' exist for factorization of a product of 2 large primes. For example, the first thing to do would be to figure out the possible last digits of the answer. We stick to decimal numbers, but a computer could do this in a number system of any base (even 999). Based on previous numbers, can an algorithm be written to 'predict' the factorization based on the individual digits in various number systems.
4111
Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems true as I know the public/private key pair. Can someone help me to prove this?  Please provide references so that I can read further into this subject.
50609
In cryptography, an elliptic curve is a group based on a finite field $GF(p^k)$; this group has $n$ elements on it, and we work on a prime-sized subgroup of size $q$.  We denote the value $h = n/q$ as the cofactor of the curve.  My question is: why would we ever want to consider using a curve which has a cofactor $h&gt;1$?  Or, in other words, why would we consider using an elliptic curve that had a composite number of points?  After all, the discrete log problem can be solved in $O(\sqrt{n / h})$ time; if we were to select a curve with $h&gt;1$, we are deliberately making this problem easier.  Now, if $h$ is small, we're not making it much easier; if (for example) $p^k \ge 2^{256}$ and $h \le 4$, this would still appear to be an intractible problem.  On the other hand, I don't know if we want to make the attacker's job any easier than necessary, unless we gain some other benefit from it (perhaps making some other attack harder, or gaining some computational efficiency).  So, is there any benefit for using a curve with a cofactor > 1?
41396
I am trying to construct a theoretical Diffie-Hellman key exchange protocol. However, i cannot understand the difference between choosing an additive group or a multiplicative group. I believe an additive would make it much more simple, but would a multiplicative group make it more difficult to break? What would be the difference between the use of those 2 kinds of number groups?
108785
Show how if Alice uses the same value of $k$ to sign two different messages $m_1$ and $m_2$, using the ElGamal signature scheme, Eve can recover the value of $a$ from the corresponding signatures $(m_1, r_1, s_1)$ and $(m_2, r_2, s_2)$. (Note: you are allowed to assume that if $\gcd(a, n) = d$ then there are $d$ solutions to the congruence $ax \equiv b \pmod n$.)     ElGamal Signature Scheme:      Key Gen:      Compute $y = g^x \;\bmod p$.      The public key is $(p, g, y)$. The secret key is $(p, g, x)$      Signature Gen:      Choose a random $k$ such that $0 &lt; k &lt; p − 1$ and $\gcd(k, p − 1) = 1$      Compute $r = g^k \;\bmod p$ and $s = k^{-1}(m – xr) \;\bmod{p-1}$   Thoughts: So far, I can tell that $r_1$ and $r_2$ are equal and $s_1$ and $s_2$ are closely related since the only variation is $m$.  We can relate the two equations for $s$, by solving them for $-xr$:  $$s_1k - m_1 \equiv s_2k - m_2 \pmod p$$  $$(s_1 - s_2)k \equiv m_1 - m_2 \pmod p$$  Let $a = s_1 - s_2$, then we know from the question that for $\gcd(a, n) = d$ there are $d$ solutions for $k$.  Now the forger can compute $g^k$ for each solution to k, until $r$ is found.  Then compute $xr \equiv m_1 - ks_1 \pmod{p-1}$  There are $d&#39; = \gcd(r, p-1)$ solutions for $x$.  The forger can compute $g^x$ for all the $x$s found until she finds $y$.  Once she has $y$ she knows the proper $x$ which can be used to find $m_1$ and $m_2$.  How does this look?
3848
I read ampersand's question , where he asked why Shamir's Secret Sharing Scheme uses arithmetic in a finite field of prime order.  The answers to that question explain that a prime field is not necessary for Shamir's scheme, but, rather, that any finite field can be used.  However, they don't really address the other part of the question, namely why do we need a finite field at all?  Couldn't we just use, say, ordinary integer arithmetic instead?  Can someone please explain (in the simplest possible manner) the reason that Shamir's Secret Sharing Scheme uses finite field arithmetic?
41298
I read the book "Introduction modern cryptography". It gives the notion of computational security of private-key encryption at first which comes from perfect security and statistical security.     Let $(E,D)$ be an encryption scheme that uses $n$-bits keys to encrypt $l(n)$-length messages. $(E,D)$ is computationally secure if    $$E_{U_{n}}(x_{0}) \approx E_{U_{n}}(x_1)$$   And then it introduces the secure game (e.g. CPA, CCA)? I think it is a part of provable security.  "Unconditional security" (or "information-theoretic security" or "perfectly secrecy") and "computational security" are two opposite classes of security. But I do not think "computational security" and "provable security" are two independent classes of security. I know that computational security emphasizes the power of attacker is bounded (polynomial-time algorithm). And the provable emphasizes the mathematical assumptions or cryptography primitives. But it also related to the computational power.
64071
I've already read  question about the difference between discrete and non discrete logarithms. But I still have problems to clarify my mind about why the Discrete Logarithm Problem is computationally hard while the NON Discrete Logarithm Problem is not, as I read in my Cryptography and Security book.  What are the computation differences? Why can I, for example, easily break a non discrete logarithm cipher but not a discrete one?
30891
In textbook RSA, the Euler $\varphi$ function $$\varphi(pq) = (p-1)(q-1)$$ is used to define the private exponent $d$. On the other hand, real-world cryptographic specifications require the Carmichael lcm function $$\lambda(pq) = \operatorname{lcm}(p-1,q-1)$$ to define $d´$. It is clear that the $d´$ divides $d$, and therefore using $d´$ may be more efficient than using $d$. My question is: Are there any further reasons, e.g. regarding security, why one should not use $d$?
120142
Any thoughts on how this can be done?        Let $\Pi_1 = (\mathrm{Gen}_1, \mathrm{Enc}_1, \mathrm{Dec}_1)$ and $\Pi_2 = (\mathrm{Gen}_2, \mathrm{Enc}_2, \mathrm{Dec}_2)$ be two encryption schemes for which it is known that at least one is CPA-secure. The problem is that you don't know which one is CPA-secure and which one may not be. Show how to construct an encryption scheme $\Pi$ that is guaranteed to be CPA-secure as long as at least one of $\Pi_1$ or $\Pi_2$ is CPA-secure.   .
13882
It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: I also want to be sure that even the person that constructed the number cannot factor it.  Of course, a random large enough integer is going to be hard to factor with high probability, but we might be unlucky.  There are also multi-party protocols for shared generation of RSA moduli (such as ), but I would like a non interactive technique.  Motivation: This was suggested by Poncho's answer to