منحنى Ed25519

الأعداد القياسية والنقاط والعملية الوحيدة التي يقوم عليها Monero كله

لماذا منحنى

نحتاج إلى "دالة أحادية الاتجاه بقفل": من السر يسهل الحصول على شيء علني، لكن ليس العكس. ونريد إجراء عمليات حسابية على الأشياء العلنية: جمعها وضربها في أعداد. والمنحنى الإهليلجي يقدّم ذلك بالضبط.

يستخدم Monero المنحنى نفسه الذي تستخدمه تواقيع Ed25519 (Daniel J. Bernstein وآخرون): منحنى Edwards ملتوٍ

النقطة زوج من الأعداد (x, y) يحقق المعادلة. وكل الحسابات تجري بترديد العدد الأولي p، لذا فـ "المنحنى" في الحقيقة سحابة من نحو 2²⁵⁵ نقطة منفصلة.

جمع النقاط

يمكن جمع النقاط: P + Q = R، حيث R أيضًا على المنحنى. وعلى منحنيات Edwards تغطي صيغة واحدة جميع الحالات (وهذا مريح وآمن):

يتصرف هذا الجمع كالجمع العادي: فهو تبديلي وتجميعي، وله "صفر" — النقطة (0, 1) — ولكل نقطة نظير (−x, y).

الضرب في عدد

ضرب نقطة في x يعني جمعها مع نفسها x مرة. وبالطبع لا أحد يجمع 2²⁵² مرة: طريقة "المضاعفة والجمع" لا تحتاج إلا إلى نحو 256 مضاعفة ونحو 128 عملية جمع.

نقطة الأساس G والرتبة l

يستخدم الجميع نقطة الأساس نفسها G المتفق عليها مسبقًا. اضرب G في 1، 2، 3، … وبعد l خطوة تعود إلى الصفر:

l هي رتبة الزمرة الجزئية المولَّدة بـ G. وعلى المنحنى ثمانية أضعاف هذا العدد من النقاط إجمالًا (8·l)؛ ويُسمى 8 العامل المرافق (cofactor). وهذا العامل مصدر عدة دقائق في Monero: سترى العامل 8 في صيغ العناوين لمرة واحدة، وفي 2017 كان من الممكن أن تنتج "النقاط ذات الرتبة الصغيرة" عدة key images لمخرج واحد (أُصلح بالتحقق من l·I = 0).

لماذا يصلح هذا للمفاتيح

خذ x عشوائيًا — هذا مفتاح خاص. واحسب P = x·G — هذا مفتاح عام. نشر P آمن. والأهم أن النقاط تدعم الجبر:

المتطابقة الثانية أساس تبادل مفاتيح Diffie–Hellman: أليس تعرف a وترى B = b·G؛ وبوب يعرف b ويرى A = a·G. كلاهما يستطيع حساب النقطة نفسها a·B = b·A = ab·G، أما الغريب فلا. وعلى هذا تُبنى العناوين لمرة واحدة.

والمتطابقة الأولى أساس التزامات Pedersen: يمكن جمع المبالغ المخفية في النقاط.

ترميز النقطة في 32 بايتًا

تُخزَّن النقطة بشكل مضغوط: يُكتب الإحداثي y (255 بتًا، بترتيب little-endian) وتوضع زوجية x في البت الأعلى من البايت الأخير. ويُستعاد x من y عبر معادلة المنحنى (حتى الإشارة — التي يعطيها البت). هذه هي البايتات الـ32 التي تراها بالنظام الست عشري حين تنظر إلى مفتاح عام في Monero.

على سبيل المثال، تُكتب نقطة الأساس G هكذا:

5866666666666666666666666666666666666666666666666666666666666666

(إحداثيها y = 4/5 mod p، وx زوجي).

الشيفرة

تنفيذ مصغّر بلغة JavaScript باستخدام BigInt — من xmrcrypto.js، الذي تستخدمه كل أدوات هذا الموقع:

const P = (1n << 255n) - 19n;
const L = (1n << 252n) + 27742317777372353535851937790883648493n;
const D = mod(-121665n * inv(121666n));

// النقاط بالإحداثيات الموسّعة (X:Y:Z:T)، x = X/Z، y = Y/Z
function add(p, q) {
  const A = mod((p.Y - p.X) * (q.Y - q.X));
  const B = mod((p.Y + p.X) * (q.Y + q.X));
  const C = mod(2n * D * p.T * q.T);
  const Dd = mod(2n * p.Z * q.Z);
  const E = B - A, F = Dd - C, G = Dd + C, H = B + A;
  return { X: mod(E * F), Y: mod(G * H), Z: mod(F * G), T: mod(E * H) };
}

// الضرب القياسي: المضاعفة والجمع
function mul(k, p) {
  let r = ZERO, q = p;
  while (k > 0n) { if (k & 1n) r = add(r, q); q = add(q, q); k >>= 1n; }
  return r;
}