مشاركة Shamir للسر: رياضيات كثيرات الحدود

تشفّر مشاركة الأسرار لشامير (1979) السر على أنه المقطع الصادي (f(0)) لكثيرة حدود عشوائية من الدرجة (k-1) فوق حقل منتهٍ. تحدد أي k نقاط كثيرة الحدود تحديدًا وحيدًا (باستخدام استيفاء لاغرانج)، بينما لا تكشف أقل من k نقاط شيئًا.

لمشاركة السر S بعتبة k بين n من الأطراف: اختر عددًا أوليًا p > S وn. اختر معاملات عشوائية a_1, ..., a_{k-1}. عرّف f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). يتلقى الطرف i الحصة (i, f(i)).

السر S=7، وp=17، وk=2 (كثيرة حدود خطية). اختر a_1=3. ‏f(x)=7+3x mod 17. الحصص: (1,10)، (2,13)، (3,16). تحدد أي نقطتين المستقيم. ‏f(0)=7. نقطة واحدة بمفردها: عدد لا نهائي من المستقيمات المحتملة، ولا تكشف أي معلومات عن S.

بالنظر إلى k نقاط (x_1,y_1),...,(x_k,y_k)، أعد بناء f(0) باستخدام لاغرانج: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. تُجرى جميع العمليات الحسابية بترديد p. لا تستخدم الفاصلة العائمة — إعادة بناء دقيقة فوق الحقل المنتهي.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

بالنسبة إلى k-1 حصة، يوجد كثير حدود واحد فقط من الدرجة k-1 يمر عبر تلك النقاط k-1 لكل قيمة سر ممكنة S. لذلك، عند معرفة k-1 حصة، تكون كل قيمة لـ S ضمن [0, p-1] متساوية الاحتمال — ولا تُكشف أي معلومات.

يجب أن يكون p أكبر من السر ومن n. ومن الخيارات الشائعة: p = 2^127-1 (عدد أولي من نوع Mersenne) للأسرار ذات 128 بت. يضمن ذلك أن تتسع جميع الحصص في 128 بت وأن تكون العمليات الحسابية فعّالة. ويمكن بدلاً من ذلك استخدام p = 2^521-1 للأسرار ذات 512 بت.

لا توفر SSS الأساسية أي سلامة للحصص؛ إذ يمكن لمساهم خبيث تقديم حصة زائفة، مما يؤدي إلى إعادة بناء سر خاطئ. تنشر Feldman VSS (Verifiable Secret Sharing) التزامات على الصورة g^{a_i} mod p، مما يتيح التحقق من الحصص من دون كشف كثير الحدود.

يمكن تحديث الحصص دورياً: يُولَّد كثير حدود جديد بالسر نفسه S، ثم تُوزَّع حصص جديدة، وتصبح الحصص القديمة غير صالحة. فإذا اخترق مهاجم أحد المساهمين بعد التحديث، فلن تفيده الحصة القديمة. ويُستخدم ذلك في أنظمة إدارة المفاتيح طويلة الأمد.

ssss (سطر أوامر Linux)، وpython-secret-sharing، ويستخدم hashicorp/vault تقنية SSS لآلية الختم الخاصة به، كما تستخدم محفظة Trezor للأجهزة تقنية SSS لنسخ احتياطي من بذرة المحفظة (SLIP-39). وتعمل جميعها على حقول أولية كبيرة.

تتطلب SSS موزّعاً موثوقاً لتوليد الحصص وتوزيعها، إذ يعرف الموزّع السر. أما السيناريو الذي لا يتوفر فيه موزّع فيتطلب DKG (Distributed Key Generation). تكشف إعادة البناء السر لمن يملك k حصص — ويمكن تجنب ذلك باستخدام MPC أو التوقيعات ذات العتبة.

في مشاركة أسرار Shamir من النوع (3,5)، ما الحد الأدنى لعدد الحصص اللازمة لإعادة بناء السر؟

ترمّز SSS الخاصة بـ Shamir الأسرار على هيئة مقاطع تقاطع كثير الحدود مع محور y. وتستعيد استيفاءات Lagrange السر من k حصص. وتوفر أمناً مثالياً قائماً على نظرية المعلومات عند امتلاك أقل من k حصة. التالي: المشاركة المرئية والمشاركة الإضافية.