身份验证、中间人攻击和数字签名:浅谈密码学(中)

    事情还没有结束呢!我们前面假设,大家公开公钥的方式是“发布在一个众人可信的网站上”,这种假设是有原因的。需要临时交换双方公钥的通话协议是不安全的,这里面存在一个戏剧性的漏洞。举个例子,假如A和B认为,任何网站都是不可靠的,他们从未并且今后也不会在网上公布自己的公钥。为了加密通信,A需要亲自告诉B他的公钥,B也需要亲自告诉A自己的公钥。收到公钥后,双方便用对方的公钥加密进行数据传输。因为用这个公钥加密后,只有对方才能解开密码,因此双方都认为这条通信线路是安全的。其实,他俩的麻烦大了。这条线路并不是安全的,第三者可以用一种很搞笑的方式来窃听消息。假设有一个人C知道A和B之间将有一次加密通话。C劫持了A和B之间的通讯线路。现在,A把他的公钥发给B,这个公钥传到一半时被C拦截下来,于是C获得了A的公钥;C再把他自己的公钥发给B,让B把C的公钥错当成A的公钥。同样地,B把他自己的公钥发给A,被C拦截下来。C把自己的公钥发给A,让A以为那是B的公钥。以后,每当A给B发加密消息时,A其实是用C的公钥在加密;C把A的消息解密后,再用B的公钥加密后传给B。类似地,一旦B给A发送消息,C都可以将消息解密,并用A的公钥进行加密后传过去。此时,A和B都以为自己在用对方的公钥加密,并都能用自己的私有钥匙解开对方传来的密文;殊不知,这中间有人仅仅用了一点雕虫小技,无声无息地窃走了所有的信息。C正是利用了公钥加密术“谁都可以加密”的性质,结结实实地玩弄了A和B。这种攻击方法叫做“中间人攻击”。
    这让我想起了经典的国际象棋骗术。一个象棋白痴宣称自己是个大牛。为了证实这一点,他将要与两位大师同时对弈。他说,我先下后下都能赢。于是,在与大师A的对弈中他为白方,与大师B对战则执黑。结果呢,两盘比赛下来居然都打成了平手。怎么回事呢?其实那个象棋白痴耍了个小伎俩,他把大师A走的棋记了下来,跑到另一边去下给B看,又把B的应着原封不动地搬到了和A的棋局上。来来回回搞了半天,他自己只起了个传递信息的作用,真正在对弈的是两个大师。


    怎样防止这种中间人攻击呢?中间人之所以能够得逞,关键就是,无论是网络通话还是国际象棋,双方总是一先一后地发送信息。不过,在网络通讯中,我们有一种很特别的办法,他可以迫使中间人无法再扮演“即时翻译”的角色。首先,A把想说的话(最好是能够证明自己身份的话)进行加密,同时B也完成相同的工作。然后,A把他的加密消息的前面一半传给B,B收到后也把他的密文的一半传给A;A再把剩下的部份传给B,之后B也把他的密文的另一半回传给A。此时,A和B分别用自己的私钥进行解密,查看对方发来的消息。这带给中间人C一个不可逾越的障碍:两段密文要合在一起才能解开,中间人拿着其中一半密文,那是一点办法都没有。此时,中间人陷入了一个非常窘迫的境地,他只有两条路可选:要么硬着头皮把这半截密文发给B,当B得到全部密文后会发现用他自己的私钥根本解不开,从而意识到中间有人捣乱;要么就忽略这半截密文,自己编几句A想跟B说的话,用B的公钥加密并发一半给B。如此一来,中间人需要编造所有A和B之间的对话,这需要相当厚的脸皮,风险异常之大,要不了多久便会露出马脚。

 
 
    RSA算法还有一个特别的应用。注意到公钥和私钥所对应的两个函数是互逆的,因此如果我用私钥来加密,用公钥同样可以恢复原来的数据。但是,用我自己的密钥加密,然后大家都可解密,这有什么用处呢?不妨来看看这样“加密”后的效果吧:第一,貌似是最荒谬的,大家都可以看到源文件;第二,很关键的,大家只能够看源文件,但不能改动它;第三,满足上述两个要求的文件别人是做不出来的。
    这些性质正好完美地描述出“签名”的实质。为了防止钓鱼网站骗取你的账户和密码,正牌的那个服务器需要发送一条消息,以证明自己确实是唯一的服务提供商。为此,你可以发送一个随机字符串过去,要求服务器用它的私钥加密。服务器传回他加密过的字符串后,若你用他的公钥解密能恢复出原来的字符串,则说明对方一定是正宗的服务提供商。只有拥有私钥的人才能做到这一点,别人是无法伪造这个“签名”的。
    数字签名还有一些其它的特殊变化。考虑这样一种情况,我有一份秘密文件需要签名,但我不希望签名者看到这份文件的内容。这种看似很不合理的情况确有发生。例如在证人保护计划中,我是一个特工,我需要保护一个非常可爱的无辜小MM。为了把她安置到一个偏远的安全地,我需要让上级签署各种通行证明文件;但为了安全起见,我不希望把安全地的位置泄露给任何人。为此,我希望我的上级对文件进行签名,但保证他们完全不知道文件内容是什么。满足这种要求的签名协议叫做“盲签名”。为了得到一种“盲签名”算法,考虑用RSA进行签名的本质:假设待签名的文本为(不超过模数n的)t,则我们实质上希望得到t^d mod n,其中n是模数,d是签名者的私人钥匙。我们的目的是,对文本t进行干扰(例如在t上面加一个大数,或者乘一个大数,或者取t的倒数的正弦值的-π次方的自然对数),让签名者不知道t是什么;但签名者签名之后,我们还能除去刚才的干扰因子,还原为t^d mod n。因此,我们需要想一个奇妙的办法,让被干扰的文本签名后,干扰因子头上的“d”正好消失了。回忆之前讲过的结论m^(ed)≡m (mod n),我们立即想到了盲签名算法:我把明文t乘上一个随机数k的e次方(e是公开钥匙),把t*(k^e)传给签名人。注意我们选取的k一定要与n互质,否则k是大质数p或q的倍数,“干扰”的结果必然为0。这下,签名人当然不可能知道t是什么,因为他不知道随机数k是多少。他对t*(k^e)进行签名,传回来的结果即为t^d * k^(ed) mod n。但k^(ed)模n就等于k,于是这个签名结果实际上就是t^d * k mod n。现在,我只需要把该结果除以只有我才知道的k(即乘以它在模n剩余类环中的逆元,这个逆元保证存在,因为k和n互质),即得到了我需要的签名文件t^d mod n。
    盲签名协议并不是只有特工才可能用到的东西,它的应用范围其实相当广。在生活中,我们每个人都可能用到过盲签名。一个最常用的例子就是投票协议——中央机构需要确定每张选票都来自合格的选举人,并且每个人最多投了一次票;但同时选举人又不希望在投票过程中泄露自己的选票内容。但是,为了检查选票的来源是否可靠,中央机构必然要鉴别每张选票所属的投票人。怎么办呢?此时,盲签名协议就派上用场了。每个选举人在自己的选票前面加上一个随机字符串作为前缀(防止以后被暴力破解),然后乘上随机数k的e次方,再连同一份(未被干扰的)身份证明,一同递交给中央机构。中央机构检查身份证明,确认这张(被干扰过的)选票来自合格的选举人。然后中央机构给这张选票签名,回传给选举人。选举人将签名结果除以k,用中央机构的公钥检查看签名是否有效,随机字符串是否和自己当初设定的一样。接着投票人匿名提交这份由中央机构签过名的(且不带干扰因子的)选票。中央机构收到选票,用公钥解密看签名是否有效。这样,中央机构既可以确信每张选票都来自合格的投票人,严格实行一人一票制度,又不能追查出任何一个投票者的选票内容。

    更复杂的盲签名协议来源于这样一种特殊情况:恐怖分子答应供出炸弹的位置,前提条件是需要得到一系列保证无罪逃脱的签名文件,包括新身份、新护照,以及总统亲自签署的免起诉书和安全离境的通行证。同时,恐怖分子又需要确信政府不能知道他的新身份和潜逃地。这需要政府在不知道文件内容的情况下签署协议。这与刚才所谈的盲签名有什么区别呢?一个巨大的区别就是,要求盲签名的不是特工,而是坏蛋,政府在没有看到文件之前不能随意签名。万一恐怖分子要求盲签名的文件实际上是一份要求政府保护全体恐怖分子的安全,保证所有人永不被通缉永不被起诉,并无偿提供恐怖组织基地和巨额资助等不平等条约该咋办?因此,这里需要一种比盲签名要求更高的协议:签名者不能看到文件内容,但要相信文件的内容是什么。
    看起来这似乎是办不到的,但事实上这是有可能的。我们有一个非常简单的办法,它是一个基于概率的协议。恐怖分子可以起草十份文件,每份文件里都包含了一个不同的新身份和潜逃地。然后恐怖分子用十个不同的随机数对这十份文件进行干扰,传给政府。政府选取其中的九份文件,向恐怖分子索要干扰因子。恐怖分子把对应的那九个k值传过去,政府对其进行解密,从而看到这九份文件都是符合要求的文件(只是文件中具体的身份名字和潜逃地点不一样)。政府对最后一个文件进行签名,并把签名结果回递给恐怖分子。恐怖分子除去干扰因子,得到他需要的签名文件。这样,恐怖分子可以保证政府不知道他的新身份和潜逃地,同时政府也能保证恐怖分子不会耍诈。恐怖分子只有1/10的概率可以骗到政府,显然不值得恐怖分子去冒这个险。为安全起见,“10”这个数字还可以任意加大。

24 条评论

  • 夜弓

    来个沙发,
    最后一个例子很有趣,它的升级版本
    恐怖分子提交N份文件
    政府检查其中N/2份确保他们的内容是合理的
    然后对剩下的N/2份文件相乘并对结果签名
    恐怖分子在签名的基础上去掉盲因子
    在这种情况下,恐怖分子骗到政府的概率更小

  • DavidW

    很强大。M67从哪里学到如此有趣的知识?能否推荐些学习资源?

  • duolon

    matrix67果然素神牛也,,,厉害,,,

    PS:神牛不用睡觉的么。。。半夜写blog。。。

  • 燕仰

    嘻嘻你看大家果然对“中”没发表什么意见嘛^_^

  • cgy4ever

    很好…
    期待下一篇

  • multiple1902

    后面提到的相信内容的盲签名思路很有创意。

  • R

    这带给中间人C一个不可逾越的障碍:两段密文要合在一起才能解开,中间人拿着其中一半密文,那是一点办法都没有。此时,中间人陷入了一个非常窘迫的境地,他只有两条路可选:要么硬着头皮把这半截密文发给B,当B得到全部密文后会发现用他自己的私钥根本解不开,从而意识到中间有人捣乱
    ————————
    M67同学这里没讲清楚啊,我本以为C完全不碰AB间的信息那么B用他自己的私钥也可以解开,后来才明白这段话的前提是“现在,A把他的公钥发给B,这个公钥传到一半时被C拦截下来,于是C获得了A的公钥;C再把他自己的公钥发给B,让B把C的公钥错当成A的公钥。同样地,B把他自己的公钥发给A,被C拦截下来。C把自己的公钥发给A,让A以为那是B的公钥。”这段话,也就是说“无法用‘私匙C’来解密‘公匙C’加密后的一半密文”。
    当然也有可能是我的理解能力比较弱才没明白……

  • NjuBee

    钓鱼网站把随机字符串给正牌得到结果再返回用户呢?
    应该更复杂一点点的协议.

  • marlon

    “假设带签名的文本为(不超过模数n的)t,则我们实质上希望得到t^d mod n”

    应该是“假设要签名的文本为。。。”吧?虽然是一字之差,但是。。

    回复:谢谢提醒,应该是“待”……

  • marlon

    恐怖份子得准备10个潜逃地点,政府选择哪个他就得去哪个地点,真是不容易啊!(并且N还可能更大)

    to 夜弓:
    我觉得你理解得不对,如果将N/2个文件相乘,恐怖份子最终得到的加密也是对N/2文件内容相乘后的加密,而相乘后的内容可能根本不可读,因此肯定不能被放行,恐怖份子需要得到的是单独一份文件的加密。

    当然这只是个人看法。

  • 夜弓

    @marlon
    呃,这不是我的理解,应用密码学的原文
    我觉得这方法的使用应该有一定局限性的
    下面才是我的理解
    比如恐怖分子提交的数据其实应该由两部分组成
    一部分是固定不变的,一部分是保密敏感的
    设计一种”乘法”,使得在政府对相乘后数据签名之后
    恐怖分子仍然可以分离原有的信息,相当于政府对每一份数据签名,条件是每一个固定不变的部分都是相同的
    这样的话政府打开N/2份数据,检查这一部分不是一份大赦令,就对剩下所有的数据打包签名。恐怖分子只有在剩下的N/2中,固定部分拥有相同的值才能解开成有效的签名。相当于恐怖分子必须猜测出政府会打开哪个子集,C(n,n/2)挑一啊。

  • manson

    并无偿提供恐怖组织基地和巨额资助等不平等条约该咋办?

  • 夜弓

    @manson
    所以我说有局限性嘛
    格式固定的内容比较适用
    比如数字现金

  • hetong_007

    对恐怖分子VS政府的手法感兴趣~

  • mrzenix

    于是乎,我购买了电子银行的那个什么银盾。

  • multiple1902

    对12楼讲的方法感兴趣

  • 云之梦

    最近看了一个魔术,发现第三段的方法不可以阻止中间人。
    中间人可以采用这种办法:
    先编造A与B的第一轮对话,分成两段发给AB。
    以后AB第N轮对话时,C给AB发送第(N-1)轮的真实对话内容。

  • nshan

    下象棋的事,我以前干过一件类似的事,我在QQ游戏平台跟别人下象棋,又在网上找了象棋游戏,跟电脑下,然后,我就把那个人下棋的棋路当作我自己在跟电脑下,然后再把电脑走的拿来跟那个人下…

  • cervelo

    我觉得你理解得不对,如果将N/2个文件相乘,恐怖份子最终得到的加密也是对N/2文件内容相乘后的加密,而相乘后的内容可能根本不可读,因此肯定不能被放行,恐怖份子需要得到的是单独一份文件的加密。

  • www.882828.com

    相信自己能力的人,任何事情都能够做到。

回复给 夜弓 取消回复

  +  15  =  23