// Bitcoin_log - Klasse zur Arbeit mit elliptischen Kurven bei Bitcoin
// y^2 = x^3 + 7 % n, n eine Primzahl
// Soll exemplarisch zeigen, wie das Verhältnis von privaten(zufällig gewählt) zu public Key ist.

import java.math.*;
import java.util.*;

public class Bitcoin_log
{
  public static BigInteger n;  // von aussen: Primzahl
  protected final static BigInteger ZWEI = BigInteger.valueOf(2);
  protected final static BigInteger DREI = BigInteger.valueOf(3);
  protected final static BigInteger SIEBEN = BigInteger.valueOf(7);
  protected static Paar_ECM basis = null;
  protected final static int GRENZE_MAX = 1 << 20;  // Begrenzung der Größe; Voller Suchraum: 1 << 128 !
  protected static boolean GGTAUSGABE = true;  // weil Zielinfo

  protected static boolean DEBUG = false;
  protected static boolean DEBUGZWERT = false;  // Ausgabe Zwischenwerte
  protected static boolean DEBUGPLUS = false;
  protected BigInteger ergGGT = null;  // zu setzen des letzten ggT

  // Bestimmt die Primzahl und den Startpunkt
  private void bestimmeP()
  {
    n = ZWEI.pow(256).subtract(ZWEI.pow(32)).subtract(ZWEI.pow(9)).subtract(ZWEI.pow(8))
          .subtract(ZWEI.pow(7)).subtract(ZWEI.pow(6)).subtract(ZWEI.pow(4)).subtract(BigInteger.ONE);
    BigInteger x = new BigInteger("55066263022277343669578718895168534326250603453777594175500187360389116729240");
    BigInteger y = new BigInteger("32670510020758816978083085130507043184471273380659243275938904335757337482424");
    basis = new Paar_ECM(x,y);
  }

  private void bestimmePTest()
  {
    n = BigInteger.valueOf(29);
    BigInteger x = new BigInteger("3");
    BigInteger y = new BigInteger("11");
    basis = new Paar_ECM(x,y);
    // TODO testen
    // https://bitcoin.stackexchange.com/questions/25024/how-do-you-get-a-bitcoin-public-key-from-a-private-key
    // 18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725  =>
    // 0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299
  }

  // addieren zweier Punkte - konnte ein Wert ermittelt werden, wird dieser zurückgegeben.
  // Bei einem ggT wird dieser gespeichert und eine ArithmeticException geworfen
  public final Paar_ECM addieren (Paar_ECM p1, Paar_ECM p2) throws Logik_Fehler, ArithmeticException
  {
    // Sonderfälle im Zusammenhang mit neutralem Element
    if (p1.istNeutral()) 
      return p2;
    else if (p2.istNeutral()) 
      return p1;

    // Wegen der darauffolgenden Vergleiche ist es wichtig, dass die BigInts immer positiv oder 0 sind
    if (DEBUG)
    {
      if (p1.x.signum() < 0 || p1.y.signum() < 0 || p2.x.signum() < 0 || p2.y.signum() < 0)
      {
        System.out.println ("Negative Eingabeparameter bei addieren"); System.exit(1);      
      }
      if (p1.x.compareTo(n) >= 0 || p1.y.compareTo(n) >= 0 || p2.x.compareTo(n) >= 0 || p2.y.compareTo(n) >= 0)
      {
        System.out.println ("Eingabeparameter >= n addieren"); System.exit(1);      
      }
    }

    // Lambda-bestimmen (sollte ungleich 1 sein)
    BigInteger zaehler = null, nenner = null; boolean gleich = false;
    if (p1.x.equals(p2.x))
    {
      // gleich oder additiv invers; y müssen bei invers gerade und ungerade sein, wenn n ungerade
      if (p1.y.equals(p2.y))
      {
        // Sonderfall: y ist 0, laut Prüfungen oben nicht neutral !
        if (p1.y.equals(BigInteger.ZERO))
        {
          // auch (-x, 0) ist eine Lösung; aber schlecht weitermachen ! x ist Wurzel von -a !
          throw new Logik_Fehler("Punkt " + p1 + " nicht mal 2"); 
        }
        // lambda = (3*x1^2) / (2 * y1)
        BigInteger temp = p1.x.modPow(ZWEI, n);
        zaehler = temp.shiftLeft(1).add(temp);  // remainder hier nicht; 2.9% CPU
        nenner = p1.y /* .shiftLeft(1) s.u. */; gleich = true;
      }
      else if ((p1.y.testBit(0) != p2.y.testBit(0)) && p1.y.equals(n.subtract(p2.y)))  // 1.2% CPU
      {
        return Paar_ECM.NEUTRAL;
      }
      else
      {
        // x gleich, y verschieden: es ist eine Wurzel ziehbar !
        for (short runde = 0; runde < 2; ++runde)
        {
          BigInteger vers = ((runde == 0) ? p1.y.subtract(p2.y) : p1.y.add(p2.y));
          BigInteger test = vers.gcd(n);
          if (! test.equals(BigInteger.ONE)) { 
            System.out.println ("Teiler " + test); ergGGT = test; 
            throw new ArithmeticException ("ggT2 ist " + ergGGT);
          }
        }
        throw new Logik_Fehler ("kein ggT gefunden");
      }      
    }
    else
    {
      // y gleich, x verschieden nicht gesondert betrachtet(lambda=0)
      // lambda = (y2 - y1) / (x2 - x1)
      zaehler = p2.y.subtract(p1.y);
      nenner = p2.x.subtract(p1.x);
    }
    // Jetzt lambda ermitteln: bei nenner-ggT > 1 hier Fehler abfangen
    BigInteger inv = null; ergGGT = null;
    try
    {
      // Für Performanz: gemeinsame 2er raus
      int weg = zaehler.getLowestSetBit(); int weg2 = nenner.getLowestSetBit(); if (gleich) ++weg2;
      if (weg2 < weg) weg = weg2;
      zaehler = zaehler.shiftRight(weg); 
      if (gleich && weg == 0) nenner = nenner.shiftLeft(1); /* doch dazu */
      else if (gleich) --weg;
      nenner = nenner.shiftRight(weg);

      inv = nenner.modInverse(n);  // 34.2% CPU
    }
    catch (ArithmeticException ex)
    {
      ergGGT = nenner.gcd(n); if (GGTAUSGABE) System.out.println("ggT3 ist " + ergGGT);
      throw ex;
    }
    BigInteger lambda = zaehler.multiply(inv).remainder(n);  // 8.8 % CPU
    if (lambda.signum() < 0) lambda = lambda.add(n);

    Paar_ECM rueck = new Paar_ECM(/*egal*/0,0);
    // x3 = lm^2 - x1 - x2
    rueck.x = lambda.modPow(ZWEI, n);  // 13.05% CPU
    if (rueck.x.signum() < 0) rueck.x = n.add(rueck.x);
    rueck.x = rueck.x.subtract(p1.x);  // 1.66 % CPU
    if (rueck.x.signum() < 0) rueck.x = n.add(rueck.x);
    rueck.x = rueck.x.subtract(p2.x);  // remainder ist teuer, vermeiden
    // y3 = -y1 + lm * (x1 - x3)
    rueck.y = lambda.multiply(p1.x.subtract(rueck.x)).remainder(n);  // 10.1% CPU
    if (rueck.y.signum() < 0) rueck.y = n.add(rueck.y);
    rueck.y = rueck.y.subtract(p1.y);  // remainder teuer; 1.6 % CPU

    // Arbeite mit positiven Werten !
    if (rueck.x.signum() < 0) rueck.x = n.add(rueck.x);
    if (rueck.y.signum() < 0) rueck.y = n.add(rueck.y);
    
    // Test:
    if (DEBUGPLUS)
    {
      teste_punkt(rueck);
    }

    return rueck;
  }

  // Fuehrt skalare Multipl. aus
  public final Paar_ECM multSkalar (BigInteger faktor, Paar_ECM p) throws Logik_Fehler
  {
    if (faktor.signum() < 0) throw new Logik_Fehler ("Skalar ist nicht >= 0");
    if (p.istNeutral()) return p;
    teste_punkt(p);

    Paar_ECM rueck = Paar_ECM.NEUTRAL;
    final int durchl = faktor.bitLength(); int weg = faktor.getLowestSetBit();
    for (int lauf = 0; lauf < (durchl-weg); ++lauf)
    {
      if (lauf > 0)  // Quadrieren
      {
        try
        {
          p = addieren (p, p); // = verdoppeln; das neutrale Element kann hier nicht entstehen !
        }
        catch (ArithmeticException ex)
        {
          return null;
        }
      }

      if (faktor.testBit(lauf+weg))
      {
        try
        {
          rueck = addieren (rueck, p);  // das neutrale Element kann entstehen
        }
        catch (ArithmeticException ex)
        {
          // System.out.println ("Addieren nicht möglich");
          return null;
        } // Ende try-catch
        if (rueck.istNeutral()) 
        {
          BigInteger tmp = BigInteger.ZERO;
          for (int i = 0; i <= lauf; ++i) if (faktor.testBit(i+weg)) tmp = tmp.setBit(i);
          System.out.println ("Zwischenergebnis: Ordnung ist " + tmp);
        }
      }
    }

    {
      // Noch Quadrierungen machen. ein ggT sollte hier nicht mehr zu erzielen sein
      for (int i = 0; i < weg && !rueck.istNeutral(); ++i)
      {
        try
        {
          rueck = addieren (rueck, rueck); // = verdoppeln; das neutrale Element kann hier nicht entstehen !
        }
        catch (ArithmeticException ex)
        {
          return null;
        }
      }
    }

    return rueck;  // Wert ermittelbar
  }

  // Testet, ob der Punkt auf der Kurve liegt, und gibt ggf. Fehlermeldung aus
  protected void teste_punkt (Paar_ECM p) throws Logik_Fehler
  {
    if (p.istNeutral()) return;  // neutrales Element liegt immer auf der Kurve

    BigInteger vergl = (p.x.modPow(DREI, n)).add(SIEBEN).remainder(n);
    if (vergl.signum() < 0) vergl = vergl.add(n);
    BigInteger poty = p.y.modPow(ZWEI, n);

    if (! vergl.equals(poty)) throw new Logik_Fehler(p + " liegt nicht auf der Kurve");
  }

  // Sucht eine Ordnung per giant-step-baby-step
  // basis^(g * m + b) = pkey, m ist Wurzel von einer Schranke, die polynomial sein sollte
  // basis^(g * m) == pkey * basis^-b, links giantStep, rechts babyStep
  public final BigInteger sucheBabyStepGiantStep (Paar_ECM pkey, BigInteger maxExponent) throws Logik_Fehler
  {
    if (pkey.istNeutral()) return BigInteger.ZERO;
    teste_punkt(pkey);

    // bestimmte Giant-Step
    Map<Paar_ECM, BigInteger> map_gst = new HashMap<Paar_ECM, BigInteger>();
    Paar_ECM gstb = multSkalar(maxExponent, basis); Paar_ECM aktuell = gstb;
    if (gstb == null) { System.out.println("ggt bei GS1"); return null; } // ggT
    map_gst.put(Paar_ECM.NEUTRAL, BigInteger.ZERO);
    map_gst.put(gstb, BigInteger.ONE);
    for (BigInteger lauf = ZWEI; lauf.compareTo(maxExponent) < 0; lauf  = lauf.add(BigInteger.ONE))
    {
      aktuell = addieren(aktuell, gstb); if (aktuell == null) { System.out.println("ggt bei GS2"); return null; } // ggT
      //System.out.println("gs nun: " + aktuell);
      if (map_gst.containsKey(aktuell)) { System.out.println("Schleife bei GiantStep erkannt, vorzeitiger Abbruch"); break; }
      map_gst.put(aktuell, lauf);
    }
    //System.out.println(map_gst.keySet());

    // bestimme Baby-Step
    BigInteger sammel = null;
    Paar_ECM bstb = new Paar_ECM(basis.x, basis.y); bstb.y = n.subtract(bstb.y); aktuell = pkey;
    for (BigInteger lauf = BigInteger.ZERO; lauf.compareTo(maxExponent) < 0; lauf = lauf.add(BigInteger.ONE))
    {
      //System.out.println("bs nun: " + aktuell);
      if (map_gst.containsKey(aktuell)) return map_gst.get(aktuell).multiply(maxExponent).add(lauf);  // Treffer
      aktuell = addieren(aktuell, bstb); if (aktuell == null) { System.out.println("ggt bei BS"); return null; } // ggT
    }
   
    return sammel;
  }

  // Legt die Kurve an, wählt zufällig einen privaten Schlüssel und ermittelt Endpunkt als public key. 
  // Versucht dann, den Logarithmus anhand Giant-Step-Baby-Step zu ermitteln
  public static void main (String [] args) throws Logik_Fehler {
    Bitcoin_log b = new Bitcoin_log();
    b.bestimmeP();
    b.teste_punkt(basis);
    // wähle privaten Schlüssel zufaellig aus
    int privateKey = Math.abs(new java.util.Random().nextInt()) % GRENZE_MAX;
    // bestimme oeffentlichen Schlüssel damit
    Paar_ECM pkey = b.multSkalar(BigInteger.valueOf(privateKey), b.basis);
    System.out.println("Private Key : " + privateKey + ", Public Key: " + pkey);
    // Versuche den privaten Schlüssel anhand des public key zu erraten, z.B. mit gsbs-Verfahren
    BigInteger erg = b.sucheBabyStepGiantStep(pkey, BigInteger.valueOf(GRENZE_MAX));
    if (erg != null) System.out.println("Private Key gefunden: " + erg);
    else System.out.println("Private key konnte nicht erraten werden");
  }

}

class Logik_Fehler extends Exception
{
  public Logik_Fehler(String wert) { super(wert); }
}