Meta tags:
description=Visualize elliptic curve cryptography with animated examples;

Headings (most frequently used words):

curve, the, elliptic, finite, addition, multiplication, point, animated, adding, points, on, field, math, curves, and, fields, key, exchange, real, subtraction, negation, division, multiplicative, inverse, square, root, efficient,

Text of the page (most frequently used words):
the (102), and (43), point (41), curve (28), for (24), number (24), this (22), that (17), points (16), addition (15), field (14), can (13), #exchange (13), #finite (13), key (12), same (12), with (11), elliptic (11), equation (10), are (10), which (10), itself (10), curve25519 (9), bob (9), alice (9), two (9), math (9), our (8), times (8), above (8), adding (8), let (8), sqrt (8), used (7), add (7), use (7), text (7), numbers (7), square (7), also (6), curve61 (6), using (6), they (6), base (6), added (6), curves (6), have (6), multiplication (6), mod (6), prime (5), what (5), way (5), random (5), over (5), one (5), you (5), below (5), coordinates (5), any (5), lambda (5), root (5), positive (5), details (4), double (4), see (4), toy (4), large (4), before (4), mathbb (4), 255 (4), f61 (4), around (4), but (4), real (4), tls (4), just (4), computes (4), like (4), going (4), get (4), frac (4), x_1 (4), from (4), value (4), each (4), operations (4), zero (4), cdot (4), define (4), inverse (4), line (4), most (3), much (3), perform (3), when (3), then (3), where (3), only (3), than (3), looks (3), has (3), simple (3), associative (3), k_b (3), k_a (3), start (3), y_1 (3), x_2 (3), x_3 (3), values (3), negate (3), undefined (3), division (3), f23 (3), solution (3), negative (3), negation (3), satisfies (3), will (3), multiplicative (3), result (3), set (3), order (3), found (2), choice (2), these (2), concepts (2), secure (2), did (2), though (2), formula (2), different (2), those (2), possible (2), very (2), digit (2), repeating (2), uses (2), other (2), how (2), does (2), cryptography (2), such (2), private (2), because (2), both (2), agreed (2), sends (2), picks (2), agree (2), section (2), conversation (2), being (2), many (2), now (2), method (2), 100 (2), multiplied (2), another (2), repeated (2), tangent (2), y_2 (2), y_3 (2), third (2), animation (2), intersection (2), finding (2), relatively (2), rules (2), draw (2), between (2), find (2), chosen (2), was (2), every (2), additions (2), finally (2), graph (2), would (2), working (2), through (2), roots (2), combine (2), fields (2), solutions (2), provided (2), table (2), non (2), members (2), all (2), together (2), need (2), integer (2), subtracting (2), might (2), modulo (2), wrap (2), again (2), commutative (2), animated (2), code, project, github, depth, information, including, exact, recommend, streamlining, listed, page, keep, mechanism, performant, should, not, fundamentally, conflict, explained, here, technical, analysis, author, paper, changes, due, wikipedia, peers, select, 256, bit, bits, overridden, more, 251, multiplications, attacker, guess, x25519, site, 252, size, been, 486662x, common, played, seen, means, compare, enter, keys, watch, occur, k_ap, k_bp, since, k_ak_bp, described, process, want, without, eavesdroppers, able, tell, upon, derive, fast, ciphers, aes, encrypt, their, enough, doing, cryptographic, work, combinations, needed, multiple, repeatedly, 16p, 32p, arbitrarily, quickly, 100p, thought, referred, scalar, refer, efficient, 3x_1, 2y_1, them, called, doubling, slope, shows, wrapping, sometimes, algebraically, easy, remember, formulas, still, lines, give, name, combination, definitions, call, somewhat, arbitrary, some, better, others, comes, back, specifically, repeats, nominate, resulting, plotted, cdot5, 171, cdot4, 101, cdot3, cdot2, cdot1, cdot0, look, plot, starting, defined, tables, pre, computed, convenience, _61, half, last, operation, tie, time, divide, instead, multiply, its, integers, equal, turns, out, there, acts, notation, easier, fit, expand, terms, concept, divided, solve, flipping, sign, vice, versa, definition, straightforward, similar, taken, know, remainder, after, dividing, pretty, greater, subtraction, inputs, outputs, floating, nothing, higher, _23, list, next, put, aside, introduce, new, matter, always, n_3, demonstrated, adds, n_1p, n_2p, n_3p, individually, results, useful, properties, later, intersects, make, yield, form, examples, looking, heart, break, down, into, parts, session, starts, made, via, popular, involves, visualizing,

Text of the page (random words):
the animated elliptic curve the animated elliptic curve visualizing elliptic curve cryptography every tls 1 3 session starts with a key exchange made via an elliptic curve the most popular curve is curve25519 and the exchange involves adding a base point p to itself over and over again curve25519 point addition we re looking at the heart of tls 1 3 key exchange but what s going on let s break it down into simple parts adding points on a curve the elliptic curves we re going to use are in this form y 2 x 3 ax b examples of elliptic curves let s define point addition a way to combine two points on an elliptic curve to yield a third point also on the curve point addition draw a line between the two points or if you re adding a point to itself make a line tangent to the curve at that point find where that line intersects the curve and finally negate the y value of that point repeated addition of a point p point addition has two useful properties which we ll need later commutative adding points in any order results in the same point p q q p p q r r q p p r q associative addition of additions has the same result as adding the points individually p q r p q r p p p p p p p p p p 2p 3p 5p p p p p p p p p p p 4p 1p 5p this is demonstrated in the animation below which adds points in random order n_1p n_2p n_3p no matter which points are added or in which order the result is always the same point that was found by adding p to itself over and over again n_3 times above point addition is associative and commutative finite field math next let s put curves aside and introduce a new set of math operations the operations of the finite field fp a finite field is just a set of numbers in this section we ll set p to 23 a prime number the finite field f23 is the list of numbers 0 through 22 mathbb f _23 0 1 2 22 all the math operations below use only those 23 numbers as inputs as outputs no negative numbers no floating point and nothing higher than 22 addition subtraction adding and subtracting in finite fields is pretty simple values of 23 and greater will wrap around to zero and values below zero will wrap around to 22 you might also know this as modulo 23 or as the remainder after dividing a number by 23 multiplication multiplication is also straightforward similar to addition the result is taken modulo 23 negation you might be used to negation as flipping a value s sign from positive to negative or vice versa another definition would be finding the value text n for n that satisfies this equation n text n 0 in fp we can solve the above and negate a number by subtracting it from p division multiplicative inverse let s define division in fp around the concept that any non zero number divided by itself is 1 frac n n 1 or if we expand one of the terms n cdot frac 1 n 1 let s use a different notation for 1 n which is easier to fit on a line n cdot n text 1 1 in our fp multiplication it s possible for two positive integers to equal 1 when multiplied together it turns out that for each positive integer in fp there is one positive integer that acts as this multiplicative inverse solution to the equation above to tie it all together when working in fp any time we need to divide by a number n we will instead multiply by its multiplicative inverse n text 1 the number which satisfies the equation n cdot n text 1 1 the inverse for each number in f23 is provided in this table square root our last operation to define is square root we ll define the square root of n as a number in fp which satisfies this equation sqrt n cdot sqrt n n only half of the non zero members of fp have a solution to the square root equation they also have two solutions much like how real numbers have a positive and negative solution for square root members of our finite field have two square roots that are each the negation of the other the solutions for f23 are provided in this table elliptic curves and finite fields now we can combine the two concepts of elliptic curves and finite field math let s start with an elliptic curve equation y 2 x 3 9x 1 for our finite field let s use the prime number 61 mathbb f _61 0 1 2 60 the tables for division and square roots in f61 are pre computed for convenience what would it look like to plot the curve above using the math of a finite field f61 on a graph starting with x 0 and working through each number from 0 to 60 using the math operations we defined above x 0 y 2 0 3 9 cdot0 1 1 mod 61 1 y sqrt 1 1 and 60 x 1 y 2 1 3 9 cdot1 1 11 mod 61 11 y sqrt 11 undefined x 2 y 2 2 3 9 cdot2 1 27 mod 61 27 y sqrt 27 24 and 37 x 3 y 2 3 3 9 cdot3 1 55 mod 61 55 y sqrt 55 undefined x 4 y 2 4 3 9 cdot4 1 101 mod 61 40 y sqrt 40 undefined x 5 y 2 5 3 9 cdot5 1 171 mod 61 49 y sqrt 49 7 and 54 and so on the resulting graph looks like this our elliptic curve plotted in fp finally we ll nominate one of the points on this curve to be the base point p 5 7 the point chosen is somewhat arbitrary but some points are better than others this point was chosen because it can be added to itself see below a relatively large number of times before it comes back to itself specifically it repeats every 73 point additions let s give a name to the combination of above definitions the curve equation the prime number for the finite field and the base point we ll call it curve61 point addition we can still add points on this curve using the math of f61 and the rules of point addition draw lines between two points find the curve intersection then negate the point s y value curve61 point addition this animation shows finite field math wrapping from 61 to 0 sometimes many times before intersection with a curve point finding the values algebraically is relatively easy just remember to use the rules of finite field math for these formulas to add two points p x_1 y_1 and q x_2 y_2 to get a third point r x_3 y_3 lambda frac y_2 y_1 x_2 x_1 x_3 lambda 2 x_1 x_2 y_3 lambda x_1 x_3 y_1 if p and q are the same point then adding them is called doubling the point the formula for this is the same but the slope lambda is the curve tangent lambda frac 3x_1 2 9 2y_1 efficient point multiplication the point at 100p is the point p added to itself 100 times it can also be thought of as the point being multiplied by the number 100 you ll see this referred to as scalar multiplication and it s just another way to refer to repeated point addition we can get to arbitrarily large multiplication of p quickly using a double and add method repeatedly double p to get 2p 4p 8p 16p 32p add combinations of the above points to get any needed multiple of p double and add method for point np key exchange now we have enough to start doing cryptographic work we re going to do a key exchange with curve61 much in the same way that tls 1 3 does a key exchange with curve25519 alice and bob want to start a private conversation to do this they re going to agree on a number without any eavesdroppers being able to tell what the number is with an agreed upon number they can derive a key for one of the many fast and secure ciphers such as aes and encrypt their conversation the process looks like this alice and bob agree to use curve61 described in the section above alice picks a random number k_a alice computes the coordinates of k_ a p and sends it to bob as a bob picks a random number k_b bob computes the coordinates of k_ b p and sends it to alice as b alice computes the coordinates of k_ a b which is k_ a k_ b p bob computes the coordinates of k_ b a which is k_ b k_ a p because point addition on curve61 is associative both k_b k_ap and k_a k_bp are the same point they re just the base point added to itself k_a times k_b times since they re the same point both alice and bob have agreed on the same number the coordinates of k_ak_bp enter numbers for bob and alice s private keys below and watch a key exchange occur k a k b go random alice bob the real curve we ve played around with a toy curve of 72 points and you ve seen what it means to add points or perform a key exchange but how does this compare to real curves used in real cryptography such as tls 1 3 the most common curve used for key exchange is curve25519 that curve has a simple equation y 2 x 3 486662x 2 x where our toy curve used f61 a field with 61 numbers in it curve25519 uses mathbb f _ 2 255 text 19 the prime number used for that field 2 255 19 is a very large 77 digit number other than the size the field looks the same as the one we ve been using mathbb f _ 2 255 text 19 0 1 2 2 255 20 where our toy curve used a base point that can only be added to itself 73 times before repeating curve25519 uses a base point that can be added to itself over 2 252 times before repeating when peers use curve25519 to perform key exchange they select a random 256 bit number though 5 of those bits are then overridden see my x25519 site for more details that s 2 251 possible point multiplications for an attacker to guess at which is a very large 76 digit number we can add and double points on curve25519 in much the same way that we did on curve61 though the formula changes due to the different curve equation see wikipedia for details using point addition we can perform a key exchange in the same way that we did with our toy curve for in depth information on curve25519 including the choice of curve equation the choice of prime number used for fp and the exact details of key exchange i can recommend the author s paper and also this technical analysis most of these details are streamlining of the concepts listed on this page to keep the exchange mechanism secure and performant and should not fundamentally conflict with what s explained here the code for this project can be found on github