基于中国剩余定理的秘密共享方案(C语言实现)

基于中国剩余定理的秘密共享方案，本质上是在利用模m运算。

一、秘密共享方案简单讲解

（t,n)门限，若得到的子秘密大于等于t个，则可以恢复出原始秘密；反之则不然。那么为什么会是这样的呢？
关键在于N>k>M，若是模一个大于原秘密k的大数，则k就是k，算出来的结果不需要改动；而要是模一个小于或等于原秘密k的大数M，则算出来的结果是k%M，必定小于M（从而小于k），因此这是得不到原始秘密的。

顺便讲一下，这里我们给定秘密k为500位，并采用（3，5）门限。
假如有同学想推广到一般情况，可以自己试试看，也不难。

二、基本思路

1. 给出（t，n）对为（3，5），并指定秘密为500位，要求我们先将秘密分解为5个子秘密（ki，di），然后再使用t个（或大于）子秘密恢复出原秘密，并验证少于t个子秘密不能恢复出原秘密。
2. 问题的关键在于如何寻找di序列？这里指定了秘密的位数为500位和门限为（3，5），那么我想5个200位的大素数一定满足要求吧（前3个200位素数乘积为600位，大于500；后两个素数乘积为400位，小于500），于是迎刃而解。
3. 后面秘密的恢复就是简单利用中国剩余定理了，具体如何可以参考我前面的博文，直接拿来用就好。

三、关键语句含义讲解

1. 这里利用大数产生器bigdig随机产生10个500位的大数（作为秘密）并存入文件。
   

2. 这里从10的199次方（最小的200位数）开始寻找素数，找满5个完成di序列的构建。
   

3. 这里使用中国剩余定理从3个子秘密中恢复出原秘密。
   

4. 这里使用中国剩余定理从2个子秘密中恢复出原秘密，结果当然是不能啦。
   

四、运行结果截图

从上面可以看到，三个子秘密可以恢复出原秘密，两个子秘密却不能。秘密共享方案实现成功！