分区容忍系统

动机

应用需要存储持久的信息,可用性取决于数据的可用性

共识的复杂度

需要共识来保证数据的一致性

冗余的代价随着节点数的增加而增加:

  • 当所有节点都参与时,共识算法的消息数量与节点数呈线性增加
  • 平方的复杂度\rArr可扩展性差

因此只使用一部分节点参与共识,例如每个集群5台机器(Chubby)。

故障恢复也需要使用共识来决定哪些机器在运行或宕机,每个故障都需要运行共识算法,因此也与节点数成比例增加(线性)。当故障频率不高的时候开销不大。

故障

  • 硬件、软件
  • 机架、网络交换机、电源
  • 运行较慢的计算机和网络
  • 数据中心

大型系统中总会有一部分磁盘、计算机或交换器出现故障,因此需要考虑故障的发生。

可扩展性(Scalability)

通常意义上,可扩展性指通过增加资源来提高性能(吞吐量、延迟或两者同时):

  • 更多的工作单元(水平扩展):关注每秒处理的请求数量
  • 更大的工作单元(垂直扩展):关注解决更大的问题(高性能计算)

但是有时可扩展性也指,通过增加资源来提高冗余度,同时不降低性能

  • 提高持久性(durability)
  • 提高可用性(availability)

异构系统(heterogenous systems)中,新增加的机器能力比初始的机器更强,可扩展性需要解决这个问题。

系统规模越大,每台机器需要的运行系统的人员就越少(economy of scale)。

继续阅读“分区容忍系统”

基于模二次剩余的对称与非对称加密算法

首先介绍有关模二次剩余的相关数论基础。然后介绍了BBS伪随机数发生器的构造以及使用BBS PRNG的对称机密系统。此外介绍因数分解假设以外的另一种假设——二次剩余假设在公钥密码系统的应用,即Rabin算法。

二次剩余的数论基础

二次剩余的定义

QR_n \coloneqq {x \in Z_n^* \ | \ \exists y \in Z_n^*: y^2 \equiv x \ \ mod \ n}

给定模n乘法群,如果对于x \in Z_n^*,存在群元素y满足y^2 = x,则x是一个二次剩余,此时y是x的一个根。QR_n是模n二次剩余的集合。

一个元素不是二次剩余就是二次非剩余,集合记作QNR_n

QR_n乘法群

对于QR_n的元素x_1x_2有以下性质:

  • x_1 \cdot x_2 \in QR_n

    两个群元相乘结果仍在群中

  • x_1^{-1} \in QR_n

    存在逆元

素数模二次剩余Z_p^*

当p>2且为素数时,Z_p^*中每个二次剩余都有两个平方根。因此平方取模的函数具有“二对一”的映射关系,这意味着Z_p*中恰好有一半的元素为二次剩余,也即|QR_p| = \frac{p-1}{2}

讲义上给出的是Z_p域,有小于等于2个根。

x \not\equiv 0, p \ne 2时,有0或2个根。

Jacobi符号

设p>2且为素数,x \in Z_p^*,Jacobi符号定义为:

\Bigl(\frac{x}{p}\Bigr) \coloneqq \begin{cases}
    1 &\text{if } x \in QR_p\\
    -1 &\text{else}
\end{cases}

实际上还有一个符号称为Legendre符号,要求模数必须为奇素数。而Jacobi符号的模数可以是任何正整数。所以Jacobi符号是Legendre符号的推广,当模数为奇素数时,Jacobi符号等于Legendre符号。

欧拉准则 Euler Criterion(模p二次剩余的判断)

\Bigl(\frac{x}{p}\Bigr) \equiv x^{\frac{p-1}{2}} mod p

欧拉准则用于判断x是否是素数p的二次剩余

继续阅读“基于模二次剩余的对称与非对称加密算法”

Basics of Cryptology 密码学基础

本文介绍密码学基础,对称及非对称算法用于加解密或身份认证、密钥生成和密钥分发问题。

保护目标

密码学可实现的保护目标:

  • 机密性,称为隐蔽(concealment)
  • 完整性,称为身份认证(authentication)

密码学无法实现的保护目标:

  • 可用性

Kerckhoff原则

加密方法一定不能是保密的,且一定要很容易被敌人获取到。

The cipher method must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.

因此:

  • 只能使用公开的、经过良好分析的算法和协议
  • 不要相信“超级安全”但保密的算法
  • 不要试图设计自己的算法(除非你是密码学专家)
  • 结合不同的安全模块并不一定会得到一个完全安全的系统,因此在组合时需要谨慎

    Combining secure building blocks does not neccessarily lead to a secure overall system.

继续阅读“Basics of Cryptology 密码学基础”

Intelligente Systeme 课程总结

智能系统课程考试之前做的总结,教授喜欢出各种简答题,所以本文主要是各种算法的优缺点、使用场景、复杂度。另外因为是德语考试,所以除了中文以外的内容大多是德语。

1. 不带权搜索

算法 BS 广度优先搜索 TS 深度优先搜索 TBS 深度限制搜索 IV 迭代加深搜索
完整性 否(树高有限时“是”) 是(t \ge d
最优
时间复杂度 b^d b^m b^t b^d
空间复杂度 b^d bm bt bd

b:分支因数

d:解的深度

m:树高

t:限制深度

完整性和最优性条件

  • 可解
  • 有限分支因数
  • 所有路径代价相同

树高有限则深度优先搜索完整,否则不具有完整性。

IV具有BS的时间复杂度,同时又有更好的空间复杂度。

继续阅读“Intelligente Systeme 课程总结”

Raft算法

一种更容易理解的共识算法。

使用共识的动机

容错(Fault Tolerance)

系统或系统上运行的服务可能会出现故障,为了恢复正常需要重新启动。这时既可以在同一台机器上重启(systemd),也可以在不同的机器上重启。

为了在不同机器上重启服务,需要协调服务(coordination service)的帮助。协调服务可以检测目标服务是否不可用,并在其他的机器上完成重启。协调服务本身也是容错的。

对于容错我们只需要该服务的一个副本(replica)。

协调服务:

  • Raft: Consul
  • Paxos: Chubby
  • Zab (atomic broadcast): Zookeeper

容错服务:

  • 需要在多个(协调服务所协调的)副本间复制状态(state replication)
  • 基于错误类型,可能需要F+1、2F+1、3F+1个副本来容忍F个错误

状态机复制(State Machine Replication, SMR)

状态机:从初始状态开始处理序列请求,在状态之间转换,最后产生输出

状态机的确定性(deterministic):对同一个状态机,同样的输入总是产生同样的转换和输出

状态机复制:

  • 对于容错的客户端-服务端系统,状态机复制是服务的复制(replication of services),协调副本与客户端请求。
  • 每个副本需要执行相同的客户端请求集合,以等价的顺序执行请求以保证副本能产生相同的内部状态和相同的输出。

继续阅读“Raft算法”

分组密码工作模式

根据每次加密的单位数据长度可以将对称加密算法分为流密码(Stream Cipher)和分组密码(Block Cipher)。本文讨论分组密码中算法对数据分组加解密的几种不同处理方式,称为分组密码的工作模式。

分组密码与流密码

分组密码

分组密码中,明文被分成长度相等的分组,若末尾不够组成一个分组则使用预设的内容进行填充,然后用相同的算法进行加密并组合形成密文。

分组密码包含以下几种常见的工作模式:

  • ECB(Electronic Codebook,电子密码本)
  • CBC(Cipher Block Chaining,密码分组链接)
  • CFB(Cipher Feedback,密码反馈)
  • OFB(Output FeedBack,输出反馈)
  • CTR(Counter,整数计数)
  • PCBC(Plain/Propagating Cipher Block Chaining,明文密码分组链接)
  • OCFB(Output Cipher FeedBack,输出密码反馈)

流密码

因为会介绍到具有流密码相似性质的CBC、CFB和OFB,所以顺便介绍一下流密码的分类。

流密码总体分为两类:同步流密码和自同步流密码(也即异步流密码)。

同步流密码
同步流密码指在该密码系统中,密钥流的生成独立明文消息和密文。同步要求严格,需要无错误传播,单个字符的错误不影响其他位。

自同步(self synchronization)流密码或异步流密码
其特点是具有记忆元件,密钥流由密钥和固定数量的之前的密文字符生成。自同步流密码在由于插入、删除或替换导致失去同步后,接受端接收到一定数量的正确密文后可以自动恢复同步,同步后的密文可以正常被解密。

继续阅读“分组密码工作模式”

RSA安全性的相关问题

语义安全性 Semantic Security

除了信息论安全、密码学健壮,我们还需要讨论算法的语义安全性。假设攻击者只具有有限的计算资源,语义安全性指在已知密文的情况下无法获得明文的信息。

基于游戏的证明(定义)

攻击者可以选择两个长度相同的明文m_0m_1交给挑战者进行加密,挑战者从两个明文中选择其一进行加密,然后攻击者根据加密后的数据判断哪一个明文被加密。

W_0W_1分别表示猜错和猜对,则攻击者的优势为:

Advantage [A, E] \coloneqq |Pr[W_0] - Pr[W_1]|

当对于所有高效的算法A,攻击者的优势Advantage[A, E]的值几乎为0(negligible),也即Pr[W_0] \thickapprox Pr[W_1]的时候,称加密方法E是语义安全的。

RSA的语义安全性

考虑RSA的语义安全性证明:攻击者可以对两个明文m_0m_1都进行加密,因为公钥是公开的,从而得到对应的密文x_0x_1。此时把x_0x_1x_b进行对比就可以知道挑战者对哪个明文进行了加密操作。

因此,传统RSA不具有语义安全性。导致这种缺陷的原因是,其加密算法具有确定性(deterministic),我们需要一种非确定性加密方案(例如概率加密)来解决这个问题。一种简单的思路是在加密前给明文添加随机数。

继续阅读“RSA安全性的相关问题”

密码学健壮的系统与RSA

Cryptographically Strong Systems

密码学健壮的系统:
使用复杂的数学问题设计密码系统,使破解密码系统的难度和求解此类数学问题的难度一样大。

数学秘密:用于解密、签名等等
素数在许多密码系统(尤其是非对称密码系统)中发挥重要作用

假设

因数分解假设(Factorization)
n = p \cdot q
已知n,难以找到p和q两个素数(当p、q足够大时难以暴力破解)
n是密钥对的公开部分。

此外还应该有一些特殊的属性:
例如模m同余:
a \equiv b \mod m

RSA算法中计算模反元素即找到与e同余的一个数

继续阅读“密码学健壮的系统与RSA”