// --------------------------------------------------------------------
// ECDLP solver using Pohlig-Hellman algorithm to reduce problem
//         size and Pollard's rho algorithm to solve ECDLP over sub
//         -group (+ a routine to brute-force group with small order
//         to avoid pb with order 2...)
//
//  
//   Pollard's rho part is a (very) modified version of 'Miracl/index.c'(DLP)
//   You will be able to find more info reading HoAC or any others
//   good crypto-papers... :)  
//                                                    Amenesia//TKM! 
// --------------------------------------------------------------------
// Info: You have to use Miracl to be able to compile it...
// ATM parameters permit to solve the ECDLP used in pDriLl's keygenme #5
// but it's quite easy to modify it in order to solve your own ECDLP
// (is well commented in a bad english :p)
// --------------------------------------------------------------------
                           
#include <stdlib.h>
#include <conio.h>
#include "miracl.h"

#define NPRIMES 10
static miracl *mip;
static big order, rholim;

 

 // --------------------------- Pollard rho ---------------------------

void iterate(epoint* X,epoint* Q,epoint* R,big a,big b)
{ // Random walk...
  //         = a(i)       if X in S1
  //  a(i+1) = a(i) + 1   if X in S2 
  //         = 2*a(i)     if X in S3
  //
  //         = b(i)       if X in S2
  //  b(i+1) = b(i) + 1   if X in S1 
  //         = 2*b(i)     if X in S3
  //
  //    X(i)   = a(i)*Q + b(i)*R
  //    X(i+1) = f(X(i))
  //
  // BTW: the criteria used by Dimedrol (ecdlp.solver) is quite
  //       good (simple and fast to compute) so i take the same :)
  
    big p = mirvar(0);    
    epoint_get(X,p,p);

    if (remain(p,7)>4)
    {  
        ecurve_add(Q,X);
        incr(a,1,a);
        if (compare(a,order)==0) zero(a);
        mirkill(p);       
        return;
    }
    if (remain(p,7)>2) 
    {     
        ecurve_add(X,X);
        premult(a,2,a);
        if (compare(a,order)>=0) subtract(a,order,a);
        premult(b,2,b);
        if (compare(b,order)>=0) subtract(b,order,b);
        mirkill(p);               
        return;
    }       
    ecurve_add(R,X);
    incr(b,1,b);
    if (compare(b,order)==0) zero(b);
    mirkill(p);   
}

 

// To avoid endless loops...
void ecdlpbf(epoint* Q,epoint* R,big k)
{
    epoint* T = epoint_init();
    copy(order,k);
    negify(k,k);
    do
    {
      incr(k,1,k);
      ecurve_mult(k,Q,T);      
    } while (!epoint_comp(T,R));
    epoint_free(T);
}


void rho(epoint* Q,epoint* R,big k)
{ // Find ax,ay,bx and by with: ax*Q + bx*R == ay*Q + by*R
  // So : (ax-ay)*R = (by-bx)*Q
  // ECDLP => k exists such as k*R = Q
  // So: (ax-ay) = (by-bx)*k mod order
  //    k = (ax-ay)*(by-bx)^1 mod order
  // BTW: check if (by-bx) is inversible
  //      (order is prime so (by-bx) is 
  //       inversible <=> (by-bx) != 0)
  
    long rr,i;
    big ax,bx,ay,by,m,n;
    epoint* Y = epoint_init();
    epoint* X = epoint_init();
    m=mirvar(0);
    n=mirvar(0);    
    ax=mirvar(0);
    bx=mirvar(0);
    ay=mirvar(0);
    by=mirvar(2);
   
    if (compare(rholim,order)>=0) 
    {
        ecdlpbf(Q,R,k);
    }
    else 
    { 
        do
            {
                rr=1L;    
                bigrand(order,ay);      
                bigrand(order,by);        
                ecurve_mult2(ay,Q,by,R,Y);
                do
                { // Search a collision...
                                epoint_copy(Y,X);
                                copy(ay,ax);
                                copy(by,bx);
                                rr*=2;
                                for (i=1;i<=rr;i++)
                                {
                                  iterate(Y,Q,R,ay,by);
                                  if (epoint_comp(X,Y)) break;
                                }
                } while (!epoint_comp(X,Y));
            } while (compare(bx,by)==0);
 
             subtract(ay,ax,m);
             if(size(m)<0){add(m,order,m);}
             subtract(bx,by,n); 
             if(size(m)<0){add(m,order,m);}                
             xgcd(n,order,n,n,n); 
             mad(m,n,n,order,order,k);  

 // I don't know why but it seems that
 //   -k*A != (-k+ord(A))*A  
 // If you are able to explain me why
 // feel free to contact me... :)
            
 ecurve_mult(k,Q,X);      
 if (!epoint_comp(X,R)){ subtract(k,order,k); }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
 ecurve_mult(k,Q,X);  
 if (!epoint_comp(X,R)){ printf("Error !!!"); } 
   }    
   // --------------------                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                 
    epoint_free(Y);
    epoint_free(X);
    mirkill(by);
    mirkill(ay);
    mirkill(bx);
    mirkill(ax);
}

 // --------------------------- End Pollard rho ---------------------------