Table of contents:

1. 1. Introduction
2. 2. Middle Part
3. 3. Conclusion

Introduction

Elliptic Curves are at the base of all of our security protocols. They are used to exchange secret keys with other users through fully surveilled channels of communication. Each elliptic curve is based on a very large prime-number that gives it its name. The most well known and widely adopted elliptic curve is named Curve25519.

Here you can see a list of safe elliptic curves: https://safecurves.cr.yp.to

As you can see, several elliptic curves that are in use, are listed as ‘not secure’. For example, the most popular “cryptography” package for flutter:

https://pub.dev/documentation/cryptography/latest/cryptography/Ecdh-class.html

contains only insecure elliptic curves, namely p256, p384 and p521.

In this article we will explore why this is the case.

I am Malte, a software developer who likes encryption, distributed systems and software architecture. Today we will explore how two parties can communicate in a secure way even though somebody can catch every message they exchange. You will learn why the United States leads a war on numbers and how you can implement elliptic curves. And we will not be shy to go indepth.

But the question of encryption bears with it a moral question; Is it right for gangsters to communicate in a secure way? What if people use encrypted communication channels to plan bad things or exchange bad images? Platforms like Encrochat and Silk Road used encryption do boost criminality.

On the other hand, there are unique dangers to banning encryption on a state level.

The flow of information creates social systems. If you can control what spreads, you can control what people think on a large scale. Certainly in the limit, if you have a monopoly on information. If you want examples where the flow of information was fully in the hands of the state, look no further than Nazi Germany, North Korea, Soviet Union under Stalin, Maoist China or the medieval Catholic Church’s. Imagine a modern Nazi Regime with AI and digital surveillance. Then thank god that it is not real.

Thus, a free society is based on a free flow of information. This part of the expressed intent of constitutions of western democracies.

Free flow of information has two aspects: Free speech that is meant to be public, as well as free speech that is meant to be private. In this article, we will focus on the private aspects of free speech. For private free speech it is important that people can share what they truly think with their innermost circle without fear of state level repercussions because of bad thought.

Mass surveillance, which, to some degree, undermines free speech in private, can be illustrated by the concept of a digital panopticon:

A panopticon is a large prison with a large watchtower in the center. The watchtower emits light in all directions. As a prisoner, you can never see whether somebody stands behind the light and blinds you. So you can never know whether you are being observed. This way, a single guard can enforce the law in the whole prison cell. A digital panopticon then is, if in your world everything is online and you never know, whether some spy agency watches you.

Saying you prefer government backdoors, because you do not want bad people to have encryption, is saying yes to a digital panopticon.

Undermining Encryption is extremely dangerous to our democracy. The moon shines for the innocent as well as the guilty the same way. Undermining encryption is extremely dangerous to our shared cybersecurity. If the governments actually want to catch criminals, they must do classically good police work. The price for undermining encryption is too damn high.

Middle Part

I assume you are not an expert in Algebra, but you can code, so just take a look at this example:

import 'dart:math';
import 'dart:typed_data';
import 'dart:core';

class EllipticCurvePoint
{
  BigInt x;
  BigInt y;

  EllipticCurvePoint(this.x,this.y);
}

class M511
{
  static final BigInt unnecessarilyLargePrimeWithLowCofactor = BigInt.parse("6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503041861");
  static final EllipticCurvePoint secureBasePoint = new EllipticCurvePoint(
      BigInt.from(5),
      BigInt.parse("2500410645565072423368981149139213252211568685173608590070979264248275228603899706950518127817176591878667784247582124505430745177116625808811349787373477"));
  static final BigInt A = BigInt.from(530438);
  static final BigInt three = BigInt.from(3);

  static EllipticCurvePoint add(EllipticCurvePoint a, EllipticCurvePoint b)
  {
    BigInt lambda;
    if ( a.x == b.x )
    {
      lambda = ((three*(a.x*a.x)+A)*(BigInt.two*a.y).modInverse(unnecessarilyLargePrimeWithLowCofactor))%unnecessarilyLargePrimeWithLowCofactor;
    } else {
      lambda = ((b.y-a.y) * (b.x-a.x).modInverse(unnecessarilyLargePrimeWithLowCofactor))%unnecessarilyLargePrimeWithLowCofactor;
    }
    BigInt xr = (lambda*lambda - a.x - b.x)%unnecessarilyLargePrimeWithLowCofactor;
    return EllipticCurvePoint(xr, (lambda*(a.x-xr)-a.y)%unnecessarilyLargePrimeWithLowCofactor);
  }
}

As you can see, there are some arcane rules for addition, plus you need a couple constants, unnecessarilyLargePrimeWithLowCofactor, secureBasePoint and A.

The secure base points and huge prime numbers with low cofactors etc. are given to you by mathematics cryptography researchers and you can look them up, for example, on https://safecurves.cr.yp.to.

Note that the add method is computationally quite expensive, as it involves the modular inverse of 512 bit numbers as well as multiple multiplications of 512 bit numbers. Remember further that the cost of an addition is constant runtime.

The study “The Chilling Effects of Surveillance and Human Rights: Insights from Qualitative Research in Uganda and Zimbabwe” [https://academic.oup.com/jhrp/article/16/1/397/7234270] noted the following:

“One of the clearest themes emerging from the research was a surveillance-induced self-censorship. In light of the importance placed on the free exchange of ideas, and the free development of an individual’s personality, this is clearly inimical to the object and purpose of the right to freedom of expression. An interviewee from Zimbabwe, straightforwardly expressed this reality:

I always practice what I would call self-censorship. I carefully construe how I communicate on certain issues and discuss them in a way that does not provide an opportunity for surveillance to become actionable. I protect myself using quite deliberate language (Participant 1).”

The study “Surveillance, Privacy, and Chilling Effects” (2015, PEN America) found that 34% of US writers avoided certain topics after learning about mass surveillance programs and 27% restricted their social media use due to fear of monitoring.

I am particularly fond of curve-M-511, which was introduced in this paper:

https://eprint.iacr.org/2013/647.pdf

and which you can see in the example above. “This is the case of Curve25519 [3] and Curve1174 [4]. However, while there is reason to look for higher security curves [15], no similar curves seem to have been proposed in the literature for higher security levels, matching the presumed levels of the standard NIST curves P-384 and P-521, as well as their binary counterparts, B-409 and B-571”

Now exchanging a shared secret requires multiplication of EllipticCurvePoints with Big Integers. Since we do not use “standard addition”, but an arcane form of “addition on elliptic curves”, the naive algorithm would be to add 1 N times. Since we have 512 bit numbers, this is practically not computationally feasible. To reduce the computational cost, we use the “double and add” scheme, where we add a number to itself to double it or we add one. This gives us a speed of O(log M * k), where M is the number of digits and k the price of an addition, which is constant.

  static EllipticCurvePoint multiply(EllipticCurvePoint ellipticCurvePoint, BigInt n) {
    BigInt done_additions = BigInt.zero;
    EllipticCurvePoint result = ellipticCurvePoint;
    while (done_additions < n) {
      if ((n - done_additions).isEven) {
        result = add(result, result);
        done_additions += ((n - done_additions) ~/ BigInt.two);
      } else {
        result = add(result, ellipticCurvePoint);
        done_additions += BigInt.one;
      }
    }
    return result;
  }

The problem with the code above is that it leaks its energy signature. Depending on the part of the if-clause you land in, you need more or less CPU cycles for the computation. Advanced hackers can detect the energy signature if they have offline-access and can read the electromagnetic fields emitted by your CPU. This includes chips on credit cards. Through this detection of the energy signature, the computation can be reverse engineered. This is called a ‘Side Channel Attack’. If you perform your code on devices where an attacker may have physical access, you need to introduce fake operations to hide the energy signature. The add method is harmless in this case, but for the sake of cybersecurity you should perform both increases of the variable done_additions in both clauses.

Bertrand Russel argues

“[…] Unfortunately, however, the men whom the police wish to catch are frequently benefactors of mankind. If the telegraph had existed, Polycrates would have caught Pythagoras, the Athenian government would have caught Anaxagoras, the Pope would have caught William of Occam, and Pitt would have caught Tom Paine when he tied to France in 1792. A large proportion of the best Germans and Russians have suffered under Hitler and Stalin; many more would have escaped but for the rapid transmission of messages. The increased power of the police therefore, is not wholly a gain. […]”.

What sounds rebellious is confirmed by the constitutions of democratic states. History has repeatedly shown that systems need to have some degree of built-in fragility towards the sentiment of the people; any state can turn totalitarian. A totalitarian state is bad. But a totalitarian state that can never be abolished? That is hell.

Indeed, the Bundesverfassungsgericht confirms:

Fundamental rights are first and foremost defensive rights of the citizen against the state; however, the fundamental rights provisions of the Basic Law also embody an objective value system that applies as a basic constitutional decision for all areas of law. (https://www.bundesverfassungsgericht.de/SharedDocs/Entscheidungen/DE/1958/01/rs19580115_1bvr040051.html).

I reiterate the status of fundamental rights: first and foremost defensive rights of the citizen against the state. In the US constitution, the right to bear arms reflects this principle.

“The Second Amendment was based partially […] described this right as an auxiliary right, supporting the natural rights of self-defense and resistance to oppression, and the civic duty to act in concert in defense of the state” (https://en.wikipedia.org/wiki/Second_Amendment_to_the_United_States_Constitution)

In the German constitution, article 20 reflects this principle (https://www.gesetze-im-internet.de/gg/art_20.html):

(1) The Federal Republic of Germany is a democratic and social federal state. (2) All state authority shall emanate from the people. It shall be exercised by the people in elections and votes and by special legislative, executive and judicial bodies. (3) The legislature shall be bound by the constitutional order, the executive power and the administration of justice shall be bound by law and justice. (4) All Germans shall have the right to resist anyone who attempts to abolish this order if no other remedy is possible.

As you can see, the founders of our constitutions have been aware that governments can turn tyrannic. This law in particularly was inspired by the learnings from Nazi Germany, where a democratically elected chancellor abolished the democratic order.

As you can see, fundamental human rights supersede the rights of governments.

The following code will yield a public key:

    BigInt alice_secret = SecurityUtils.randomBigInt(512);
    BigInt bob_secret = SecurityUtils.randomBigInt(512);

    EllipticCurvePoint alicePublicKey = M511.multiply(M511.secureBasePoint, alice_secret);
    EllipticCurvePoint bobPublicKey = M511.multiply(M511.secureBasePoint, bob_secret);

You can calculate the public key from the private key, but you can not compute the private key from the public key. Because of this, Alice and Bob can now freely share their public keys in the surveilled communication channel.

The Bundesverfassungsgericht stated that:

The right to freedom of expression is, as one of the most direct manifastions of the human personality in society, one of the noblest human rights altogether (un des droits les plus précieux de l”homme after article 11 of the general declaration of human and citizen’s rights from 1789). For a free democratic state order, it is absolutely constitutive, because it is this very right that enables the constant intellectual dispute, the battle of opinions, that is its life blood. In a certain sense, this right is the absolute foundation of any freedom, “the matrix, the indispensable condition of nearly every other form of freedom” (Cardozo).

The right to freedom of expression is codified in Article 19(2) of the International Covenant on Civil and Political Rights states that:

Everyone shall have the right to freedom of expression; this right shall include freedom to seek, receive and impart information and ideas of all kinds, regardless of frontiers, either orally, in writing or in print, in the form of art, or through any other media of his choice.

Digital Fascism is when the power of the state and the power over the flow of information merge.

Encryption is a Human Right.

This is how Bob and Alice exchange a private key:

BigInt aliceSharedSecret = M511.multiply(bobPublicKey, alice_secret).x
BigInt bobSharedSecret = M511.multiply(alicePublicKey, bob_secret).x

They will both compute the same shared key. This shared key can then be used with a key derivation function to compute a shared password.

Conclusion

Let us recall all the steps we need to take to exchange a shared secret in five steps:

First, choose a good elliptic curve from https://safecurves.cr.yp.to. Avoid NIST curves. Curve25519 is okay, but it only has 128 bit security and most symmetric encryption schemes work with 256 bit security. It is perceivable that 128 bit security is in the range of breaking for a couple million dollars.

Second, implement addition and multiplication for elliptic curves in your programming language. Use the code from this article as a reference, or grind through the Wikipedia Page on elliptic curves, where you can find further information and the addition rules (https://en.wikipedia.org/wiki/Elliptic_curve).

Third, implement the double and add algorithm to make calculating an EllipticCurvePoint times a BigInt computationally feasible. Use fake operations to hide the energy signature of the calculations.

Fourth, choose a very large private key at random (512 bit in case of M-511, 256 bit in case of Curve25519) and multiply it with the secure base point that is also part of the elliptic curve.

Fifth, multiple your private key with the public key of your partner. If your partner does the same, nobody can know which secret you exchanged and you will both have the same secret.

No bad person is worth our democracy. And our well-fortified democracy depends on encryption. We can not give up human rights for everyone, just because the police is underfunded; In fact, the police exist to uphold the very order that gives free speech to the people, the order that is worth upholding. Without human rights, whatever police is there to defend, is not a noble cause. Only because what the police do is ultimately aimed at enforcing human rights are there actions good. Only a state that can guarantee human rights can tell a terrorist to the just order from somebody who brings well-needed reform, from a hero who unshackles society from its unconscious chains.

New thought may suspicious. Idealists may seem crazy. Innovation may seem dangerous.

But our constitutions protect free speech, because we are western demoracies, we are the melting pot of thought, the drivers of innovation. No country that stifles its free thinkers, those who seem suspicious, in the long-term, has the capacity to reform itself. No country that stifles its free thinkers can be innovative and outperform our western democracies, based on the shared value of freedom of speech.

We embrace diversity of thought, we embrace debate, we embrace crazy ideas. And as long as there is encryption, diversity in thought is secure from persecution. We do not run around with scissors in our head, silencing our very thoughts out of fear that we might accidentially say them loudly. We are free to think, speak and innovate.

So let us carry forward the fire of encryption.

Thanks and goodbye, Malte