Million Dollar Curve

An elliptic curve everyone can trust.


Time has come to get rid of arbitrary choices.

By using publicly verifiable randomness produced in February 2016 by many national lotteries from all around the world, we propose to generate a cryptographically secure elliptic curve for the ECDH cryptosystem as an alternative to the NIST P-256 and the Curve25519 curves.

It is designed so that nobody (even us!) can put a trap in it.

Get the full paper   Get the source code » #MDCurve on Twitter  

The Million Dollar Curve MDCurve201601 »

Overview

Today most of elliptic-curve cryptography relies on the same set of curves: ANSSI FRP256v1, NIST P-256, NIST P-384, Curve25519, secp256k1, brainpoolP256t1, Curve1174 and a few others.

However, several of these curves parameters generation processes contain unjustified choices, specific constants or specific hash algorithms. Examples include the NIST P256 curve, whose parameters are derived from an unjustified seed (C49D3608 86E70493 6A6678E1 139D26B7 819F7E90), and the ANSSI FRP256v1 curve, for which no justification whatsoever is provided. The infamous Dual-EC-DRGB story legitimates the concerns many specialists have about the use of arbitrary choices.

I no longer trust the constants.

Of course, one should not conclude that cryptographic algorithms using similar constants are systematically insecure (certainly, some designers are honest!) and we will not dispute the right to trust those algorithms. Yet, in the perspective of eventually obtaining a legitimately trusted cryptographic algorithm by everybody, we believe that every future standard should rule out any cryptographic design involving arbitrary choices.

Choosing security and inspiring public trust above all.

The generation of elliptic curve parameters can be split into several parts:

  • The design: this part specifies and commits on all the security criteria the curve shall meet, on the implied parameter space, and on a deterministic procedure which, given an input seed, outputs elliptic curve parameters guaranteed to follow the aforementioned security criteria.
  • The randomness extractor: this part specifies the entropy source, as well as how and when the entropy shall be extracted from it;
  • The seed generation: this part computes the seed from the extracted entropy;
  • The instantiation: this part generates the parameters using the aforementioned seed and deterministic procedure.

Any choice of elliptic curve parameters should be performed in a justifiable, systematic, and comprehensive way. In addition to providing an algorithmic description on paper, we believe that one should also provide readable and executable code, and use an unimpeachable and publicly-verifiable entropy source.

Image Technical Paper

Technical paper

In our technical paper, we describe a deterministic procedure to generate a cryptographically secure elliptic curve from a random seed. To the best of our knowledge, any curve generated through our methodology is secure (and in particular, meets all the SafeCurves criteria).

Get the full paper  

Image Source Code

Source code

In addition to the technical paper, we publish and commit on the source code implementing our whole methodology, i.e. both the seed extraction algorithm and the elliptic curve parameters generation procedure.

Get more details »

Image Lotteries

Unimpeachable entropy source

By carefully selecting and combining many future lottery draws, we obtain an unpredictable, unbiased, publicly observable, and archived entropy source, that is easily verifiable in the future.

Nobody can predict what seed will be produced by those draws, even us!

Go to a list of lotteries »

The Million Dollar Curve.

On this website, we use the methodology described in our technical paper to generate an elliptic curve, that we call the Million Dollar Curve, as an alternative to curves P-256 and Curve25519 for the ECDH cryptosystem.

More precisely, we provide a tutorial that describes the whole process of generating an elliptic curve called the Three Cents Curve based on lottery draws from October 2015. Our methodology will then be fully instantiated to generate the Million Dollar Curve: we will commit on the design and the list of draws in January 2016, and the curve MDCurve201601 (Million Dollar Curve of January 2016) will be generated using lottery draws from February 2016.

In order for the Million Dollar Curve to inspire confidence to the greatest number, we want to integrate comments we receive in the methodology before committing on the methodology and the entropy source we will use. Please drop us an email and we will gladly listen.

Source Code and Usage Instructions

Code overview

We provide 5 scripts, written in Python 3, that implement the whole methodology described in the technical paper:

  01_draws_to_seed.py

takes as an input the path to a text file containing an ordered list of lottery draws, the quantity of entropy to be extracted from those draws (in a format described in the tutorial), and the number of lone bits to add. It outputs a JSON file containing the following parameters:

  • seed: the integer value of the seed.
  • seed_upper_bound: an integer such that the seed lies between 0 (included) and seed_upper_bound (excluded).
  • approx_seed_entropy: an approximate value of the quantity of entropy contained in the seed. Note that the quantity of entropy given as an input to the script is a minimum value, so that the final quantity will typically contain a few more bits.
  • lone_bits: The number of lone bits included in the seed, as given as an input to this script.
In case the requested minimum quantity of entropy cannot be extracted from the lottery draws, this script fails and doesn't create the output file. Also, if the output file already exists, the script exits immediately.

  02_generate_bbs_parameters.py

takes as an input an integer min_prime_bitsize and a JSON file containing a seed and its upper bound. Typically, the input JSON file results from an execution of the previous script. It outputs a JSON file containing the following parameters:

  • bbs_p: a strong strong prime of size min_prime_bitsize (or more).
  • bbs_q: another strong strong prime of size min_prime_bitsize (or more).
  • bbs_s: a proper starting point for BBS (i.e., a quadratic residue of \(\mathbb{Z}_{pq}^*\)).
This script makes sure that the seed contains enough entropy to properly generate the parameters above. If this is not the case, it exists and doesn't create the output file. Also, if the output file already exists, the script exits immediately.

  03_generate_prime_field_using_bbs.py

takes as an input an integer prime_size and a JSON file containing the parameters of BBS. Typically, the input JSON file results from an execution of the previous script. It outputs a JSON file containing the following parameters:

  • p: a prime (congruent to \(3 \bmod 4\)) of prime_size bits, generated using BBS.
  • bbs_p: the exact same strong strong prime bbs_p specified in the input JSON file.
  • bbs_q: the exact same strong strong prime bbs_q specified in the input JSON file.
  • bbs_s: the internal state of BBS after the generation of p (which is a quadratic residue of \(\mathbb{Z}_{pq}^*\)).
This script fails if bbs_p or bbs_q are not strong strong primes, or if the output file already exists. In such cases, it exists immediately and doesn't create the output file.

  04_generate_curve_using_bbs.py

takes as an input a JSON file containing the parameters of BBS and a prime p. It outputs a JSON file containing the following parameters:

  • p: the prime \(p\) as given in the input JSON file.
  • d: the parameter \(d \in \mathbb{F}_p \setminus \{0,1\}\) of the equation of the Edwards curve $$E(\mathbb{F}_p) \;:\; x^2+y^2 = 1 + d x^2 y^2.$$
  • cardinality: the cardinality of \(E(\mathbb{F}_p)\).
  • cardinality_twist: the cardinality of the twist of \(E(\mathbb{F}_p)\).
  • trace: the trace of the curve.
The output JSON file provides a base point \((x,y) \in E(\mathbb{F}_p) \) for the curve, generating a subgroup of cardinality \(\#E(\mathbb{F}_p) / 4\):
  • base_point_x : the \(x\) coordinate of the base point.
  • base_point_y : the \(y\) coordinate of the base point.
The script search for an acceptable curve by testing candidates iteratively (and deterministically). The number of the good candidate is saved to the output JSON file:
  • candidate_nbr: number of the good candidate.
Finally, the output JSON file also contains the BBS after the generation of the curve and of the base point.
The script has two optional parameters --start and --max_nbr_of_tests that provide basic support for launching several instances of this script in parallel:
  • --start START allows to start the search for a good candidate from the candidate number START.
  • --max_nbr_of_tests MAX_NBR_OF_TESTS allows to make the script exit after MAX_NBR_OF_TESTS candidates (unless a good candidate is found).
The third (and last) optional parameter --fast allows to discard bad candidates much faster by taking advantage of the fact that the Schoof–Elkies–Atkin algorithm implementation that we use to compute \(\#E(\mathbb{F}_p)\) can exit early if it detects that \(\#E(\mathbb{F}_p)\) will eventually be divisible by a small prime \(> 4\). When using this option, the cardinalities of bad candidates are not always output to the standard output.

  05_prove_primes.py

When they require to test whether a number is prime, the four previous scripts only check that it is a pseudo-prime. This script implements a (generalized) Pocklington primality test to actually prove that the list of pseudo-primes given as an input are indeed primes.

Helpers

The 5 scripts rely on the following 4 helpers:

  • bbsengine.py is a simple implementation of BBS.
  • pari_light_interface.py is a simple interface to a few routines provided by the PARI C library. None of the functions defined in this file are actually called from the five main scripts. Rather, they are called in the following helper.
  • subroutines.py provides mathematical helper functions.
  • utils.py provides basic functions for printing information on screen, etc.

Required libraries

Altogether, the scripts rely on several standard Python 3 libraries (argparse, bbsengine, ctypes, ctypes.util, datetime, json, math, os, re, subroutines, and sys) and on GMP, using gmpy2. By means of the pari_light_interface.py helper, they also make call to the PARI library (that should therefore be installed too). Since we use PARI to count point on elliptic curves, the seadata.tgz must be installed too (this package is otherwise optional in most PARI implementations). To install this package, see Optional PARI/GP packages.

These libraries should be readily available on Linux, and are easy to install on Mac OS X using MacPorts. Installing the seadata.tgz package for PARI is only slightly more involved. The source code we provide has been extensively tested with the 3.4.3 release of Python, the 2.0.7 version of gmpy2, and the 2.7.4 version of PARI.

Download

All the source code (scripts and helpers) is available on GitHub.

Source code  

Tutorial: Generating the Three Cents Curve

What is the Three Cents Curve and what is this tutorial about?

The Three Cents Curve is a toy cryptosystem, with realistic size parameters. The aim of this tutorial is to describe the whole process of generating this curve with our methodology. Note that the Three Cents Curve differs from the Two Cents Curve (which is the running example given in the technical paper).

Although the Three Cents Curve is a curve with 128 bit security, we firmly recommend not to use it for cryptographic purposes. The reason is that this curve was not generated using our full methodology (the reason why should be clear by the end of this tutorial). Yet, since it provides realistic sized parameters, it is close to being a full-fledged curve.

The tutorial

This tutorial will describe what would have been an acceptable process for generating this curve, in accordance with the methodology described in the technical paper. For this, Assume that today is...

  • Phase I: Some day in the beginning of June 2015

    Designing the Three Cents Curve cryptosystem

    As cryptographers willing to provide the community with a way of generating secure curves, we produce a document (a text file) describing:

    • The full specification of the cryptosystem we are willing to generate. In that case, we aim for an elliptic curve in Edwards form $$ E \;:\; x^2 + y^2 = 1 + dx^2y^2$$ over a prime field \(\mathbb{F}_p\), together with a point \((x,y)\) on this curve that shall generate a large subgroup.
    • Inspired by SafeCurves, we specify the complete list of security criteria that the cryptosystem shall meet:
      1. \(p\) must be a 256 bit prime.
      2. The parameter \(d\) of the Edwards curve must not be a square in \(\mathbb{F}_p\).
      3. The number of point \(\#E(\mathbb{F}_p)\) must be of the form \(4q\), where \(q\) is prime.
      4. The base point \((x,y)\) must generate a subgroup of order \(q\).
      5. The embedding degree \(m\) of the curve must verify \(m > (q-1)/100\).
      6. The CM field discriminant \(D\) of the curve must verify \(|D| \ge 2^{100}\).
      7. The curve must be twist secure, i.e., the constraints 3. and 5. must also hold for the twist of \(E\).
    • Those constraints implicitly define an acceptable set for the parameters \(p, d, x, y\) of the cryptosystem. We develop simple code that, given a seed containing enough entropy, deterministically compute specific values for the parameters. For any acceptable input, the code returns parameters that meet all the security criteria listed above.
    The text file containing all this information is here: 2015_06_three_cents_curve.txt.

  • Phase II: On the 21st of June, 2015

    Commitment on the design of the Three Cents Curve family

    On the 21st of June, 2015 (a date corresponding to \(t_0\) in the technical article), we commit on the design (i.e., on the 2015_06_three_cents_curve.txt file) by:

    • By using Let's Encrypt (U.S.) to timestamp the SHA256 of 2015_06_three_cents_curve.txt. Although Let's Encrypt does not provide a dedicated way to timestamp digital documents (yet?), we suggest to ask for a certificate for the URL

      MDC201506.SHA256.c2ecf0526d6e17ee.bb77b1ce6d3a25c3.d94b1d19860d767a.61db4d7de9427af6.cryptoexperts.com

      which obviously contains the SHA256 of the Design text file (the dots in the hash are unfortunate but seems to be required for technical reasons). The notBefore field of the certificate would then correspond to the timestamp (note that this field sometimes indicates a time that is a few minutes earlier than the date at which the URL was submitted, but this is not a problem for us).
    • Posting the following tweet on Twitter (U.S.):
        Tweeted by @CryptoExperts on the 21st of June, 2015
      (Don't look for the tweet, this is only an example)

      #MDC201506 SHA256
      c2ecf0526d6e17eebb77b1ce6d3a25c3d94b1d19860d767a61db4d7de9427af6 https://cryptoexperts.github.io/million-dollar-curve/2015_06_three_cents_curve.txt

    • By having the 2015_06_three_cents_curve.txt certified in the Bitcoin blockchain (Worldwide), e.g., using Proof of Existence or BTProof.
    • By publishing 2015_06_three_cents_curve.txt on GitHub (U.S.), together with the scripts.
    • By adding a note to the technical paper on the Cryptology ePrint Archive (U.S.).
    • By publishing 2015_06_three_cents_curve.txt on Bitbucket (Aus).
    • By publishing a video simply displaying the SHA256 and the SHA512 of 2015_06_three_cents_curve.txt on DailyMotion (FR).
    • By recording Siri while reading every hexadecimal character of the SHA256 and of the SHA512 of 2015_06_three_cents_curve.txt, and then publishing the sound on SoundCloud (DE).
    • By publishing an image of the SHA256 and SHA512 of 2015_06_three_cents_curve.txt on Flickr (U.S.)
    • By using free hash chain services such as TrueTimeStamp or obtaining a timestamp from a digital notary such as Virtual-Notary or StartSSL.

  • Phase Pre-III: In the beginning of September, 2015

    Choosing a proper way to instantiate a Three Cents Curve

    As Standardizers willing to instantiate a cryptosystem according to the Design committed above, we produce a text file containing:

    • A list of 220 future lottery draws around the world, the first draw taking place on the 1st of October 2015 (\(t_3\)), the last on the 13th of October 2015 (\(t_3'\)).
    • A clear pointer to the committed Design (e.g., by providing the SHA256 of the 2015_06_three_cents_curve.txt file).
    • Simple source code that takes as an input an ordered list of lottery draws and extracts the entropy of those draws to produce a uniformly distributed seed (under the assumption that the draws are uniformly distributed on their respective space).
    The technical paper discusses how we believe this process can be conducted in an appropriate way. The text file containing all this information is here: 2015_09_three_cents_curve_standardization.txt.

  • Phase III: On the 23rd of September, 2015

    Committing on the generation process of the Three Cents Curve

    On the the 23d of September, 2015 (a date corresponding to \(t_2\) in the technical article), we commit on the aforementioned 2015_09_three_cents_curve_standardization.txt file, using similar means than those that were used to commit on the Design file.

    Note that we took care to commit 2015_09_three_cents_curve_standardization.txt at a time \(t_2 < t_3\), i.e., before the first draw of the list of 220 draws actually takes place.

  • Phase IV: October 1st - October 13rd 2015

    Lottery Draws

    During this period, the draws on which we committed on in Phase III take place, and the full list of result is gathered.

  • Phase V: Any time after the 13th of October, 2015

    Curve generation

    After the 13th of October, 2015, all the draws have taken place and anybody can update the list of the 220 draws on which we committed. The full list of results is available here: draws.txt. Here is an excerpt:

    # Start date (t3): 2015-10-01 # Target Entropy: 8192 # Draw Id m n draw 2015-10-01_au_powerball 6 40 3,5,16,17,27,40 2015-10-01_br_quina 5 80 23,32,56,76,77 2015-10-01_ca_daily_keno_midday 20 70 15,17,18,19,21,27,28,29,33,38,41,49,50,54,56,58,59,65,69,70 2015-10-01_ca_daily_keno_night 20 70 1,4,7,11,19,20,29,30,32,33,34,40,41,45,46,48,50,53,54,58 2015-10-01_de_keno 20 70 5,9,19,20,21,23,25,27,33,35,38,43,49,52,55,56,58,59,65,70 2015-10-01_es_bonoloto 6 49 6,10,18,20,40,41 2015-10-01_es_la_primitiva 6 49 11,17,30,39,45,49 2015-10-01_fr_keno_midday 20 70 1,2,4,9,12,16,20,29,36,38,43,46,47,52,53,57,60,65,68,69 2015-10-01_fr_keno_night 20 70 1,4,5,6,10,11,13,17,22,27,38,39,41,42,43,48,51,53,58,62 2015-10-01_it_super_enalotto 6 90 2,17,21,49,69,74 ... 2015-10-13_br_quina 5 80 6,13,35,46,49 2015-10-13_ca_daily_keno_midday 20 70 1,3,11,14,15,16,19,25,30,35,43,47,50,52,53,55,57,58,61,62 2015-10-13_ca_daily_keno_night 20 70 3,4,10,12,17,19,20,22,23,28,31,32,36,45,46,47,60,65,68,70 2015-10-13_de_keno 20 70 4,10,13,20,28,32,40,42,43,44,46,47,52,54,58,63,64,66,67,70 2015-10-13_es_bonoloto 6 49 11,19,32,35,39,44 2015-10-13_eu_euromillions 5 50 12,15,26,29,47

    From this file anyone can execute the script 01_draws_to_seed.py on which we committed, in order to extract entropy and compute the seed:

    ./01_draws_to_seed.py draws.txt in_02.json 8192 --nbr_lone_bits 10

    This produces the JSON file in_02.json (available here) contains the following parameters:

    approx_seed_entropy = 8223 lone_bits = 10 seed = 1664436082852779444802442192988970575531930397222494321228063629864557961728803883926094550385167058026090587442804992621666228031824850408977931653953205224907452192448402947670055261150764551727944796583924695849500240128137466901314993974704108255639919385356455453617053087121025389652870978012187565785575464644714958917678079274569379823362558091467611799751193407675046826807548694116669844166972705365969552771149984160062544074389146982409243075813736699100075589396723882917071122015731981374614095302089754494985407927832926024234836396358084285809717464826379318750876768993887869840031466090921436832230498035339095298529291587853714219329774235775210961379127330113823477598764527438778847626145011633782593212645562064448659471877722480871999974702080179183834126740699517184521454943938035113938692998317616147636425414962743790714831677740118246878312210571012425841034033128661986723276972882209299270350199282190617841430606201104803753345366988416652963111938108353169079015641546969256318597263496182315932504553869628818983731124877921578768421573130326980198457985853933167041178401907899567953650045468446161244047687507035837811771600202409909526557843389429455601479289633348882813556807503769979728957591763637621737145956120815220344555748920676312816814656460166181343305464690936269322579570407807762636457326224984914613872538193178504113292256360371831014862510954694946783505875916871595421574730030018201003626509323351542883853608834849092416755445122210741037507932150659416521202870433052456864432922150184966576408871635089341598440450145024174442340774136708941993724850490599222135355391720073383074540738447294180965530961137799570246200068162112468745891496003006169621316053393275704733196781368570411976629532995051915685204926483953406664939370869964416695536624121769396683994351915735775797639217795093078385321306543055120144565661953122858193755809973160189059524656983365610112983211718256501009825173809999924357509149066306953519903416637248043489493183726451360472341666092059964278878276574420041448907840407445249481718650690416690775758933245281009973900311691502576296253316680849678468235039210114017450884506944754770897523525941138413734814028885865857866444976690953612864968929784638694658289257251181357074750560995592810208579415743638539558225063210137757410358643416635839606812394994891101077266204256187787492062451504528393807321466708332847566242091400223420779877679952622051662350002253651495133907341754 seed_upper_bound = 4078760853137366152565665359692641039385592116341792872174798293528730262505604856319984891330326499724588304315794346056827503608640844582004272617182928864730734193080477046244934560445194888018926038312523778544581999220598232461784026472137408919884797239288514956084013173341120259946951032471347862933908049519338819085102396116540035985609568910996351733394837041133831507469134335187139469760120261847923343499519578444590415470483381011336125873301787848247709938136258591551456285922915975926764694558075000354349419311367522811408768994613285440887109567797862891121077183005290727585879502584733529754489120189587944482660578728381733205292149488895964956969710417847950557953655800264098812806856466959112148876651995406206966050775213683808859958755812475416154322120830140661273887276848635151983587529184272984574556667043624065090410875990380572588107168689382535001627304696050578210355907340666453558982971202255333432775066898676327161853623859679786270428734392966386543639164091424740538368536165400286507871533582157790871675410027382485168692604395871565299251138312714475762573808959818134553603071816832386859763429380550095983034986058417000612156642929612826563488839685279016609385318784084049942605080191498002919729562400190864894127088678948576410389436282889357468591916375683532741581763651636102277026910781851214197515177481112220139710899345903260327834754682153619235021280611826160386317317328661616704836140532491691386237112388826910843914553456570679510755548742185380127658616175054047136422029049104417360642770872815660646361135507253674090997828130247154987646923171770730495701379970962903467568032213361012558458938060621275945410710110443526088103376767068521669280446083222824945458107842332647677069633044260420967869635123892580747798068962208928960074912924697779520324760635130691381310240967401765086313970825010189295113753045997872481740966507003742742832417209416256025942964664848830188760574594066885788122685263106441535957491546516097644214950870199400377916215850401801148959152950297778724814834581397128318128091443452181468211989958420501734609756372909906023306986860868954878220677807462827469559365944814758907124374137189565747715802421313738221471257545427485769197245808006977353378799330644960247109710084437262010321614667307967351935919867699325447057426780624404603270164990858292195087155389512414721474560000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

    This JSON we obtained can now be used as an input the the first script provided by the committed Design:

    ./02_generate_bbs_parameters.py in_02.json in_03.json 2048

    As explained in the technical paper and in the Source code section of this website, this script generates two strong strong primes of 2048 bits (at least) and a starting point for the BBS PRNG. It saves these results the JSON file in_03.json available here, with the following results:

    bbs_p = 35996412491659794106448678139203938249319697793346228632758700385153828129222749516077912753343035129789819747816348453087580050481996153995521308039730936961618334905667713791346937674536432092801009873985890146457492187047606448036554590564796981762282692096900641341020117017885420307506471120134152019935744189317325819234436421439715327857275211487684243785270234661937364552442351195200733126410361318413535774155794766283380974477515359668232245678657176490984667263872574921785081459817762257992362678454589660781072420366409686780905394019828621484459905747476774917671346051159496277702425357569133770443119 bbs_q = 30315858869239431089212426514783714062428473234435833692057820645959694566008634325041433180776896793285445888034627949706231004647893532536024771869124634392824449630944436227669260567061622692804476138599018096428493105738397355007990979053630728062311300025984776092617287790160254448606785404410421995726235326915743414650055648079666247870233079356651945395857036418250763093029380246643546664785718151008002877713894928073721216341320396221599090958437786830763819867002491028083039229220195943232749087198595707235991378178782441122374868962214544288908100679420248140749400244100103512014551094178606281398127 bbs_s = 18476426484133019619998234396934849051966797182536070934506269854004374204414136339314377524571231797390359179695957049688508697050157500214667193474820494653369134031708114847593144064625415532686231461386488622149871002216153721536130644578728635711394588600500832804852689345505588408177295103694098702331375837758368406095112432947707310011873806823384013560875404650395910416660196334382526154266971128648615654982055521502794313048094309540419504951302162746456649418700812060831427876891970165668060726241688197548728249239884217479590511603628877205033352497364354469143120798218913543911839860000097598329037494350535649378407580398643700122323369548041629677121721973753511494261644724003034028338651573419655204199846776134666189017880004663596460410032954382086307747756870889896894524260105011340917794046775756652937089267415768365147537020349548255221010874106356366998440915763901915123853642601607553756397146899127153931718082422816549057021341447091544410200586397764184633299229883062636542402843211347084313695101888396936147476602127101258995255751180194010017332444760927624323897059669055522613843653741214924538943210013162984710377440648716185527119859749450609782543570111304936910079063707774290435862746

    Using these parameters, anyone can execute the second script provided by the Design, in order to generate the 256-bit prime \(p\) defining the finite field for the Three Cents Curve:

    ./03_generate_prime_field_using_bbs.py in_03.json in_04.json 256

    This generates a JSON file named in_04.json specifying the prime we were looking for, as well as an updated state of the BBS PRNG. The file is available here, it contains the following results:

    bbs_p = 35996412491659794106448678139203938249319697793346228632758700385153828129222749516077912753343035129789819747816348453087580050481996153995521308039730936961618334905667713791346937674536432092801009873985890146457492187047606448036554590564796981762282692096900641341020117017885420307506471120134152019935744189317325819234436421439715327857275211487684243785270234661937364552442351195200733126410361318413535774155794766283380974477515359668232245678657176490984667263872574921785081459817762257992362678454589660781072420366409686780905394019828621484459905747476774917671346051159496277702425357569133770443119 bbs_q = 30315858869239431089212426514783714062428473234435833692057820645959694566008634325041433180776896793285445888034627949706231004647893532536024771869124634392824449630944436227669260567061622692804476138599018096428493105738397355007990979053630728062311300025984776092617287790160254448606785404410421995726235326915743414650055648079666247870233079356651945395857036418250763093029380246643546664785718151008002877713894928073721216341320396221599090958437786830763819867002491028083039229220195943232749087198595707235991378178782441122374868962214544288908100679420248140749400244100103512014551094178606281398127 bbs_s = 16231249049289512183816108274139410008959347871291657480241802255571614754777066194725352335563239959933548478062079522271990145699776322456398385700223125565569257249758201487125056248913059978410072798926972267808251247173058791746560537593858664276102129052592952950327611814240424713850191447417636663531641397215846024226609699275919847744016594863529001030951393681091784144561701636056734226990419608829565443727396180437528093169529171743378973271256572695803016611472151850312477890344457296387863326098536333877357302652175539293031823984410244560554546550672398522518623206389657545780138501006919050268721753696332886298203438679845296041259359332435756266592470651896950183346866887144681521429757183980122188623006646503186966559592632414784945403544702360536821125889716509251163306415155154150553139559189980979605453545858460054316575152784881467825030802940550344251225733031611421609669883678178934480349237244199614711901351540034563328973484524695768320106795632767954597859635858794796783991377252578300266399421088724523375073422668086490862267546327476362499803034251505650131538267136074401723559119467940653489794522406722813658363856847025074467194006481609878829631103051152964731001602596537283064429604 p = 91246932342305152449750051429713245449807489613263384851830108981264650686779

    Using these parameters, anyone can execute the third script provided by the Design, in order to generate the Edwards curve and the base point:

    ./04_generate_curve_using_bbs.py in_04.json out.json --fast

    This generates a JSON file named out.json specifying all the remaining parameters of the Three Cents Curve. Those parameters are obtained after 13879 bad candidates. The out.json file is available here, it contains (among others) the following parameters:

    base_point_x = 37757004397508297461488232022133215112657762713920729625869178332980531926037 base_point_y = 78446303868801273512921965105183307537468280825605151126468994204353829363786, candidate_nbr = 13880 cardinality = 91246932342305152449750051429713245449776357953969544416800235471101452818604 cardinality_twist = 91246932342305152449750051429713245449838621272557225286859982491427848554956 d = 83729813207862236689454561512349386173963508197506719807406274769840427582251 discriminant = -91004637289708212066283662649310061398127799680941464991704514056966882295035 embedding_degree = 22811733085576288112437512857428311362444089488492386104200058867775363204650 embedding_degree_twist = 22811733085576288112437512857428311362459655318139306321714995622856962138738 p = 91246932342305152449750051429713245449807489613263384851830108981264650686779 trace = 31131659293840435029873510163197868176

What is wrong with the Three Cents Curve?

Although the final curve we obtained has realistic sized parameters, you should not trust it. Indeed, this tutorial did not fully respect the methodology. In particular, the dates indicated in this tutorial are fictive. In reality, the Design of the Three Cents Curve was generated on the 21st of December, that is, at a time when all the draw results were actually known. As a consequence, you cannot be sure that we did not design the whole (deterministic) process as a function of those draw results, in order to make sure to eventually obtain a curve with a trapdoor. Moreover, we did not really commit on any of the text files. For this reason, we iterate our warning:

Hopefully, we plan to draw a proper curve, suited for cryptographic purposes. We call it, the Million Dollar Curve.

The Million Dollar Curve

Introducing the Million Dollar Curve

The Million Dollar Curve will be an alternative to curves P-256 and Curve 25519 to instantiate the ECDH cryptosystem, and will be produced in February 2016. This 128-bit secure elliptic curve is to be generated following the full methodology described in the technical paper and demonstrated in the tutorial to generate the Three Cents Curve. In particular, by committing publicly on the (deterministic) process and the list of draws before they actually happen, our methodology is designed so that nobody (even us!) can put a trap in the Million Dollar Curve.

Our objective is for the Million Dollar Curve to inspire confidence to the greatest number. In that sense, we want to integrate comments we receive in the methodology before committing on the final methodology, final source code and the lottery draws we will use.

You can direct any comment you have to us and we will gladly listen. Email us!

In what follows, we describe how we will generate the MDCurve201601 Curve (Million Dollar Curve of January 2016).

Our methodology can easily be adapted (and reproducible by anyone) for new curves with possibly different specifications (e.g. not an Edwards curve or aiming at 256 bits of security), and of course new lottery draws.

We will likely generate new Million Dollar Curves in the future on this website as needed.

Timeline to generate the MDCurve201601 Curve

  • Phase I: Before January 25th 2016 Done!

    Receiving comments on our methodology

    In order for the Million Dollar Curve to win its spur, we greatly welcome any comment to improve the methodology we propose.

    Email us!
  • Phase II: January 27th 2016 Done!

    Commitment on the design to generate MDCurve201601

    On January 27th 2016, we presented a full document (a text file) that describes the generation of Million Dollar Curve of January 2016 (named MDCurve201601), the list of security criteria we consider, and the acceptable set of parameters.

    This design text file can be downloaded here: 2016_01_27_million_dollar_curve.txt

    The SHA256 hash of this file is

    e9dd4baf0d351b5a64c59ed6b1efd3108094b3585e17a0e5350fb200500058d9

    We commited on this design text file in the following ways:

    • We created a Let's Encrypt (U.S.) certificate for the subdomain

      mdcurve.design.201601.sha256.e9dd4baf0d351b5a.64c59ed6b1efd310.8094b3585e17a0e5.350fb200500058d9.cryptoexperts.com

      where one can see the SHA256 hash of the design text file. The certificate can be consulted/validated by visiting the following url:

      https://mdcurve.design.201601.sha256.e9dd4baf0d351b5a.64c59ed6b1efd310.8094b3585e17a0e5.350fb200500058d9.cryptoexperts.com

      The certificate can also be dowloaded here: mdcurve.design.201601.crt The certificate is also archived on crt.sh (you can look for X509v3 Subject Alternative Name).
    • We have uploaded a sound file on SoundCloud (DE). Check out the song 2016_01_27_million_dollar_curve on CryptoExperts' SoundCloud page.
    • We have uploaded a picture of a handwritten version of the SHA256 hash of the design text file on 500px (U.S.). Unfortunately, the picture cannot be consulted on CryptoExperts' profile anymore. CryptoExperts' account has been suspended, for unknown reasons.
    • We published the design text file on CryptoExperts' Github million-dollar-curve directory (U.S.) and the SHA256 hashes of both the design text file and the Let's Encrypt certificate on the Bitbucket million-dollar-curve directory (Aus).
    • We published a video showing the SHA256 of the design text file on Dailymotion (FR). You can watch it on CryptoExperts' Dailymotion page.
    • We used the TrueTimeStamp service to have the design text file included in their sequence of fingerprints. The certificate we obtained is here: TrueTimeStamp-certificate-1497.txt. One can easily check that the SHA256 hash of the file was timestamped on January 27, 2016 3:49:54 pm UTC.
    • We obtained a certificate from Virtual-Notary (U.S.). This certificate can be downloaded here: virtual-notary-cert-document-644891.p12. One can easily check that the SHA256 hash of the file was timestamped on Wednesday January 27, 2016 11:04.37 EST (UTC-0500).
    • We created a "trusted timestamp" with BTProof. At the time of writing, the SHA256 of the design text file has not yet been seen on the blockchain.
    • We created a new revision of the technical paper on the IACR Cryptology ePrint Archive (International). We added a note to this revision, with the SHA256 of the design text file. You can retrieve this version at https://eprint.iacr.org/2015/1249/20160127:164115.
    • We posted the following tweet on Twitter (U.S.):
        Tweeted by @CryptoExperts on Wednesday January 27, 2016
      Link to the tweet

      #MDCurve201601 SHA256
      e9dd4baf0d351b5a64c59ed6b1efd3108094b3585e17a0e5350fb200500058d9 https://cryptoexperts.github.io/million-dollar-curve/specifications/mdcurve_201601/2016_01_27_million_dollar_curve.txt

  • Phase III: January 29th 2016 Done!

    Commitment on the list of draws to consider in February 2016

    On January 29th 2016, we commited on a text file containing a list of future draws (starting on February 1st, 2016), a clear pointer to the aforementioned design (Phase II), and a source code that deterministically computes the seed from the listed draws.

    This design text file can be downloaded here: 2016_01_29_million_dollar_curve_seeding.txt

    The SHA256 hash of this file is

    f8bdb5bd4957a2d65b567378bb32744d0d0573a77e4ef0247311a5a4b98744da

    We commited on this design text file in the following ways:

    • We created a Let's Encrypt (U.S.) certificate for the subdomain

      mdcurve.seeding.201601.sha256.f8bdb5bd4957a2d6.5b567378bb32744d.0d0573a77e4ef024.7311a5a4b98744da.cryptoexperts.com

      where one can see the SHA256 hash of the design text file. The certificate can be consulted/validated by visiting the following url:

      https://mdcurve.seeding.201601.sha256.f8bdb5bd4957a2d6.5b567378bb32744d.0d0573a77e4ef024.7311a5a4b98744da.cryptoexperts.com

      The certificate can also be dowloaded here: mdcurve.seeding.201601.crt The certificate is also archived on crt.sh (you can look for X509v3 Subject Alternative Name).
    • We have uploaded a sound file on SoundCloud (DE). Check out the song 2016_01_29_million_dollar_curve_seeding on CryptoExperts' SoundCloud page.
    • We have uploaded a picture of a handwritten version of the SHA256 hash of the design text file on 500px (U.S.). Unfortunately, the picture cannot be consulted on CryptoExperts' profile anymore. CryptoExperts' account has been suspended, for unknown reasons.
    • We published the seeding text file on CryptoExperts' Github million-dollar-curve directory (U.S.) and the SHA256 hashes of both the seeding text file and the Let's Encrypt certificate on the Bitbucket million-dollar-curve directory (Aus).
    • We used the TrueTimeStamp service to have the design text file included in their sequence of fingerprints. The certificate we obtained is here: TrueTimeStamp-certificate-1497.txt. One can easily check that the SHA256 hash of the file was timestamped on January 29, 2016 10:57:48 am UTC.
    • We published a video showing the SHA256 of the design text file on Dailymotion (FR). You can watch it on CryptoExperts' Dailymotion page.
    • We obtained a certificate from Virtual-Notary (U.S.). This certificate can be downloaded here: virtual-notary-cert-document-304168.p12. One can easily check that the SHA256 hash of the file was timestamped on Friday January 29, 2016 06:05.19 EST (UTC-0500).
    • We used Proof of Existence to have the SHA256 of the seeding text file certified in the Bitcoin blockchain. The transaction broadcast was timestamped on the 30th of January, 2016, at 23h16 GMT (see the Document information). This can be checked using the command line:
      # curl -d d=f8bdb5bd4957a2d65b567378bb32744d0d0573a77e4ef0247311a5a4b98744da https://www.proofofexistence.com/api/v1/status
      {"digest":"f8bdb5bd4957a2d65b567378bb32744d0d0573a77e4ef0247311a5a4b98744da","payment_address":"14n84qmsbL81gnppaE6WcEvMB5jLrBsZmm","pending":false,"timestamp":"2016-01-29 12:39:00","tx":"99a5f547aa4569cc34d3a9ff66f22b8086f44c0b90bc53e1c4a5ed54f4f7b43c","txstamp":"2016-01-30 23:16:37","blockstamp":"2016-01-30 23:33:22","network":"livenet","success":true}
    • We created a new revision of the technical paper on the IACR Cryptology ePrint Archive (International). We added a note to this revision, with the SHA256 of the design text file. You can retrieve this version at https://eprint.iacr.org/2015/1249/20160129:141701.
    • We posted the following tweet on Twitter (U.S.):
        Tweeted by @CryptoExperts on Wednesday January 29, 2016
      Link to the tweet

      #MDCurve201601 SHA256
      f8bdb5bd4957a2d65b567378bb32744d0d0573a77e4ef0247311a5a4b98744da https://cryptoexperts.github.io/million-dollar-curve/specifications/mdcurve_201601/2016_01_29_million_dollar_curve_seeding.txt

  • Phase IV: February 1st - February 14th 2016 Done!

    Lottery Draws

    During this period, the draws on which we committed on in Phase III took place, and the full list of results was gathered.

    On February 15th 2016, we published the final list of draw results. This list is available here:

    draws.txt

    Among the 260 draws we committed on during Phase III, only 5 did not take place:

    • 4 Brazilian draws (namely, 2016-02-08_br_quina, 2016-02-08_br_lotofacil, 2016-02-09_br_quina, and 2016-02-09_br_dupla_sena), which were not drawn probably because of the Brazilian Carnival (February 5-February 10 in 2016).
    • Another Brazilian draw (2016-02-03_br_mega_sena), which actually took place on February 2.
    As explained in the file committed in Phase III, these missing draws are not an issue.

  • Phase V: After February 14th 2016 Done!

    Curve generation

    On February 15th 2016, the required draws we committed on were available, and the full list of results was made public.

    Using the source code committed on in Phase III, we generated the seed from the full list of results:

    python3 01_draws_to_seed.py draws.txt in_02.json 8192 --nbr_lone_bits 30
    We obtained the following file, containing the seed: in_02.json

    Using the source code committed on in Phase II and the aforementioned seed, we generated the BBS parameters, the prime field, and the MDCurve201601 curve as follows:

    python3 02_generate_bbs_parameters.py in_02.json in_03.json 2048

    We obtained the following file, containing the BBS parameters: in_03.json

    python3 03_generate_prime_field_using_bbs.py in_03.json in_04.json 256

    We obtained the following file, containing the prime for the underlying field: in_04.json

    python3 04_generate_curve_using_bbs.py in_04.json out.json

    On the 29535th iteration, we obtained the following file, containing the parameters for the Million Dollar Curve: out.json

    See below for a summary of what we obtained!

The Million Dollar Curve - MDCurve201601

The Million Dollar Curve (MDC201601) is an elliptic curve in Edwards form, suited for cryptographic applications, providing 128 bits of security. It comes with a base point generating a large subgroup. This curve was generated using a novel and (hopefully) unimpeachable process, allowing anyone to make sure that no backdoor could have been introduced. Here is a small list of the features of the million dollar curve:

  • Since the Million Dollar Curve is an Edwards curve \(x^2+y^2 = 1 + dx^2y^2\) on a prime field \(F_p\) where \(d\) is not a square, it benefits from a complete addition formula.
  • Since it is an Edwards, the number of points of the Million Dollar Curve is a multiple of 4. In addition, it is of the form \(4q\) where \(q\) is prime.
  • The base point generates a subgroup of prime order \(q\).
  • The Million Dollar Curve is twist-secure.

The parameters of the Million Dollar Curve are:

p         = 109112363276961190442711090369149551676330307646118204517771511330536253156371
d         = 39384817741350628573161184301225915800358770588933756071948264625804612259721
nbr pts   = 109112363276961190442711090369149551675722038296192275550523913172742087892972
q         = 27278090819240297610677772592287387918930509574048068887630978293185521973243
base pt x = 82549803222202399340024462032964942512025856818700414254726364205096731424315
base pt y = 91549545637415734422658288799119041756378259523097147807813396915125932811445

Here are a few more properties of the Million Dollar Curve:

twist nbr pts       = 109112363276961190442711090369149551676938576996044133485019109488330418419772
twist q             = 27278090819240297610677772592287387919234644249011033371254777372082604604943
discriminant        = -16614462762133134914405550644570535788911111926729660424467118032738408266371
embed. degree       = 27278090819240297610677772592287387918930509574048068887630978293185521973242
trace               = 608269349925928967247598157794165263400
twist embed. degree = 27278090819240297610677772592287387919234644249011033371254777372082604604942

List of Lotteries

In this table, one can find an exhaustive list of lotteries we use, that is lotteries for which we could easily access an up-to-date archive of draws. Each lottery picks a number \(m\) among \(n\) numbers, and we specify the resulting entropy per draw and the number of draws per week.

Lottery name \(m\) \(n\) Entropy Weekly draws Weekly entropy
Australian Monday Lotto 6 45 22.95 1 22.95
Australian OZ Lotto 7 45 25.43 1 25.43
Australian Powerball 6 40 21.87 1 21.87
Australian Saturday Lotto 6 45 22.95 1 22.95
Australian Wednesday Lotto 6 45 22.95 1 22.95
Belgian Lotto 6 45 22.95 2 45.90
Brasilian Dupla-Sena 6 50 23.92 2 47.84
Brasilian Lotofácil 15 25 21.64 3 64.92
Brasilian Mega-Sena 6 60 25.57 2 51.14
Brasilian Quina 5 80 24.51 6 147.06
Canadian Daily Keno (Midday Draw) 20 70 57.16 7 400.12
Canadian Daily Keno (Evening Draw) 20 70 57.16 7 400.12
Canadian Loto 649 (Main Draw) 6 49 23.73 2 47.46
Canadian Loto Max (Main Draw) 7 49 26.35 1 26.35
Canadian Lottario 6 45 22.95 1 22.95
Swiss Loto 6 42 22.32 2 44.64
German Euro Jackpot 5 50 21.01 1 21.01
German Keno 20 70 57.16 7 400.12
German Loto 6 49 23.73 2 47.46
Spanish Bonoloto 6 49 23.73 6 142.38
Spanish El Gordo 5 54 21.59 1 21.59
Spanish La Primitiva 6 49 23.73 2 47.46
European Euro Millions 5 50 21.01 2 42.02
French Keno (Noon) 20 70 57.16 7 400.12
French Keno (Evening) 20 70 57.16 7 400.12
French Loto 5 49 20.86 3 62.58
Italian SuperEnalotto 6 90 29.21 3 87.63
Mauritius Loto 6 40 21.87 1 21.87
Dutch Lotto (Standard 1st trecking draws) 6 45 22.95 1 22.95
New Zealand Keno (1st daily draw - 10AM) 20 80 61.61 7 431.27
New Zealand Keno (2nd daily draw - 1PM) 20 80 61.61 7 431.27
New Zealand Keno (3rd daily draw - 3PM) 20 80 61.61 7 431.27
New Zealand Keno (4th daily draw - 6PM) 20 80 61.61 7 431.27
New Zealand Lotto 6 40 21.87 2 43.74
UK Health Lottery (Saturday £1 draw) 5 50 21.01 1 21.01
US Hot Lotto 5 47 20.54 2 41.08
US Mega Millions 5 75 24.04 2 48.08
US NY Cash 4 Life 5 60 22.38 2 44.76
US NY Lotto 6 59 25.42 2 50.84
US Powerball 5 69 23.42 2 46.84
US Wild Card 5 33 17.85 2 35.70
Total \(\approx\)5189

Frequently Asked Questions

Since the publication of this project, we have received many questions and saw many reactions on, e.g., Twitter. We plan to answer most of them on this webpage.

  • Is Million Dollar Curve nothing more than "yet another safe curve"?

    Yes and no.

    The Million Dollar Curve in itself is just another safe curve, but it is generated using a novel process. This process is detailed in our technical paper and allows to generate parameters everyone can trust for new cryptosystem standards, but also in any other situation requiring verifiable randomness.

  • Is there anything wrong with Curve25519?

    No.

    We, at CryptoExperts, actually use Curve25519 and recommend it to our partners. Yet, we think that people should not rely on the same few safe curves that are currently out. Our methodology allows to easily produce safe alternatives.

  • Curve25519 vs. Million Dollar Curve

    Curve25519 was designed to be as fast as possible, with no security compromise. This is both a strength and a potential weakness:

    • a strength because it gives a valid argument that no trapdoor was introduced in the design,
    • a potential weakness because Curve25519 uses a very specific prime field. As of now, no attack exploiting this specificity is known.

    For applications where speed is paramount, Curve25519 is probably the best option. But for most applications, where losing a little on the efficiency side is "not a big deal", Million Dollar Curve is probably the safest choice.

    See also the answer by Ruggero on Stack Exchange.

  • What if a government agency rigs a few lotteries?

    This is not an issue.

    Our parameter generation process was specifically designed to avoid this kind of problem. As explained in Section 4.4 of our technical paper, in order to manipulate the parameter generation, an adversary has to rig all the last lottery draws (what we call the "Last draw attack"). We mitigate this risk by relying on independent lotteries from various countries around the world.

  • Do you really think that national lotteries are unimpeachable?

    Yes and no.

    Most national lotteries follow a strict protocol which is specifically designed to avoid manipulations (certified drawing machines, supervision of a bailiff, legal process, etc.). It is pretty obvious that in the past some lotteries have been manipulated, but manipulations with financial motive are not a concern for us (at most, a few bits of entropy are lost). Besides, as explained in the previous answer, an adversary would have to manipulate all the last lottery draws.

  • How can I verify the parameters if a lottery archive is no longer available?

    These archives are usually duplicated in several places over the Internet or sometimes printed in newspapers. If at a given time in the future the result of a drawing becomes completely unavailable, verification will become impossible.

    However, the lotteries that have been selected are well established and will most certainly continue to exist for some time. During this period, everyone will be able to fully verify/re-generate the Million Dollar Curve, which in itself is a convincing argument for later use.

  • I have never heard about half of these lotteries, how do I even know they are real?

    You can probably verify that lotteries from your own country actually exist: you might even have played them before hearing about Million Dollar Curve. Your friends in Mauritius, Canada, and New Zealand can certainly confirm the same thing.

    Besides, lotteries are such popular games that "faking" one in a convincing way is probably impossible without being noticed at some point.

  • What if a lottery does not perform the expected draws during Phase IV of the generation process?

    This situation is already taken into account in our generation process and the scripts we provide, so this is not a problem. The missing draws are simply ignored (see, for example, section How to treat missing draws in 2015_09_three_cents_curve_standardization.txt)