طرح اشتراک راز شامیر (Shamir’s Secret Sharing)

طرح اشتراک راز شامیر (Shamir’s Secret Sharing): تقسیم امن راز بدون افشای اطلاعات

تصور کنید کلید بسیار حساسی دارید: عبارت بازیابی کیف پول کریپتو، کلید اصلی رمزنگاری یک بانک، یا رمز باز کردن خزانهٔ یک شرکت. اگر این کلید را فقط به یک نفر بسپارید، با چالش نقطهٔ تک‌شکست (Single Point of Failure) روبه‌رو هستید؛ اگر آن را به چند نفر بدهید، هر فرد به‌تنهایی دسترسی کامل خواهد داشت.
چگونه می‌توان یک راز را بین چند نفر تقسیم کرد به طوری که تنها با کنار هم قرار گرفتن تعداد مشخصی از آن‌ها راز بازیابی شود و اگر حتی یک نفر کمتر باشد، هیچ سرنخی از راز فاش نشود؟
این مسئله با طرح اشتراک راز شامیر (Shamir’s Secret Sharing - SSS) حل می‌شود؛ الگوریتمی رمزنگاری که پایهٔ آن نه بر حدس و الگوریتم‌های پیچیده، بلکه بر هندسهٔ چندجمله‌ای‌ها و جبر مجرد استوار است.

طرح آستانه‌ای $(k, n)$ چیست؟

طرح اشتراک راز شامیر یک راز (مانند کلید اصلی یا پسورد) را به $n$ سهم ($Share$) یکتا تقسیم می‌کند. این سیستم بر پایهٔ طرح آستانه‌ای $(k, n)$ کار می‌کند:

• توزیع ($Distribution$): راز به $n$ سهم تقسیم شده و بین افراد توزیع می‌شود.
• بازیابی ($Reconstruction$): هر ترکیب دلخواه از حداقل $k$ سهم می‌تواند راز را بازسازی کند.
• امنیت کامل ($Perfect Secrecy$): داشتن کمتر از $k$ سهم، هیچ‌گونه اطلاعاتی دربارهٔ راز ارائه نمی‌دهد.

مثال: در یک طرح $3$ از $5$ ($n=5$ و $k=3$)، کلید به $5$ سهم تقسیم می‌شود. هر $3$ نفر می‌توانند راز را بازیابی کنند، اما $2$ نفر حتی با به‌کارگیری تمام توان پردازشی جهان، هیچ اطلاعاتی به دست نمی‌آورند. از نظر ریاضی، با داشتن کمتر از $k$ سهم، تمامی مقادیر ممکن برای راز، شانس برابری دارند.

ایدهٔ هندسی: تعیین منحنی با تعداد مشخصی نقطه

پایه و اساس این روش بر یک اصل هندسی ساده روی صفحهٔ مختصات بنا شده است:

• از ۱ نقطه، بی‌نهایت خط راست عبور می‌کند.
• با داشتن ۲ نقطه، تنها یک خط راست یکتا مشخص می‌شود.
• از ۲ نقطه، بی‌نهایت سهمی (منحنی درجه ۲) می‌گذرد.
• با داشتن ۳ نقطه، یک سهمی یکتا کاملاً مشخص می‌شود.

قاعدهٔ کلی جبر این است که برای تعیین یکتای یک چندجمله‌ای از درجهٔ $d$، به حداقل $d + 1$ نقطه نیاز داریم. بنابراین اگر آستانهٔ مورد نیاز برای بازیابی $k$ باشد، درجهٔ چندجمله‌ای برابر است با:
$$d = k - 1$$

برای درک بهتر، ویدیو زیر را مشاهده کنید:

راز کجا پنهان می‌شود؟

راز اصلی برابر با عرض از مبدأ چندجمله‌ای قرار داده می‌شود؛ یعنی مقدار $y$ به ازای $x = 0$.
سپس به هر فرد یک نقطهٔ متمایز روی منحنی به‌صورت $(x, y)$ تحویل داده می‌شود (با شرط $x \neq 0$). اگر برای بازسازی به $k$ نقطه نیاز باشد، داشتن $k - 1$ نقطه بی‌نهایت منحنی ممکن باقی می‌گذارد که از آن نقاط عبور می‌کنند؛ در نتیجه عرض از مبدأ (راز) کاملاً ناشناخته می‌ماند.

مثال عددی در فضای معمولی: طرح ۲ از ۳ $(k=2, n=3)$

برای درک شهودی، یک طرح آستانه‌ای با $k = 2$ و $n = 3$ را بررسی می‌کنیم. چون $k = 2$ است، درجهٔ چندجمله‌ای $d = 2 - 1 = 1$ خواهد بود (معادله خط راست به صورت $y = mx + b$).

• راز ($b$): $11$
• شیب تصادفی ($m$): $3$
• معادله خط: $y = 3x + 11$

سهم‌ها با جای‌گذاری مقادیر $x = 1, 2, 3$ ساخته می‌شوند:

• سهم ۱: $(1, 14)$
• سهم ۲: $(2, 17)$
• سهم ۳: $(3, 20)$

بازسازی راز با دو سهم

فرض کنید دارندگان سهم ۱ و سهم ۲ پیش هم می‌آیند: $(1, 14)$ و $(2, 17)$.ابتدا شیب خط ($m$) را محاسبه می‌کنند:
$$m = \frac{y_2 - y_1}{x_2 - x_1} = \frac{17 - 14}{2 - 1} = 3$$سپس با جای‌گذاری یکی از نقاط در $y = 3x + b$ مقدار $b$ به دست می‌آید:
$$14 = 3(1) + b \implies b = 11$$راز ($b = 11$) به‌دقت بازیابی شد. این مثال روند ریاضی را نشان می‌دهد، اما در پیاده‌سازی واقعی به دلیل خطاهای اعشاری و نشت اطلاعات از اعداد حقیقی استفاده نمی‌شود.

چرا ریاضیات معمولی کافی نیست؟ نقش میدان‌های متناهی ($\mathbb{Z}_p$)

استفاده از اعداد حقیقی یا اعشاری در رمزنگاری دو مشکل عمده ایجاد می‌کند:

1. خطای گرد کردن: محاسبات اعشاری در رایانه دقیق نیستند و ممکن است منجر به بازیابی نادرست راز شوند.
2. نشت اطلاعات: در حساب معمولی، مقادیر بزرگ سهم‌ها می‌توانند بازهٔ حدس برای شیب یا راز را محدود کنند و امنیت مطلق را از بین ببرند.

راه‌حل: نظریه هم‌نهشتی روی اعداد اول

در پیاده‌سازی واقعی از میدان متناهی ($\mathbb{Z}_p$) با یک عدد اول $p$ استفاده می‌شود:

• یک عدد اول $p$ انتخاب می‌شود که از راز و تعداد کل سهم‌ها ($n$) بزرگ‌تر است ($p > \text{Secret}$ و $p > n$).
• تمام محاسبات در$\pmod p$انجام می‌شوند (مجموعهٔ اعداد $\{0, 1, \dots, p-1\}$).
• در این ساختار، نشت اطلاعات صفر می‌شود زیرا هر سهم، احتمالی کاملاً یکسان برای تمام رازهای ممکن ایجاد می‌کند.

مثال گام‌به‌گام روی میدان متناهی ($p = 11$)

عدد اول $p = 11$ را انتخاب می‌کنیم. تمام محاسبات در مجموعهٔ $\{0, 1, 2, \dots, 10\}$ انجام می‌شوند.
فرض کنید طرح $2$ از $3$ ($k=2$) با خط زیر تعریف شده است:
$$y = (2x + 5) \pmod{11}$$راز برابر است با $b = 5$ (مقدار $y$ در $x = 0$).

ساخت سهم‌ها:

معادلهٔ خط ما به صورت زیر تعریف شده است:
$$y = (2x + 5) \pmod{11}$$راز در این معادله، همان عرض از مبدأ یعنی $5$ است ($y$ به ازای $x = 0$).
حالا برای ساخت سهم‌های مختلف، مقادیر دلخواه و غیرصفر $x$ (مثلاً $x = 3$ و $x = 4$) را در معادله جای‌گذاری کرده و گام‌به‌گام حساب می‌کنیم:

ساخت سهم ۱ (به ازای $x = 3$)

۱. محاسبهٔ مقدار اولیه:
$$2(3) + 5 = 6 + 5 = 11$$۲. اعمال$\pmod{11}$: باید باقی‌ماندهٔ تقسیم $11$ بر $11$ را به دست آوریم. چون $11$ بر $11$ بخش‌پذیر است، باقی‌مانده برابر $0$ می‌شود:
$$11 \equiv 0 \pmod{11}$$۳. مختصات سهم ۱: $(3, 0)$

ساخت سهم ۲ (به ازای $x = 4$)

۱. محاسبهٔ مقدار اولیه:
$$2(4) + 5 = 8 + 5 = 13$$۲. اعمال $\pmod{11}$: باید باقی‌ماندهٔ تقسیم $13$ بر $11$ را به دست آوریم. عدد $13$ برابر است با $(1 \times 11) + 2$؛ پس باقی‌مانده برابر $2$ می‌شود:
$$13 \equiv 2 \pmod{11}$$۳. مختصات سهم ۲: $(4, 2)$

بازسازی کامل راز با سهم‌های $(3, 0)$ و $(4, 2)$

۱. محاسبه شیب ($m$):
$$m = \frac{2 - 0}{4 - 3} = 2$$معادله به صورت $y = (2x + b) \pmod{11}$ درمی‌آید.
۲. محاسبه عرض از مبدأ ($b$):با قرار دادن سهم $(3, 0)$:
$$0 \equiv (2(3) + b) \pmod{11} \implies 0 \equiv (6 + b) \pmod{11}$$در پیمانهٔ $11$ عددی که با $6$ جمع شود و مضرب $11$ گردد $5$ است ($6 + 5 = 11 \equiv 0$). بنابراین:
$$b = 5$$راز با موفقیت و بدون خطای گردکردن به دست آمد ($S = 5$).

یک سوءتفاهم رایج: چرا به هیچ‌کس سهمی با $x = 0$ داده نمی‌شود؟

گاهی وجود مقدار $y = 0$ در یک سهم (مانند سهم $(3, 0)$) باعث سردرگمی می‌شود. باید بین $x = 0$ و $y = 0$ تفکیک قائل شد:

• راز اصلی مقدار $y$ به ازای $x = 0$ است.
• سهم‌ها فقط برای مقادیر $x = 1, 2, 3, \dots$ توزیع می‌شوند.
• اگر به فردی سهمی با $x = 0$ داده شود (مثلاً $(0, 5)$)، آن فرد مستقیماً و بدون نیاز به دیگران راز را در اختیار دارد.
• مقدار $y = 0$ در سهم $(3, 0)$ صرفاً نقطه‌ای از منحنی است که محور $x$ را قطع کرده و هیچ اطلاعاتی از راز ($x=0$) افشا نمی‌کند.

بازسازی با سهمی: طرح ۳ از ۴ $(k=3, n=4)$ روی $\pmod{11}$

برای آستانهٔ $k = 3$ به چندجمله‌ای درجهٔ ۲ نیاز داریم:
$$y = (ax^2 + bx + c) \pmod{11}$$فرض کنید سه سهم زیر در اختیار ما قرار دارد:

• سهم ۱: $(1, 10)$
• سهم ۲: $(2, 8)$
• سهم ۳: $(3, 10)$

تشکیل دستگاه معادلات

با جای‌گذاری سهم‌ها در معادله:
$$\begin{aligned} a(1)^2 + b(1) + c &\equiv 10 \pmod{11} \implies a + b + c \equiv 10 \pmod{11} \quad \text{(معادله ۱)} \\ a(2)^2 + b(2) + c &\equiv 8 \pmod{11} \implies 4a + 2b + c \equiv 8 \pmod{11} \quad \text{(معادله ۲)} \\ a(3)^2 + b(3) + c &\equiv 10 \pmod{11} \implies 9a + 3b + c \equiv 10 \pmod{11} \quad \text{(معادله ۳)} \end{aligned}$$

حل دستگاه معادلات

۱. حذف $c$:

• تفریق معادله ۱ از معادله ۲:
  $$\begin{aligned} (4a + 2b + c) - (a + b + c) &\equiv 8 - 10 \pmod{11} \\ 3a + b &\equiv -2 \equiv 9 \pmod{11} \quad \text{(معادله A)} \end{aligned}$$
• تفریق معادله ۱ از معادله ۳:
  $$\begin{aligned} (9a + 3b + c) - (a + b + c) &\equiv 10 - 10 \pmod{11} \\ 8a + 2b &\equiv 0 \pmod{11} \implies 4a + b \equiv 0 \pmod{11} \quad \text{(معادله B)} \end{aligned}$$

۲. محاسبهٔ $a$ و $b$:

• تفریق معادله A از معادله B:
  $$\begin{aligned} (4a + b) - (3a + b) &\equiv 0 - 9 \pmod{11} \\ a &\equiv -9 \equiv 2 \pmod{11} \implies a = 2 \end{aligned}$$
• جای‌گذاری $a = 2$ در معادله A:
  $$3(2) + b \equiv 9 \pmod{11} \implies 6 + b \equiv 9 \implies b = 3$$

۳. محاسبهٔ $c$ (راز):

• جای‌گذاری $a = 2$ و $b = 3$ در معادله ۱:
  $$2 + 3 + c \equiv 10 \pmod{11} \implies 5 + c \equiv 10 \implies c = 5$$

چندجمله‌ای بازسازی‌شده برابر است با $y = (2x^2 + 3x + 5) \pmod{11}$ و مقدار راز برابر با $5$ است.

شرایط انتخاب عدد اول $p$

عدد اول $p$ نمی‌تواند دلخواه باشد و باید دو شرط اساسی را برآورده کند:

1. $p > \text{Secret}$: اگر $p$ از راز کوچک‌تر باشد، محاسبهٔ پیمانه مقدار راز را تغییر داده و بازسازی درست غیرممکن می‌شود.
2. $p > n$: هر سهم نیازمند یک $x$ یکتا در مجموعهٔ $\{1, 2, \dots, p-1\}$ است؛ بنابراین $p$ باید از تعداد کل سهم‌ها بیشتر باشد.

در پیاده‌سازی‌های عملی رمزنگاری، از اعداد اول بسیار بزرگ (مانند اعداد اول ۲۵۶ بیتی) استفاده می‌شود تا فضای راز بزرگ و غیرقابل حدس باشد.

تمرین کاربردی انتخاب $p$

بانکی می‌خواهد یک کلید عددی با مقدار $450$ را بین $5$ مدیر توزیع کند ($n = 5$). کدام عدد اول مناسب است؟

• گزینه A: $p = 7$ (نادرست: هم از راز و هم از $n$ کوچک‌تر است)
• گزینه B: $p = 401$ (نادرست: کوچک‌تر از راز $450$ است)
• گزینه C: $p = 521$ (درست: هم $521 > 450$ و هم $521 > 5$)

کاربردهای واقعی Shamir’s Secret Sharing

• بازیابی اجتماعی در کیف‌پول‌های وب۳ (Social Recovery): تقسیم عبارات بازیابی بین چند دستگاه یا افراد مورد اعتماد.
• خزانه‌های چندامضایی و مدیریت شرکتی: نیاز به تایید حداقل $k$ مدیر برای انجام تراکنش‌های مالی حساس.
• ماژول‌های امنیتی سخت‌افزاری (HSM) و سیستم‌های ابری: توزیع کلیدهای اصلی رمزنگاری بین سرورهای جغرافیایی مختلف.

جمع‌بندی

امنیت طرح اشتراک راز شامیر مبتنی بر پیچیدگی محاسباتی یا «سختی حدس زدن» نیست؛ بلکه بر پایهٔ امنیت مطلق نظریه اطلاعات ($Information-Theoretic Security$) استوار است. با داشتن کمتر از $k$ سهم، تعداد بی‌نهایتی منحنی با تمامی عرض از مبدأهای ممکن وجود دارند که شانس بروز هر یک کاملاً یکسان است.