从简单的凯撒暗码和波利比乌斯暗码简介到多轮加密的 DES 和 AES 算法,懂得加密算法的根本概念。

原文标题:《科普 | 从数学到物理学:加密算法简介》
撰文:George Moraetes
翻译 & 校订:闵敏 & 阿剑

是否是只要那些数学脑筋很好的人,才能懂得那些在信息安然中常经常使用到的技巧(暗码学)?假设你要成为暗码学家,那能够是的,毕竟暗码学家的任务就是构造极难破解的加密算法。然则加密办法在铛铛代界的用处曾经异常广泛了,从保护用户的信用卡信息、保护长途用户的搜集连接,到保护智力产权、防止盗版,暗码学无处不在。

我这篇文章的目标,就是把令人望而生畏的暗码学转述成大年夜白话,让大年夜家都能懂得这些办法是若何用来加密数据的。

科普 | 从数学到物理学:加密算法简介暗码学就是数学和物理学的组合;它是信息安然技巧的核心,保护我们的数据安然和隐私

暗码学(Cryptology)的汗青

「cryptology」 和 「cryptography」 两个词在现代的文献中常常是无差别混用的,这就把对它们实际意义的混淆延长到了语义学中。实际上,这几个不合的词语最好如许解释:

  • Cryptology(暗码学) —— 对保密技巧的艺术性 和 / 或许 暗码体系迷信性的研究
  • Cryptography(暗码设计学)—— 设计暗码体系来保密的实用办法
  • Cryptoanalysis(暗码学分析)—— 努力于发明无需得知密钥或算法就可以从密文中反推出明文的马脚

译者注:正如作者所说,在现代的文献中,「cryptology」 和 「cryptography」 根本上是没有差其他了,都是 「暗码学」 的意思,并且,暗码学固然脱胎于加密办法研究,但现代的暗码学早已不止于研究加解密,而是延长到了研究若何保证通信中的 「机密性」、「身份同一性」 等属性上。是以,可以说,作者这里的定义即使不算过时,也至少是窄化了暗码学。不过,出于懂得作者原意的须要,对下文中的照应词语,我们仍沿用此处的翻译。

本文的绝大年夜部分篇幅是在解释 「Cryptography (暗码设计学)」,也就是今时昔日的暗码学实际,也欲望读者能认识到这几个词的含义和差别。

就其本身而言,暗码学作为一种迷信的研究曾经存在了很多年,已知最早的一个暗码设计学的例子是在一段刻于公元前 1900 年的铭文,是在埃及贵族 Khnumhotep 二世坟场的主墓室里发明的。那个雕刻者到处应用一些奇怪的符号来代替更罕见的符号。不过目标仿佛其实不是隐蔽信息,只是为了改变其情势,让它看起来更崇高一些。

科普 | 从数学到物理学:加密算法简介

在罗马帝国的壮盛时代(公元前 100 年),Julius Caesar (凯撒大年夜帝)也因应用加密技巧向前哨将军传送消息而有名。这类字符调换型加密办法(cipher)被称为 「凯撒暗码」,能够是文献中最常提到的人类曾用过的加密办法。(所谓 「cipher」,就是用来加密或许解密的算法)。所谓 「字符调换型加密办法」,就是把明文(我们想要加密的消息)中的每个字母都换成另外一个字母,构成密文(即被编码过的消息)。凯撒所用的办法是把每个字母位移三位,比如,「A」 会被换成 「D」,「B」 会被换成 「E」,以此类推(都是换成该字母前面第三个字母)。照应地,最后的几个字母会被换成开首的字母,比如 「X」 会被换成 「A」。

在第二次世界大年夜战时代,美国海军从纳瓦霍人(Navajo)中招募并练习了很多闇练应用纳瓦霍语的人。从编码消息的角度来看,这是个绝妙的办法,由于很少有纳瓦霍人以外的人学过怎样说这类说话,并且当时还没有效纳瓦霍语出版的书。然则除词语以外,纳瓦霍人的白话其实不是非常复杂(按暗码设计学的标准来看),一个母语为纳瓦霍语的人再加上一个练习有素的暗码学家,协作起来完全可以破解这套暗码。日自己曾经有过一次机会,就是在 1942 年 「巴丹逝世亡行军(Bataan Death March)」 时代他们在菲律宾捉住了 Joe Kieyoomia。Joe 是美国海军的一名纳瓦霍中士,但他其实不是密语播报员,只担任翻译无线电消息。只不过,由于他没有参与过密语练习,这些词语是甚么意思他一点也不懂。当他说本身不克不及解读这些消息时,日自己就开端严刑鞭挞他。是以,日本陆军和海军历来没有破译过这些密语。

再到 1970 年代,IBM 发明他们的客户须要某种情势的加密手段,所以他们成立了一个暗码学小组,由 Horst-Feistel 领头。他们设计出了一种加密算法叫 「Lucifer」。1973 年,美国国度标准局(如今叫做国度技巧与标准局,NIST)放出话来,欲望大年夜家能提议一种够格成为国度标准的数据加密办法。他们明显曾经认识到,本身买了很多并没有甚么暗码学基本的贸易产品。Lucifer 终究被接收了,是以叫做 「DES (数据加密标准)」。1997 年今后,DES 被穷举式搜刮进击攻破。DES 的重要成绩在于加密密钥的位数太小。随着计算机运算力的增长,经过过程暴力穷举一切能够的密钥组合来破解密文渐突变成了一种可行的办法。

在 80 年代,大年夜家简直只要一个选择,就是 DES。明天的情况曾经大年夜不雷同了,有一大年夜堆更结实、更快,设计也更好的算法可供选择。成绩曾经变成了你若何厘清这些选择。

1997 年,NIST 再次收罗新的加密算法提案,终究收到了 50 份提案。2020 年,NIST 接收了 「Rijndael」 算法,并定名为 「AES」,高等加密标准。

基来源基本理

所谓加密,就是一个改变数据,使之变得弗成辨识、无授权者没法应用的过程;同时,它还要包管解密过程能成功把改变后的数据恢复成原始情势。安然技巧普通都把加密的数学办法和用于加密的参数(叫做 「key (密钥)」)差别开来。被选定的密钥(平日是一段随机的字符串)也是加密过程的输入,对加密过程来讲也是必弗成少的。同一把密钥常常也是解密过程的须要输入。

这个保护过程的道理是,只需密钥(有时辰也叫 「口令」,password)没有裸露、只被取得授权的人所知,那么原始数据就不会裸露给其他人。只要知道密钥的人才网job.vhao.net能解密密文。这个思路,我们叫 「私钥」 暗码设计学(译者注:称作 「对称暗码学」 能够更恰当一些,由于加解密过程是对称的,都应用同一把密钥),也是最广为人知的加密情势。

那么,加密之所以须要的根本来由以下:

  • 机密性(confidentiality)—— 在传输数据的时辰,不欲望窃听者可以或许知道被广播的消息的内容。在保管数据的时辰不欲望未经授权的人(比如黑客)可以或许拜访,也是同理。

  • 身份认证(Authentication)—— 相当于签名。收信者欲望能确证该信息是特定的某小我收回的,其他人不克不及假装(乃至初始发信方前面想狡赖也弗成能)。

  • 完全性(Integrity)—— 这意味着收信者可以或许证明本身取得的数据是完完全整、没有经第三方修悛改的。
  • 弗成狡赖性(Non-repudiation)—— 防止发信方狡赖本身创建过、发送过某条消息。

译者注:作者在这里提到的才算是现代暗码学研究的范围。比如身份认证和弗成狡赖性,都是很重要的属性,然则在实用中简直与加解密过程有关,但对数字签名的研究毫无疑问是暗码学的内容。加解密的安然性跟机密性有关,只是现代暗码学的一部分。

Cipher

暗码设计学是(经过过程加密)隐蔽敏感数据的艺术和迷信。它包含加密过程(就是在原始的 「原文」 上应用加密算法)和解密过程(就是在密文上应用算法,使之恢复到可读的情势)。

要解释甚么是 Cipher,最好照样给你看几个简单的例子:

波利比乌斯暗码

波利比乌斯暗码(Polibius Cipher)也是一种字符调换型暗码。在我这个示例中,我用的是一个 6×6 的二维矩阵,可以把一切的大年夜写字母和数字 0 到 9 都包含出来。然后我们可以得出下表:

科普 | 从数学到物理学:加密算法简介

有了这个矩阵,我们便可以开端代换了。比如,字母 「A」 可以表示成 「1 × 1」,或许 「X = 1,Y = 1」,乃至再简化成 11。再举例,字幕 「N」 可以表示成 「2 × 3」,或许 「X = 2,Y = 3」,简化后就是 23。

来尝尝加密一条简单的信息:

消息(原文):ENCRYPT ME 2 DAY

加密后的数据(密文):51–23–31–63–15–43–24 13–51 55 41–11–15

归入冷僻字符后,这张表可以变得很大年夜很复杂。并且,定期地随机改变字符的地位也会让暴力破解无从下手。这很像我们明天在高等计算型加密办法所用的多态性(polymorphism)。

凯撒暗码

科普 | 从数学到物理学:加密算法简介

汗青最悠长的加密算法之一就是以其创造者凯撒而有名的凯撒暗码(Caeser Cipher)。他用这套办法来包管跟罗马将军们的安然通信,如许罗马帝国的仇人们就算拿到信也没有办法读懂。凯撒暗码是加密的一种低级情势,很轻易被破解,所以明天曾经根本不会用在任何安然用处中了。

从道理下去说,凯撒暗码就是重排字母表,不合的位移值也会使得编码后的数据完全不合。位移值,望文生义,就是经过过程让字母左移或许右移必定位数来生成密文的数值。(译者注:所以,在这里,大年夜家可以把凯撒暗码懂得成一种根据字母表次序的位移来加密的算法(cipher),而位移值就是那个 Key,密钥。)

这里我们用右移 3 位的做法来看一个实际的例子:

英文原文:ENCRYPT ME

密文:HQFUBSW PH (解密时辰要照应左移 3 位才能解密)

下面这条消息可以经过过程测验测验一切能够的位移值来暴力破解:赓续测验测验新的位移值,直到解出来的原文看起来像模样。加倍复杂的暗码比如 Vigenere 暗码和 Gronsfeld 暗码也是用异样的道理设计出来的。然则解密起来就很费事,是以每个字母都代表一个位移值。

维吉尼亚暗码表

科普 | 从数学到物理学:加密算法简介

在懂得暗码设计学之前,我们先要懂得加密算法的任务道理,由于它们是一切加密过程的基本。速记是一种记录隐蔽信息的办法,实际上可以归为古典暗码设计学一类,由于现代暗码设计学曾经成了 「计算机安然」 的代名词。

多态性

多态性是暗码设计学中较为高等的部分,在计算机加密技巧中最为罕见。多态性指的是,一种加密办法在每次应用时都邑产生不合的成果,并且在每次应用过后都邑产生改变。多态性罕见于计算机加密算法。也就是说,假设我们将雷同的数据加密两次,每次都邑取得一个不合的加密成果。

我们用汽车钥匙来打个比方。如今,我们只须要在一个小巧的电子遥控设备上悄悄一按,便可以解锁汽车了。当你解锁车门时,你或许历来没思虑过个中的道理 —— 你按下按钮的那一刻,会有一段特定的数据发送到你的车上,一旦婚配成功,车门就解锁了。要完成这点,最简单的办法是为每个遥控设备设定不合的频率。然则,如许管理起来会很费事。是以,一切遥控设备都采取了异样的波长,然则应用不合的算法(转动码)来生成发送给汽车的数据。这些就是多态性算法。

由于这些算法每次应用过后都邑产生改变,很难对其停止逆向工程。即使有黑客破解了算法(起首,破解多态性算法本身难度就很大年夜),他还得找到与该算法婚配的汽车 / 钥匙(这又是一项复杂的义务)。

经常使用算法

现如今,经常使用的加密算法不过乎私钥加密办法和公钥加密办法。私钥加密办法可以用来保护关键 / 敏感数据。密钥密文只需一把钥匙(由通信两边共享)破解,是以被称为对称性暗码设计学。

科普 | 从数学到物理学:加密算法简介

1949 年,贝尔实验室的 Claude Shannon 公布了私钥加密办法的根本实际。数十年来的演变曾经孕育出了很多高质量的私钥加密算法。但是,直到 1975 年,一个名为 DES 的强大年夜私钥加密办法才取得了广泛应用。

公钥 / 非对称性暗码设计学出生于 20 世纪 70 年代中期。公钥加密办法须要用到一对密钥,分别是对外地下的公钥和相对应的由小我持有的私钥。例如,接收方可以创建一对密钥,并将公钥分享给任何想要向 ta 发送密文的人。发送方可以应用公钥加密发送给接收方的信件,接收方可以用私钥来解密。

科普 | 从数学到物理学:加密算法简介

加密算法的强大年夜程度取决于三个重要身分:

  • 基本举措措施—— 假设相干暗码设计重要由软件完成,那么底层基本将是最脆弱的环节。假设你总是会加密某些信息,那么对黑客来讲,最好的做法是黑进你的电脑,在信息被加密前将其偷得手。比拟破解密钥来讲,入侵体系或许应用病毒感染体系要轻易很多。很多情况下,破解密钥最简单的办法是窃听用户,并在密钥被传入加密法式榜样时停止拦截。
  • 密钥长度—— 在暗码设计学中,密钥长度很重要。假设进击者没法装置按键监督器(keystroke monitor),那么破解密文的最好办法就是经过过程赓续的试错来暴力破解。实用的加密算法必须将密钥长度设定得足够长,来根绝暴力破解的能够性。然则,随着电脑运算速度一年比一年快,密钥长度的安然阈值也须要一向进步。专家们承认,小于等于 64 位的密钥,包含 DES 密钥在内,都很轻易被暴力破解。在 1999 年,电子前哨基金会(Electronic Frontier Foundation)赞助开辟了一种叫做 「Deep Crack」 的设备,可以在三天以内破解一个 DES 加密密钥。所以如今加密算法的密钥长度普通都在 100 位以上,多数算法支撑 256 位的密钥。
  • 算法质量—— 算法质量本身是很难评价的,基于一个现有算法去构造一个看似可行的算法是很轻易的,但只要经历老道的专家细心检查才能发明个中的奥妙马脚。算法中的马脚会产生 「捷径」,让进击者可以在暴力搜刮进击时辰跳过大年夜批密钥。举个例子,风行的紧缩法式榜样 PKZIP 之前持续了一个定制的的加密功能,应用 64 位的密钥。实际下去说,应当要 264 测验测验才能试完一切的密钥。但实际上,有捷径可走,所以进击 PKZIP 加密算法只需 227 次测验测验就可以破解密文。发明如许马脚的唯一办法就是测验测验破解算法,普通来讲就是应用关于其它算法的技能。只要在经过如许的分析和进击以后,算法的质量才会展示出来,所以,还没有找出如许的马脚,其实不代表这个算法永久不被发明有马脚。

算法的类型

DES—— DES 曾经经受住了时间的考验,多来年出版的研究都证清楚明了其质量。经过四分之一世纪的研究以后,研究员也只能找出一些猜想式的进击办法,并且实用性还不如暴力破解。DES 算法的唯一真实弱点就是它太短的密钥长度(56 位)。

科普 | 从数学到物理学:加密算法简介

三重 DES—— 应用 112 位或许 168 位的密钥持续三次应用 DES 算法。终究这个算法会比其它有类似强度的算法慢很多,并且,由于计算机照样强大年夜到了能破解这个算法,这一办法曾经过时了。

AES—— 高等加密标准(AES)支撑三种密钥大年夜小,128 位的、192 位的和 256 位的,而数据则按 128 位为一个组。如今 AES 被当作标准,全球都在应用。

Rijndael 暗码表

科普 | 从数学到物理学:加密算法简介

DES 是明白设计为内置在硬件中的,从没推敲过怎样让它在软件层面完成。后来,NIST 评价了履行效力和存储需求,包管 AES 能在 C 说话和 Java 说话中任务,既能在任务站中运转,也能在资本更无限的情况比如嵌入式 ARM 处理器和智能卡中运转。

固然荷兰研究院 Vincent Rijman 和 Joan Daemen 创造的 Rijndael 算法博得了 NIST 精算,但一切进入 AES 决赛的算法比拟较 DES 和 DES 的替换品都浮现出了巨大年夜的进步。一切这些算法都是分组加密(block cipher)算法并且支撑 128 位乃至更大年夜的密钥;没有一种算法有严重的马脚;终究选择实际上是暗码设计强度和性能的衡量。

AES 基于一种叫做 「置换-分列」 的设计道理,在计算中既有置换,又有分列,不管在软件层照样硬件层,计算起来都很快。不像其前辈 DES,AES 不应用费斯托暗码(Feistel)道理,AES 是 Rijndael 暗码的一种变种,应用固定的 128 位大年夜小作为输入,并且支撑 128 位、192 位 和 256 位的临界维数(critical dimension)。相反,Rijndael 设计标准仅指定了输入组和密钥的大年夜小都是 32 的倍数,最小是 128 位,最大年夜是 256 位。

AES 在一个 4×4 的字节矩阵上操作,这些举证叫做 「状况」。然则 Rijndael 算法的某些版本的输入组更大年夜,是以矩阵更大年夜。大年夜部分 AES 计算都是在一个特定的无限域内完成的。

AES 算法所用的密钥大年夜小会照应决定转换操作的反复轮数。对应关系以下:

  • 128 位密钥对应 10 轮反复
  • 192 位密钥对应 12 轮反复
  • 256 位密钥对应 14 轮反复

科普 | 从数学到物理学:加密算法简介

每轮都包含几个处理步调,而每个步调都包含 4 个类似但不合的阶段,个中包含取决于加密密钥本身的一个阶段。在解密的时辰,须要用同一把密钥来反向反复操作、将密文恢复成原文。

量子暗码学

科普 | 从数学到物理学:加密算法简介

下面这个图示说清楚明了量子密钥分发筹划(BB84 协定),它完成了一种包含量子力学的暗码学协定,可以或许包管安然通信。它让通信两边可以生成一个共享的随机密钥(是个对称密钥),这个密钥只要他们两边才知道,是以可以用于加解密消息。量子力学是一组描述构成宇宙的光子、电子和其它粒子活动规律的迷信定律。

业界一向在尽最大年夜尽力寻觅可以或许抵抗黑客进击的最高安然手段,而新一代的暗码设计学曾经从数学转向物理学。量子力学迷信家曾经进入暗码学的世界了,这些迷信家欲望应用量子力学的道理来发送没法被黑的消息。这就是 「量子暗码学」 的大年夜概,它是在之前这几十年里才生长起来的。

量子暗码学将本身的根扎在量子物理学中。构成我们这个宇宙的根本粒子具有内涵的不肯定性,能够同时存在于此处或彼处,也能够有不止一种状况。只要在撞上一个物体或许被丈量时,它们才会浮现出活动景象。

暗码设计学是信息安然的一个诱人范畴,也是最复杂的学科之一。不过,我们从简单的凯撒暗码和波利比乌斯暗码简介到多轮加密的 DES 和 AES 算法,信赖读者会认为懂得起暗码算法的概念来不那么复杂了。

关于暗码学这门迷信,我们曾经懂得其汗青、从最简单到最复杂的加密算法的根本概念。

来源链接:medium.com