تقسیم رمز با استفاده از قضیه باقی‌مانده چینی

تقسیم راز به معنای برگرداندن راز با استفاده از یک سری سهم، به طوری که هر سهم یک سری اطلاعات از راز دارد. در این صفحه به تقسیم راز با استفاده از قضیه باقیمانده چینی می‌پردازیم.

تقسیم راز انواع مختلفی دارد یکی از پایه‌ای‌ترین نوع‌ها طرح‌های آستانه‌ای می‌باشد که در آن به ازای یک $k$ برای دستیابی به راز حداقل به $k$ سهم نیاز داریم و اگر $k$ سهم داشته باشیم حتماً می‌توانیم به راز دست پیدا کنیم، روش تقسیم رمز با استفاده از قضیه باقیمانده چینی نیز یکی از روش‌های طرح آستانه‌ای می‌باشد.

شرح

فرض کنید راز مورد نظر $S$باشد، با توجه به قضیه باقیمانده چینی اگر برای یک $k$تایی $m_{1},m_{2},...,m_{k}$که هردوتایی از آن‌ها نسبت به هم اول هستند و $S<\prod _{i=1}^{k}m_{i}$ باقیمانده $S$بر $m_{i}$ها را بدانیم، $S$یکتا بدست می‌آید و اگر $S\geqslant \prod _{i=1}^{k}m_{i}$حداقل دو جواب برای $S$طبق قضیه باقیمانده چینی وجود دارد. این گزاره ایده ای برای انتخاب کردن سهم‌ها می‌دهد.

اگر $n$ عدد مثبت انتخاب کنیم که دو به دو نسبت به هم اول باشند مثل $0<m_{1}<m_{2}<...<m_{n}$ و سهم‌ها باقیمانده $S$ بر $m_{i}$ها باشند، برای اینکه با استفاده از هر $k$ تا سهم بتوان $S$ را پیدا کرد و با کمتر از $k$ سهم نتوان $S$را پیدا کرد باید شرط روبرو برقرار باشد: $\prod _{i=n-k+2}^{n}m_{i}<S<\prod _{i=1}^{k}m_{i}$ (چون $\prod _{i=1}^{k}m_{i}$ بین همه زیرمجموعه‌های حداقل $k$ عضوی کمترین ضرب است و $\prod _{i=n-k+2}^{n}m_{i}$ بین همه زیرمجموعه‌های کمتر از $k$ عضوی بیشترین ضرب است) در این صورت طبق چیزی که قبلاً گفتیم چون ضرب $m_{i}$‌های هر $k-1$سهم کمتر از $S$است پس نمی‌توان به صورت یکتا به $S$دست یافت و از طرفی چون ضرب هر $k$سهم از $S$بیشتر است می‌توان $S$را به صورت یکتا بدست آورد.

روش مینوت (Mignotte)

دنباله $Mignotte(k,n)$شامل $n$عدد مثبت است مثل $0<m_{1}<m_{2}<...<m_{n}$ که دو به دو نسبت به هم اول هستند و $\prod _{i=n-k+2}^{n}m_{i}<\prod _{i=1}^{k}m_{i}$.

به ازای یک $S$ رندوم که شرط $\prod _{i=n-k+2}^{n}m_{i}<S<\prod _{i=1}^{k}m_{i}$ را دارا می‌باشد سهم‌ها به این صورت تعریف می‌شوند : $s_{i}=S\%m_{i}$ ($a\%b$ برابر باقیمانده تقسیم $a$ بر $b$ است)

و طبق قضیه باقیمانده چینی برای به دست آوردن $S$ از $k$ سهم باید معادله زیر را حل کنیم:

${\begin{cases}x\equiv &s_{i_{1}}\ {\bmod {\ }}m_{i_{1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{cases}}$

روش ازموث-بلوم (Asmuth-Bloom)

دو عدد طبیعی $n$ و $k$ را در نظر بگیرید که دارای شرط روبرو باشند $2\leqslant k\leqslant n$ و یک مجموعه از اعداد طبیعی مثل $0<m_{0}<m_{1}<...<m_{n}$ که دو به دو نسبت به هم اول هستند و شرط $m_{0}.\prod _{i=n-k+2}^{n}m_{i}<\prod _{i=1}^{k}m_{i}$ برقرار است، فرض کنید $S$ یک عدد تصادفی باشد که در شرط $0\leqslant S<m_{0}$ صدق می‌کند، حال برای مشخص کردن سهم‌ها یک عدد تصادفی $\alpha$انتخاب می‌کنیم که در شرط $S+\alpha m_{0}<\prod _{i=1}^{k}m_{i}$صدق کند، سپس سهم‌ها را به این صورت تعریف می‌کنیم : $s_{i}=(S+\alpha m_{0})\%m_{i}$

در این صورت به ازای هر $k$ سهم چون $S+\alpha m_{0}<\prod _{i=1}^{k}m_{i}$ طبق قضیه باقیمانده چینی می‌توان $S+\alpha m_{0}$ را به صورت یکتا پیدا کرد پس می‌توان با باقیمانده گرفتن $S+\alpha m_{0}$ بر $m_{0}$ می‌توان $S$ را پیدا کرد.

برتری این روش نسبت به روش قبل این است که در روش قبلی با داشتن $k-1$ سهم اطلاعاتی راجع به $S$ داشتیم چون اگر ضرب $m_{i}$های متناظر این $k-1$ سهم برابر $Z$ باشد با استفاده از قضیه باقیمانده چینی باقیمانده $S$ را بر $Z$داشتیم، در صورتی که در روش ازموث-بلوم با داشتن همین $k-1$ سهم باقیمانده $S+\alpha m_{0}$ را بر $Z$ داریم و چون $\alpha$ را یک عدد تصادفی انتخاب کردیم در واقع اطلاعاتی دربارهٔ خود $S$ نداریم.

مثال

در ادامه مثالی از روش ازموث-بلوم را بررسی می‌کنیم:

${\begin{cases}n=4\\k=3\\m_{0}=3,m_{1}=11,m_{2}=13,m_{3}=17,m_{4}=19\\\end{cases}}$

در مثال بالا $m_{i}$ها دارای شرایط گفته شده می‌باشند چون هم دو به دو نسبت به هم اول هستند (چون همه اعداد اول هستند و هر دو عدد اولی نیز نسبت به هم اول هستند) و در شرط $m_{0}.\prod _{i=n-k+2}^{n}m_{i}<\prod _{i=1}^{k}m_{i}$ نیز برقرار هستند ($3\times 17\times 19<11\times 13\times 17$).

فرض کنید $S=2$ باشد و عدد تصادفی‌ای که انتخاب کردیم $\alpha =51$باشد در این صورت در شرط $S+\alpha m_{0}<\prod _{i=1}^{k}m_{i}$ صدق می‌کند (چون $2+51\times 3=155<11*13*17=2431$).

در این صورت سهم‌ها برابر $\{1,12,2,3\}$ می‌باشند. حال با استفاده از باقیمانده چینی به ازای هر سه سهم می‌توان به عدد $S$ رسید.

جستارهای وابسته

• قضیه باقیمانده چینی
• تقسیم راز

منابع

• Oded Goldreich, Dana Ron and Madhu Sudan, Chinese Remaindering with Errors, IEEE Transactions on Information Theory, Vol. 46, No. 4, July 2000, pages 1330-1338.
• C.A. Asmuth and J. Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, IT-29(2):208-210, 1983.
• Sorin Iftene. General Secret Sharing Based on the Chinese Remainder Theorem with Applications in E-Voting. Electronic Notes in Theoretical Computer Science (ENTCS). Volume 186, (ژوئیه ۲۰۰۷). Pages 67–84. Year of Publication: 2007. ISSN 1571-0661.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. شابک ‎۰−۲۶۲−۰۳۲۹۳−۷. Section 31.5: The Chinese remainder theorem, pages 873-876.
• Ronald Cramer. Basic Secret Sharing (Lectures 1-2), Class Notes. October 2008, version 1.1.