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

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

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

## شرح
فرض کنید راز مورد نظر Sباشد، با توجه به قضیه باقیمانده چینی اگر برای یک kتایی m_1,m_2,...,m_kکه هردوتایی از آن‌ها نسبت به هم اول هستند و S  باقیمانده Sبر m_iها را بدانیم، Sیکتا بدست می‌آید و اگر S \geqslant \prod_{i=1}^k m_iحداقل دو جواب برای Sطبق قضیه باقیمانده چینی وجود دارد. این گزاره ایده ای برای انتخاب کردن سهم‌ها می‌دهد.

اگر n عدد مثبت انتخاب کنیم که دو به دو نسبت به هم اول باشند مثل 0 و سهم‌ها باقیمانده S بر m_iها باشند، برای اینکه با استفاده از هر k تا سهم بتوان S را پیدا کرد و با کمتر از k سهم نتوان Sرا پیدا کرد باید شرط روبرو برقرار باشد: \prod_{i=n-k+2}^n 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 که دو به دو نسبت به هم اول هستند و \prod_{i=n-k+2}^n m_i .

به ازای یک S رندوم که شرط \prod_{i=n-k+2}^n 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.\prod_{i=n-k+2}^n m_i  برقرار است، فرض کنید S یک عدد تصادفی باشد که در شرط 0\leqslant S  صدق می‌کند، حال برای مشخص کردن سهم‌ها یک عدد تصادفی \alphaانتخاب می‌کنیم که در شرط S+\alpha m_0صدق کند، سپس سهم‌ها را به این صورت تعریف می‌کنیم : s_i=(S+\alpha m_0)\%m_i

در این صورت به ازای هر k سهم چون S+\alpha m_0 طبق قضیه باقیمانده چینی می‌توان 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  نیز برقرار هستند (3\times17\times19).

فرض کنید S=2 باشد و عدد تصادفی‌ای که انتخاب کردیم \alpha=51باشد در این صورت در شرط S+\alpha m_0 صدق می‌کند (چون 2+51\times3=155).

در این صورت سهم‌ها برابر \{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. .
* 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.
رده:الگوریتم‌های رمزنگاری