Shamir का Secret Sharing: बहुपद का गणित

Shamir का गुप्त साझाकरण (1979) सीमित क्षेत्र पर यादृच्छिक (k-1) घात वाले बहुपद के y-अंतःखंड (f(0)) के रूप में गुप्त मान को कूटबद्ध करता है। कोई भी k बिंदु बहुपद को विशिष्ट रूप से निर्धारित करते हैं (लैग्रांज अंतर्वेशन); k से कम बिंदु कुछ भी प्रकट नहीं करते।

n सहभागियों के बीच सीमा k वाला गुप्त मान S साझा करने के लिए: S और n से बड़ा एक अभाज्य p चुनें। यादृच्छिक गुणांक 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। सभी अंकगणितीय क्रियाएँ मॉड्यूलर होती हैं। फ़्लोटिंग-पॉइंट नहीं — सीमित क्षेत्र पर सटीक पुनर्निर्माण।

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 हिस्सों की जानकारी होने पर [0, p-1] में S का प्रत्येक मान समान रूप से संभावित रहता है — कोई जानकारी प्रकट नहीं होती।

p का मान गुप्त मान और n दोनों से बड़ा होना चाहिए। सामान्य विकल्प: 128-बिट गुप्त मानों के लिए p = 2^127-1 (मर्सेन अभाज्य)। इससे सभी हिस्से 128 बिट में समा जाते हैं और गणना कुशल रहती है। वैकल्पिक रूप से, 512-बिट गुप्त मानों के लिए p=2^521-1 का उपयोग करें।

मूल SSS में हिस्से की अखंडता की कोई व्यवस्था नहीं होती: कोई दुर्भावनापूर्ण हिस्सेदार गलत हिस्सा दे सकता है, जिससे गुप्त मान का गलत पुनर्निर्माण हो सकता है। Feldman VSS (सत्यापन योग्य गुप्त साझाकरण) g^{a_i} mod p की प्रतिबद्धताएँ प्रकाशित करता है, जिससे बहुपद को प्रकट किए बिना हिस्सों का सत्यापन किया जा सकता है।

हिस्सों को समय-समय पर नवीनीकृत किया जा सकता है: उसी गुप्त मान S वाला नया बहुपद बनाएँ, नए हिस्से वितरित करें और पुराने हिस्से अमान्य हो जाएँगे। नवीनीकरण के बाद किसी हिस्सेदार के तंत्र में सेंध लगाने वाले हमलावर को पुराना हिस्सा बेकार मिलेगा। इसका उपयोग लंबे समय तक चलने वाली कुंजी-प्रबंधन प्रणालियों में किया जाता है।

ssss (Linux आदेश-पंक्ति), python-secret-sharing, hashicorp/vault अपने सील तंत्र के लिए SSS का उपयोग करता है, और Trezor हार्डवेयर बटुआ बटुए के बीज के बैकअप के लिए SSS (SLIP-39) का उपयोग करता है। ये सभी बड़े अभाज्य क्षेत्रों पर काम करते हैं।

SSS में हिस्से बनाने और वितरित करने के लिए एक विश्वसनीय वितरक आवश्यक होता है, और वितरक गुप्त मान जानता है। वितरक के बिना काम करने वाली स्थिति के लिए DKG (वितरित कुंजी निर्माण) आवश्यक है। पुनर्निर्माण से k हिस्से रखने वाले प्रत्येक व्यक्ति के सामने गुप्त मान प्रकट हो जाता है — MPC/सीमांक हस्ताक्षर इसे समाप्त करते हैं।

Shamir का SSS गुप्त मानों को बहुपद के y-अवरोधों के रूप में कूटबद्ध करता है। Lagrange अंतर्वेशन k हिस्सों से गुप्त मान पुनः प्राप्त करता है। k से कम हिस्सों के लिए पूर्ण सूचना-सैद्धांतिक सुरक्षा मिलती है। अगला विषय: दृश्य और योगात्मक गुप्त साझाकरण।