鸡蛋的两种吃法 : 字节顺序

2017/07/24

1 字节顺序

鸡蛋有几种吃法?也许你从未注意。Jonathan Swift 的小说 Gulliver’s Travels 描写了这么一个故事: Lilliput 国的皇帝因按古法打鸡蛋时弄破的手指,于是下令全体臣民吃鸡蛋时必须先打破鸡蛋较小的一端(little-endian)。但百姓这对项命令本极度反感,并为此发动叛乱。

在计算机时代,计算机网络的开创者之一, Danny Cohen 开始使用 Swift 的小说中的词语 大端、小端 来描述字节的顺序,大小端这一术语开始被人们所接纳。 在计算机时代的远古时期,计算机刚被发明的时候,由于不能统一规则,对多字节对象在存储器上的存储方式有两种不同的方式。但它们有一个共识,即,多字节的对象都被存储为连续的字节序列,而对象的地址则这段连续序列中的最小的字节的地址。

例如,一个 int 类型的变量 n 的地址为 0x100,即 &n == 0x100,那么 n 将被存储在 0x100,0x101,0x102,0x103 这段位置。 假定有一个 w 位的整数,其 位 表示为 [bw-1, bw-2, … ,b1, b0] , 其中 bw-1 为最高位,b0 为最低位。这些位按每 8 位,即一个字节分组, 表示为 [Bx-1, Bx-2, … , B1, B0] ,其中 Bn = [bn*8-1, bn*8-2, … , bn*8-8] 。 有的机器选择选择在存储器按照从低字节到高字节的顺序来存储,这种方式称为 小端法(little-endian) ,基本所有的 Intel 机器都采用这种方式。而别一部分机器则选择按照高字节到低字节的方式来存储,称为 大端法(big-endian) ,大部分 IBM 和 Sun 的机器都采用这种规则。

所以,当一段数据从使用小端规则的机器传送到使用大端规则的机器上时,数据是无法正确解析的。除非明确的告诉计算机,这段数据需要使用哪种规则来解析。这计算机网络发明以后,这种不兼容的带来的负面作用显得尤为突出。于是一个规则产生了,在网络传输过程中,数据的发送方必须将多字节数据转换成大端法表示后再发送。而数据的接收方则需要按照大端法来解析多字节数据,再转换为它的内部表示。这样,在网络中,终端只关心本机的字节序与网络字节序,而不用关心网络另一端的机器使用什么样的字节充。所以又将大端法称为 网络字节序 ,以区分 本机字节序

阅读全文…

对称密码的模式(MODE)

2017/07/16

1 科谱:密码学中的常见概念

1.1 密钥

根据密钥的使用方法,可以将密钥分为两种:

  • 对称密钥 是指在加密和解密时使用同一密钥的方式
  • 公钥 加密和解密使用的不是同一种密钥,也称 非对称密钥

1.2 单向散列

单向散列是由单向散列函数计算出来的一组数值。它不能保证数据的机密性,是用来保证数据的完整性的。例如,有安全意识的软件发布者会向用户公布软件的散列值,一般是 MD5. 可以通过检验软件的 MD5 散列值,判断软件是否被篡改过。

1.3 随机数

随机数可以通过硬件生成,也可以通过软件来生成。通过硬件生成的随机数列,是根据传感器收集的热量、声音的变化等事实上无法预测和重现的自然现象信息来生成的,可以称为 真随机数 . 而一般由软件生成的随机数是可以周期性重现的,这种随机数称为 伪随机数 。生成随机数的软件叫做 伪随机数生成器

2 对称加密

常用的对称加密方法有 DES 与 AES 两种。

2.1 DES

DES 是一种将 64bit 的明文加密成 64bit 密文的对称密钥算法,它是密钥长度也是 64bit,但是它的密钥每隔 7bit 会设置一个用于错误检查的 bit, 所以实质上其密钥长度是 56bit . 因为 DES 每次只能加密 64bit 明文,所以需要对超过 64bit 的明文进行分组。以分组为单位进行处理的密码算法也称为 分组密码 。分组后的明文以什么样的方式进行加密,我们称之为 模式(mode) 。 DES 的基本结构以其设计者的名字(Horst Feistel)命名,也称 Feistel 网络可 Feistel结构。在 Feistel 结构中,将 64bit 明文再分作两部分,每部分 32bit。假如标记为 A B 两部分,那么有如下步骤:

  1. 对 B 使用子密钥 subkey 进行加密运算,生成 Bf(B,subkey) = B'
  2. B~ 与 A 进行异或运算,生成 C : B' XOR A = C
  3. C 与 B 组合,生成密文 D : C # B = D

这三个步骤称为一个 轮(round) .可以看到,密文D的后半部分 B 没有被加密。我们将组成 D 的 C 与 B 部分进行互置,即令 A = B, B = C,再重复上面的步骤 1 ~ 3 ,这样明文的每一个部分都被加密了。 DES 就是一种由 16 个轮循环组成的 Feistel 网络。每一轮都会生成一个不同的密钥,所以称为子密钥。

2.2 3DES

DES 可以在有限时间内被暴力破解。三重DES 作为 DES 的代替品产生了。三重DES 是为了增加 DES 的强度,将 DES 算法重复 3 次所得到的一种密码算法。也叫 TDEA(Triple Date Encryption Algorithm), 也简写作 3DES ,或 DES3 . 需要注意的,3DES 并不是将 DES 加密过程重复3将,而是将 DES 算法重复 3 次,其过程是:

  1. 使用密钥 K1 对明文进行 DES 加密
  2. 使用密钥 K2 对步骤1 产生的密文进行解密
  3. 使用密钥 K3 对步骤2 产生的 “明文” 进行加密

这一过程是由 IBM 公司设计出来的,其目的是为了兼容 DES 算法:如果这 3 个步骤使用了相同的密钥,那么其加密就与 DES 完全相同了。 如果步骤1 和步骤3 使用相同的密钥,而步骤2 使用不同的密钥,这种三重 DES 称为 DES-EDE2, EDE 表示 Encryption-Decryption-Encryption。 而正是由于 3DES 特别重视向下兼容,导致其效率低且不够安全,所以在实际中很少被使用。

2.3 AES

AES (Advanced Encryption Standard) 是取代 DES 成为新标准的一种对称密钥算法。全世界的科学家提交了多个对称密钥算法为在AES 的候选,而最终在 2000年, 从这些候选算法中先出一种名为 Rijhdeal 的对称密码算法,将其确定为 AES 算法。 和 DES 一样, AES(Rijndeal) 也是由多个 轮构成的,不过不是 Feistel 结构 ,而是 SPN 结构,每一轮分为为 SubBytes, ShiftRows, MixColumns 和 AddRoundKey 4 个步骤

 

3 分组模式

前面提到的 DES 和 AES 都只能加密固定长度的明文,如果需要加密任意长度的明文,就需要对分组密码进行迭代,这个迭代的方法就是所谓的 “模式”。分组密码的主要模式有如下 5 种:

  • ECB Electronic CodeBook mode (电子密码本)
  • CBC Cipher Block Chaining mode (密码分组链接)
  • CFB Cipher FeedBack mode (密码反馈)
  • OFB Output FeedBack mode (输出反馈)
  • CTR CounTeR mode (计数器)

3.1 ECB 模式

将明文分组直接加密的方式就是 ECB 模式。这种模式很简单,但通常不会被使用。在 ECB 模式中,明文分组成密文分组是一一对应的,因此,如果明文中存在多个相同的明文分组,则这些明文分组最终都将被转换为相同的密文分组,只要观察密文就可以知道明文中存在怎么的组合,并以此为线索来破译密码。

 

阅读全文…

git 使用笔记 (不定期更新中)

2017/06/24

子模块 (Submodule)

添加

git submodule add [remotegiturl] [localdir]

更新

git submodule update --init --recursive

clone 时更新子模块

git clone [remotegiturl] --resuresive

远程更新(更新到最新)

submodule 不会detach到源的任何一个分支,而只是源的某一个commit,
使用 git submodule update --remote
将本地的子模块更新到最新。如果需要将远程仓库的子模块了更新到最新,可以先更新本地,再push到远程仓库:

删除

git 没有提供删除子模块的命令

 

分支(branch)

git 仓库在创建的时候默认会创建一个 master 分支

创建分支

git branch [branch_name]
会创建一个新的分支。此时仍然工作在原分支上,而不会自动切换到新创建的分支上。git 对分支的名称有一些限制:

  • 可以包含斜杠(/),但不能以斜杠(/) 开头或结尾
  • 不能以点号(.), 减号(-) 开头, 点号也不能紧跟在斜杠后面,并且不能出现连接的两个点号。如 feature/.new ,feature..new 都是非法的
  • 不能包含任何空白字符(如空格,tab)
  • 不能包含在 git 中具有特殊意义的字符。包括 ~, ^ , : , ? , * , [
  • 不能包含任何 ASCII控制字符,即值小于八进制 \040 的字符或 DEL(八进制\177)

查看分支

  • git branch 当后面不跟任何参数时,显示本地所有的分支,并对当前分支做特殊标识。
  • git branch -r 会查看远程分支
  • git branch -a 会将本地分支和远程分支都列出来
  • git show-branch 另一个命令可以查看更详细的内容:输出分为两个部分,使用减号分隔。

    减号的个数是同分支的个数决定的,有多少个分支就有多少个 ‘-‘ 。
    上半部分显示所的有分支。当前分支使用 ‘*’,其他分支分别使用不同颜色的 ‘!’ 标识。颜色没有特殊的意义,只是用来区分不同的分支而已;
    下半部分显示 commit 列表。每个列表使用 ‘*’ 和不同颜色的 ‘+’ 表示。这里的颜色和上半部分 ‘!’ 相对应,表示该分支上有此 commit 

阅读全文…

Note 242

TCP 协议概述

2017/06/16

TCP(TRANSMISSION CONTROL PROTOCOL,即传输控制协议)

是当今网络中使用得最为广泛的协议。与 UDP不同,TCP 提供了一种 面向连接(connection-oriented) 的、可靠的字节流服务。”面向连接”,是指使用 TCP 的两个应用程序 必须在它们可以交换数据之前,通过相互联系建立起一个 TCP 连接。建立起连接的两端称为两个 端点(endpoint) 。因为 TCP 是面向连接的,所以像广播和组播这样的概念在 TCP 中是不存在的。 TCP 提供了流的概念,应用程序可以将任意大小的数据交给 TCP而不用关心如何发送。如,一个应用程序在一端先后写入 10 个字节、20个字节、50个字节的数据,连接的另一端的应用程序是不需要关心这个过程的,应用程序可以选择自己读取数据流的大小,如一次读20字段分4次读取,也可以一次读入80个字节。

一个 TCP 块包含了 TCP头和应用程序数据,称之为 报文段(segment) 。TCP 是依赖于 IP 协议的,TCP 必须将报文段转换成一个 IP 可以携带的分组,这被称为一个 组包(packetizition)

 

如图,显示了 TCP 在 IP 数据报中的封装,以及 TCP 头部的结构。其中,着色部分用于与该报文的发送方关联的相反方向上的数据流。

  • 端口号 每个TCP 头包含了源和目标的端口号,这两个值与IP头部的源和目标IP地址一起组成了唯一标识。一个IP与一个端口的组合被你为一个 端点(endpoint) 或一个 套接字(Socket) ,每一个TCP连接由一对套接字唯一标识。
  • 序列号 字段标识了TCP发送端到接收端的数据流的字节数,代表着该报文段的数据中的第一个字节。它是一个32位无符号数,到达 232-1后再循环到0. 使用序列号,TCP的接收端可以丢弃重复的报文,并归整以杂乱次序到达的报文。TCP接收到报文的顺序是不可控的,然而TCP是一种流协议,它不能向程序程序提供顺序错乱的数据,因此,TCP接收端在向上层提供数据时,会等待较小序列号的报文,并对报文进行排序。
  • 确认号 可以认为,TCP 发送的数据的每一个字节都已被编号。当TCP接收到另一端发送的数据时,它会发送一个确认。但这个确认可能不会立即发出。当接收方向发送方确认接收时,确认号表示发送言期望收到的下一个报文的序列号。所以确认号应该为 序列号 + 收到的数据的字节数据 + 1 。确认号字段只有在ACK字段启用后才有效。TCP使用确认是积累的,可以认为,一个确认号 N 表示 N-1 个字节已经被成功接收。
  • 头部长度 字段给出了头部的长度,以32位字为单位。该字段只有4位,那么它能表示的最大头部长度为 60 字节。((2^{4}-1) * 32 / 8)。即一个TCP报文的头部长度的范围为 20 ~ 60 字节。
  • 窗口大小 字段用来控制流量。该字段以字节为单位,因为它是 16 位的,故限制了窗口大小为 65535 字节,从而限制了 TCP 的吞吐性能。
  • TCP校验和 字段由发送方计算和保存,由接收方校验。它用于检测传送过程中的比特差错。如果一个报文的校验和无效,那么TCP会丢弃它而不会返回任何确认信息。然而TCP可能会对一个已经确认过的报文再次确认,以帮助发送方计算它的拥塞控制。
  • 紧急指针 字段只有在URG字段设置时才有效。它表示从报文的序列号开始的一个 正偏移 ,用以产生紧急数据的字段一个字段的序列号。
  • 选项 是可变的。最常见的选项是 “最大段大小” 选项(MSS),连接的每一个端点一般在它发送的第一个报文上指定该选项(即设置SYN位字段的那个报文),指定该选项的发送者在相反方向上希望接收到的报文段的最大值。
  • 标识位
    • CWR: 拥塞窗口减(发送方降低它的发送速率)
    • ECE: ECN 回显(发送方接收到了一个更早的拥塞报告)
    • URG: 紧急(紧急指针字段有效)
    • ACK: 确认(确认号字段有效)
    • PSH: 推送(接收方应该尽快给应用程序传送这个数据 —然而没有被可靠实现或用到)
    • RST: 重置连接(连接取消,经常是因为错误)
    • SYN: 用于初始化一个连接的同步序列号
    • FIN: 结束向对方发送数据

当TCP发送一组报文段时,通常会设置一个重传计时器,等待对方确认接收。当对方的确认报文到达时,该计时器会被更新,如果确认没有及时到达,这个报文就会被重传。 TCP提供了一种可靠、面向连接、字节流、传输层的服务。在接下来,我们将对TCP的细节进行研究。

 

Note , 274

什么是 REST

2017/04/05

1 REST的概念

Roy Thomas Fielding 博士在2000年 发表了论文 Architectural Styles and the Design of Network-based Software Architectures (《架构风格与基于网络的软件架构设计》) 。在这篇论文中,首次系统地阐述了 REST 的架构风格和设计思想。REST,全称为(Resource) Representational State Thransfer ,常见的翻译为”表现层状态转移”,它省略了主语:资源。通俗来讲,即资源在网络中以某种表现形式进行状态转移。

  • Resource: 资源,即数据。泛指 Web 上一切可以识别、命名、可访问或处理的实体,如 HTTPPage,音频文件等。使用统一资源定位符指(URI)向资源.
  • Representational:某种表现形式。如 JSON,XML,二进制流等
  • State Transfer: 状态变化。通过 HTTP 动词实现。

在互联网发展的早期,网页的前后端是融合在一起的,如JSP,PHP.互联网发展的今天,客户端硬件设备层出不穷,而不同的Client又需要展示相同的商业逻辑。REST 接口可以为为不同的设备提供一套统一的接口。

简单来说, REST 即为: 使用URL定位资源,使用HTTP原语描述操作

HTTP原语,指 HTTP提供的原始方法,如 GET\POST\DELETE\HEAD etc

2 RESTful设计风格

RESTful 不是架构,而是一种架构风格,它提供了一些设计原则和约束条件。 REST 架构风格最重要的约束有:

  1. C/S架构。 Client/Server 架构形式提供了基本的分布式,客户端发走请求,服务端响应可拒绝请求。使用 HTTP Status Code 传递 Server 状态信息,如果出错则返回错误信息,则客户端处理异常。
  2. 无状态。通信的传话状态应该全部由客户端维护。即请求中应该包括全部的必要信息。
  3. 缓存。无状态不胜表示可能出现重复的请求。事实上有些请求只需要第一次完成执行,其余次请求皆可以享用这次请求的成果。缓存可以抵消一部分无状态带来的影响。
  4. 统一接口。这意味着每一个REST应用都共享一种能用架构。
  5. 分层系统:将系统划分为几个部分,每个部分负责单一职责。然后通过上层对下层的依赖和调用组成一个完成的系统。通常将系统划分为:应用层、服务层、数据访问层。

如果一个架构满足 REST 原则 ,那么就可以称它为 RESTful 架构。

API 发布之后,就很难再修改。所以在设计API时需要遵循一定规范,且又需要灵活友好。
阅读全文…

Note , , 392

C++11/14 新特性 (多线程)

2017/03/28

在 C++11 之前 ,C++ 标准并没有提供统一的并发编程标准,也没有提供语言级别的支持。这导致我们在编写可移植的多线程程序时很不方便,往往需要面向不同的平台进行不同的实现,或者引入一些第三方平台,如Boost,pthread_win32 等。 从C++11开始 ,对并发编程进行了语言级别的支持,使用使用C++进行并发编译方便了很多。这里介绍C++11并发编译的相关特性。

1 线程

1.1 线程的创建

std::thread 的构造函数如下:

我们只需要提供线程函数或函数对象,即可以创建线程,并可以同时指定线程函数的参数。

join函数将会阻塞线程,直到线程函数执行完毕,主线程才会接着执行。如果线程函数有返回值,返回值将被忽略。 在使用线程对象的过程中,我们需要注意线程对象的生命周期。如果线程对象先于线程函数结束,那么将会出现不可预料的错误。可以通过线程阻塞的方式来等待线程函数执行完(join),或让线程在后台执行。 如果不希望线程被阻塞,可以调用线程的 detach() 函数,将线程与线程对象分离。但需要注意的是,detach 之后的线程无法再使用join来进行阻塞了,即detach之后的线程,我们无法控制了。当我们不确定一个线程是否可以join时,可以先使用 thead::joinable() 来进行判断。

另外,我们还可以通过 std::bind, lambda 来创建线程(其实就是使用函数对象创建线程)。

线程不可以被复制,但是可以被移动:
阅读全文…