double and add algorithmus für elliptische kurven/ integer binär darstellen

[andreas2505]

hallo,

ich möchte gerne den double and add algorithmus für elliptische kurven implementieren. (siehe Anhang)
Dazu muss ich aber einen integer Wert binär darstellen und weiß nicht so recht, wie ich das umsetzen soll. Weiterhin muss ich in dann auch noch halbieren und abrunden...
Steht ja alles im Algorithmus (bis zu dem Kästchen)

Kann mir jemand sagen, wie ich das binär darstellen kann und wie ich dann den Schritt berechnen kann, in dem der Wert durch zwei geteilt und abgerundet wird?

 

[faetzminator]

Kann mir jemand sagen, wie ich das binär darstellen kann und wie ich dann den Schritt berechnen kann, in dem der Wert durch zwei geteilt und abgerundet wird?

String binValue = Integer.toBinaryString(x)

Was meinst du mit abrunden? Wenn du in Java 3 / 2 (als int) teilst, dann kriegst du automatisch 1, da von 1.5 das .x abgeschnitten wird.

 

[andreas2505]

naja das steht doch im algorithmus, im anhang, wie ich das meine.
Aber wenn das ein String ist, kann ich doch damit nicht den restlichen Algorihtmus druchführen, oder?
Wenn ja wie?

 

[faetzminator]

Ich muss zugeben, dass ich die Aufgabe nur teilweise verstehe.
Na klar, du kannst z.B. [c]charAt(x)[/c] oder [c]toCharArray()[/c] mit [c]- '0'[/c] verwenden. Ansonsten kann man den String natürlich auch einfach mit [c]Integer.parseInt(str)[/c] wieder in einen int parsen. Der Grund, warum hier ein String zurückgegeben wird, wird wohl die begrenzte Datenmenge des int sein.
Probier einfach mal, das zu programmieren und schreib bei Schwierigkeiten wieder rein.

 

[Dekker]

Überleg mal in welchem Format Integer in Java gespeichert werden. Richtig, die sind binär kodiert.

 

[andreas2505]

Also das hab ich bis jetzt!

An den Stellen wo die Fragezeichen sind, kann ich das aus dem Algorithmus (siehe oben ) nicht umsetzen

public EPoint mult(BigInteger n, EllipticCurve ec) {
            ECPoint q = this;
            ECPoint r = POINT_INFINITY;
            
            while (n.bitLength() > 0) {
                if (???) {
                    r = r.add(q, ec);
                }
                q = q.add(q);
                n = ???;
                if (n.bitLength() > 0) {
                    ????
                }
            }
            return r;
        }

Wäre super,wenn mir jemand an diesen Stellen helfen kann...

 

[andreas2505]

kann mir denn gar keiner weiterhelfen???

Die ganze Sache mit elliptischen Kurven brauch eigentlich nicht betrachtet werden. Es geht eigentlich nur um die 3 Stellen mit ????

1. wie frage ich n=1 (mod 2) ab???
2. wie mache ich n=abgerundet(n/2)???
3. wie kann ich wieder zu einem Schritt zurückkehren???

steht alles im Algorithmus oben..., weiß halt nicht wie ichs umsetzen soll

 

[faetzminator]

1. wie frage ich n=1 (mod 2) ab???

n=1 (mod 2)? Also Modulo macht man mit [c]%[/c]. Also wie [c]3 + 2 // 5[/c] einfach [c]3 % 2 // 1[/c]

2. wie mache ich n=abgerundet(n/2)???

Da du mit int's arbeitest, wird der Nachkommawert - wie bereits von mir erklärt - abgeschnitten. Du musst also nichts aufrufen.

3. wie kann ich wieder zu einem Schritt zurückkehren???

Das macht er auch ohne deine if-Abfrage (Z11). Aber er würde die Schleife solange ausführen, wie [c]n.bitLength() > 0[/c] ist. Also musst du n in der Schleife noch bearbeiten oder ein anderes Abbruchkriterium finden.

 

[andreas2505]

n=1 (mod 2)? Also Modulo macht man mit % . Also wie 3 + 2 // 5 einfach 3 % 2 // 1

Aber das ist doch eine schreibweise von n in binärer form (siehe Algorithmus). Da kann man das doch nicht so machen oder?

Also musst du n in der Schleife noch bearbeiten oder ein anderes Abbruchkriterium finden.

Wie genau soll ich denn n noch bearbeiten oder was für ein Kriterium soll ich wählen?

 

[Ariol]

Aber das ist doch eine schreibweise von n in binärer form (siehe Algorithmus). Da kann man das doch nicht so machen oder?

Wenn die binäre Form als String vorliegt kann man das letzte Zeichen überprüfen:

n%2==0 --> letztes Zeichen = '0'
n%2==1 --> letztes Zeichen = '1'
n/2 = letztes Zeichen des Strings abschneiden.

 

[andreas2505]

public ECPoint mult(Integer n, EllipticCurve ec) {
            ECPoint q = this;
            ECPoint r = POINT_INFINITY;
            
            String binValue = Integer.toBinaryString(n);
            
            while (n > 0) {
                if (n%2==1) {
                    r = r.add(q, ec);
                }
                q = q.add(q, ec);
                n = n/2;
            }
            
            return r;
        }

so hab ichs jetzt. Es kommen zwar keine Fehler raus, aber auch nicht die richtige Werte!

Irgendwas muss also nicht richtig sein

 

[Dekker]

Zeig mal deine Add methode. Rechnet ihr bei euch mit Galois Feldern?

 

[andreas2505]

public ECPoint add(ECPoint b, EllipticCurve e) {
        
        if (this.equals(POINT_INFINITY)) {
            return b;
        }
        if (b.equals(POINT_INFINITY)) {
            return this;
        }
        if (this.x.equals(x)) {
            if (this.y.equals(y.negate())) {
                return POINT_INFINITY;
            }
        }
        
        BigInteger lambda;
        
        if (this.equals(b)) {
            System.out.println("+");
            lambda = BigInteger.valueOf(3).multiply(this.x).multiply(this.x).add(e.a).multiply(BigInteger.valueOf(2).multiply(this.y).modInverse(e.field.p)).mod(e.field.p);
        }
        else {
            lambda = b.y.subtract(this.y).multiply(b.x.subtract(this.x)).modInverse(e.field.p).mod(e.field.p);
        }
        
        BigInteger xNeu = lambda.multiply(lambda).subtract(this.x).subtract(b.x).mod(e.field.p);  
        BigInteger yNeu = lambda.multiply(this.x.subtract(xNeu)).subtract(this.y).mod(e.field.p);  
  
        return new ECPoint(xNeu, yNeu);  
            
    }

Die ganze Rechnung basiert auf elliptischen Kurven in einem finiten Feld Fp

die add Methode funktioniert, die wurde getestet.

EDIT:

Naja, obwohl, bei einigen Punktion funktioniert sie doch irgendwie nicht...

 

[systemn]

    public static boolean is0(int val, int i) {
        while (i-- > 1) {
            val >>= 1;
        }
        return (val & 1) == 0;
    }

 

[andreas2505]

ich verstehe nicht, was das letzte Posting mir sagen soll