Nytro Posted July 16, 2014 Report Posted July 16, 2014 Elliptic Curve Cryptography for Non-AlgebraistsBitcoin has captured a lot of attention as the first viable Cryptocurrency. But just how does Bitcoin incorporate the cryptography into its design? At its core Bitcoin relies on two techniques: hash function and public-key cryptography. The selected hash function is Sha256, which offers a larger block size than the commonly used Sha1. The public-key scheme is not the popular RSA public-key algorithm, but the lesser known elliptic-curve cryptography (ECC). For a comprehensive comparison of ECC and RSA, you can go here. This post, however, intends to explain the concepts behind ECC with as little math as possible, and then relate the concepts back to the terms commonly used, but not at the cost of clarity. Without further ado, let’s begin. Number Experiment We start with a little number experiment. Say we pick a number 11. We can put all the positive numbers between 0 and 10 into a set, called S. S = {0, 1, 2, 3, …..10} We then randomly pick a number from this set, and create a sequence A, based on the following rules: A1= the selected number, 4 in this case. An = the reminder of (An-1 + A1) divided by 11If the selected number is 4, then the sequence would be: 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 0, ….Two observations:Before 0 occurs in the sequence, every number in S appears exactly once including number 0. After 0, the sequence just repeats itself. Yes, this is just modular math. One way to visualize and carry out this experiment is to consider a clock set at 4 o’clock. If we continue adding 4 hours to the time, eventually we will visit every (hour) position. In this case, 12 o’clock translates to 0 o’clock. Without going into formal definitions, in our example, the set (S) and the operation (Add) form a group. This is actually quite important. To rephrase it, a group is defined on a set and an operation upon the set members. Furthermore, our example is a cyclic group. (By cyclic, recall how we can use number 4 to generate every number in S.) This experiment can be repeated with any prime number, say p. Consequently, this cyclic group is often denoted as Zp. Last, we give the number zero in this example (it may not always be the case) a special name, Identity, because the result of adding it to any number is equal to the number itself. The group concept (a set and an operation) is important. In the next step, we will find a group structure in an elliptic curve. Elliptic Curve An elliptic curve is a curve defined by polynomial in two variables. It has a general form: y2 = x3 + ax + b (1) where 4a3 + 27b2 ? 0 Based on the values of a and b, the curve may look differently. In all cases, the curve is symmetric about x-axis. (Source: wolfram.com) Remember, our goal here is to find a group structure. Again, to form a group, we need a set and an operation. Since we are talking about an elliptic curve, naturally we would like the set to include all the points on the curve. How do we define the operation? Let’s call this operation Add, denoted “+”. Operation Add needs to satisfy a condition: Suppose P and Q are two points from the set, P + Q is also a point from the set. Using a pseudo language, we may describe the idea as Where do we start looking for the R = P + Q given P and Q? By examining line PQ, we have the following observations:When P and Q form a non-vertical line, line PQ will intercept the curve at a third point. If P and Q are the same point, PQ is the tangent line. When P and Q form a vertical line, line PQ will not intercept the curve. However, we will treat the line PQ as if it intercepts the curve at an infinitely far point. In a sense, we have added a point at infinity to the curve. Now we are ready to define the operation Add: Given points P and Q, draw line PQ and compute the third point interception T, with coordinates (x, y). We define point R = P + Q, where R has the coordinates (-x, y). Geometrically, R = P + Q can be illustrated as Or algebraically, R can be derived from P and Q. With that, we have successfully defined the group of an elliptic curve, sometimes referred to as an elliptic curve group. Many articles will take a sharp turn here and start talking about field and subgroup, but our direction is different. So far, we have implicitly framed our discussion on real numbers and hence can easily draw elliptic polynomials as continuous curves. A continuous curve looks smooth, but it consists of infinite points. We would like to work on a finite set, therefore we turn our interest to integers. Let’s pick a number, p, and only focus on point (x, y), where x and y are integers and 0 < x, y < p. Furthermore, we will use modular math of p. Let’s use an example to see where we can get from here. Suppose we pick an elliptic curve And we pick a prime number, 17. How many point solutions exist? In this case, it isn’t too difficult to check every possible solution by enumerating x from 0 to 16. [TABLE=width: 640][TR][TD=width: 64]X[/TD][TD=width: 64]0[/TD][TD=width: 64]3[/TD][TD=width: 64]5[/TD][TD=width: 64]6[/TD][TD=width: 64]7[/TD][TD=width: 64]9[/TD][TD=width: 64]10[/TD][TD=width: 64]13[/TD][TD=width: 64]16[/TD][/TR][TR][TD=width: 64]y1[/TD][TD=width: 64]6[/TD][TD=width: 64]1[/TD][TD=width: 64]16[/TD][TD=width: 64]3[/TD][TD=width: 64]6[/TD][TD=width: 64]1[/TD][TD=width: 64]11[/TD][TD=width: 64]10[/TD][TD=width: 64]13[/TD][/TR][TR][TD=width: 64]y2[/TD][TD=width: 64]11[/TD][TD=width: 64]16[/TD][TD=width: 64]1[/TD][TD=width: 64]14[/TD][TD=width: 64]11[/TD][TD=width: 64]16[/TD][TD=width: 64]6[/TD][TD=width: 64]7[/TD][TD=width: 64]4[/TD][/TR][/TABLE] We should not forget there is also a point at infinity (?, ?). While we can use brute force to find all solutions, there is a better way. That’s because the solution set is actually a cyclic group. In other words, we need only to find a starting point, P. Our strategy is to utilize the Add operation we defined earlier to generate the sequence until we reach the point at infinity, i.e., the Identity: P, P+P, P+P+P… Identity In a simpler manner, the sequence is P, 2P, 3P… Identity Carry it out and we get: (0, 6), (9, 1), (6, 3), (7, 6), (10, 11), (3, 1), (13, 10), (5, 16), (16, 13), (16, 4), (5, 1), (13, 7), (3, 16), (10, 6), (7, 11), (6, 14), (9, 16), (0, 11), ‘Identity’There are 19 points. Supposing we start from point (5, 1), the sequence will be different but consists of the same points: (5, 1), (6, 3), (10, 6), (3, 1), (9, 16), (16, 13), (0, 6), (13, 7), (7, 6), (7, 11), (13, 10), (0, 11), (16, 4), (9, 1), (3, 16), (10, 11), (6, 14), (5, 16), ‘Identity’ To summarize what we just did: using a point that we repeatedly summed with itself, we developed an infinite sequence of all the solutions to the elliptic curve. Now we are ready to get into the idea of elliptic curve cryptosystems. Elliptic Curve Cryptosystem An Elliptic Curve Cryptosystem is based on the so-called ECDLP (elliptic curves discrete logarithm problem). Formally, ECDLP is defined in three steps:Let E be an elliptic curve de?ned over a ?nite ?eld Fp Let G =<B> be a cyclic subgroup of E(Fp). Let Q ? G, ECDLP is the problem of ?nding n ? Z such that Q = nB, where n < |G|. Let’s take these on one by one. Step 1: (1.a) Pick an elliptic curve, E. (1. Pick a prime number, p, and use modular arithmetic. This will restrict us to the integers ranging from 0 to p-1. Numbers {0..p-1} and operations, (modular) addition and division, combined are denoted as Fp. Let the term “Field” refer to a set of points with well-defined operations, addition and division, upon the points of that given set.Step 2: (2.a) Suppose point B is a solution of the curve E. Notice B’s coordinates are integers between 0 and p-1. (2. Using the equations of (2), (3) and (4), compute the sequence B, 2B, 3B… and eventually obtain the Identity. We denote the distinct elements generated from B as <B>. Also, let G = <B>. (2.c) <B> is generated from a single point B, hence it is described as cyclic. By subgroup, it means that set G is a subset of a bigger set (i.e., the elliptic curve).Step 3. (3.a) Pick a point Q from the set G. Recalling G=<B>, every point in G is a multiple of B. In other words, there exists an integer n, which is less than the selected prime P (or the size of G, |G|). (3. It turns out that given B and Q, it is difficult to find n, such that nB=Q. This difficulty is exactly why elliptic curves are used for cryptography. (3.c) You may wonder where the name “discrete logarithm” comes from. Discrete logarithm means solving for x of an equation ax = b, where a and b are known integers. Compare this equation with the equation nB=Q. We can see the similarity, but the former involves a raised power and the latter is simple addition. Recall the “addition” in the Elliptic Curve is purely our definition of an operation. For convenience, we denoted it as “Add,” but we can also denote it as “Multiple,” when the two operands are the same. In other words, <B> can be written instead as B, B2, B3, ….We have now completely defined the problem. In an upcoming post, we will explore how to build a non-symmetric encryption algorithm on top of the ECDLP.Sursa: Elliptic Curve Cryptography for Non-Algebraists | Quote
