UC知道关于一个算法的问题
来源：百度知道 编辑：UC知道 时间：2024/05/14 06:35:40
问题：你要在一张白纸上写长为100位的由数字0、1组成序列，比如00110110011。。。等，假设你写0的时间为1秒，写1的时间为2秒，那么，别人可以根据你每写一位数字的时间来推测你写的是0或是1。
请问：你要如何写才能不让别人推测出你写的数字呢？
前提条件：
1、写0和写1的时间是固定不变的，即写0一定需1秒，写1一定需2秒；
2、每写一个数字，都要往后移一位，所以，别人可以看出你写一位的起止时间；
3、序列必须按顺序写，而不能跳着写；
4、序列是什么就必须写什么，不能改变序列的值；
5、写的节奏是暴露的，即不能说躲起来写不给别人看见等无意义的方法。
---------------------------------------------
我想到的一个方法是：写完0的时候，停顿1秒，再往后移一位，这样写0的时间和写1的时间就是一样的，别人就无法判断你写的是0还是1。不过这个方法比较耗时，因为假设0和1的概率是均等的，那么100位共需要50+100=150秒，用了我的方法后需要200秒。
请教大家，有更好的方法么？让别人猜不出你写的数字，又节省时间的？
（其实，这是我最近研究的一个算法，由于算法每一步执行时间固定，容易受到时间分析攻击，不是很安全，我想破了脑袋都想不出什么好的办法，极度郁闷中，我把算法的步骤用简单的写数字0和数字1表示出来，简化成了上面的问题，盼各位达人赐教！不甚感激！如有达人能想到比我的方法节省时间的好方法，且答案经得起推敲，我一定请他吃饭，有斐！绝不食言！！）
请问：你要如何写才能不让别人推测出你写的数字呢？
前提条件：
1、写0和写1的时间是固定不变的，即写0一定需1秒，写1一定需2秒；
2、每写一个数字，都要往后移一位，所以，别人可以看出你写一位的起止时间；
3、序列必须按顺序写，而不能跳着写；
4、序列是什么就必须写什么，不能改变序列的值；
5、写的节奏是暴露的，即不能说躲起来写不给别人看见等无意义的方法。
---------------------------------------------
我想到的一个方法是：写完0的时候，停顿1秒，再往后移一位，这样写0的时间和写1的时间就是一样的，别人就无法判断你写的是0还是1。不过这个方法比较耗时，因为假设0和1的概率是均等的，那么100位共需要50+100=150秒，用了我的方法后需要200秒。
请教大家，有更好的方法么？让别人猜不出你写的数字，又节省时间的？
（其实，这是我最近研究的一个算法，由于算法每一步执行时间固定，容易受到时间分析攻击，不是很安全，我想破了脑袋都想不出什么好的办法，极度郁闷中，我把算法的步骤用简单的写数字0和数字1表示出来，简化成了上面的问题，盼各位达人赐教！不甚感激！如有达人能想到比我的方法节省时间的好方法，且答案经得起推敲，我一定请他吃饭，有斐！绝不食言！！）
1.从攻击角度看，由于写入时存在前提条件1，因此，可以根据写入的时间延迟来判断写入的是0还是1。再根据其他前提条件可以得出写入的所有数字序列。
2.从防止攻击角度看，只有在前提条件1处设计算法来迷惑攻击。下面结合算法条件、要求和目的来谈谈算法问题。为了节省时间的要求，仅考虑每次写入的时间延迟上限为2秒。
(1).最简单的算法就是前提条件1，原因是攻击者无法判断出写入延迟时间为2秒时写入的是0还是1。但是，这个算法将受到门槛攻击，也就是说，最简单的攻击方法就能直接命中。
(2).进一步考虑，除了的写入延迟时间为1秒时必然会被识别出写入0以外，新算法只要在写入0的地方将时间延迟延长为2秒就可以迷惑攻击。问题是需要在哪几个写入0的地方进行时间延迟呢？
(3).假设写入的数字序列总个数为N，其中数字1的个数为n，那么在某个0位置上进行时间延长，受到攻击的概率则为1/C(n+1,1)=1/(n+1)；同理可以计算出在某两个0位置上进行时间延长受到攻击的概率为1/C(n+1,2)，以次类推，在某m个0位置上进行时间延长受到攻击的概率则为1/C(n+1,m)。由上面的推导可以得出，受到攻击的概率最小的地方是在m=(n+1)/2个0位置上进行时间延长。当然实际上m取(n+1)/2与(N-n)之间的较小值。一个极端的情况是当n=0时，m可以取1或以上任一个值。因此，问题就演变为在时间损失与攻击概率之间的取舍了。