# here be dragons from manim import * import math import numpy as np config["background_color"] = "#301934" def point_addition(p, q): m = (q[1] - p[1]) / (q[0] - p[0]) xr = m * m - p[0] - q[0] yr = m * (p[0] - xr) - p[1] return np.array([xr, yr, 0]) def get_y_pos(x): return np.sqrt(x**3 - x + 1) def get_y_neg(x): return -np.sqrt(x**3 - x + 1) def update_r(p2, p0x, get_point): p2.move_to(get_point(point_addition([p0x, get_y_pos(p0x)], [0.4, 0.8149])[0])) def get_qubits(x: int) -> int: return 9 * x + math.ceil(math.log2(x)) + 10 class CurveGraph(Scene): def construct(self): ax = Axes( x_range=[-3, 3, 1], y_range=([-3, 3, 1]), axis_config={"include_numbers": False}, tips=False, color=BLACK, fill_color=BLACK, stroke_color=BLACK, ).to_edge(DOWN) posgraph = ax.plot( lambda x: get_y_pos(x), x_range=[-1.3244, 3], use_smoothing=True, discontinuities=[-1.325, -0.577, 0, 0.577], dt=0.001, color=YELLOW, fill_color=YELLOW, ) neggraph = ax.plot( lambda x: get_y_neg(x), x_range=[-1.3244, 3], use_smoothing=True, discontinuities=[-1.325, -0.577, 0, 0.577], dt=0.001, color=YELLOW, fill_color=YELLOW, ) title = Tex(r"Graph of $y^2 = x^3 - x + 1$", color=WHITE, font_size=54) title.to_edge(UP) dot_discontinuity = Dot( (ax.coords_to_point(-1.325, 0)), stroke_color=YELLOW, fill_opacity=0.0, stroke_width=3.0, ) self.wait(3) self.play(Create(ax, lag_ratio=0.01, run_time=1)) self.play(FadeIn(title, shift=DOWN), run_time=0.9) self.wait(8) self.play(Create(posgraph), Create(neggraph)) self.play(Create(dot_discontinuity, run_time=0.5)) self.wait(39) dotr = 0.06 p0start = -1.22 p0tracker = ValueTracker(p0start) p0 = Dot(posgraph.get_point_from_function(p0start), color=RED, radius=dotr) p0.add_updater( lambda m: m.move_to(posgraph.get_point_from_function(p0tracker.get_value())) ) p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) negP = Dot(neggraph.get_point_from_function(p0start), radius=dotr) p0.z_index = 2 p1.z_index = 2 p2.z_index = 2 negP.z_index = 2 line = Line(p0, p1) line.set_length(20) labelP = MathTex("P", color=WHITE).next_to(p0, UP) labelQ = MathTex("Q", color=WHITE).next_to(p1, UP) labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) labelNegP = MathTex("-P", color=WHITE).next_to(negP, DOWN) identity = Tex( r"Definition: $P + \mathcal{O} = P$ \\That is, $\mathcal{O}$ is the identity element.", font_size=42, ).to_edge(UP) addition = Tex(r"Definition: $P + Q + R = \mathcal{O}$", font_size=48).to_edge( UP ) addition_r = Tex(r"Definition: $P + Q + = -R$", font_size=48).to_edge(UP) negation = Tex( r"Definition: $(-P)$ is defined to be $P$, \\but symmetric over the $x$-axis", font_size=42, ).to_edge(UP) inverse = Tex( r"From the definition of negation, \\we can say that $P + (-P) = \mathcal{O}$", font_size=42, ).to_edge(UP) approaches = Tex( r"As $P$ approaches $Q$, they form a tangent line.", font_size=44 ).to_edge(UP) app = Tex( r"As $P$ approaches $Q$, \\then $P + Q$ becomes the same as $\underbrace{P + P}_{2P}$.", font_size=44, ).to_edge(UP) self.play( Create(p0), Create(p1), Create(p2), Write(labelP), Write(labelQ), Write(labelR), ) self.play(FadeTransform(title, identity)) self.wait(6) self.play(Write(line), run_time=1.5) self.play(FadeTransform(identity, addition)) self.wait(12) self.play(FadeTransform(addition, addition_r)) self.wait(14) self.play(Write(labelNegP), Uncreate(labelQ), Uncreate(labelR), FadeOut(line)) self.play(Uncreate(p1), Uncreate(p2), Create(negP)) P_to_negP = Line(p0, negP) extended_P_to_negP = P_to_negP.copy().set_length(5) self.play(Create(P_to_negP), FadeTransform(addition_r, negation)) self.wait(1) self.play(Flash(p0, color=YELLOW), Flash(negP, color=YELLOW)) self.wait(3) self.play( Transform(P_to_negP, extended_P_to_negP), Uncreate(labelP), Uncreate(labelNegP), FadeTransform(negation, inverse), ) p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) p2.add_updater( lambda m: update_r( m, p0tracker.get_value(), posgraph.get_point_from_function ) ) line2 = Line(p0, p1) line2.set_length(20) line2.add_updater( lambda m: ( m.set_points_by_ends(p0.get_center(), p1.get_center()), m.set_length(20), ) ) p1.z_index = 2 p2.z_index = 2 self.wait(8) self.play( Create(p1), Create(p2), # Write(line), FadeTransform(inverse, approaches), ) self.play(Uncreate(negP), FadeOut(P_to_negP), run_time=1) self.play(Write(line2)) self.wait(1) self.play(p0tracker.animate.set_value(0.399), run_time=6) self.wait(4) label2P = MathTex("2P", color=WHITE).next_to(p0, UP) labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) self.play( FadeTransform(approaches, app), Write(label2P), Write(labelR), ) graph = Group( ax, dot_discontinuity, p0, p1, p2, posgraph, neggraph, ) # transformedGraph = graph.copy().scale(0.25).to_edge(DR) self.wait(5) self.play(Uncreate(label2P), Uncreate(labelR)) self.play(FadeOut(line2), FadeOut(app, shift=UP)) self.wait(0.5) # self.play(Transform(graph, transformedGraph)) self.play(FadeOut(*graph)) self.wait(2) equations = Tex( r"Let's take a look at the equations we're going to use now." ).to_edge(UP) slope = Tex( r"We can calculate the slope of $P$ and $Q$ with\\$m = \frac{Q_y - P_y}{Q_x - P_x}$" ).next_to(equations, DOWN * 2) coordinatesR = Tex( r"And then we can calculate the coordinates of $R = P + Q$ with\\$R_x = m^2 - P_x - Q_x$\\$R_y = P_y + m(R_x - P_x)$" ).next_to(slope, DOWN * 2) if_p_equals_q = Tex(r"If $P = Q$, then").next_to(coordinatesR, DOWN) derivative = MathTex( r"\frac{\frac{d}{dx} (x^3 + ax + b)}{\frac{d}{dy} (y^2)}", font_size=40 ).next_to(if_p_equals_q, DOWN) new_slope = MathTex(r"\frac{3x^2 + a}{2y}", font_size=40).move_to(derivative) self.play(FadeIn(equations, shift=DOWN)) self.wait(2) self.play(Write(slope)) self.wait(4) self.play(Write(coordinatesR)) self.wait(5) self.play(Write(if_p_equals_q)) self.wait(0.5) self.play(Write(derivative)) self.wait(3) self.play(Transform(derivative, new_slope)) self.wait(10) self.play(FadeOut(*self.mobjects)) self.wait(16) class ModularArithmetic(Scene): def construct(self): circle = Circle(radius=3, color=BLUE_B) invisible_circle = ( Circle().set_stroke(GRAY, opacity=0).surround(circle, buffer_factor=0.6) ) center = Dot(circle.get_center(), color=WHITE, radius=0.1) self.wait(20) self.play(Create(circle), Create(invisible_circle), Create(center)) numbers_clock = VGroup() for (i, angle) in enumerate(reversed(range(90, 360 + 90, 30))): point = invisible_circle.point_at_angle((angle % 360) * DEGREES) text = Text(str(i + 1), font_size=24).move_to(point) numbers_clock += text self.play(Write(numbers_clock)) twelve = invisible_circle.point_at_angle(PI / 2) - np.array([0, 0.5, 0]) pointer = Line(center, twelve) self.play(Create(pointer)) self.wait(2) # Rotate to 14 h fourteen = MathTex( r"14 \equiv 2 \: (\textrm{mod} \, 12)", font_size=40 ).to_edge(UP) self.play(Write(fourteen)) self.play( Rotate(pointer, angle=(-2 * PI - PI / 3), about_point=ORIGIN), run_time=4 ) self.wait(3) self.play(Uncreate(fourteen)) self.wait(0.5) # Reset to 12 self.play(Rotate(pointer, angle=PI / 3, about_point=ORIGIN), run_time=1) self.wait(4.5) # Rotate to 11 h eleven = MathTex(r"-1 \equiv 11 \: (\textrm{mod} \, 12)", font_size=40).to_edge( UP ) self.play(Write(eleven)) self.play(Rotate(pointer, angle=PI / 6, about_point=ORIGIN)) self.wait(14) # Reset self.play( Uncreate(eleven), Uncreate(center), Uncreate(pointer), Uncreate(numbers_clock), Uncreate(circle), run_time=1, ) self.wait(14) mod_4 = Tex( r"$2 \cdot k \equiv 1 \: (\textrm{mod} \, 4)$ \\ $k \, \text{doesn't exist} \, (\nexists)$" ) self.play(Write(mod_4)) self.wait(12) self.play(FadeOut(mod_4)) self.wait() title_mod = Tex( r"List of multiplicative inverses in $n \: (\textrm{mod} \, 8)$" ).to_edge(UP) table = ( MobjectTable( [ [MathTex("1"), MathTex(r"1 \cdot 1 = 1 \equiv 1")], [MathTex("2"), MathTex(r"\nexists")], [MathTex("3"), MathTex(r"3 \cdot 3 = 9 \equiv 1")], [MathTex("4"), MathTex(r"\nexists")], [MathTex("5"), MathTex(r"5 \cdot 5 = 25 \equiv 1")], [MathTex("6"), MathTex(r"\nexists")], [MathTex("7"), MathTex(r"7 \cdot 7 = 49 \equiv 1")], ], col_labels=[MathTex("n"), MathTex("n^{-1}")], ) .scale(0.6) .to_edge(DOWN) ) cells = VGroup( table.get_cell((3, 1), color=RED_B), table.get_cell((3, 2), color=RED_B), table.get_cell((5, 1), color=RED_B), table.get_cell((5, 2), color=RED_B), table.get_cell((7, 1), color=RED_B), table.get_cell((7, 2), color=RED_B), ) self.play(table.create(), Write(title_mod)) self.wait(4) self.play(Create(cells), run_time=2.5) # for cell in cells: # self.play(Create(cell), run_time=0.75) self.wait(6) # for cell in cells: # self.play(Uncreate(cell), run_time=0.25) self.play(Uncreate(cells), run_time=2.5) self.wait() self.play(Uncreate(table), Uncreate(title_mod), run_time=2.5) self.wait() fraction = MathTex(r"\frac{3}{4}", r"\: (\textrm{mod} \, 5)") inverse = MathTex(r"3 \cdot ", r"4^{-1}", r"\: (\textrm{mod} \, 5)") result = MathTex(r"3 \cdot ", r"4", r" \equiv 2", r"\: (\textrm{mod} \, 5)") self.play(FadeIn(fraction, shift=UP)) self.wait(9) self.play(TransformMatchingTex(fraction, inverse)) self.wait(15) self.play(TransformMatchingTex(inverse, result)) self.wait(17) field = MathTex(r"\mathbb{F}_p").next_to(result, DOWN * 1.5) self.play(Write(field)) self.wait(5) self.play(Uncreate(field), Uncreate(result)) CHR = 31 def extended_euclidean_algorithm(a, b): s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = b, a while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t return old_r, old_s, old_t def inverse_of(n, p): gcd, x, y = extended_euclidean_algorithm(n, p) assert (n * x + p * y) % p == gcd if gcd != 1: # Either n is 0, or p is not a prime number. raise ValueError("{} has no multiplicative inverse " "modulo {}".format(n, p)) else: return x % p def get_y_pos(x): return np.sqrt(x**3 - x + 1) def get_y_field(x): square = (x**3 - x + 1) % CHR inverse = inverse_of(x, CHR) return (square * inverse) % CHR X_LIMIT = CHR X_RANGE = np.int32(get_y_pos(X_LIMIT)) class EllipticFiniteField(Scene): def construct(self): ax = Axes( x_range=[-1, X_LIMIT, 1], y_range=([-1, X_RANGE, 1]), axis_config={"include_numbers": False, "include_ticks": False}, tips=False, color=BLACK, fill_color=BLACK, stroke_color=BLACK, ).to_edge(DOWN) ax2 = Axes( x_range=[-1, CHR - 1, 1], y_range=[-1, CHR - 1, 1], axis_config={"include_numbers": False}, tips=False, color=BLACK, fill_color=BLACK, stroke_color=BLACK, ).to_edge(DOWN) posgraph = ax.plot( lambda x: get_y_pos(x), x_range=[-1.3244, X_LIMIT], use_smoothing=True, discontinuities=[-1.325, -0.577, 0, 0.577], dt=0.001, color=YELLOW, fill_color=YELLOW, ) title = MathTex(r"y^2 = x^3 - x + 1", font_size=44).to_edge(UP) title_field = MathTex( r"y^2 = x^3 - x + 1", r"\: (\textrm{mod} \, %d)" % CHR, font_size=44 ).to_edge(UP) title_fieldpm = MathTex( r"y = \pm\sqrt{x^3 - x + 1}", r"\: (\textrm{mod} \, %d)" % CHR, font_size=44 ).to_edge(UP) dots = [] field_dots = [] field_neg = [] for i in range(1, X_LIMIT): dots.append(Dot(posgraph.get_point_from_function(i), color=ORANGE)) field_dots.append(get_y_field(i)) field_neg.append(-get_y_field(i) % CHR) dots = VGroup(*dots) field_dots = ax2.plot_line_graph(range(1, CHR), field_dots).set_color(ORANGE) field_neg = ax2.plot_line_graph(range(1, CHR), field_neg).set_color(YELLOW) self.play(Create(ax, lag_ratio=0.01, run_time=1)) self.play(Create(posgraph), Create(dots), run_time=2) self.play(Write(title)) self.wait(2) self.play(Transform(ax, ax2, replace_mobject_with_target_in_scene=True)) self.play(FadeOut(posgraph)) self.wait(1) self.play(TransformMatchingTex(title, title_field)) self.wait(1) self.play( Transform( dots, field_dots["vertex_dots"], replace_mobject_with_target_in_scene=True, ), Create(field_neg["vertex_dots"]), ) self.wait(31.5) linep2 = Line( ax2.coords_to_point(0, CHR / 2, 0), ax2.coords_to_point(CHR, CHR / 2, 0), color=WHITE, ) self.play(Create(linep2)) self.wait(5) upper_rect = Polygon( ax2.coords_to_point(0, 0, 0), ax2.coords_to_point(0, CHR / 2, 0), ax2.coords_to_point(CHR, CHR / 2, 0), ax2.coords_to_point(CHR, 0, 0), color=MAROON_B, fill_color=MAROON_B, fill_opacity=0.8, ) lower_rect = Polygon( ax2.coords_to_point(0, CHR / 2, 0), ax2.coords_to_point(CHR, CHR / 2, 0), ax2.coords_to_point(CHR, CHR, 0), ax2.coords_to_point(0, CHR, 0), color=MAROON_B, fill_color=MAROON_B, fill_opacity=0.8, ) self.play(FadeOut(lower_rect), run_time=1.5) self.wait(1) self.play(FadeOut(upper_rect), run_time=1.5) self.wait(4) self.play(Uncreate(linep2)) self.wait(5) graph = VGroup(ax2, field_dots["vertex_dots"], field_neg["vertex_dots"]) # transformedGraph = graph.copy().scale(0.25).to_edge(DR) self.play(TransformMatchingTex(title_field, title_fieldpm)) self.wait(15) self.play(FadeOut(title_fieldpm, shift=UP)) # self.play(Transform(graph, transformedGraph, replace_mobject_with_target_in_scene=True)) self.wait(14) ref_group_law = Tex( r"[1] An elementary proof of the group law for elliptic curves \\Friedl, Stefan\\ October 2017", font_size=24, ).to_edge(UR) self.play(FadeIn(ref_group_law, shift=LEFT)) self.wait(10) self.play(FadeOut(ref_group_law, shift=RIGHT)) self.wait(43) self.play(FadeOut(graph), run_time=2) self.wait() mult_of_p = MathTex( r"P &= (52, 14) \: (\textrm{mod} \, 61)", r"2P &= (4, 0)", r"3P &= (52, 47)", r"4P &= \mathcal{O}", r"5P &= (52, 14)", r"6P &= (4, 0)", r"&\;\;\vdots", arg_separator=r" \\", ) suborder = Tex(r"Order of P \\(or of the subgroup of P) = 4", font_size=36) curveorder = MathTex( r"&\text{Order of the curve} \\", "[", r"E: x^3 &- x + 1 \: (\textrm{mod} \, 61)", "]", "= 64", font_size=36, ).next_to(suborder, DOWN * 1.5) ref_schoofs = Tex( r"[2] Schoof's Algorithm for Counting Points on $E(\mathbb{F}_{k})$ \\Musiker, Gregg \\December 2005", font_size=24, ).to_edge(UR) orders = VGroup(suborder, curveorder).arrange(DOWN, buff=0.8).to_edge(RIGHT * 2) surr_rect = SurroundingRectangle(orders, color=RED_A, buff=0.4) p1 = ( mult_of_p.get_part_by_tex(r"P &= (52, 14)").get_edge_center(LEFT) + UP * 0.25 ) p5 = mult_of_p.get_part_by_tex(r"5P &= (52, 14)").get_edge_center( LEFT ) + np.array([-0.22, 0.88, 0]) self.play(Write(mult_of_p), run_time=4) self.wait(11) arrow = CurvedArrow(p5, p1, angle=-TAU / 4, color=RED_B) self.play(Create(arrow)) self.wait(24) self.play(Create(surr_rect), Write(orders)) self.wait(25) self.play(FadeIn(ref_schoofs, shift=LEFT)) self.wait(6) self.play(FadeOut(ref_schoofs, shift=RIGHT)) self.wait() all_mobjs = VGroup(orders, surr_rect, arrow, mult_of_p) self.play(FadeOut(all_mobjs)) class EllipticMultiplication(Scene): def construct(self): discrete_log = Tex("For $Q = nP$, given P and Q, find n") self.play(Write(discrete_log)) dlp = Text("The Discrete Logarithm Problem (DLP)").next_to( discrete_log, UP * 1.2 ) self.wait(10) self.play(FadeIn(dlp, shift=DOWN)) # self.play(FadeOut(dlp, shift=UP)) # self.play(FadeOut(discrete_log, shift=UP)) desirable = Text("Actually a desirable property!", font_size=36).next_to( discrete_log, DOWN * 1.2 ) self.wait(41) self.play(FadeIn(desirable, shift=UP)) self.wait(10) self.play(FadeOut(desirable, shift=DOWN)) factors = MathTex( r"\text{Factors of } 210 \Rightarrow 2 \cdot 3 \cdot 5 \cdot 7" ).next_to(discrete_log, DOWN * 1.2) self.play(FadeIn(factors, shift=UP)) self.wait(10) self.play(FadeOut(factors, shift=DOWN)) self.wait(23) iverunoutofnames = Tex( r"Computing $Q = nP$ knowing n and P is trivial, \\ while the DLP remains hard \\ (A trapdoor function!)", font_size=42, ).next_to(discrete_log, DOWN * 1.2) self.play(Write(iverunoutofnames)) self.wait(22) self.play(FadeOut(VGroup(iverunoutofnames, dlp, discrete_log))) self.wait(11) class BobAndGoogle(Scene): def construct(self): template = TexTemplate(preamble=r"\usepackage{hyperref}") bob = Text("Bob", font_size=34).to_edge(LEFT) google = Text( "Google", t2c={ "[:1]": "#3174f0", "[1:2]": "#e53125", "[2:3]": "#fbb003", "[3:4]": "#3174f0", "[4:5]": "#269a43", "[5:]": "#e53125", }, font_size=34, ).to_edge(RIGHT) self.play(Write(bob), Write(google)) self.wait(14) params = MathTex( r"\text{\Large{P-256}} \\ p &= \mathrm{0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff} \\ a &= \mathrm{0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc} \\ b &= \mathrm{0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b}", font_size=23, ).to_edge(UP * 3.5) paramsrect = SurroundingRectangle( params, color=RED_A, buff=0.3, fill_color=GRAY_A, fill_opacity=0.25 ) params_top = params.copy().to_edge(UP) params_rect_top = SurroundingRectangle( params_top, color=RED_A, buff=0.3, fill_color=GRAY_A, fill_opacity=0.25 ) ref_params = Tex( r"[3] OpenSSL Curve Definitions \\ \url{https://github.com/openssl/openssl/}", font_size=24, tex_template=template, ).to_edge(UR) self.play(Create(paramsrect), Write(params)) self.wait() self.play(FadeIn(ref_params, shift=LEFT)) self.wait(3) self.play(FadeOut(ref_params, shift=RIGHT)) self.play(Transform(paramsrect, params_rect_top), Transform(params, params_top)) random_number = Text(r"priv = rand(1, subgroup_order)", font_size=30) priv_bob = MathTex(r"\text{priv}_{\text{Bob}}", font_size=33).next_to( ORIGIN, LEFT ) priv_gogl = MathTex(r"\text{priv}_{\text{Google}}", font_size=33).next_to( ORIGIN, RIGHT ) self.play(Write(random_number)) self.wait(3) self.play(ShrinkToCenter(random_number)) self.play(GrowFromCenter(priv_bob), GrowFromCenter(priv_gogl)) self.wait(10) trans_priv_bob = priv_bob.copy().next_to(bob, DOWN) trans_priv_gogl = priv_gogl.copy().next_to(google, DOWN) self.play(Transform(priv_bob, trans_priv_bob)) self.play(Transform(priv_gogl, trans_priv_gogl)) self.wait(3) base_point = MathTex(r"\text{Base point: }", r"(x, y)") gen_point = MathTex(r"G = ", r"(x, y)") self.play(FadeIn(base_point, target_position=params.get_edge_center(DOWN))) self.wait(2) self.play(TransformMatchingTex(base_point, gen_point)) self.wait(1) gen_bob = MathTex(r"G = (x, y)").next_to(priv_bob, RIGHT * 0.05) gen_bob.font_size = 33 gen_gogl = MathTex(r"G = (x, y)").next_to(priv_gogl, LEFT * 0.05) gen_gogl.font_size = 33 priv_bob_with_gen = ( MathTex(r"\text{priv}_\text{Bob} \cdot ", r"G = (x, y)", font_size=33) .to_edge(LEFT) .shift(DOWN * 0.7) ) priv_gogl_with_gen = ( MathTex(r"G = (x, y)", r"\cdot \text{priv}_\text{Google}", font_size=33) .to_edge(RIGHT) .shift(DOWN * 0.7) ) self.play(FadeOut(priv_bob)) self.play( Transform( gen_point.copy(), priv_bob_with_gen, replace_mobject_with_target_in_scene=True, ), ) self.wait() self.play(FadeOut(priv_gogl)) self.play( Transform( gen_point, priv_gogl_with_gen, replace_mobject_with_target_in_scene=True ) ) self.wait() pub_bob = MathTex( r"\text{pub}_\text{Bob}", font_size=33, ).next_to(bob, DOWN) pub_gogl = MathTex(r"\text{pub}_{\text{Google}}", font_size=33).next_to( google, DOWN ) # self.play(ShrinkToCenter(gen_bob), ShrinkToCenter(priv_bob)) self.play(ShrinkToCenter(priv_bob_with_gen)) self.play(GrowFromCenter(pub_bob)) self.wait(1) # self.play(ShrinkToCenter(gen_gogl), ShrinkToCenter(priv_gogl)) self.play(ShrinkToCenter(priv_gogl_with_gen)) self.play(GrowFromCenter(pub_gogl)) self.wait(1.5) new_pub_gogl = pub_gogl.copy().next_to(bob, DOWN) new_pub_bob = pub_bob.copy().next_to(google, DOWN) self.play( Transform(pub_gogl, new_pub_gogl, path_arc=PI / 4), Transform(pub_bob, new_pub_bob, path_arc=-PI / 4), run_time=3, ) self.wait(4) self.play(Indicate(pub_gogl), Indicate(pub_bob), run_time=1.5) self.wait(24) shared_secret = MathTex( r"\text{Shared Secret}", r"&= \\ (S_x, S_y)", r"&= \\ \text{pub}_\text{Bob}", r"\cdot \text{priv}_\text{Google} &= \\", r"\text{pub}_\text{Google}", r"\cdot \text{priv}_\text{Bob}", font_size=33, organize_left_to_right=True, ) self.play( Transform( VGroup(pub_gogl, pub_bob), shared_secret, replace_mobject_with_target_in_scene=True, ) ) self.wait(52) process_secret = MathTex( r"\text{Shared Secret}", r"= (S_x, S_y)", r"\Rightarrow \text{Cipher}" ) p0 = bob.get_right() p1 = google.get_left() darrow = DoubleArrow(p0, p1, buff=1.5).next_to(process_secret, DOWN * 1.5) darrow_text = Tex( r"Encrypted data \\ (secure, even through an insecure channel!)", font_size=36, ).next_to(darrow, DOWN) self.play(TransformMatchingTex(shared_secret, process_secret)) self.wait() self.play(Create(darrow)) self.wait(1) self.play(Write(darrow_text), run_time=1.5) self.wait(32) self.play(FadeOut(*self.mobjects), run_time=3) self.wait(2) class RSAQubits(Scene): def construct(self): tablersa = Table( [ ["1024", "160"], ["2048", "224"], ["3072", "256"], ["7680", "384"], ["15360", "521"], ], col_labels=[Text("RSA"), Text("ECC")], ).scale(0.6) in_bits = Tex( r"Comparison of RSA and \\Elliptic Curves key sizes (in bits)", font_size=35 ) g = Group(tablersa, in_bits).arrange(DOWN, buff=0.6) tablequbits = Table( [ ["192", str(get_qubits(192))], ["256", str(get_qubits(256))], ["384", str(get_qubits(384))], ["512", str(get_qubits(512))], ], col_labels=[Text("Bits"), Text("Qubits")], ).scale(0.6) surr_rect = SurroundingRectangle( VGroup(in_bits, tablersa), color=RED_A, buff=0.5 ) self.play(Create(surr_rect), Create(tablersa), Write(in_bits), run_time=2.5) self.wait(75) self.play(Uncreate(surr_rect), Uncreate(tablersa), Uncreate(in_bits)) self.wait(3) self.play(Create(tablequbits)) self.wait(50) self.play(Uncreate(tablequbits)) self.wait(21.5) serge_lang = Tex( r"It is possible to write endlessly \\on elliptic curves. (This is not a threat.) \\ -- Serge Lang", font_size=42, ) self.play(Write(serge_lang)) self.wait(10) self.play(FadeOut(serge_lang)) self.wait(10) def get_y_neg(x): return -np.sqrt(x**3 - x + 1) def update_r(p2, p0x, get_point): p2.move_to(get_point(point_addition([p0x, get_y_pos(p0x)], [0.4, 0.8149])[0])) class CurveGraph(Scene): def construct(self): ax = Axes( x_range=[-3, 3, 1], y_range=([-3, 3, 1]), axis_config={"include_numbers": False}, tips=False, color=BLACK, fill_color=BLACK, stroke_color=BLACK, ).to_edge(DOWN) posgraph = ax.plot( lambda x: get_y_pos(x), x_range=[-1.3244, 3], use_smoothing=True, discontinuities=[-1.325, -0.577, 0, 0.577], dt=0.001, color=YELLOW, fill_color=YELLOW, ) neggraph = ax.plot( lambda x: get_y_neg(x), x_range=[-1.3244, 3], use_smoothing=True, discontinuities=[-1.325, -0.577, 0, 0.577], dt=0.001, color=YELLOW, fill_color=YELLOW, ) title = Tex(r"Graph of $y^2 = x^3 - x + 1$", color=WHITE, font_size=54) title.to_edge(UP) dot_discontinuity = Dot( (ax.coords_to_point(-1.325, 0)), stroke_color=YELLOW, fill_opacity=0.0, stroke_width=3.0, ) self.play(Create(ax, lag_ratio=0.01, run_time=1)) self.play(Create(posgraph), Create(neggraph)) self.play(Create(dot_discontinuity, run_time=0.5)) self.play(FadeIn(title, shift=DOWN), run_time=0.9) self.wait(5) dotr = 0.06 p0start = -1.22 p0tracker = ValueTracker(p0start) p0 = Dot(posgraph.get_point_from_function(p0start), color=RED, radius=dotr) p0.add_updater( lambda m: m.move_to(posgraph.get_point_from_function(p0tracker.get_value())) ) p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) negP = Dot(neggraph.get_point_from_function(p0start), radius=dotr) p0.z_index = 2 p1.z_index = 2 p2.z_index = 2 negP.z_index = 2 line = Line(p0, p1) line.set_length(20) labelP = MathTex("P", color=WHITE).next_to(p0, UP) labelQ = MathTex("Q", color=WHITE).next_to(p1, UP) labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) labelNegP = MathTex("-P", color=WHITE).next_to(negP, DOWN) identity = Tex( r"Definition: $P + \mathcal{O} = P$ \\That is, $\mathcal{O}$ is the identity element.", font_size=42, ).to_edge(UP) addition = Tex(r"Definition: $P + Q + R = \mathcal{O}$", font_size=48).to_edge( UP ) negation = Tex( r"Definition: $(-P)$ is defined to be $P$, \\but symmetric over the $x$-axis", font_size=42, ).to_edge(UP) inverse = Tex( r"From the definition of negation, \\we can say that $P + (-P) = \mathcal{O}$", font_size=42, ).to_edge(UP) approaches = Tex( r"As $P$ approaches $Q$, they form a tangent line.", font_size=44 ).to_edge(UP) app = Tex( r"As $P$ approaches $Q$, \\then $P + Q$ becomes the same as $2P$.", font_size=44, ).to_edge(UP) self.play( Create(p0), Create(p1), Create(p2), Write(labelP), Write(labelQ), Write(labelR), ) self.play(FadeTransform(title, identity)) self.wait(5) self.play(Write(line), run_time=1.5) self.play(FadeTransform(identity, addition)) self.wait(5) self.play(Write(labelNegP), Uncreate(labelQ), Uncreate(labelR), FadeOut(line)) self.play(Uncreate(p1), Uncreate(p2), Create(negP)) P_to_negP = Line(p0, negP) extended_P_to_negP = P_to_negP.copy().set_length(5) self.play(Create(P_to_negP), FadeTransform(addition, negation)) self.wait(5) self.play( Transform(P_to_negP, extended_P_to_negP), Uncreate(labelP), Uncreate(labelNegP), FadeTransform(negation, inverse), ) self.wait(5) p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) p2.add_updater( lambda m: update_r( m, p0tracker.get_value(), posgraph.get_point_from_function ) ) line2 = Line(p0, p1) line2.set_length(20) line2.add_updater( lambda m: ( m.set_points_by_ends(p0.get_center(), p1.get_center()), m.set_length(20), ) ) p1.z_index = 2 p2.z_index = 2 self.play( Create(p1), Create(p2), # Write(line), FadeTransform(inverse, approaches), ) self.wait(2) self.play(Uncreate(negP), FadeOut(P_to_negP), run_time=1) self.play(Write(line2)) self.wait(1) self.play(p0tracker.animate.set_value(0.399), run_time=6) self.wait() label2P = MathTex("2P", color=WHITE).next_to(p0, UP) labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) self.play( FadeTransform(approaches, app), Write(label2P), Write(labelR), ) graph = Group( ax, dot_discontinuity, p0, p1, p2, posgraph, neggraph, ) # transformedGraph = graph.copy().scale(0.25).to_edge(DR) self.wait(5) self.play(Uncreate(label2P), Uncreate(labelR)) self.play(FadeOut(line2), FadeOut(app, shift=UP)) self.wait(0.5) #self.play(Transform(graph, transformedGraph)) self.play(Uncreate(graph)) self.wait(1) equations = Tex( r"Let's take a look at the equations we're going to use now." ).to_edge(UP) slope = Tex( r"We can calculate the slope of $P$ and $Q$ with\\$m = \frac{Q_y - P_y}{Q_x - P_x}$" ).next_to(equations, DOWN * 2) coordinatesR = Tex( r"And then we can calculate the coordinates of $R = P + Q$ with\\$R_x = m^2 - P_x - Q_x$\\$R_y = P_y + m(R_x - P_x)$" ).next_to(slope, DOWN * 2) dotdotdot = Tex("...") if_p_equals_q = Tex(r"If $P = Q$, then").next_to(coordinatesR, UP) derivative = MathTex( r"\frac{\frac{d}{dx} (x^3 + ax + b)}{\frac{d}{dy} (y^2)}", font_size=60 ).next_to(if_p_equals_q, DOWN) new_slope = MathTex(r"\frac{3x^2 + a}{2y}", font_size=60).move_to(derivative) self.play(FadeIn(equations, shift=DOWN)) self.wait(2) self.play(Write(slope)) self.wait(4) self.play(FadeOut(equations), run_time=1) self.play(Write(coordinatesR)) self.wait(5) self.play(FadeOut(slope), FadeOut(coordinatesR)) self.wait(1) self.play(FadeIn(dotdotdot)) self.wait(3) self.play(FadeOut(dotdotdot)) self.wait(0.5) self.play(Write(if_p_equals_q)) self.wait(0.5) self.play(Write(derivative)) self.wait(3) self.play(Transform(derivative, new_slope)) self.wait(3) self.play(Uncreate(if_p_equals_q), Uncreate(new_slope)) self.wait(1) class ModularArithmetic(Scene): def construct(self): circle = Circle(radius = 3, color=BLUE_B) invisible_circle = Circle().set_stroke(GRAY, opacity=0).surround(circle, buffer_factor=0.6) center = Dot(circle.get_center(), color=WHITE, radius=0.1) self.add(circle, invisible_circle, center) numbers_clock = VGroup() for (i, angle) in enumerate(reversed(range(90, 360 + 90, 30))): point = invisible_circle.point_at_angle((angle % 360) * DEGREES) text = Text(str(i + 1), font_size=24).move_to(point) numbers_clock += text self.play(Write(numbers_clock)) twelve = invisible_circle.point_at_angle(PI/2) - np.array([0, 0.5, 0]) pointer = Line(center, twelve) self.play(Create(pointer)) self.wait() # Rotate to 14 h fourteen = MathTex(r"14 \equiv 2 (\textrm{mod} 12)").to_edge(UP) self.play(Write(fourteen)) self.play(Rotate(pointer, angle=(-2 * PI - PI/3), about_point=ORIGIN), run_time=4) self.wait(3) self.play(Uncreate(fourteen)) self.wait(0.5) # Reset to 12 self.play(Rotate(pointer, angle=PI/3, about_point=ORIGIN), run_time=1) self.wait(3) # Rotate to 11 h eleven = MathTex(r"-1 \equiv 11 (\textrm{mod} 12)").to_edge(UP) self.play(Write(eleven)) self.play(Rotate(pointer, angle=PI/6, about_point=ORIGIN)) self.wait(3) # Reset self.play(Uncreate(eleven), Uncreate(center), Uncreate(pointer), Uncreate(numbers_clock), Uncreate(circle), run_time=1) self.wait(3) title_mod = Tex(r"List of multiplicative inverses in $n$ (\textrm{mod} 8)").to_edge(UP) table = MobjectTable([ [MathTex("1"), MathTex(r"1 \cdot 1 = 1 \equiv 1")], [MathTex("2"), MathTex(r"\nexists")], [MathTex("3"), MathTex(r"3 \cdot 3 = 9 \equiv 1")], [MathTex("4"), MathTex(r"\nexists")], [MathTex("5"), MathTex(r"5 \cdot 5 = 25 \equiv 1")], [MathTex("6"), MathTex(r"\nexists")], [MathTex("7"), MathTex(r"7 \cdot 7 = 49 \equiv 1")], ], col_labels=[MathTex("n"), MathTex("n^{-1}")]).scale(0.6).to_edge(DOWN) cells = VGroup(table.get_cell((3, 1), color=RED_B), table.get_cell((3, 2), color=RED_B), table.get_cell((5, 1), color=RED_B), table.get_cell((5, 2), color=RED_B), table.get_cell((7, 1), color=RED_B), table.get_cell((7, 2), color=RED_B)) self.play(table.create(), Write(title_mod)) self.wait(4) self.play(Create(cells), run_time=2.5) # for cell in cells: # self.play(Create(cell), run_time=0.75) self.wait(4) # for cell in cells: # self.play(Uncreate(cell), run_time=0.25) self.play(Uncreate(cells), run_time=2.5) self.wait() self.play(Uncreate(table), Uncreate(title_mod), run_time=2.5) self.wait() fraction = MathTex(r"\frac{3}{4}", r"\: (\textrm{mod} \, 5)") inverse = MathTex(r"3 \cdot ", r"4^{-1}", r"\: (\textrm{mod} \, 5)") result = MathTex(r"3 \cdot ", r"4", r" \equiv 2", r"\: (\textrm{mod} \, 5)") self.play(FadeIn(fraction, shift=UP)) self.wait() self.play(TransformMatchingTex(fraction, inverse)) self.wait() self.play(TransformMatchingTex(inverse, result)) self.wait() field = MathTex(r"\mathbb{F}_p").next_to(result, DOWN * 1.5) self.play(Write(field)) self.wait(3) self.play(Uncreate(field), Uncreate(result)) CHR = 31 def extended_euclidean_algorithm(a, b): s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = b, a while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t return old_r, old_s, old_t def inverse_of(n, p): gcd, x, y = extended_euclidean_algorithm(n, p) assert (n * x + p * y) % p == gcd if gcd != 1: # Either n is 0, or p is not a prime number. raise ValueError( '{} has no multiplicative inverse ' 'modulo {}'.format(n, p)) else: return x % p def get_y_pos(x): return np.sqrt(x**3 - x + 1) def get_y_field(x): square = (x ** 3 - x + 1) % CHR inverse = inverse_of(x, CHR) return (square * inverse) % CHR X_LIMIT = CHR X_RANGE = np.int32(get_y_pos(X_LIMIT)) class EllipticFiniteField(Scene): def construct(self): ax = Axes( x_range=[-1, X_LIMIT, 1], y_range=([-1, X_RANGE, 1]), axis_config={"include_numbers": False, "include_ticks": False}, tips=False, color=BLACK, fill_color=BLACK, stroke_color=BLACK, ).to_edge(DOWN) ax2 = Axes( x_range=[-1, CHR-1, 1], y_range=[-1, CHR-1, 1], axis_config={"include_numbers": False}, tips=False, color=BLACK, fill_color=BLACK, stroke_color=BLACK ).to_edge(DOWN) posgraph = ax.plot( lambda x: get_y_pos(x), x_range=[-1.3244, X_LIMIT], use_smoothing=True, discontinuities=[-1.325, -0.577, 0, 0.577], dt=0.001, color=YELLOW, fill_color=YELLOW, ) # title_pedantic = Tex("$\{(x, y) \\in \\mathbb{R} | y^2 = x^3 - x + 1$\}", font_size=32).to_edge(UP) # title_field_pedantic = Tex("$\{(x, y) \\in (\\mathbb{F}_{%d})^2 | y^2 = x^3 - x + 1 (\\mod %d)\}$" # % (CHR, CHR), # font_size=32).to_edge(UP) title = MathTex(r"y^2 = x^3 - x + 1", font_size=44).to_edge(UP) title_field = MathTex(r"y^2 = x^3 - x + 1", r"\: (\textrm{mod} \, %d)" % CHR, font_size=44).to_edge(UP) dots = [] field_dots = [] field_neg = [] for i in range(1, X_LIMIT): dots.append(Dot(posgraph.get_point_from_function(i), color=ORANGE)) field_dots.append(get_y_field(i)) field_neg.append(-get_y_field(i) % CHR) dots = VGroup(*dots) field_dots = ax2.plot_line_graph(range(1, CHR), field_dots).set_color(ORANGE) field_neg = ax2.plot_line_graph(range(1, CHR), field_neg).set_color(YELLOW) self.play(Create(ax, lag_ratio=0.01, run_time=1)) self.play(Create(posgraph), Create(dots), run_time=2) self.play(Write(title)) self.wait(1) self.play(Transform(ax, ax2, replace_mobject_with_target_in_scene=True)) self.play(FadeOut(posgraph)) self.wait(1) self.play(TransformMatchingTex(title, title_field)) self.wait(1) self.play(Transform(dots, field_dots["vertex_dots"], replace_mobject_with_target_in_scene=True), Create(field_neg["vertex_dots"])) self.wait(2) linep2 = Line(ax2.coords_to_point(0, CHR / 2, 0), ax2.coords_to_point(CHR, CHR / 2, 0), color=WHITE) self.play(Create(linep2)) self.wait(2) upper_rect = Polygon( ax2.coords_to_point(0, 0, 0), ax2.coords_to_point(0, CHR / 2, 0), ax2.coords_to_point(CHR, CHR / 2, 0), ax2.coords_to_point(CHR, 0, 0), color=MAROON_B, fill_color=MAROON_B, fill_opacity=0.8) lower_rect = Polygon( ax2.coords_to_point(0, CHR / 2, 0), ax2.coords_to_point(CHR, CHR / 2, 0), ax2.coords_to_point(CHR, CHR, 0), ax2.coords_to_point(0, CHR, 0), color=MAROON_B, fill_color=MAROON_B, fill_opacity=0.8) self.play(FadeOut(lower_rect), run_time=1.5) self.wait(1) self.play(FadeOut(upper_rect), run_time=1.5) self.wait(1) self.play(Uncreate(linep2)) self.wait(5) graph = Group( ax2, field_dots["vertex_dots"], field_neg["vertex_dots"] ) # transformedGraph = graph.copy().scale(0.25).to_edge(DR) self.play(Uncreate(title_field)) # self.play(Transform(graph, transformedGraph, replace_mobject_with_target_in_scene=True)) self.wait(3) ref_group_law = Tex(r"[1] An elementary proof of the group law for elliptic curves \\Friedl, Stefan\\ October 2017", font_size=24).to_edge(UR) self.play(FadeIn(ref_group_law, shift=LEFT)) self.wait(3) self.play(FadeOut(ref_group_law, shift=RIGHT)) self.wait() self.play(Uncreate(graph)) self.wait() mult_of_p = MathTex(r"P = 30 \\ 2P = 312, \\ 3P = 3123")