كنغر

خوارزمية بولارد كانغر (Pollard's Kangaroo) المُسرَّعة بواسطة GPU لحل مشكلة اللوغاريتم المنفصل للمنحنى الإهليلجي (ECDLP) على secp256k1.

الميزات

• 🖥️ GPU عبر المنصات — Vulkan (AMD, NVIDIA, Intel)، Metal (Apple Silicon)، DX12 (Windows) عبر wgpu
• 🦀 Rust نقي + WGSL — لا تبعية لـ CUDA، يتم تجميع شادرات الحوسبة في وقت التشغيل
• ⚡ نقاط مميزة (Distinguished Points) — كشف تصادم فعال مع ضبط تلقائي لبتات DP
• 🔄 خريطة النفي (Negation map) — تسريع بحوالي 1.29× عبر المسيرات الموجهة بـ Y-parity مع حراس دورة
• 🦘 كناغر متعددة المجموعات — قطعان tame، wild1، wild2 لزيادة احتمالية التصادم
• 🎯 قيود معيارية (Modular constraints) — إذا كان k ≡ R (mod M)، قلّص مساحة البحث بعامل M
• ⚙️ معايرة تلقائية — توقيت إرسال GPU وحجم مجموعة العمل يُضبطان عند بدء التشغيل
• 📊 معايير أداء مدمجة — --benchmark لاختبار العتاد، --save-benchmarks لتسجيل النتائج
• 📦 موفرو بيانات — مصادر ألغاز قابلة للتوصيل (تكامل boha لألغاز بيتكوين)
• 💻 حل احتياطي بواسطة CPU — حلّال CPU نقي للاختبار والمقارنة

لماذا هذا المشروع؟

معظم تطبيقات Kangaroo الحالية (JeanLucPons/Kangaroo، RCKangaroo، إلخ) تدعم فقط GPUs من NVIDIA عبر CUDA. يستخدم هذا التطبيق WebGPU/wgpu الذي يوفر حوسبة GPU عبر المنصات عبر Vulkan و Metal و DX12.

التثبيت

آرتش لينكس (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

من المصدر

git clone https://github.com/oritwoen/kangaroo
cd kangaroo
cargo build --release

مع مزود boha

cargo build --release --features boha

الاستخدام

kangaroo --pubkey <PUBKEY> --start <START> --range <BITS>

الوسائط

يجب تحديد --target أو --pubkey.

أمثلة

استخدام مزود البيانات (boha):

# حل لغز باستخدام بيانات boha (تلقائي: المفتاح العام، البداية، النطاق)
kangaroo --target boha:b1000/66

# تجاوز النطاق (ابحث في مجموعة فرعية أصغر)
kangaroo --target boha:b1000/66 --range 60

# عرض الألغاز المتاحة
kangaroo --list-providers

معاملات يدوية:

kangaroo \
    --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
    --start 8000000000 \
    --range 40

مع قيد معياري (k ≡ 37 mod 60):

kangaroo \
    --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
    --start 8000000000 \
    --range 40 \
    --mod-step 3c \
    --mod-start 25

هذا يقلل مساحة البحث بحوالي 60 مرة. مفيد عندما يكون هيكل المفتاح الجزئي معروفًا (مثل مفتاح تم إنشاؤه بنمط خطوة يمكن التنبؤ به).

كيف يعمل

خوارزمية بولارد كانغر تحل مشكلة اللوغاريتم المنفصل في وقت O(√n) حيث n هو نطاق البحث. تعمل على النحو التالي:

1. الكناغر الأليفة (Tame) تبدأ من نقطة معروفة وتقوم بقفزات عشوائية
2. الكناغر البرية (Wild) تبدأ من المفتاح العام المستهدف وتقوم بنفس النوع من القفزات
3. عندما يهبط كنغر بري وآخر أليف على نفس النقطة (تصادم)، يمكننا حساب المفتاح الخاص

تحسين النقاط المميزة (DP): بدلاً من تخزين كل النقاط التي تمت زيارتها، نخزن فقط النقاط التي تحتوي الإحداثي x على عدد محدد من البتات الصفرية الرائدة. هذا يقلل بشكل كبير من استخدام الذاكرة مع السماح باكتشاف التصادم.

الأداء

العمليات المتوقعة: ~2^(range_bits/2)

قم بتشغيل kangaroo --benchmark لاختبار عتادك دون لمس الملفات. استخدم kangaroo --benchmark --save-benchmarks لتحديث BENCHMARKS.md.

حالات الاستخدام

غير مفيد لـ:

• البحث عن مفتاح كامل 256 بت (مستحيل رياضيًا)
• القوة العمياء لعبارة مرور BIP39 (استخدم هجوم القاموس بدلاً من ذلك)
• ألغاز بدون معلومات جزئية عن المفتاح

استخدام المكتبة

use kangaroo::{KangarooSolver, GpuContext, GpuBackend, parse_pubkey, parse_hex_u256, verify_key};

fn main() -> anyhow::Result<()> {
    let pubkey = parse_pubkey("03...")?;
    let start = parse_hex_u256("8000000000")?;

    let ctx = pollster::block_on(GpuContext::new(0, GpuBackend::Auto))?;
    let mut solver = KangarooSolver::new(
        ctx,
        pubkey.clone(),
        start,
        40,  // range_bits
        12,  // dp_bits
        1024, // num_kangaroos
    )?;

    loop {
        if let Some(key) = solver.step()? {
            if verify_key(&key, &pubkey) {
                println!("Found: {}", hex::encode(&key));
                break;
            }
        }
    }

    Ok(())
}

موفرو البيانات

يدعم Kangaroo موفري بيانات خارجيين لمصادر الألغاز. يقوم المزودون بتوفير المفتاح العام ونطاق المفتاح وبيانات وصفية أخرى للغز.

boha (ميزة اختيارية)

boha يوفر بيانات ألغاز التشفير بما في ذلك لغز معاملة بيتكوين (b1000).

البناء مع دعم boha:

cargo build --release --features boha

الاستخدام:

# حل لغز معين
kangaroo --target boha:b1000/66

# عرض الألغاز القابلة للحل (غير المحلولة مع مفتاح عام معروف)
kangaroo --list-providers

يتحقق المزود من تجاوزات النطاق - لا يمكنك البحث خارج نطاق مفتاح اللغز.

البنية

src/
├── main.rs              # نقطة دخول CLI
├── lib.rs               # دخول المكتبة + Args + run()
├── solver.rs            # تنسيق حلال GPU
├── cli.rs               # أدوات CLI (التتبع، شريط التقدم)
├── benchmark.rs         # مجموعة معايير أداء مدمجة
├── modular.rs           # تحويل القيد المعياري
├── math.rs              # عمليات حسابية 256 بت، توليد قناع DP
├── convert.rs           # تحويلات Limb/بايت لـ GPU↔CPU
├── provider/
│   ├── mod.rs           # واجهة نظام المزود
│   └── boha.rs          # مزود boha (مقيد بالميزة)
├── cpu/
│   ├── cpu_solver.rs    # حلال CPU نقي (اختبار/مقارنة)
│   ├── dp_table.rs      # كشف تصادم النقاط المميزة
│   └── init.rs          # تهيئة الكناغر + جداول القفز
├── crypto/
│   └── mod.rs           # أغلفة k256/secp256k1
├── gpu/
│   ├── pipeline.rs      # إعداد خط أنابيب الحوسبة
│   └── buffers.rs       # إدارة مخازن GPU
├── gpu_crypto/
│   ├── context.rs       # سياق GPU + اختيار الخلفية
│   └── shaders/         # مكتبة شادرات WGSL
│       ├── field.wgsl   # عمليات حقل secp256k1
│       └── curve.wgsl   # عمليات نقطية جاكوبية
└── shaders/
    └── kangaroo_affine.wgsl  # شادر حوسبة كانغر الرئيسي

المتطلبات

• Rust 1.70+
• GPU يدعم Vulkan (AMD, NVIDIA, Intel) أو Metal (macOS)
• على لينكس مع AMD RADV، يجب Mesa 25.x أو أحدث (الإصدارات الأقدم من Mesa قد تتعطل على الفهرسة الديناميكية WGSL في حلقات الشادر)
• برامج تشغيل GPU مثبتة

الترخيص

رخصة MIT - راجع LICENSE للتفاصيل.

المشاريع ذات الصلة

• JeanLucPons/Kangaroo - تطبيق CUDA (NVIDIA فقط)
• RCKangaroo - تطبيق CUDA (NVIDIA فقط)
• boha - مكتبة بيانات ألغاز التشفير والمكافآت