Hello,密码学:第三部分,公钥密码(非对称密码)算法

《Hello,密码学:第二部分,对称密码算法》中讲述了对称密码的概念,以及DES和AES两种经典的对称密码算法原理。既然有对称密码的说法,自然也就有非对称密码,也叫做公钥密码算法。对称密码和非对称密码两种算法的本质区别在于,加密密钥和解密密钥是否相同

  • 对称密码的加解密密钥相同,用密钥A加密,也用密钥B解密。
  • 公钥密码的加解密密钥不同,用密钥A加密,而用密钥B解密。
非对称密码的爱心小锁

一、公钥密码产生的初衷

公钥密码产生的初衷就是为了解决 密钥配送 的问题。

Alice 给远方的 Bob 写了一封情意慢慢的信,并使用强悍的 AES-256 进行了加密,但她很快就意识到,光加密内容不行,必须要想一个安全的方法将加密密钥告诉 Bob,如果将密钥也通过网络发送,很可能被技术高手+偷窥癖的 Eve 窃听到。

既要发送密钥,又不能发送密钥,这就是对称密码算法下的“密钥配送问题”

解决密钥配送问题可能有这样几种方法:

  1. 通过事先约定的共享密钥解决
  2. 通过密钥分配中心解决
  3. 通过公钥密码解决
方法一: 事先约定的共享密钥

这种方法比较高效,但有局限性:

  • 只适用于较近的距离。也就是不必通过不信任的网络就能通信的情况,比如办公室内的同事之间,完全可以面对面传递一下密钥。一旦距离较远,无法面对面交互,就出现了问题。
  • 只适用于小规模使用。即使距离较近,但如果通信人数众多,比如一个公司有 1000 人,每个员工都可以和另外 999 个人进行加密通信,每个人都需要 999 个密钥,整个公司需要的密钥数量为 1000 × 999 ÷ 2 = 499500 个密钥,这显然不现实。
方法二:密钥分配中心

与方法一不同,密钥不再由通信个体来保存,而由密钥分配中心(KDC)负责统一的管理和分配。双方需要加密通信时,由 KDC 生成一个用于本次通信的通信密钥交由双方,通信双方只要与 KDC 事先共享密钥即可。这样就大大减少密钥的存储和管理问题。

因此,KDC 涉及两类密钥:

  • 身份密钥:代表通信个体身份的密钥,好比工卡。企业有 1000 个员工,KDC 中就保存 1000 个身份密钥,人来人往,身份密钥也随之发生变化。
  • 通信密钥:也叫做会话密钥,仅在一个通信会话过程中有效。

领略下 KDC 的过程:

  1. KDC 事先保存了 Alice 和 Bob 的身份密钥,分别记为 iKey-Alice 和 iKey-Bob,i 是 identity 的意思;
  2. Alice 向 KDC 发出要与 Bob 通信的请求;
  3. KDC 生成一个通信密钥,记为 cKey,c 是 communication 的意思;
  4. KDC 从数据库中调取 Alice 和 Bob 的身份密钥,用 iKey-Alice 对 cKey 进行加密后发送给Alice,用iKey-Bob 对 cKey 加密后发送给 Bob;
  5. Alice 使用 iKey-Alice 解密出 cKey 后,并使用 cKey 对信息进行加密后发送给 Bob;
  6. Bob 使用 iKey-Bob 解密出 cKey 后,并使用 cKey 对来自 Alice 的加密信息进行解密;
  7. 本次会话结束后,Alice 和 Bob 按照公司要求,在本地删除本次使用通信密钥 cKey。

KDC 通过中心化的手段,确实能够有效的解决方法一的密钥管理和分配问题,安全性也还不错。但也存在两个显著的问题:

  • 性能问题:由于所有的加密通信,都要和 KDC 发生交互,KDC 的负荷会随着通信会话的增加而陡增,一旦瘫痪,整个组织的加密通信都将瘫痪。
  • 安全问题:KDC 也是软件,也存在漏洞,黑客 Mallory 可能直接对 KDC 下手。一旦 KDC 的密钥数据库被破解,整个组织的加密通信都将被破译。
方法三:公钥密码

使用公钥密码,加密密钥和解密密钥不同,只要拥有加密密钥,所有人都能进行加密,但只有拥有解密密钥的人才能进行解密。于是就出现了这个过程:

  • 信息接收者事先将加密密钥通过普通途径发送给信息发送者即可,不必担心加密密钥被窃听;
  • 信息发送者使用加密密钥对信息进行加密并发送给信息接收者;
  • 信息接收者使用解密密钥对加密信息进行解密。

密钥配送的问题天然被解决了。当然,解密密钥丢失而导致信息泄密,这不属于密钥配送的问题。

下面,再详细看下这个过程。

二、公钥密码的基本流程

公钥密码流程的核心,可以用如下四句话来概述:

  1. 发送者只需要加密密钥
  2. 接收者只需要解密密钥
  3. 解密密钥须妥善保管,不能被窃听者获取
  4. 加密密钥无所谓,被窃听者获取也没关系

既然加密密钥是公开的,因此也叫做 “公钥(Public Key)”
既然解密密钥是私有的,因此也叫做 “私钥(Private Key)

公钥和私钥是一一对应的,称为 “密钥对”,他们好比相互纠缠的量子对,彼此之间通过严密的数学计算关系进行关联,不能分别单独生成。

在公钥密码体系下,再看看 Alice 如何同 Bob 进行通信。

公钥密码体系的通信

在公钥密码体系下,通信过程是由 Bob 开始启动的:

  1. Bob 生成公私钥对,妥善保管私钥
  2. Bob 将公钥发送给 Alice,公钥被 Eve 窃听也没关系
  3. Alice 使用 Bob 的公钥对消息进行加密
  4. Alice 将加密后的消息发送给 Bob,密文被 Eve 截取也没关系
  5. Bob 使用私钥对密文进行解密

过程看起来非常简单,但为什么即使公钥被窃取也没有关系?这就涉及了上文提到的严密的数学计算关系了。如果上一篇文章对称密钥的 DES 和 AES 算法进行概述,下面一节也会对公钥体系的数学原理进行简要说明。

三、RSA算法背后的数学原理

自从 Diffie 和 Hellman 在1976年提出公钥密码的设计思想后,1978年,Ron Rivest、Adi Shamir 和 Reonard Adleman 共同发表了一种公钥密码算法,就是大名鼎鼎的 RSA,这也是当今公钥密码算法事实上的标准。其实,公钥密码算法还包括ElGamal、Rabin、椭圆曲线等多种算法,这一节主要讲述 RSA 算法的基本数学原理。

  • RSA 加密公式:密文 = 明文 ^ E mod N
  • RSA 解密公式:明文 = 密文 ^ D mod N
  • RSA 公钥:{E, N}
  • RSA 私钥:{D, N}

一堆符号,解释下,E 代表 Encryption,D 代表 Decryption,N 代表 Number。

从公式种能够看出来,RSA的加解密数学公式非常简单(即非常美妙)。RSA 最复杂的并非加解密运算,而是如何生成密钥对,这和对称密钥算法是不太一样的。而所谓的严密的数学计算关系,就是指 E 和 D 不是随便选择的

RSA加密和解密
RSA的核心问题:生成密钥对

密钥对的生成,是 RSA 最核心的问题,RSA 的美妙与奥秘也藏在这里面。

  • 求 N
  • 求 L(L是生成密钥对过程种一个关键的中间变量)
  • 求 E
  • 求 D
接下来是一点点数学介绍了!

1. 求N

求 N 公式:N = p × q

其中,p 和 q 是两个质数,而且应该是很大又不是极大的质数。如果太小的话,密码就容易被破解;如果极大的话,计算时间就会很长。比如 512 比特的长度(155 位的十进制数字)就比较合适。

这样的质数是如何找出来的呢?需要通过 “伪随机数生成器(PRNG)” 进行生成,然后再判断其是否为质数。如果不是,就需要重新生成,重新判断。

判断一个数是否为质数,并不是看其能不能分解质因数,而是通过数学的判断方法来完成,比如费马测试和米勒·拉宾测试等。(描述复杂数学算法的念头还是算了吧)

2. 求L

求 L 公式:L = lcm(p-1, q-1)

lcm 代表 “最小公倍数(least common multiple)” 。注意,L 在加解密时都不需要,仅出现在生成密钥对的过程中

3. 求E

E 要满足两个条件:
1)1 < E < L
2)gcd(E,L) = 1

gcd 代表 “最大公约数(greatest common divisor)”。gcd(E,L) = 1 就代表 “E 和 L 的最大公约数为1,也就是说,E 和 L 互质”。

L 在第二步已经计算出来,而为了找到满足条件的 E,第二次用到 “伪随机数生成器(PRNG)”,在 1 和 L 之间生成 E 的候选,判断其是否满足 “gcd(E,L) = 1” 的条件。

可以使用“欧几里得辗转相除法”计算最大公约数。(描述复杂数学算法的念头还是算了吧)

经过前三步,已经能够得到密钥对种的 “公钥:{E, N}” 了。

4. 求D

D 要满足两个条件:
1)1 < D < L
2)E × D mod L = 1

只要 D 满足上面的两个条件,使用 {E, N} 进行加密的报文,就能够使用 {D, N} 进行解密。

"E × D mod L = 1" 在数学上的表述方式为:在以 L 为模的世界中,E 和 D 互为倒数。我们平时说的乘法中的倒数(比如 3 和 1/3),只是 L 为 1 的特殊情况

至此,N、L、E、D 都已经计算出来,再整理一下

求解目标 计算公式
求 N N = p × q (p 和 q 都是用 “伪随机数生成器(PRNG)” 生成的大质数)
求 L L = lcm(p-1, q-1)(lcm 代表计算最小公倍数)
求 E E 要满足两个条件: 1 < E < L,以及 gcd(E,L) = 1(gcd 代表计算最大公约数),即 E 和 L互质
求 D D 要满足两个条件:1 < D < L,以及 E × D mod L = 1
RSA密钥对
RSA 模拟实践

模拟实践的过程包括两部分,第一部分是生成密钥对,第二部分是对数据进行加解密。为了方便计算,都使用了较小的数字。

第一部分:生成密钥对

1. 求N
准备两个质数,p = 5,q = 7,N = 5 × 7 = 35

2. 求L
L = lcm(p-1, q-1) = lcm (4, 6) = 12

3. 求E
gcd(E, L) = 1,即 E 和 L 互质,而且 1 < E < L,满足条件的 E 有多个备选:5、7、11,选择最小的 5 即可。于是,公钥 = {E, N} = {5, 35}

4. 求D
E × D mod L = 1,即 5 × D mod 12 = 1,满足条件的 D 也有多个备选:5、17、41,选择 17 作为 D(如果选择 5 恰好公私钥一致了,这样不太直观),于是,私钥 = {D, N} = {17, 35}

至此,我们得到了公私钥对:

  • 公钥 = {5, 35}
  • 私钥 = {17, 35}

第二部分:模拟加解密

明文我们也使用一个比较小的数字 -- 4,利用 RSA 的加密公式:

密文 = 明文 ^ E mod N = 4 ^ 5 mod 35 = 9
明文 = 密文 ^ D mod N = 9 ^ 17 mod 35 = 4

尼玛,好大啊

从这个模拟的小例子能够看出,即使我们用了很小的数字,计算的中间结果也是超级大。如果再加上伪随机数生成器生成一个数字,判断其是否为质数等,这个过程想想脑仁儿就疼。还好,现代芯片技术,让计算机有了足够的运算速度。然而,相对于普通的逻辑运算,这类数学运算仍然是相当缓慢的。这也是一些非对称密码卡/套件中,很关键的性能规格就是密钥对的生成速度

网上搜索到的某密码卡性能参数

四、针对 RSA 的攻击

公钥密码体系中,用公钥加密,用私钥解密,公钥公开,私钥隐藏。因此:

  • 黑客能够拿到的信息:1)密文;2)公钥(即 E 和 N)
  • 黑客无法拿到的信息:1)明文;2)私钥(即 D 和 N);3)中间计算过程的信息(即 p、q、L)。当然,私钥中的 N 其实能够拿到,和明文的 N 是一样的。
攻击方式一:直接破解明文

加密公式为:密文 = 明文 ^ E mod N

破译的过程就是对该公式进行逆运算。由于除了对明文进行幂次运算外,还加上了“模运算”,因此在数学上,该逆运算就不再是简单的对数问题,而是求离散对数问题,目前已经在数学领域达成共识,尚未发现求离散对数的高效算法

攻击方式二:通过暴力破解求 D

暴力破解的本质就是逐个尝试。当前主流的 RSA 算法中,使用的 p 和 q 都是 1024 位以上,这样 N 的长度就是 2048 位以上。而 E 和 D 的长度和 N 差不多,因此要找出 D,就需要进行 2048 位以上的暴力破解。即使上文那个简单的例子,算出(蒙出) “9 ^ D mod 35 = 4” 中的 D 也要好久吧。

攻击方式三:通过 E 和 N 求出 D

因为 E 和 N 是已知的,而 D 和 E 在数学上又紧密相关(通过中间数 L),能否通过一种反向的算法来求解 D 呢?

  • E × D mod L = 1
  • L = lcm(p-1, q-1)

从这个地方能够看出,p 和 q 是极为关键的,这两个数字不泄密,几乎无法通过公式反向计算出 D。也就是说,对于 RSA 算法,质数 p 和 q 绝不能被黑客获取,否则等价于交出私钥

既然不能靠抢,N = p × q,N是已知的,能不能通过 “质因数分解” 来推导 p 和 q 呢?或者说,一旦找到一种高效的 “质因数分解” 算法,就能够破解 RSA 算法了

幸运的是,这和上述的“离散对数求解”一样,当下在数学上还没有找到这种算法,当然,也无法证明“质因数分解”是否真的是一个困难问题。因此只能靠硬算,只是当前的算力无法在可现实的时间内完成。这也是很多人都提到过的,“量子时代来临,当前的加密体系就会崩溃”,从算力的角度看,或许如此吧

既不能抢,也不能算,能不能猜呢?也就是通过 “推测 p 和 q 进行破解”

p 和 q 是通过 PRNG(伪随机数生成器)生成的,于是,又一个关键因素,就是采用的伪随机数生成器算法要足够随机

随机数对于密码学极为重要,后面会专门写一篇笔记

攻击方式四:中间人攻击(最常见的 RSA 攻击手段)

前三种攻击方式,都是基于 “硬碰硬” 的思路,而 “中间人攻击” 则换了一种迂回的思路,不去尝试破解密码算法,而是欺骗通信双方,从而获取明文。具体来说,就是:主动攻击者 Mallory 混入发送者和接收者之间,面对发送者伪装成接收者,面对接收者伪装成发送者。

中间人攻击

这个过程可以重复多次。需要注意的是,中间人攻击方式不仅能够针对 RSA,还可以针对任何公钥密码。能够看到,整个过程中,公钥密码并没有被破译,密码体系也在正常运转,但机密性却出现了问题,即 Alice 和 Bob 之间失去了机密性,却在 Alice 和 Mallory 以及 Mallory 和 Bob 之间保持了机密性。即使公钥密码强度再强大 N 倍也无济于事。也就是说,仅仅依靠密码算法本身,无法防御中间人攻击

而能够抵御中间人攻击的,就需要用到密码工具箱的另一种武器 -- 认证。在下面一篇笔记中,就将涉及这个话题。

好了,以上就是公钥密码的基本知识了。

五、混合密码体系

公钥密码体系能够完美的解决对称密码体系中 “密钥配送” 这个关键问题,但是抛开 “中间人攻击” 问题不谈,公钥密码自己也有个严重的问题:

公钥密码处理速度远远低于对称密码。不仅体现在密钥对的生成上,也体现在加解密运算处理上。

因此,在实际应用场景下,往往会将对称密码和公钥密码的优势相结合,构建一个 “混合密码体系”。简单来说:首先用相对高效的对称密码对消息进行加密,保证消息的机密性;然后用公钥密码加密对称密码的密钥,保证密钥的机密性。

下面是混合密码体系的加解密流程图。整个体系分为左右两个部分:左半部分加密会话密钥的过程,右半部分是加密原始消息的过程。原始消息一般较长,使用对称密码算法会比较高效;会话密钥一般比较短(十几个到几十个字节),即使公钥密码算法运算效率较低,对会话密钥的加解密处理也不会非常耗时。

著名的密码软件 PGP、SSL/TLS、视频监控公共联网安全建设规范(GB35114) 等应用,都运用了混合密码系统。

1. 混合密码体系-加密流程
混合密码体系-加密流程
2. 混合密码体系-解密流程
混合密码体系-解密流程

好了,以上就是公钥密码算法的全部内容了,拖更了很久,以后还要更加勤奋一些。


为了避免被傻啦吧唧的审核机器人处理,后面就不再附漂亮姑娘的照片(也是为了你们的健康),改成我的摄影作品,希望不要对收视率产生影响,虽然很多小伙儿就是冲着姑娘来的。

就从喀纳斯之旅开始吧。

喀纳斯-月亮湾
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,214评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,307评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,543评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,221评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,224评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,007评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,313评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,956评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,441评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,925评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,018评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,685评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,234评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,240评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,464评论 1 261
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,467评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,762评论 2 345