我开发了一个基于 Beancount 的账本托管服务 HostedBeans,欢迎大家来了解纯文本复式记账并试用我的服务。
标签 #密码学

零毫秒的图景一下子清晰起来了

去中心化的零毫秒计划了很久,一直都没能开始,原因很简单,就是我无法想象这样一个项目应该如何设计,都有哪些部分,从哪开始。

即使这两年来我学习了不少有关公钥加密和证书体系,Bitcoin 的实现,一些 DHT 网络的实现等,但依旧如此。

这段时间有很多目标类似的项目出现,我所知道的就有 BitMessage, BitTorrent Chat, Tox.

所以我以为这个项目就要这么坑掉了。

但前一阵,我一直想着重写 ZeroMS-1x, 即两年前我初学 Qt 的时候,写的零毫秒的第一个版本,一个十分简易的中心化,C/S 结构的聊天工具。

重写的目的也很简单,只是希望当初花了好大功夫写的东西不至于不能运行——虽然重写的时间应该不会小于当初花费的时间。

于是我开始设想如何设计这个重写版本。

首先不能再使用之前那丑陋的通讯协议载体,转而使用 JSON.

然后就是之前那蛋疼的帐号机制。

之前的帐号机制是使用 PHPWind 论坛(后来是 esoTalk)系统的帐号系统,服务器会请求论坛上的一个 PHP API 来验证登录信息。

我决定使用公钥加密(RSA), 的密钥对代替帐号系统。

一对公私玥就是一个帐号,公钥是帐号的唯一 ID, 私钥是持有帐号的凭证。

登录时,客户端用私钥为登录信息签名,同时提供一个短的,不唯一,可变的昵称作为友好的显示名。

再进一步,可以让发信人对所有发出的消息进行签名,以认证身份。

再进一步,可以让发信人对所有签名过的消息,用收信人的公钥进行加密,使只有拥有私钥的收信人才能解密。

至此,我们惊奇地发现,虽然整体仍是 C/S 结构的网络,但是我们似乎已经剥夺了服务器的大部分权力——服务器无法查看消息的内容,也无法篡改或伪造消息。

于是,服务器似乎变成了一个非必须的部分,因为作为服务器,不需要什么资格,也没有什么权力,任何人都可以当服务器!

甚至可以让多个服务器接力地完成一个消息的送达过程。只需要送达就可以了!无论中间是谁来传递的,也无论中间有多少人经手,因为它们看不了消息也改不了消息,就算你写在纸上飞鸽传书也没有什么不可以。

这时的服务器已经不能叫做服务器了,应该叫网关或者路由,就像 IP 中的网关一样,工作是将 IP 数据包送达指定的地址。IP 网络的网关各自维护了自己的路由表,同时基于 IP 地址的 IP 网络也是一个结构化的网络,所以这很简单。

而在零毫秒的网关之间,可以维护一个分布式散列表(DHT), 如类似 Kademlia 协议的 DHT, 储存网络上每个用户(公钥)和所对应的地址。

这样一来,原来我想要的去中心化即时通讯就是这么简单!之前一直把它想得过于复杂了,原来就是这么简单的一个构造而已!

既然图景已经清晰,我们还可以讨论一些更为细节的话题。

首先是公钥交换,通过上面的设计,要与一个人通讯,必须知道他的公钥,当然,获取公钥的过程很简单,问题是如何保证这个过程的安全性呢?如果密钥在通信的途中被替换了怎么办?这在 HTTP 环境下很容易发生。

有人提出应成立一个证书颁发机构(CA), 对用户的公钥进行签名,但这似乎有悖于去中心化的精神。

我认为公钥交换应该由用户自行解决,用户可以自行选择渠道,如 HTTP, HTTPS, 其他 IM 如 QQ, 当面交换纸质(二维码)公钥。而事实上也有提供公钥交换服务的网站,如 pgp.mit.edu (我不得不吐槽一下这个网站居然只有 HTTP 版本), 这些望着本来是为了交换 PGP 公钥而设计的,不过对零毫秒也是适用的。

因为用户可以自行选择渠道,用户的选择越多样,「信任链」的构成就越分散,攻击者发起攻击的成本就越高,整个系统就越安全。

之前我们讨论过,网关无法阅读或修改流经它的消息,但是网关可以选择丢弃消息,不予转发,那么如何应对这种消息丢失的情况呢?

事实上 IP 的网关也有类似的特点,即它可以随意丢弃消息,IP 对此的解决方案就是不予考虑,将这个工作交由上层协议来实现,比如 TCP.

TCP 会在通讯的双方,也就是两个端点来进行一些操作,而中间的 IP 网关不必考虑,甚至不必知道这是一个承载 TCP 协议的包。

「在端点实现功能」也是 TCP/IP 网络体系的一大特点。

由此,零毫秒中的两个客户端之间,应该自行协商,防止消息丢失。

最简单的办法就是在每一条消息中,嵌入上一条消息的散列值(Hash), 当中间的某个消息丢失时,双方可以察觉到,自行协商,对丢失的消息进行重传。

这样一来,客户端需要自行维护很多状态,例如对于每个联系人的上一条消息,这导致用户在更换设备时需要一并携带这些信息,否则就会导致通讯不正常,这是目前很难解决的问题,最理想的就是使用同步盘服务(可以是自建的)来同步这些数据。

另一方面是接收离线消息,客户端可以指定一个长期在线的网关作为离线代理,由这个网关来代收离线消息,上线后再从这个网关抓取离线消息,这符合在端点实现功能的原则。

这个网关可以是用户自建的,也可以是公共的「离线代理网关」。

最后要讨论的一个话题就是组群。

建立一个组群就是生成一个新的密钥对,公钥即为该组群的ID, 私钥由管理员掌握,用于签发新成员加入和移除现有成员的通知。

然后组群的成员根据管理员签发的公告,计算出目前的成员列表,逐个发送消息。

这个实现似乎很不完善,既无法阻止成员把消息发到非组群成员那,也无法阻止成员忽略组群中的一些成员,全靠成员的自觉。

而且如果有其他 10 个成员,那么每条消息就需要发送 10 遍,因为要保证网关不能阅读消息的内容,每一条消息都需要用不同的,收信人的公钥来加密。

利用 Bitcoin 网络进行时间区间证明

有这样一个有趣的话题,如果我在今天,2013 年 12 月 31 日,截取一张截图,那么在事后如何证明这张截图是今天所截取的呢?

同时我希望这个证明足够可靠,关键信息不掌握在少数人手中,任何人无法篡改已经证明的信息,证明不会因为某些机密信息的泄露而失效,且任何人都要可以非常方便地验证这个证明。

乍一看,简单。但细一想,又似乎不可能。

其实这个问题可以分解成两个问题:

  • 首先要证明这张图必须在某个时间之后才能被截取出来
  • 然后需要证明这张图必须在某个时间之前才能被截取出来

「证明这张图必须在某个时间之后才能被截取出来」这个问题简单,只需在截图中包含一些「只有在该时间后才能获取到的信息」,比如当天双色球的中奖号码等等。

这很好理解,如果我在截图中包含了 2013.12.31 的双色球中奖号码,就可以毫无疑问地证明这张图是在 2013.12.31 之后被截取的。

但是,这并不能妨碍我在 2014.1.1 重新截取一张截图,加入 2013.12.31 的双色球号码。所以我们还必须证明「这张图必须在某个时间之前才能被截取出来」。

解决这个问题的关键是要把这张截图的信息,永久地保存到某个可以随时查证的地方,比如我们可以让这张图片登上报纸头条,它就是永远可被查证的了,今后我们可以随时把需要证明的图片与 2013.12.31 的报纸进行对比,证明图片的真伪。

综上只需要在截图中加入当日的双色球号码,并且让它登上报纸头条即可。

——等等,你在开玩笑么。

好吧,所以我要提 Bitcoin, Bitcoin 给我们提供了这样的一个机会,它既是双色球,又是报纸。使用下文的方法进行一次证明只需花费你几分钟的时间,和一点点金钱(几分钱).

首先我们准备一张图片(记作 PIC).

pic.png

因为图片本身很大,对整张图片应用各种加密算法很不划算,所以我们要对这张图片进行散列,如果散列算法足够可靠,我们可以认为散列值就代表了这张图片(记作 HASH), 我们选用在今后很长一段时间都足够可靠的 SHA-256 算法,Bitcoin 网络使用的也是该算法。

HASH = sha256(PIC) = 896c53284a04c3df2c5fe81b1fa228d421ed6c87190da60e153562786346af75

然后我们去瞧一眼 Bitcoin 网络最新的区块(Block) 的散列值,Bitcoin 的区块大约每隔十分钟出现一个,除非你控制了世界上几乎全部的(参与 Bitcoin, 下略)的计算机,否则没有人能预测到它。同时新生成的 Block 会马上被同步到世界上所有的计算机上,事后同样没有人能够篡改。它在此起到了「双色球」的作用。

北京时间 2013.12.31 21:32 产生的最新一个区块的散列值如下,记作 BBH(Bitcoin Block Hash):

BBH = 0000000000000001149d2d7b4fcc693095fef279a1300f938e9cbeec1b43c034

然后我们将最新区块的散列值加到图片上,记作 HASH2:

HASH2 = sha256(HASH1 + BBH) = 277e31d0a5495dbeb642f459be2bcb768d728a7c1e9e008c4d6276dc938d4195

以后我们需要用 HASH2 来表示这张图片(而不是HASH), 因为 HASH2 中包含了最新区块的信息。

至此,我们完成了后向证明。

即,我们证明了「HASH2 只有在拥有 HASH(即 PIC) 且晚于北京时间 2013.12.31 21:32 的情况下才能取得」。

然后,我们使用 HASH2 作为钱包私钥,来生成对应的 Bitcoin 收款地址,因为比特币钱包私钥和收款地址本质上是一对公钥加密算法(如 RSA)的私钥和公钥,因此从公钥无法推出私钥。我们得到了这个收款地址,即证明了我们拥有私钥,再进一步证明了我们拥有 HASH2, HASH, 和 PIC.

在这个过程中,Bitcoin 网络起到了「报纸」的作用,(理想情况下)每笔交易会在下一个区块「截稿」的时候被定格,成为区块的一部分,被同步到世界上所有的计算机上,随时可以查证,又无人可以篡改。

在这一步我使用了 blockchain.info 提供的导入私钥的服务,暂时我还未查证 blockchain.info 以何种格式理解该私钥,但这不影响结论。

我由 HASH2 得出了对应的 Bitcoin 收款地址(记作 PUB):

1ALtyqivh8VgnefQ8okroJUFuNqJYFgSac

然后我向该地址汇入了 0.0001 个 Bitcoin, 以证明我在此时就已经获知了该收款地址,同时支付了 0.0001 个 Bitcoin 的交易手续费(其实可以更少一点), 该交易被收录到了于北京时间 2013.12.31 21:49 产生的新区块中。

至此,我们完成前向证明。

即,我们证明了「我在北京时间 2013.12.31 21:49 之前,就已经拥有该图片了」。

也即,我们在北京时间 2013.12.31 21:49 钱通过向 PUB 中汇款的方式,证明了我们在此刻之前已经获知了 PUB, 而获知 PUB 的前提是 获知 HASH2, HASH, 和 PIC.

至此我我们完成了整个证明过程,证明了我在北京时间 2013.12.31 21:32 - 21:49 这 17 分钟的时间段拥有这张截图,而在这之前或者之后,即使我拥有这种图片,和以上全部信息,也无法做出同样的证明,世上只此一份。

当然,你在今后出示这种图片的同时需要出示 HASH2.

或者你也可以通过某种方式把 HASH2 嵌入到原始图片中(这个工作需要你在做前向证明之前完成).

最后的福利:那个钱包里用于证明的 0.0001 Bitcoin 我没有取走,谁要就拿去吧。

笔记:公钥加密算法

在一年多以前,我曾计划写一个系列,关于密码学基础的科普文章。但当我写完第一篇,散列算法的时候,便觉得自己功力尚浅,仍需修炼。今天重新捡起来,写下去。

公钥密码学,也称非对称加密,可以说是现代密码学的基础设施之一。公钥密码学也可以说标志着现代密码学的诞生,让密码学从政府,军方之间的斗智斗勇,成为了具有严谨数学基础的学科。

目前使用最为广泛的公钥加密算法:RSA, 其发明者因此获得图灵奖(计算机领域的最高奖项).

应该说密码学一直以来和军队,战争都是密不可分的。

我们设想这样一个场景,同属一个阵营的两个部队,被相隔一段距离,其间都被地方部队占领,这意味着他们之间通过信使传递的所有信息,都是可能被敌人监控(阅读)的。

那么如何在事先没有沟通的情况下安全地交换信息呢?

对于经典的对称加密算法(对等加密, 共享密钥加密), 这是很难做到的。因为对称加密需要一个密钥(密码), 而两个部队事先是没有沟通过的,没有对密钥达成共识。

而且他们现在也不可能再协商密钥,因为现在他们所有的通信都是被监控的了,一旦他们在这种环境下协商密钥,那么敌人也会知道密钥,便也能解密他们之后传送的加密信息。

对称加密对加密和解密都使用同一个密钥,我们可能需要的是一种针对加密和解密,使用不同密钥的加密算法,这便是非对称加密的含义。

试想,部队A可以生成一对密钥,分别用于加密(公钥)和解密(私钥), 然后将公钥发送给部队B. B便可以使用这份密钥对信息进行加密,再将加密信息发送回A了。

这里的公钥,即使被敌人获取也没有关系,因为这里的公钥,仅仅能够用于加密数据,而唯一可以解密数据的私钥,自始自终都在A手中,从未公布出去。

这样一来,A和B便可以在受监控的情况下,没有实现沟通,便能安全地交换信息了。

让我们进一步设想,如果敌人可以篡改A和B之间发送的信息呢?

例如当A发送公钥给B的时候,敌人将公钥拦截下来,自己生成一堆公私钥,将自己的公私钥发送给B. 相当于敌人冒充了B与A建立联系,建立了两个加密通道,分别是从A到敌人,和从敌人到B.

这样以来,敌人便可以在两个通道之间,监控到A和B通信的明文了,同时敌人还可以任意篡改A和B之间发送的信息,即使它们已经被加密。

这便是经典的“中间人攻击”. 应该说如果A和B没有事先沟通过,而且没有一个可信的第三方,那么这个问题几乎是无解的。

但如果允许A和B事先进行沟通,该如何在敌人可以篡改信息的前提下,安全地交换信息呢?

其实这个问题很好解决,只需在实现沟通时互相交换密钥即可,其后敌人(中间人)便无法再进行冒充了,因为密钥根本没有在这时被交换。

然而更为通用的做法是使用“数字签名”,数字签名恰好是公钥加密的逆运算。即将加密密钥保密,而将解密密钥公布出去,使得只有自己可以加密信息,而任何人都可以解密信息。

要实现数字签名,只需自己将要签名的信息(通常是一个散列摘要值)加密并公布即可,其他人可以认为,凡是用你公布出去的解密密钥能解密的信息,都是你自己加密(签名)过的。

这样便可以识别一段信息,是否真正地由其宣传的发信人所发送,识别出被中间人所篡改的信息。

在前面的情况下,我们还需要考虑的是“重放”攻击,即中间人虽然不知道A和B传输的实际内容,但却可以将其中的一份信息复制两遍甚至更多,已达到干扰的目的。通常应对重放攻击只需在加密信息中约定一个递增的编号,或者时间戳即可。

下面我们来讨论公钥加密算法(RSA)背后的数学原理,本人数学很渣,只能大概谈谈应用RSA时需要了解的一些原理,更详细的数学原理请围观各种大牛的文章,如: http://www.matrix67.com/blog/archives/5100

RSA基于这样一个原理:计算两个数的乘积是十分容易,但对一个数进行因式分解,得到这两个数却十分不易。

可能这个原理并不直观,甚至有点反常识,但RSA选择的两个数的乘积,都是2^2048这样数量级的数字,换算为十进制,那么将会是1后面跟6000多个0.

直到目前,对大数进行因式分解仍是一个难题,数学家还没有找到比试除法更高效一点的方法,因此在目前,对一个足够大的数进行因式分解可以认为是一项不可能完成的任务。但也不排除今后有数学家发明进行因式分解的简单方法,届时,RSA算法,甚至整个密码学,整个世界都会坍塌。

有点虎头蛇尾啊,本来打算最后举一个RSA计算的例子的,结果还是写不下去 …

精子生于 1995 年,英文 ID jysperm.

订阅推送

通过 Telegram Channel 订阅我的博客日志、产品和项目的动态:

王子亭的博客 @ Telegram


通过邮件订阅订阅我的博客日志、产品和项目的动态(历史邮件):

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-ND  授权发布。最后生成于 2024-04-08.