########################################################################################################################
# Description
########################################################################################################################

This file specifies a proper way to instantiate the "Design" of the Three Cent Curve cryptosystem, in the sense of
[1]. It commits on an ordered list of *future* lottery draws and on a way to turn the draws into a seed (and upper bound
on the seed), when the times come. This seed will then be used "as-is" as an input to the Design on which we commit
bellow.

See https://cryptoexperts.github.io/million-dollar-curve


########################################################################################################################
# Authors
########################################################################################################################

CryptoExperts


########################################################################################################################
# Date
########################################################################################################################

23th of September, 2015


########################################################################################################################
# Contact
########################################################################################################################

curves@cryptoexperts.com


########################################################################################################################
# Committed Design
########################################################################################################################

The Design we consider is the Three Cent Curve cryptosystem, as specified in the file 2015_06_three_cents_curve.txt
available at:

http://127.0.0.1:4000/million-dollar-curve/specifications/2015_06_three_cents_curve.txt

The SHA256 of this file is

c2ecf0526d6e17eebb77b1ce6d3a25c3d94b1d19860d767a61db4d7de9427af6

The Design was timestamped on the 21st of June, 2015 using various means, including:

- By obtaining a certificate from Let's Encrypt for the URL

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

- By posting the following tweet on Twitter:

  #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

- By adding a note to the technical paper [1] on the Cryptology ePrint Archive


########################################################################################################################
# About the list of ordered future lottery draws
########################################################################################################################

The exact list of lottery draws we consider is given bellow. line beginning with a '#' are ignored. Any blank line is
ignored. Apart from these, each line corresponds to one lottery draw, identified by a clear 'id'. The ids follow a
strict naming convention:

YYYY-MM-DD_<2 letters country code>_<string allowing to identify the game considered>_<optional number indicating the number of the draw, when the game draws multiple times on the same day>.

The columns after the 'id' respectively denote the number of balls drawn (m) and the total number of balls available
(n). The last column will eventually contain a list of the balls drawn (the order does not matter).

Consider, for example, the first line of the list:

2015-10-01_au_powerball         6  40 None

The first column "2015-10-01_au_powerball" is the id the Powerball draw that will take place on the 1st of October 2015
in Australia. This game draws 6 balls among 40. Since the result of this future draw is not known yet, we indicate
'None' in the last column.

Another example: consider the draw identified by

2015-10-01_nz_keno_1

This id designates the *first* Keno draw that will take place in New Zealand on the 1st of October 2015. This game draws
20 numbers among 80, and does so 4 times on the 1st of October. This is why the id is post-fixed with a '_1'.

The complete list of 220 draws is specified later in this file


########################################################################################################################
# How to update the list when the draw results will be known
########################################################################################################################

Assuming for example, that the Powerball numbers drawn on the 1st of October 2015 in Australia are 1,36,5,9,31, and 25,
one should update the corresponding line as follows:

2015-10-01_au_powerball         6  40 1,36,5,9,31,25

Note that order in which the drawn numbers are specified is not important (i.e., it has no influence on the computed
seed).


########################################################################################################################
# How to treat missing draws
########################################################################################################################

It might happen that a specific lottery decide *not* to perform a draw at a date when it was supposed to. When this
occurs, we choose to specify 'None' as a draw result. In that case, the corresponding line will be ignored in the seed
computation. Doing so eventually decreases the quantity of entropy contained in the final seed. If such events occur too
often among the list of 220 draws indicated bellow, the seed might end up containing to few entropy for instantiated the
Design. If this occurs, the script we provide will simply abort. To increase our success probability, we took care of
listing more lottery draws than necessary.


########################################################################################################################
# How to compute the seed from the lottery draws
########################################################################################################################

The script we provide bellow allows to compute a seed from the draws, when are available (i.e., after the 13th of
October, 2015). Assuming that the file containing those results is named 'draws.txt', the script should typically be
executed as follows:

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

Note that this script should only be executed once all the draws have been gathered (thus, after the 13th of December,
2015). If it succeeds, the seed obtained is guaranteed to contain at least 8192 bits of entropy.

One can also note that we require 10 lone bits in the end (see [1] for more details).

########################################################################################################################
# The ordered list of 220 lottery draws
########################################################################################################################

-----BEGIN LOTTERY DRAWS FILE (draws_empty.txt)-----
# Start date (t3): 2015-10-01
# Target Entropy: 8192

# Draw Id                       m  n  draw
2015-10-01_au_powerball         6  40 None
2015-10-01_br_quina             5  80 None
2015-10-01_ca_daily_keno_midday 20 70 None
2015-10-01_ca_daily_keno_night  20 70 None
2015-10-01_de_keno              20 70 None
2015-10-01_es_bonoloto          6  49 None
2015-10-01_es_la_primitiva      6  49 None
2015-10-01_fr_keno_midday       20 70 None
2015-10-01_fr_keno_night        20 70 None
2015-10-01_it_super_enalotto    6  90 None
2015-10-01_nz_keno_1            20 80 None
2015-10-01_nz_keno_2            20 80 None
2015-10-01_nz_keno_3            20 80 None
2015-10-01_nz_keno_4            20 80 None
2015-10-01_us_ny_cash_4_life    5  60 None
2015-10-02_br_dupla_sena        6  50 None
2015-10-02_br_lotofacil         15 25 None
2015-10-02_br_quina             5  80 None
2015-10-02_ca_daily_keno_midday 20 70 None
2015-10-02_ca_daily_keno_night  20 70 None
2015-10-02_ca_loto_max          7  49 None
2015-10-02_de_euro_jackpot      5  50 None
2015-10-02_de_keno              20 70 None
2015-10-02_es_bonoloto          6  49 None
2015-10-02_eu_euromillions      5  50 None
2015-10-02_fr_keno_midday       20 70 None
2015-10-02_fr_keno_night        20 70 None
2015-10-02_nz_keno_1            20 80 None
2015-10-02_nz_keno_2            20 80 None
2015-10-02_nz_keno_3            20 80 None
2015-10-02_nz_keno_4            20 80 None
2015-10-02_us_mega_millions     5  75 None
2015-10-03_au_saturday_lotto    6  45 None
2015-10-03_be_lotto             6  45 None
2015-10-03_br_mega_sena         6  60 None
2015-10-03_br_quina             5  80 None
2015-10-03_ca_daily_keno_midday 20 70 None
2015-10-03_ca_daily_keno_night  20 70 None
2015-10-03_ca_loto_649          6  49 None
2015-10-03_ca_lottario          6  45 None
2015-10-03_ch_loto              6  42 None
2015-10-03_de_keno              20 70 None
2015-10-03_de_lotto             6  49 None
2015-10-03_es_bonoloto          6  49 None
2015-10-03_es_la_primitiva      6  49 None
2015-10-03_fr_keno_midday       20 70 None
2015-10-03_fr_keno_night        20 70 None
2015-10-03_fr_loto              5  49 None
2015-10-03_it_super_enalotto    6  90 None
2015-10-03_mu_loto              6  40 None
2015-10-03_nl_lotto             6  45 None
2015-10-03_nz_keno_1            20 80 None
2015-10-03_nz_keno_2            20 80 None
2015-10-03_nz_keno_3            20 80 None
2015-10-03_nz_keno_4            20 80 None
2015-10-03_nz_lotto             6  40 None
2015-10-03_uk_health_lottery    5  50 None
2015-10-03_us_hot_lotto         5  47 None
2015-10-03_us_ny_lotto          6  59 None
2015-10-03_us_powerball         5  69 None
2015-10-03_us_wild_card         5  33 None
2015-10-04_ca_daily_keno_midday 20 70 None
2015-10-04_ca_daily_keno_night  20 70 None
2015-10-04_de_keno              20 70 None
2015-10-04_es_el_gordo          5  54 None
2015-10-04_fr_keno_midday       20 70 None
2015-10-04_fr_keno_night        20 70 None
2015-10-04_nz_keno_1            20 80 None
2015-10-04_nz_keno_2            20 80 None
2015-10-04_nz_keno_3            20 80 None
2015-10-04_nz_keno_4            20 80 None
2015-10-05_au_monday_lotto      6  45 None
2015-10-05_br_lotofacil         15 25 None
2015-10-05_br_quina             5  80 None
2015-10-05_ca_daily_keno_midday 20 70 None
2015-10-05_ca_daily_keno_night  20 70 None
2015-10-05_de_keno              20 70 None
2015-10-05_es_bonoloto          6  49 None
2015-10-05_fr_keno_midday       20 70 None
2015-10-05_fr_keno_night        20 70 None
2015-10-05_fr_loto              5  49 None
2015-10-05_nz_keno_1            20 80 None
2015-10-05_nz_keno_2            20 80 None
2015-10-05_nz_keno_3            20 80 None
2015-10-05_nz_keno_4            20 80 None
2015-10-05_us_ny_cash_4_life    5  60 None
2015-10-06_au_oz_lotto          7  45 None
2015-10-06_br_dupla_sena        6  50 None
2015-10-06_br_quina             5  80 None
2015-10-06_ca_daily_keno_midday 20 70 None
2015-10-06_ca_daily_keno_night  20 70 None
2015-10-06_de_keno              20 70 None
2015-10-06_es_bonoloto          6  49 None
2015-10-06_eu_euromillions      5  50 None
2015-10-06_fr_keno_midday       20 70 None
2015-10-06_fr_keno_night        20 70 None
2015-10-06_it_super_enalotto    6  90 None
2015-10-06_nz_keno_1            20 80 None
2015-10-06_nz_keno_2            20 80 None
2015-10-06_nz_keno_3            20 80 None
2015-10-06_nz_keno_4            20 80 None
2015-10-06_us_mega_millions     5  75 None
2015-10-07_au_wednesday_lotto   6  45 None
2015-10-07_be_lotto             6  45 None
2015-10-07_br_lotofacil         15 25 None
2015-10-07_br_mega_sena         6  60 None
2015-10-07_br_quina             5  80 None
2015-10-07_ca_daily_keno_midday 20 70 None
2015-10-07_ca_daily_keno_night  20 70 None
2015-10-07_ca_loto_649          6  49 None
2015-10-07_ch_loto              6  42 None
2015-10-07_de_keno              20 70 None
2015-10-07_de_lotto             6  49 None
2015-10-07_es_bonoloto          6  49 None
2015-10-07_fr_keno_midday       20 70 None
2015-10-07_fr_keno_night        20 70 None
2015-10-07_fr_loto              5  49 None
2015-10-07_nz_keno_1            20 80 None
2015-10-07_nz_keno_2            20 80 None
2015-10-07_nz_keno_3            20 80 None
2015-10-07_nz_keno_4            20 80 None
2015-10-07_nz_lotto             6  40 None
2015-10-07_us_hot_lotto         5  47 None
2015-10-07_us_ny_lotto          6  59 None
2015-10-07_us_powerball         5  69 None
2015-10-07_us_wild_card         5  33 None
2015-10-08_au_powerball         6  40 None
2015-10-08_br_quina             5  80 None
2015-10-08_ca_daily_keno_midday 20 70 None
2015-10-08_ca_daily_keno_night  20 70 None
2015-10-08_de_keno              20 70 None
2015-10-08_es_bonoloto          6  49 None
2015-10-08_es_la_primitiva      6  49 None
2015-10-08_fr_keno_midday       20 70 None
2015-10-08_fr_keno_night        20 70 None
2015-10-08_it_super_enalotto    6  90 None
2015-10-08_nz_keno_1            20 80 None
2015-10-08_nz_keno_2            20 80 None
2015-10-08_nz_keno_3            20 80 None
2015-10-08_nz_keno_4            20 80 None
2015-10-08_us_ny_cash_4_life    5  60 None
2015-10-09_br_dupla_sena        6  50 None
2015-10-09_br_lotofacil         15 25 None
2015-10-09_br_quina             5  80 None
2015-10-09_ca_daily_keno_midday 20 70 None
2015-10-09_ca_daily_keno_night  20 70 None
2015-10-09_ca_loto_max          7  49 None
2015-10-09_de_euro_jackpot      5  50 None
2015-10-09_de_keno              20 70 None
2015-10-09_es_bonoloto          6  49 None
2015-10-09_eu_euromillions      5  50 None
2015-10-09_fr_keno_midday       20 70 None
2015-10-09_fr_keno_night        20 70 None
2015-10-09_nz_keno_1            20 80 None
2015-10-09_nz_keno_2            20 80 None
2015-10-09_nz_keno_3            20 80 None
2015-10-09_nz_keno_4            20 80 None
2015-10-09_us_mega_millions     5  75 None
2015-10-10_au_saturday_lotto    6  45 None
2015-10-10_be_lotto             6  45 None
2015-10-10_br_mega_sena         6  60 None
2015-10-10_br_quina             5  80 None
2015-10-10_ca_daily_keno_midday 20 70 None
2015-10-10_ca_daily_keno_night  20 70 None
2015-10-10_ca_loto_649          6  49 None
2015-10-10_ca_lottario          6  45 None
2015-10-10_ch_loto              6  42 None
2015-10-10_de_keno              20 70 None
2015-10-10_de_lotto             6  49 None
2015-10-10_es_bonoloto          6  49 None
2015-10-10_es_la_primitiva      6  49 None
2015-10-10_fr_keno_midday       20 70 None
2015-10-10_fr_keno_night        20 70 None
2015-10-10_fr_loto              5  49 None
2015-10-10_it_super_enalotto    6  90 None
2015-10-10_mu_loto              6  40 None
2015-10-10_nl_lotto             6  45 None
2015-10-10_nz_keno_1            20 80 None
2015-10-10_nz_keno_2            20 80 None
2015-10-10_nz_keno_3            20 80 None
2015-10-10_nz_keno_4            20 80 None
2015-10-10_nz_lotto             6  40 None
2015-10-10_uk_health_lottery    5  50 None
2015-10-10_us_hot_lotto         5  47 None
2015-10-10_us_ny_lotto          6  59 None
2015-10-10_us_powerball         5  69 None
2015-10-10_us_wild_card         5  33 None
2015-10-11_ca_daily_keno_midday 20 70 None
2015-10-11_ca_daily_keno_night  20 70 None
2015-10-11_de_keno              20 70 None
2015-10-11_es_el_gordo          5  54 None
2015-10-11_fr_keno_midday       20 70 None
2015-10-11_fr_keno_night        20 70 None
2015-10-11_nz_keno_1            20 80 None
2015-10-11_nz_keno_2            20 80 None
2015-10-11_nz_keno_3            20 80 None
2015-10-11_nz_keno_4            20 80 None
2015-10-12_au_monday_lotto      6  45 None
2015-10-12_br_lotofacil         15 25 None
2015-10-12_br_quina             5  80 None
2015-10-12_ca_daily_keno_midday 20 70 None
2015-10-12_ca_daily_keno_night  20 70 None
2015-10-12_de_keno              20 70 None
2015-10-12_es_bonoloto          6  49 None
2015-10-12_fr_keno_midday       20 70 None
2015-10-12_fr_keno_night        20 70 None
2015-10-12_fr_loto              5  49 None
2015-10-12_nz_keno_1            20 80 None
2015-10-12_nz_keno_2            20 80 None
2015-10-12_nz_keno_3            20 80 None
2015-10-12_nz_keno_4            20 80 None
2015-10-12_us_ny_cash_4_life    5  60 None
2015-10-13_au_oz_lotto          7  45 None
2015-10-13_br_dupla_sena        6  50 None
2015-10-13_br_quina             5  80 None
2015-10-13_ca_daily_keno_midday 20 70 None
2015-10-13_ca_daily_keno_night  20 70 None
2015-10-13_de_keno              20 70 None
2015-10-13_es_bonoloto          6  49 None
2015-10-13_eu_euromillions      5  50 None
-----END LOTTERY DRAWS FILE (draws_empty.txt)-----


########################################################################################################################
# The script turning a list of lottery draws into a seed
########################################################################################################################

The script uses a helper file (utils.py) also provided bellow (note that helper was already prived in the Design text
file). As for the script provided with the committed Design, our Python 3 script require the non standard gmpy2 library.

-----BEGIN 01_draws_to_seed.py-----
#!/usr/bin/env python3

# This file is part of Million Dollar Curve

# Copyright (C) 2015, 2016  CryptoExperts

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 3 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software Foundation,
# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA

import argparse
import json
import os
import re
import math
from datetime import datetime,timedelta
import gmpy2
import utils


def main():

    # Test local versions of libraries

    utils.test_python_version()
    utils.test_gmpy2_version()

    # Parse command line arguments
    
    parser = argparse.ArgumentParser(description="From a table of draws, output a seed of appropriate length.")

    parser.add_argument("input_draw_file", help="""Text file with draws.""")
    parser.add_argument("output_seed_file", help="""JSON file where we can store the seed computed from the draws.""")
    parser.add_argument("entropy_to_gather", help="""Minimum entropy to extract before drawing lone bits.""")
    parser.add_argument("--nbr_lone_bits", type=int, help="""Number of lone bits to extract.""", default=0)
    
    args = parser.parse_args()


    # Check arguments
    
    output_seed_file = args.output_seed_file
    if os.path.exists(output_seed_file):
        utils.exit_error("The output file '%s' already exists. Exiting."%(output_seed_file))


    # Declare a few important variables
    
    two_pow_entropy_to_gather = (1<<int(args.entropy_to_gather))
    
    seed = 0
    L = 1 # before lone bits are drawn, seed lies in [0,L - 1]

    lone_bits_part = 0
    nbr_lone_bits = args.nbr_lone_bits


    # Scan the input file, construct the seed
    
    with open(args.input_draw_file, "r") as f:
        
        for line in f:

            if not line or line.strip() == "" or line.startswith("#"):
                continue

            (draw_id, m, n, draw) = re.split("\s+", line.strip(), maxsplit=3)

            if draw == "None":
                continue
            
            m = int(m)
            n = int(n)
            draw = [ int(x) for x in draw.split(",") ]
            index = index_from_draw(draw,m)

            if L < two_pow_entropy_to_gather:
                
                print("Draw %s used to extract entropy"%(draw_id))
                seed = gmpy2.bincoef(n,m)*seed + index
                L *= gmpy2.bincoef(n,m)
                
            else:
                
                print("Draw %s used to extract a lone bit"%(draw_id))
                b = index & 1
                seed += L * (b << (args.nbr_lone_bits - nbr_lone_bits))
                nbr_lone_bits -= 1

            if L >= two_pow_entropy_to_gather and nbr_lone_bits == 0:
                break

    if nbr_lone_bits > 0 or L < two_pow_entropy_to_gather:
        utils.exit_error("There wasn't enough draws to collect to request quantity of entropy and lone bits.")

    seed_upper_bound = L * 2**(args.nbr_lone_bits)
    seed_entropy = math.floor(gmpy2.log2(seed_upper_bound))
    print("The seed contains more than %d bits of entropy (including the %s lone bits)."%(seed_entropy,args.nbr_lone_bits))
    print("The seed is %d"%(seed))

    print("Saving the seed to %s"%(output_seed_file))
    with open(output_seed_file, "w") as f:
        json.dump({"seed": int(seed),
                   "seed_upper_bound": int(seed_upper_bound),
                   "approx_seed_entropy": int(seed_entropy),
                   "lone_bits": int(args.nbr_lone_bits)}, 
                  f)

            
def index_from_draw(draw,m):
    index = 0
    draw = sorted(draw)
    for i in range(m):
        index += gmpy2.bincoef(draw[i]-1, i+1)
    return index


if __name__ == "__main__":
    main()
-----END 01_draws_to_seed.py-----

-----BEGIN utils.py-----
#!/usr/bin/env python3

# This file is part of Million Dollar Curve

# Copyright (C) 2015, 2016  CryptoExperts

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 3 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software Foundation,
# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA

import sys
import platform
import os.path
import subroutines
import gmpy2

def exit_error(s):
    sys.exit("[ERROR] %s"%s)

def colprint(col1,col2 = "",col1_size = 50):
    col1_size = max(col1_size, len(col1))
    if col2 != "":
        print(col1 + " " * (col1_size - len(col1)) + col2)
    else:
        print(col1)

def write_and_flush(s):
    sys.stdout.write(s)
    sys.stdout.flush()

    
def test_gmpy2_version():
    expected_gmpy2_version = '2.0.7'
    local_gmpy2_version = gmpy2.version()
    if local_gmpy2_version != expected_gmpy2_version:
        print('[WARNING] You are using version %s of gmpy2. These scripts have been tested with version %s'
              %(local_gmpy2_version, expected_gmpy2_version), file=sys.stderr)

        
def test_python_version():
    expected_python_version = '3.4.3'
    local_python_version = platform.python_version()
    if local_python_version != expected_python_version:
        print('[WARNING] You are using version %s of Python. These scripts have been tested with version %s'
              %(local_python_version, expected_python_version), file=sys.stderr)

        
def test_pari_version():
    expected_pari_version = '2.7.4'
    local_pari_version = subroutines.pari_version()
    if local_pari_version != expected_pari_version:
        print('[WARNING] You are using version %s of PARI. These scripts have been tested with version %s'
              %(local_pari_version, expected_pari_version), file=sys.stderr)
    
        
def test_pari_seadata():
    """Look for the seadata package for PARI. Exit if it cannot be found."""
    datadir = subroutines.pari_cfg_datadir()
    seadata_path = os.path.join(datadir,"seadata")
    if not os.path.exists(seadata_path):
        exit_error("Cannot find the seadata.tgz package for PARI. Please install this package in %s. See http://pari.math.u-bordeaux.fr/packages.html."%(datadir))
-----END utils.py-----


########################################################################################################################
# References
########################################################################################################################

[1] Thomas Baigneres, Cecile Delerablee, Matthieu Finiasz, and Tancrede Lepoint, With Little Help from our Friends. Trap Me If You Can. Available on https://www.cryptoexperts.com
[2] PARI/GP. http://pari.math.u-bordeaux.fr
[3] Python. https://www.python.org
[4] GMP. The GNU Multiple Precision Arithmetic Library. https://gmplib.org