<?php
/* SECURE DEMO ONLY — NOT FOR REAL KEYS
 * Baby-Step Giant-Step over a SMALL window on secp256k1
 * Requires: ext-gmp
 * Limits: max window = 2^24 (~16.7M); memory ~ sqrt(window)
 * Use only with self-made small d for education/testing.
 */

ini_set('display_errors', '1'); error_reporting(E_ALL);

function g($x){ return is_string($x) ? gmp_init($x, 0) : $x; } // auto base (0x... ok)
function mod($a,$p){ $r = gmp_mod($a,$p); return gmp_sign($r)<0? gmp_add($r,$p):$r; }
function inv($a,$p){ $a = mod($a,$p); $ii = gmp_invert($a,$p); return $ii===false? null:$ii; }

function inf(){ return ['inf'=>true]; }
function is_inf($P){ return isset($P['inf']) && $P['inf']===true; }
function norm($P,$p){ return is_inf($P)?$P:['x'=>mod($P['x'],$p),'y'=>mod($P['y'],$p)]; }

function eqP($A,$B){
  if (is_inf($A) && is_inf($B)) return true;
  if (is_inf($A) || is_inf($B)) return false;
  return gmp_cmp($A['x'],$B['x'])==0 && gmp_cmp($A['y'],$B['y'])==0;
}
function negP($P,$p){ return is_inf($P)?$P:['x'=>$P['x'],'y'=>mod(gmp_neg($P['y']),$p)]; }

function addP($P,$Q,$a,$p){
  if (is_inf($P)) return $Q;
  if (is_inf($Q)) return $P;

  if (gmp_cmp($P['x'],$Q['x'])==0) {
    if (gmp_cmp(mod(gmp_add($P['y'],$Q['y']),$p), 0)==0) return inf(); // P + (-P) = O
    // else doubling
  }

  if (!eqP($P,$Q)) {
    $num = mod(gmp_sub($Q['y'],$P['y']),$p);
    $den = mod(gmp_sub($Q['x'],$P['x']),$p);
    $invden = inv($den,$p); if ($invden===null) return inf();
    $m = mod(gmp_mul($num,$invden),$p);
  } else {
    // m = (3x^2 + a)/(2y)
    $num = mod(gmp_add(gmp_mul(3,gmp_mul($P['x'],$P['x'])),$a),$p);
    $den = mod(gmp_mul(2,$P['y']),$p);
    $invden = inv($den,$p); if ($invden===null) return inf();
    $m = mod(gmp_mul($num,$invden),$p);
  }

  $x3 = mod(gmp_sub(gmp_sub(gmp_mul($m,$m),$P['x']),$Q['x']),$p);
  $y3 = mod(gmp_sub(gmp_mul($m,gmp_sub($P['x'],$x3)),$P['y']),$p);
  return ['x'=>$x3,'y'=>$y3];
}
function subP($P,$Q,$a,$p){ return addP($P,negP($Q,$p),$a,$p); }

function mulP($k,$P,$a,$p){
  if ($k < 0) return mulP(gmp_neg($k), negP($P,$p), $a,$p);
  $R = inf(); $N = $P; $k = gmp_init($k,10);
  while (gmp_cmp($k,0)>0){
    if (gmp_testbit($k,0)) $R = addP($R,$N,$a,$p);
    $N = addP($N,$N,$a,$p);
    $k = gmp_div_q($k,2);
  }
  return $R;
}

function hexstr($g){ return gmp_strval($g,16); }
function keyP($P){ return is_inf($P)?'INF':(hexstr($P['x']).',' . hexstr($P['y'])); }

/**
 * BSGS over a limited window:
 * Solve P = d*G, with d in [offset, offset + range - 1]
 * range = 2^bits, bits <= 24 (hard limit)
 */
function ecdlp_bsgs_window($G,$P,$a,$p,$offset,$bits){
  $MAX_BITS = 256;
  if ($bits < 1 || $bits > $MAX_BITS) throw new Exception("bits must be 1..$MAX_BITS");
  $range = gmp_pow(2,$bits);

  // Shift: H = P - offset*G  => H = d' * G , d' in [0..range-1]
  $H = subP($P, mulP($offset,$G,$a,$p), $a,$p);
  $H = norm($H,$p);

  $m = gmp_add(gmp_sqrt($range), gmp_init(1)); // ceil(sqrt(range))
  $table = [];

  // baby: j*G
  $cur = inf();
  for ($j = gmp_init(0); gmp_cmp($j,$m) < 0; $j = gmp_add($j,1)){
    if (gmp_cmp($j,0)==0) $cur = inf();
    elseif (gmp_cmp($j,1)==0 && is_inf($cur)) $cur = $G;
    else $cur = is_inf($cur) ? $G : addP($cur,$G,$a,$p);
    $table[keyP(norm($cur,$p))] = gmp_strval($j,10);
  }

  $mG = mulP($m,$G,$a,$p);
  $gamma = $H;

  for ($i = gmp_init(0); gmp_cmp($i,$m) <= 0; $i = gmp_add($i,1)){
    $k = keyP($gamma);
    if (isset($table[$k])){
      $j = gmp_init($table[$k],10);
      $dprime = gmp_add(gmp_mul($i,$m), $j);
      if (gmp_cmp($dprime,$range) < 0){
        $d = gmp_add($offset, $dprime);
        // verify
        if (eqP(mulP($d,$G,$a,$p), $P)) return $d;
      }
    }
    $gamma = subP($gamma,$mG,$a,$p);
    $gamma = norm($gamma,$p);
  }
  return null;
}

/* ====== secp256k1 params ====== */
$p = g("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");
$a = g("0");  $b = g("7");
$G = [
  'x'=>g("0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"),
  'y'=>g("0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8")
];

/* ====== simple HTML form ====== */
function h($s){ return htmlspecialchars($s,ENT_QUOTES,'UTF-8'); }
$defaults = [
  'Px' => '',
  'Py' => '',
  'bits' => '256',      // search window: 2^bits  (max 24)
  'offset' => '0'      // decimal offset
];

$inp = [];
foreach ($defaults as $k=>$v){ $inp[$k] = isset($_POST[$k])? trim($_POST[$k]) : $v; }

$result = null; $err = null;

if ($_SERVER['REQUEST_METHOD']==='POST'){
  try{
    if ($inp['Px']==='' || $inp['Py']==='') throw new Exception("مختصات P را وارد کنید (هگز با 0x... یا دسیمال).");

    $P = ['x'=>g($inp['Px']), 'y'=>g($inp['Py'])];

    // Curve check: y^2 == x^3 + 7 (mod p)
    $lhs = mod(gmp_powm($P['y'],2,$p),$p);
    $rhs = mod(gmp_add(gmp_powm($P['x'],3,$p),$b),$p);
    if (gmp_cmp($lhs,$rhs)!=0) throw new Exception("P روی منحنی secp256k1 نیست.");

    $bits = intval($inp['bits']);
    $offset = g($inp['offset']);

    $d = ecdlp_bsgs_window($G,$P,$a,$p,$offset,$bits);
    if ($d===null){
      $result = "در بازهٔ مشخص‌شده چیزی پیدا نشد. بازه (bits/offset) را تغییر بده.";
    } else {
      $result = "d (فقط در بازهٔ محدود جستجو شده) = " . gmp_strval($d);
    }
  } catch (Throwable $e){
    $err = $e->getMessage();
  }
}
?>
<!doctype html>
<html lang="fa" dir="rtl">
<head>
  <meta charset="utf-8">
  <title>secp256k1 — BSGS (Windowed, Safe Demo)</title>
  <style>
    body{font-family:tahoma,arial,sans-serif;max-width:820px;margin:32px auto;padding:0 16px;line-height:1.7}
    input{width:100%;padding:10px;margin:6px 0;border:1px solid #ddd;border-radius:8px}
    button{padding:10px 16px;border:none;border-radius:8px;background:#222;color:#fff;cursor:pointer}
    .card{border:1px solid #eee;border-radius:12px;padding:16px;margin-top:12px;background:#fafafa}
    small{color:#666}
    code{background:#f3f3f3;padding:2px 6px;border-radius:6px}
  </style>
</head>
<body>
  <h2>secp256k1 — جستجوی آموزشی d در بازهٔ کوچک (BSGS Window)</h2>

  <form method="post" class="card">
    <label>Px (hex یا decimal):</label>
    <input name="Px" placeholder="0x..." value="<?=h($inp['Px'])?>" required>

    <label>Py (hex یا decimal):</label>
    <input name="Py" placeholder="0x..." value="<?=h($inp['Py'])?>" required>

    <label>bits (حداکثر 24):</label>
    <input name="bits" type="number" min="1" max="256" value="<?=h($inp['bits'])?>" required>

    <label>offset (شروع بازه، دسیمال):</label>
    <input name="offset" value="<?=h($inp['offset'])?>" required>

    <button type="submit">جستجو در بازه</button>
    <div><small>این ابزار فقط در بازهٔ <code>[offset, offset + 2^bits - 1]</code> جستجو می‌کند و برای کلیدهای واقعی کارایی ندارد.</small></div>
  </form>

  <?php if ($err): ?>
  <div class="card" style="border-color:#f99;background:#fff6f6"><strong>خطا:</strong> <?=h($err)?></div>
  <?php endif; ?>

  <?php if ($result): ?>
  <div class="card"><strong>نتیجه:</strong> <?=h($result)?></div>
  <?php endif; ?>

  <div class="card">
    <strong>راهنمای تست امن:</strong>
    <ol>
      <li>یک عدد کوچک (مثلاً <code>d=123456</code>) بردار و با تابعی بیرونی <code>P = d·G</code> بساز (یا از همین کد، بخش <em>mulP</em> را موقتاً برای ساخت P استفاده کن).</li>
      <li>مختصات <code>P</code> را اینجا وارد کن، <code>offset=0</code> و <code>bits</code> را طوری بگذار که بازه شامل d باشد (برای d=123456، مثلاً bits=17).</li>
      <li>کد باید همان d را در بازهٔ محدود برگرداند.</li>
    </ol>
    <p><small>پیچیدگی زمانی/حافظه ≈ \(O(2^{bits/2})\). برای bits=24 حدود 4096 baby-step ذخیره می‌شود.</small></p>
  </div>

  <div class="card">
    <strong>تذکر مهم امنیتی:</strong>
    <ul>
      <li>ECDLP روی secp256k1 با بازهٔ کامل مرتبهٔ گروه غیرعملی است؛ این ابزار صرفاً برای آموزش در بازه‌های کوچک است.</li>
      <li>استفادهٔ غیرمجاز/غیراخلاقی ممنوع است. این کد هیچ‌گاه توانایی شکستن کلیدهای واقعی را ندارد.</li>
    </ul>
  </div>
</body>
</html>
