对称与非对称RSA加密

加密方法根据是否使用同一把密钥,分为对称与非对称加密。使用同一把钥匙进行加密及解密,称为对称加密。使用一对钥匙,其中一把钥匙加密的内容,必须用与之配对的钥匙解密,称为非对称加密。对称加密是可逆的,非对称加密是不可逆的。

对称加密及密钥交换

异或运算就是一种对称加密。比如使用二进制密钥1111对二进制数字1010进行异或运算:加密过程1010xor1111=0101,解密过程0101xor1111=1010。第一次异或运算是加密,第二次异或运算是解密。数学过程就是AxorBxorB=A。异或是可逆运算,而取模是不可逆运算。比如5%3=2, 但是X%3=2求X,这X就有很多解,3*n+2,运算不可逆。

要使用对称加密通讯内容,就需要双方通过安全方式交换密钥。使用取模运算结合指数运算,就可以通过“迪菲-赫尔曼-墨克密钥交换方案(Diffie–Hellman–Merkle key exchange)”安全交换密钥。过程如下:

  1. 双方约定一个运算法则g^X%p。比如g=3, p=5;
  2. Alice选一个私密的数X=a,执行g^a%p运算得到A。比如a=2,A=3^2%5=4;
  3. Bob选一个私密的数X=b,执行g^b%p运算得到B。比如b=3,B=3^3%5=2;
  4. 通讯告知各自运算得到的结果,A=4,B=2;
  5. Alice通过自己私密的a=2和Bob告知的B=2,算出密钥K=B^a%p=2^2%5=4;
  6. Bob通过自己私密的b=2和Alice告知的A=4,算出密钥K=A^b%p=4^3%5=4;
  7. 之后采用对称密钥K加密内容进行通讯。

如下图所示,红色为私密内容,其它都可公开:

由于第三方不知道Alice和Bob内心想的那个数是什么,即便窃听了全部通讯过程,也无法算出密钥。

非对称RSA加密

若是使用非对称加密,就无需考虑密钥交换的事。将公钥PublicKey公开,隐藏与之对应的私钥PrivateKey。公钥加密的内容只能用与之对应的私钥解密,反之亦然。公钥加密的内容,只有拥有私钥的接收方才能解密,确保信息不泄露。私钥加密的内容,任何人都可以拿公钥尝试解密,验证发信人都身份,可当作电子签名使用。其中一种公开公钥的算法就是RSA加密算法。RSA是三个发明人首字母的缩写,Ron Rivest、Adi Shamir、Leonard Adleman。他们在文章《A Method for Obtaining Digital Signatures and Public-Key Cryptosystems》中描述了该方法。

简单说,随机挑选两个隐密的大质数p, q, 计算n=p*q,r=(p-1)*(q-1)。对信息M加密得到密文C=E(M)=M^e%n;对密文C解密得到原文M=D(C)=C^d%n。私钥是(d, n),公钥是(e, n)。私钥d满足gcd(d,r) = 1,gcd指greatest common divisor,最大公约数,即d是与r互质的整数;公钥e满足e*d%r=1,e和d相乘对r取模,余数是1。使用公钥加密过程为Encryption E,使用私钥解密过程为Decryption D,密文称为Ciphertext C。E, D满足:D(E(M))=M,E(D(M))=M,即用其中一把钥匙加密对内容,要用与之配对的钥匙解密。

整个过程:

  1. 随机私密大质数p, q, 计算n=p*q, r=(p-1)*(q-1);
  2. 挑选私钥d,满足gcd(d,r)=1;计算公钥e,满足e*d%r=1;
  3. 销毁p, q, r;公开公钥(e, n),保密私钥(d, n);
  4. Bob发信息M给Alice,就用Alice的公钥(e, n)加密:C=M^e%n;
  5. Alice收到密文C,用自己的私钥(d, n)解密:M=C^d%n。

举个简单例子:

  1. 挑选p=2, q=5,计算出n=10, r=4;
  2. 挑选私钥d=3,计算出公钥e=7;(可在WolframAlpha 输入gcd(x,4)=1挑一个3,输入x*3%4=1挑一个7);
  3. Alice全网公开公钥(7, 10), 保密私钥(3, 10);
  4. Bob发信息2给Alice,使用Alice的公钥(7, 10)加密:2^7%10=8 (在WolframAlpha 输入2^7 mod 10得到8);信息2使用Alice的公钥加密后的密文是8。
  5. Alice收到密文8,使用私钥(3, 10)解密:8^3%10=2。2这就是Bob发给Alice的信息。

示意图如下:

每个字母通过ASCII表都对应着一个数字编码,通过将数字进行RSA加密,就可以保证通讯过程即便被监听,通讯内容也不会被第三方知道。上面的n=p*q=10,换算成二进制就是1010,4-bit加密。HTTPS通讯协议,zerossl默认证书是RSA-4096bit加密。ProtonMail默认是RSA-2048bit加密。

要破解RSA,方法是因数分解n,取得p和q。目前就是拼计算机的速度,遍历法求解。比如上文的n=10,一猜就是p=2, q=5。目前有记录的,被破解的最长RSA密钥是768位,2009年被破解。

2019/12/29, Sat

转行的代价-J曲线

两年前开始写订阅号,后来因为毕业的事,毕业之后因为转行的事,停更了一年多的时间。经历了不少事,现在依然没站稳脚跟,不能算转行成功。

毕业之前,曾想象过在学术圈工作三四十年的状态,有点发怵。自己在科研方面已经江郎才尽,对学术上的热情已经被榨干,实在撑不起三四十年。身边有朋友转行去互联网、金融等领域,我自己看好物联网,教授也给机会让我负责一个创业项目。于是毕业之后,就开始了创业。当然,既然拿着博后的工资,基金申请、审稿、项目结题啥的,该负责都还是得做。只是少看paper,不做实验罢了。

创业公司的商务和技术都是从零开始搞,与当初进入学术圈不同。搞科研,身边都是学习的榜样;创业,没在对的圈子里,只能到处找资源、认识人、看公开课、自学。从注册公司、开户、公司秘书、会计、审计,到后期的商业计划书、股份、融资,都得搞。技术方面,Linux服务器、Java编程、嵌入式C、PCB schematic、layout、assemble都学。一年多弄下来,感觉啥都懂一些,却没有一样是精通的。

创业的经历跟我进入学术圈的途径不一样。进学术圈,是从第一线动手开始,本科跟着师兄师姐做样品做测试;硕士把好朋友的研究方向学来,在自己实验室重现,小创新,开个研究方向;博士则完全“自学”,选题、搭实验设备、写代码批量处理数据、提出新的研究思路、发表论文、最后是申请基金。整个过程是从最具体的动手做实验,到最抽象的动脑写论文写本子。而这次的创业经历,则是完全相反的路径。教授手里有核心的算法,要补上硬件和软件,才能做成产品。我还不懂软硬件技术实现的时候,就开始做统筹规划的事,然后自学补上技术。是从动脑到动口、动手。开始是找代工,接着跟工程师了解技术,最后才是自己动手做小修改。从跟投资人谈业务到跟工程师谈技术实现,到现在自己能动手搭个网页、改个硬件功能。搞科研,我基础不差,能从零开始搞出一个课题。公司的业务,没有工程师,我只能空谈技术和任务拆分,有点浮沙筑高楼的感觉。还需要点时间吧,毕竟科研搞了七年才入门,创业才搞了一年多。

整个过程,我经历过一个恐慌期。刚开始的时候,接触到的一切都是新东西,给我极大的不安全感。最近开始接触商业模式、市场、变现之类的事,同样面对大量的新东西,只是我能说服自己不必再像当初一样恐慌。只要多点耐心,总能爬上新的高峰。要从一个小山头爬到另一个小山头,必须得先下山,熬过低谷,才能慢慢爬上新的高峰。这期间,就怕意志动摇,稍微下行,就怀疑自己,退回原处,一辈子安于那个熟悉的小山头。要是一直不安于现状,想爬上新的高峰,就得反复经历这样的J曲线。最后回头看,一段段的J曲,会拼接成一条螺旋上升曲线。

2018/12/22, Sat

安全邮件ProtonMail

网上的一切服务都经由服务器提供,邮件服务也不例外。若是邮件内容以明文方式存储在服务器,就有可能被“非法”访问。

比如,在你“不知情”的条件下,第三方服务获取了读写你邮件的权限,就可以无障碍阅读你的邮件。Gmail邮件门事件就是用户主动授权给第三方,使得第三方可以明文阅读用户的邮件。无需知道你的邮件秘密,只需要你授权告知Google,Google就能开放权限给第三方明文阅读你的邮件。

也就是说,有一种方法,可以越过你的密码验证,只要Google点头,就可以无障碍读写你的邮件。而实际上,Google就曾通过扫描用户的邮件,获取私人信息,用于他的广告业务[1]。谷歌告诉华尔街日报,其内部员工可以在“特殊情况”下访问用户的电子邮件, 例如为了安全,需要获取用户信息调查数据泄露或滥用。邮件门事件中的电子邮件管理公司Return Path软件公司,扫描过2百万注册用户的邮件,他们的电脑每天扫描分析1亿封邮件。他们的员工为了训练自己的软件算法,读过8千多封私人邮件[2]。

拿我自己的学校邮箱举例。因为它是明文存储,我自己作为普通用户能读取的文件,管理员root用户就可以无障碍读写,也可以授权其它用户读写。如下图所示,只要有必要,完全可以检索分析出,我在什么时候,给谁,发过什么内容的邮件。也可以统计出我使用邮件的习惯,全部关键词,我的全部联系人,等等等。任何使用该邮件服务的用户,包括各个级别的教授,只要需要,管理员root用户都可以分析统计并修改他们的邮件。这是指从原理上能技术实现,至于用户和邮件是否被分析,不是技术问题。

有一种方法可以防止服务器管理员读写我们的邮件,那就是将邮件加密后存储在服务器中。虽然管理员依然可以读取邮件的内容,但因为邮件的内容是加密的,所以看到的是加密后的乱码。如下图,test1.me@protonmail.com 发邮件到test2.me@protonmail.com,内容分别为hi1和hi2,因为邮件是端到端(End-to-End Encryption, E2EE)加密的,所以服务器存储的是乱码。即便服务器被非法访问,读到的也是加密后的密文,无法使用。

端到端加密 (E2EE),是指通过公钥-私钥对(public key-private key)加密通讯的内容(注:并不是加密通讯过程)。公钥加密的内容,只能被配对的私钥解密,反之,私钥加密的内容,只能用配对的公钥解密。通常,公钥会对全网公开,私钥自己保存。

比如Bob和Alice通讯。Bob和Alice都有各自的公钥-私钥对,且称为Bob-PublicKey,Bob-PrivateKey,Alice-PublicKey, Alice-PrivateKey。Bob发邮件给Alice,为了保证内容只被Alice读出,Bob会使用Alice-PublicKey加密。即便通讯被监听,第三方拿到邮件内容,也只有Alice用Alice-PrivateKey才能解密,阅读。为了确保邮件的确是Bob发出,而不是别人伪造的,Bob会用自己的的PrivateKey再加密内容。若是第三方谎称自己是Bob给Alice发邮件,那Alice只要使用Bob-PublicKey尝试解密,只要能顺利解密,就能验证,这是Bob发来的邮件[3]。

图片引自ProtonMail: How does end-to-end encryption work?

ProtonMail (PM) 就是采用来端到端加密的邮件服务,保证了只有通讯双方才知道邮件内容。整个过程都自动完成,无需用户理会,跟普通邮件的使用过程一样。PM服务器存储的是加密后的内容,无法被任何第三方读取。

如果是PM与PM之间的通讯,默认是E2EE加密;若是PM到跟其它邮件系统通讯,那就不是E2EE通讯;但保存在PM服务器的内容,任何情况下都是E2EE加密的[4]。为了保证通讯内容是E2EE,最好双方都使用PM。或者通过PM提供的“Encrypt for non-ProtonMail users”功能,手动设置密钥。对方收到邮件链接,而不是邮件明文;通过密钥登陆PM临时邮件系统,查看内容。比如HSBC Enterprise给我Gmail发邮件的时候,就是用这种方式,我需要通过链接登陆他们的系统读取邮件内容,不能直接在Gmail上查看。即便是只有你自己使用PM,用最省事的方式直接发邮件给非PM用户,也至少保证了,PM服务器无法从我这一端读取邮件。至于对方服务器是否监听通讯内容,PM控制不了。

有不少提供E2EE邮件服务的公司,其中PM是最流行的。据说有些线人爆料,会要求记者提供PM邮箱收取内容。还听说,Snowden除了Lavabit就是使用PM。PM邮件可以免费使用,500M空间,够一般用户私人使用。若要更多存储空间或其它功能,需要付费订阅。通过设置自己操作系统的时间为黑色星期五,网页登陆PM邮件系统后,有30~50%的优惠,这是官方故意留的后门。它提供域名邮箱,提供公司邮件系统服务。尤其是对于公司,各式企业邮箱服务,若非E2EE,通讯内容都是被明文存储在服务器。如果需要,邮件服务商都可以明文读取邮件内容,窃取商业机密。

PS:

  • 我跟PM及Gmail不存在利益关系,是两者的普通用户。
  • PM也可以想法子窃取用户的邮箱密码。但保护用户隐私是他们的商业模式,若被发现它们窃听某用户邮件,所有用户都会瞬间抛弃它。
  • Gmail的用户并非Google的客户,它要靠广告客户盈利。如果我不是他的客户,那我就会成为它的产品,被卖给它的客户。Google和Facebook都一样,是由商业模式决定的。

参考资料:

  1. Google to Stop Reading Users’ Emails to Target Ads
  2. Tech’s ‘dirty secret’: App developers are sifting through your Gmail
  3. 省略了通讯过程中非对称加密的很多细节
  4. What is encrypted?

2018/12/11, Tue

专利是情报

专利是情报,而不是申请。这是昨天听一个专利检索软件的入门讲座时学来的观点。

以前作为在校学生,提到专利,想到的词就是“申请”。专利基本跟“paper”是一个意思,都跟动词“写”搭配,写paper,写专利。曾经有一个博士毕业的师兄,去企业研发部,据说就是写专利,申请专利。如今在创业公司,投资人总问公司有什么专利。他们想通过专利确保项目有技术壁垒。有时候,写那些专利,不见得技术真多么原创多么牛,专利也不是为了告别人侵权,而是保护自己,防止别人申请了专利,反过来告我们侵权。这就是在此之前我对专利的理解。

“专利是情报”指的不是申请专利,而是研究别人的专利。可以通过研究竞争对手的专利,了解对方公司的技术方案与部署。从这个角度看,专利就是情报。既然是情报,自然要加密。比如,明明是与汽车相关的专利,非要写成会移动的盒子。比如明明是自己公司的专利,非要弄个子公司申请,还把公司名字写错。

同样道理,自己公司申请专利的时候,也意味着是在泄露公司情报。为了不被竞争对手轻易解读,我们写专利的时候就要尽可能隐晦。既要达到保护自己防止被告侵权的目的,又要尽可能少泄露公司的情报。即便最后肯定会被对方解读出来,那也要尽可能地拖延对方公司的进度,耗费对方公司的资源。题目要抽象,摘要要含糊,内容要晦涩。能耗对方工程师两个小时去看原文,就绝不能让他们花两分钟看个摘要就弄懂,更不能让他们扫一眼题目就知道怎么回事。

Paper就是另外一回事,追求的是影响力引用率。要尽可能写得浅显易懂,能题目就解释清楚的事,绝不能浪费读者去读摘要的时间。能用一百字摘要讲明白的事,就别耽误人去读正文。总之,越简单明了越有利于文章的传播,方便读者引用,提高影响力。

公司跟学校还真不一样。在学校,即便是写专利,教授们也只是想法子让它涵盖更多的内容,多引申拔高,从来没听说过要对情报进行加密。也愿意去做报告,让越多的人知道越好。

2018/12/6, Thu