macOS Sierra (10.12.3)编译Faiss

最近 Facebook AI实验室开源了相似性搜索库 Faiss
Faiss是用于有效的相似性搜索( similarity search)和稠密矢量聚类( clustering of dense vectors)的库。它包含了可在任何大小向量集合里进行搜索的算法,向量集合的大小甚至可达到 RAM容纳不下的地步。另外,它还包含了用于评估和参数调优的支持代码。 FaissC++编写,有 Python/numpy的完整包装。其中最有用的一些算法则在 GPU上实现。

机器上没有安装 HomeBrew的,请参考让Mac也能拥有apt-get类似的功能——Brew

下面,我们介绍一下如何在 macOS Sierra (10.12.3)上编译 Faiss

1.下载 Faiss源代码

2.安装编译需要的工具

3.修改调整源代码,准备编译

4.编译

5.执行测试用例

其余的示例,参考源代码中的 INSTALL文件中的内容即可。

支持向量机通俗导论(理解SVM的三层境界)

作者:July 。致谢:pluskid、白石、JerryLead。
说明:本文最初写于2012年6月,而后不断反反复复修改&优化,修改次数达上百次,最后修改于2016年11月。
声明:本文于2012年便早已附上所有参考链接,并注明是篇“学习笔记”,且写明具体参考了pluskid等人的文章。文末2013年的PDF是为证。

前言

动笔写这个支持向量机(support vector machine)是费了不少劲和困难的,原因很简单,一者这个东西本身就并不好懂,要深入学习和研究下去需花费不少时间和精力,二者这个东西也不好讲清楚,尽管网上已经有朋友写得不错了(见文末参考链接),但在描述数学公式的时候还是显得不够。得益于同学白石的数学证明,我还是想尝试写一下,希望本文在兼顾通俗易懂的基础上,真真正正能足以成为一篇完整概括和介绍支持向量机的导论性的文章。

本文在写的过程中,参考了不少资料,包括《支持向量机导论》、《统计学习方法》及网友pluskid的支持向量机系列等等,于此,还是一篇学习笔记,只是加入了自己的理解和总结,有任何不妥之处,还望海涵。全文宏观上整体认识支持向量机的概念和用处,微观上深究部分定理的来龙去脉,证明及原理细节,力保逻辑清晰 & 通俗易懂。

同时,阅读本文时建议大家尽量使用chrome等浏览器,如此公式才能更好的显示,再者,阅读时可拿张纸和笔出来,把本文所有定理.公式都亲自推导一遍或者直接打印下来(可直接打印网页版或本文文末附的PDF)在文稿上演算,从而享受随时随地思考、演算的极致快感。

继续阅读支持向量机通俗导论(理解SVM的三层境界)

802.11 Four-way handshake Messages

1.  4-way handshake sequence

0_13104396958zm8

2. Key Heirarchy

0_1310440023gpQ0

The EAPOL encryption key is the middle 128 bits of the PTK value.

And the first 128 bits of the PTK (KCK), is used in the computation(and validation) of the EAPOL frame MIC field value (4way handshake Message 1/2).

3. EAPOL Frame format

0_1310440523Xe68

4 Key Data Format

0_13104406628SwT

Key data may be zero or more InformationElement(s) (such as the RSN information element), and zero or more key dataencapsulation(s) (KDEs) (such as GTK(s)).

4.1 RSN Information

0_1310440804770w

4.2 GTK

If theEncrypted Key Data subfield (of the Key Information field) is set, the entireKey Data field shall be encrypted. If the Key Data field uses the NIST AES keywrap, then the Key Data field shall be padded before encrypting if the key datalength is less than 16 octets or if it is not a multiple of 8. The paddingconsists of appending a single octet 0xdd followed by zero or more 0x00 octets.When processing a received EAPOL-Key message, the receiver shall ignore thistrailing padding.  Key Data fields that are encrypted but do not containthe GroupKey or STAKey KDE, shall be accepted.

If the GroupKey or STAKey KDE is included in the Key Data field but theKey data field is not encrypted the EAPOL-Key frames shall be ignored.

0_1310440955sZ01

5. Sample 4-way Handshake

5.1 Message 1

The Authenticator sends an EAPOL-Key frame containing an ANonce.

0_13104413205d5G

Key data is zero.

5.2 Message 2

The Supplicant derives a PTK from ANonce and SNonce.

The Supplicant sends an EAPOL-Key frame containing SNonce, the RSN information element

from the Association Request frame and a MIC.

0_1310441522WyDx

MIC is the KCK (The first 128 bits in the PTK).

Key data is RSN Information.

802.1X authentication, CCMP pairwise dna group cipher suites.

5.3 Message 3

The Authenticator derives PTK from ANonce and SNonce and validates the MIC in the EAPOL Key frame

The Authenticator sends an EAPOL-Key frame containing ANonce, the RSN from its Beacon or Probe

Response messages, MIC whether to install the temporal keys, and the encapsulated GTK

0_1310442380H8du

Should the MIC data  be same with the one in Message 2   ?!

Key data is RSN Information + GTK,  and the data is encapsulated by using of the AES algrithm with the KEK(The middle 128 bits in PTK).

5.4  Message 4

To be added.

原始链接 http://blog.csdn.net/stevenliyong/article/details/6599528

在VC中编译和使用OpenSSL

在编译OpenSSL前,需要正确安装Perl,因为在编译OpenSSL时需要使用到该程序。

下载最新版本的Perl:http://downloads.activestate.com/ActivePerl/releases/5.20.1.2000/ActivePerl-5.20.1.2000-MSWin32-x64-298557.msi。然后安装之。

Windows 一定要使用 ActivePerl 主要是由于换行跟Linux ,Unix 的不同,如果使用其他的Perl生成的MakeFile 文件,会导致NMake无法正常的编译。

另外,一定要确保ActivePerl在系统的PATH 环境变量中在最前面,并且在命令行中执行 PATH命令的输出是跟环境变量中是一致的,Windows中有时候会发生刚刚添加的环境变量不能及时更新到命令行界面的问题,即使是你已经重新打开新的命令行窗口了。

下载最新版本的OpenSSL:http://www.openssl.org/source/openssl-1.0.1j.tar.gz

一定要使用最新的OpenSSL,早期的版本有Heartbleed的BUG,另外一定要是新下载并且刚刚解压缩出来的,没有修改过的文件,有时候,某些不经意的修改会导致编译不成功。

然后将源码释放的c:\openssl-1.0.1j目录中。

进入openssl源码目录。

以下为参照该目录下的文件INSTALL.W32的执行过程:

运行configure:

创建Makefile文件:

此处建议执行 do_ms ,有时候执行do_nasm会不正常,尽管文档中说执行 do_nasm

编译动态库:

编译静态库:

测试动态库:

测试静态库:

安装动态库:

安装静态库:

清除上次动态库的编译,以便重新编译:

清除上次静态库的编译,以便重新编译:

安全协议系列(三)----CCMP与WPA-PSK

本节讨论 CCM 在 WiFi 中的实际应用 -- CCMP 协议

根据 RFC 3610,完成 CCMP 报文的加解密,需要提供:分组密钥(K)、随机数(Nonce)、附加认证数据(AAD),这三个参数从哪里来?

另外, 作为处理对象的 CCMP 报文又来自哪里? 正常是通过抓包获取,但无线报文比普通的有线(以太)报文抓取相对麻烦点
幸运的是,万能的 Internet 已经给我们准备好了,在 Wireshark 网站 -- wiki.wireshark.org -- 中有个网页链接
主流协议的报文都被世界各地的网友抓取并上传到链接指向的页面上
进入页面,下载其中一个叫 wpa-Induction.cap  (Wireshark 原始地址点击这里)的抓包文件,该文件将作为后续的解密报文

至于分组密钥 K,它与 STA 如何接入 WiFi 网络有关,具体而言
如果 STA 是通过 WPA-PSK/WPA2-PSK 模式(这是家用无线路由器中使用最多的模式)接入,则 K 来源于配置此模式时输入的密码(后面记为 PSK)
如果 STA 是通过 WPA-Enterprise/WPA2-Enterprise 模式接入,则 K 来自 802.1X 认证过程中协商出来的密钥(后续会单独讨论 802.1X 认证)
这两种模式下,STA/AP 双方最终都会得到名为 PMK 的密钥
PMK 的作用类似一个密钥种子,它衍生出(更为准确说是协商出)密钥 PTK(其中就包括分组密钥 K)

就文件 wpa-Induction.cap 而言,它抓取的是 WPA-PSK 模式下 STA 与 AP 的交互报文,AP 的密码(PSK)为 Induction

本节讨论 WPA-PSK 模式下:无线网络密码(PSK) --> PMK --> PTK --> K 的具体变化情况

在无线路由器上配置过 WPA-PSK 模式的网友知道,配置时除了要输入 PSK,还要指定无线网络名(标准名为 SSID)
SSID 有两个作用:标识 AP 自己的名称(与其他 AP 区分出来),另一个就是参与 PMK 的构造
构造过程遵循 PKCS #5 v2.0 中的 PBKDF2 标准,简言之,我们可以认为 PMK = PBKDF2(PSK, SSID)

wpa-Induction.cap 中的 SSID 又是多少?这需要查看类型为 Beacon 的报文
其中有个字段解析为 SSID parameter set: Coherer,即 SSID 名称为 Coherer

这里我们看到,一旦输入的 PSK 和 SSID 固定,PMK 就不再变化,这带来了一定的安全性问题
因为知道 PSK 的 STA 可以通过抓取四次握手报文,嗅探别的 STA 与 AP 之间的流量(见后面详细说明)
在 WPA-Enterprise/WPA2-Enterprise 模式中,PMK 是动态生成的,避免了上述担心

脚本 PBKDF2.pl 是生成 PMK 过程的代码实现,下面是其内容及执行结果

C:\>perl PBKDF2.pl Induction Coherer
输出如下:
Salt = SSID = Coherer
Password    = Induction
WPA-PSK:PMK = A288FCF0CAAACDA9A9F58633FF35E8992A01D9C10BA5E02EFDF8CB5D730CE7BC

前已述及,PMK 会协商出 PTK,这个协商过程就是著名的 EAPOL-Key 四次握手
具体而言,四次握手的前两个报文(分别由 STA/AP 发出)各自包括了一串名为 WPA Key Nonce 的随机数(分别记为 ANonce/SNonce)

在 wpa-Induction.cap 中,EAPOL-Key 四次握手报文分别为 #87 #89 #92 #94,其中
#87 报文包含 WPA Key Nonce: 3e8e967dacd960324cac5b6aa721235bf57b949771c867989f49d04ed47c6933 -- ANonce
#89 报文包含 WPA Key Nonce: cdf405ceb9d889ef3dec42609828fae546b7add7baecbb1a394eac5214b1d386 -- SNonce

光有这两个随机数还不够,IEEE 802.11i 中还规定,STA 和 AP 的无线 MAC 地址(分别记为 AA/SPA)也要参与 PTK 的生成
最终生成 PTK 需要五个参数:PMK、AA、SPA、ANonce、SNonce

脚本 PMK2PTK.pl 对上述过程进行了实现,下面是其内容及执行结果

C:\>perl PMK2PTK.pl a288fcf0caaacda9a9f58633ff35e8992a01d9c10ba5e02efdf8cb5d730ce7bc 000c4182b255 000d9382363a
3e8e967dacd960324cac5b6aa721235bf57b949771c867989f49d04ed47c6933
cdf405ceb9d889ef3dec42609828fae546b7add7baecbb1a394eac5214b1d386
上面命令行实际在一行内输入,只处为折行显示

输出如下:
EAPOL-Key Confirm Key               b1cd792716762903f723424cd7d16511
EAPOL-Key Encrypt Key               82a644133bfa4e0b75d96d2308358433
(TKIP|CCMP) Temporal Key            15798d511beae0028313c8ab32f12c7e
TKIP MIC Key(for Authenticator Tx)  cb71c893482669da
TKIP MIC Key(for Supplicant Tx)     af0e9223fe1c0aed

从输出结果中看到,PTK 并不是一个单独的密钥,而是分成若干部分
其中 EAPOL-Key Confirm Key 和 EAPOL-Key Encrypt Key 仅用于 EAPOL-Key 的四次握手(对握手报文起加密和认证作用)
第三行 (TKIP|CCMP) Temporal Key 参与报文的加解密,在我们讨论的上下文中,就是 CCM 中的分组密钥 K
最后二行 TKIP MIC Key(...) 仅适用于 TKIP 协议,与 CCMP 协议无关

下面以报文 #99 为例,剖析 CCMP 的具体操作,报文内容如下
  08 41 2c 00 00 0c 41 82 b2 55 00 0d 93 82 36 3a -- IEEE 802.11 Data 报文头
  ff ff ff ff ff ff b0 01 01 00 00 20 00 00 00 00
  7e cc f6 0a c1 dd ff b0 47 96 c3 0b a1 9c 92 c6 -- 此行开始共 336 字节(共 21 行)为密文部分
6f 4d 1c e7 27 08 c2 95 cf 58 19 45 8c 18 d5 1f    提取为文件 wpa-Induction-cipher.txt
64 56 7a 7c c5 ff 85 e7 a6 8b 23 8a 33 5e 44 44
f7 de 0c 5e ef 72 1d 9f db 0d 51 44 03 d1 c9 06
46 15 23 3e fc e2 4b 41 6d 53 8c 88 84 5e 46 0d
29 63 0e da 72 97 fd db b5 66 ac 0a 05 f9 21 1f
bf 24 39 9a 15 a9 15 11 04 39 bd 0c 0c 51 0a 08
4a 88 90 50 01 fc 64 cc 9a 4f ca d2 51 d6 e0 f1
55 00 b7 13 fb 42 c2 44 60 58 2a 68 d0 a5 b9 9c
80 8e 01 2c 20 0a c5 27 b0 eb 32 0f 75 7d 60 ea
01 fa 79 f6 5c 2f c3 55 66 90 62 d9 25 e3 e4 4c
02 91 c1 a7 36 d5 0f 0b 8c 6c 68 de 9e 53 6e d9
7f eb 43 93 82 80 4b 73 92 3a 61 7f cc ef 37 60
cf 65 98 f7 7e 39 b9 90 a6 d1 67 ab 5c a6 a9 57
76 38 fe a8 34 2c 97 ab d5 54 f5 6f ea 48 eb 48
be 52 df c8 27 66 7b 1c 09 08 78 58 b9 96 9a 74
10 2d 53 e3 7d 35 2e e4 62 44 84 3d 02 f5 1b 04
43 64 cb 26 33 fd 2e 8c 16 0a 21 31 24 56 e5 74
74 89 33 e0 d8 49 5b e8 23 97 d8 9c b7 39 f7 ab
a0 e8 44 c2 b8 dc 3a 3d 57 d1 a7 b0 7e a9 ff 97
a3 d7 17 ff 02 83 0b 58 2c a8 94 27             -- 本行中前 8 字节为认证字段部分,后 4 字节为 FCS
                                                     CCMP 协议规定:认证字段长度 M = 8

现在已经知道分组密钥 K = 15798d511beae0028313c8ab32f12c7e
另两个参数 AAD/Nonce,它们在 IEEE 802.11i 有详细定义,这里直接给出结果

AAD = l(a) || a,构造比较复杂,我们估且认为它是下列字段的组合(实际上做了一些修正,感兴趣可参考标准)
l(a) || Frame Control || Address 1 || Address 2 || Address 3 || Sequence Control || Address 4 || Qos Control
长度    2           2             6            6            6               2                6             2
其中最后两个字段 Address 4、Qos Control 为可选字段, 所以 AAD 长度范围是 24-32 字节
将 AAD 以 16 字节为单位分组,得到 B_1、B_2 两个附加认证分组,其中 B_2 可能要用 0 填充

在本例中,实际的 AAD 内容为(最后两个字段 Address 4、Qos Control 不存在,末尾填充 0)
00 16 08 41 00 0c 41 82 b2 55 00 0d 93 82 36 3a ff ff ff ff ff ff 00 00 00 00 00 00 00 00 00 00
l(a)  Fc    Address 1         Address 2         Address 3         此处开始用 0 填充

生成 AAD 分组文件
C:\>perl -e "binmode STDOUT; print pack('H*','00160841000c4182b255000d9382363affffffffffff00000000000000000000')" > aad.txt

Nonce 相对简单,其长度 = 15 - L = 15 - 2 = 13,格式为
Nonce = Priority Octet || A2                || PN
= 00             || 00 0d 93 82 36 3a || 00 00 00 00 00 01
= 00 00 0d 93 82 36 3a 00 00 00 00 00 01

B_0 = Flags || Nonce                                  || l(m)
= 59    || 00 00 0d 93 82 36 3a 00 00 00 00 00 01 || 01 50 -- 0x0150 = 336
= 59 00 00 0d 93 82 36 3a 00 00 00 00 00 01 01 50
生成 B_0 分组文件
C:\>perl -e "binmode STDOUT; print pack('H*','5900000d9382363a0000000000010150')" > b_0.txt

计算 A_i ...
A_0 = 01 00 00 0d 93 82 36 3a 00 00 00 00 00 01 00 00
A_1 = 01 00 00 0d 93 82 36 3a 00 00 00 00 00 01 00 01
生成 A_1 || A_2 || ... 分组文件
C:\>perl -e "binmode STDOUT; for($i=1;$i<22;$i++){print pack('H28n','0100000d9382363a000000000001',$i)}" > a_i.txt
# 循环 21 次,因为 21 * 16 = 336,索引为何从 1 开始,参见上节

计算密钥流 E( K, A_1 || A_2 || ... )
C:\>openssl enc -aes-128-ecb -K 15798d511beae0028313c8ab32f12c7e -iv 0 -nopad -in a_i.txt > enc_key.txt

密文 与 加密密钥 异或,得到明文

C:\>perl xor_file.pl wpa-Induction-cipher.txt enc_key.txt > wpa-Induction-plain.txt

明文内容是什么呢?我们对下答案,看看 Wireshark 自身的 CCMP 解密结果,如下图
08233422-706caedf229f4c11bc525f490f45bfc1
原来是 DHCP Request 报文,这也说明 WiFi 安全属于二层安全范畴
仔细对比明文 wpa-Induction-plain.txt 的内容,完全符合

仅仅满足数据的机密性还是不够的,如何判断报文是否被篡改过?
CCMP 是通过附在密文后的 8 字节认证字段(红色显示部分)来解决的,下面按照 RFC 3610 中的规定进行验证

已知 A_0 = 01 00 00 0d 93 82 36 3a 00 00 00 00 00 01 00 00
生成 A_0 分组文件
C:\>perl -e "binmode STDOUT; print pack('H*','0100000d9382363a0000000000010000')" > a_0.txt

生成数据校验密钥 E(K, A_0)
C:\>openssl enc -aes-128-ecb -K 15798d511beae0028313c8ab32f12c7e -iv 0 -nopad -in a_0.txt > mac_key.txt
C:\>od -An -tx1 mac_key.txt
37 ef 73 a5 87 be 43 61 92 b3 6e ed c2 01 a3 49 -- 取前 8 字节 37 ef 73 a5 87 be 43 61

数据校验密钥 与 认证字段 异或,得到 X_n+1(即 CBC-MAC)的期望值
C:\>perl xor.pl 37ef73a587be4361 a3d717ff02830b58
结果为 XOR = 9438645A853D4839

而真实的 CBC-MAC 由密钥 K 对 -- B_0 || AAD分组 || WiFi明文分组(wpa-Induction-plain.txt) -- 进行 CBC 加密得到

合并 B_0 || AAD分组 || WiFi明文分组
C:\>perl -pe "BEGIN{binmode STDOUT;}" b_0.txt aad.txt wpa-Induction-plain.txt > b.txt

AES 加密计算 CBC-MAC

C:\>perl AES-CBC.pl encrypt 15798d511beae0028313c8ab32f12c7e 00000000000000000000000000000000 b.txt > cbc-mac.txt
文件 cbc-mac.txt 的最后一个分组为
94 38 64 5A 85 3D 48 39 5B 35 A9 89 E6 47 A3 3B
其前 8 字节 9438645A853D4839期望值 相同,校验成功,说明报文未被篡改

再看报文最后一个字段 FCS(蓝色显示部分),在 CCMP 中也是起校验作用
不过校验范围为除 FCS 外的整个报文,即:报文头 || 密文 || 认证字段,不像 WEP 报文中是针对明文校验
同样也可以利用 perl 自带的 crc32.bat 脚本进行验证

来源 http://www.cnblogs.com/efzju/p/3247155.html

安全协议系列(二)----CCM与CCMP

CCMP(CTR with CBC-MAC Protocol) 是 IEEE 802.11i 中推出使用基于 AES 的 CCM 模式的安全加密协议。
与原来脆弱的 WEP 算法及临时补救措施 TKIP 协议相比,它具有更好的安全性,在 WiFi 中得到广泛的应用。

CCM(Counter with CBC-MAC) 定义在 RFC 3610 中,它是一种使用分组算法(例如 AES)进行数据认证和加密的通用模式。

下面是 RFC 3610 中重要部分的中文注释说明

1.  Introduction

   Counter with CBC-MAC (CCM) is a generic authenticated encryption block cipher mode.
CCM 对明文数据(记为 m,其长度记为 l(m))进行分组加密和认证,处理结果同时包括密文和认证字段

   CCM is defined for use with 128-bit block ciphers, such as the Advanced Encryption Standard (AES).
专门用于 block size 为 128 位的分组加密算法,如 AES

2.  CCM Mode Specification

   For the generic CCM mode there are two parameter choices.
CCM 有 2 个参数选项

   The first choice is M, the size of the authentication field.
Valid values are 4, 6, 8, 10, 12, 14, and 16 octets.
第 1 个选项: M -- 输出的认证字段长度(单位:字节),取值范围:4, 6, 8, 10, 12, 14, and 16

   The second choice is L, the size of the length field.
Valid values of L range between 2 octets and 8 octets.
第 2 个选项: L -- 表示 l(m) 值的字节数( l(m) < 2^(8L) ),取值范围:2-8

   将 M 和 L 转换为 M' 和 L'(以便容纳在一个字节中),转换关系如下
Name  Description                               Size    Encoding
----  ----------------------------------------  ------  --------
M'    Number of octets in authentication field  3 bits  (M-2)/2
L'    Number of octets in length field          3 bits  L-1

   CCMP 协议规定:M = 8 L = 2, 即 m 最长为 65535 字节,认证字段为 8 字节

2.1.  Inputs -- 认证加密 m 所需的参数

   1.  An encryption key K suitable for the block cipher.
分组密钥 K

   2.  A nonce N of 15-L octets.  Within the scope of any encryption key K,
the nonce value MUST be unique.
随机数 N,15-L 字节长,在 K 的生命过程中要确保 N 不被重复使用

   3.  The message m, consisting of a string of l(m) octets where 0 <=
l(m) < 2^(8L).  The length restriction ensures that l(m) can be
encoded in a field of L octets.
此段内容上面已讲得很清楚

   4.  Additional authenticated data a, consisting of a string of l(a)
octets where 0 <= l(a) < 2^64.  This additional data is
authenticated but not encrypted, and is not included in the
output of this mode.  It can be used to authenticate plaintext
packet headers, or contextual information that affects the
interpretation of the message.  Users who do not wish to
authenticate additional data can provide a string of length zero.
附加认证数据 a,用于数据的完整性校验(不参与加密运算),可选
       通常用于认证 报文头的明文字段 或 对消息理解有影响的上下文

   The inputs are summarized as:

      Name  Description                                 Size
----  -----------------------------------         -----------------------
K     Block cipher key/分组加密密钥                 Depends on block cipher
N     Nonce/随机数                                 15-L octets
m     Message to authenticate and encrypt         l(m) octets
a     Additional authenticated data/附加认证数据    l(a) octets

2.2.  Authentication -- 生成认证字段

   The first step is to compute the authentication field T.  This is
done using CBC-MAC [MAC].  We first define a sequence of blocks B_0,
B_1, ..., B_n and then apply CBC-MAC to these blocks.
第一步计算认证字段 T,使用 CBC-MAC 算法,该算法涉及输入分组 B_0,B_1, ..., B_n

   The first block B_0 is formatted as follows, where l(m) is encoded in
most-significant-byte first order:
第一个数据分组 B_0 构成如下
Octet Number   Contents
------------   ---------
0              Flags          1    字节
1 ... 15-L     Nonce N        15-L 字节
16-L ... 15    l(m)           L    字节(L 的值见 Flags 字节)

   Within the first block B_0, the Flags field is formatted as follows:
分组 B_0 中的首字节 Flags 构成如下
Bit Number   Contents
----------   ----------------------
7            Reserved (always zero)
6            Adata
5 ... 3      M' (1--7) = (M-2)/2  (M:4--16)
2 ... 0      L' (1--7) = L-1      (L:2--8)
Another way say the same thing is:  Flags = 64*Adata + 8*M' + L'.

   B_0 构成如下
    长度   1      15-L           L
   +----+-----+-----------+------------+
   |字节 |  0  | 1 .. 15-L | 16-L .. 15 |
   +----+-----+-----------+------------+
   |内容 |Flags|  Nonce N  |  m 的长度  |
   +----+-----+-----------+------------+
       /      \                  ^
      /        \                 |
     /          \     L -- m 的长度表示范围
    /            \     (L 越大,m 可以越长)
   / Flags 展开后  \              |
   +----+-+-----+-+-+-+-+-+-+    |L'(L) 决定
   |位  |7|  6  |5|4|3|2|1|0|    |Nonce 的长度
   +----+-+-----+-+-+-+-+-+-+    |
   |内容 |0|Adata| M'  | L'  | ---+
   +----+-+-----+-+-+-+-+-+-+

   The Adata bit is set to zero if l(a)=0, and set to one if l(a)>0.
如果 Bit6(Adata 位)=0,表示要生成附加认证数据 a,否则表示没有

   If l(a)>0 (as indicated by the Adata field), then one or more blocks
of authentication data are added.  These blocks contain l(a) and a
encoded in a reversible manner.  We first construct a string that
encodes l(a).
生成附加认证数据 a,需要构造认证数据块(一个或多个),数据块编码如下

   If 0 < l(a) < (2^16 - 2^8), then the length field is encoded as two
octets which contain the value l(a) in most-significant-byte first
order.
a 长度 < 65536-256,此情况比较普遍

   The length encoding conventions are summarized in the following
table.  Note that all fields are interpreted in most-significant-byte
first order.

    First two octets   Followed by       Comment
-----------------  ----------------  -------------------------------
0x0000             Nothing           Reserved
0x0001 ... 0xFEFF  Nothing           For 0 < l(a) < (2^16 - 2^8)
0xFF00 ... 0xFFFD  Nothing           Reserved
0xFFFE             4 octets of l(a)  For (2^16 - 2^8) <= l(a) < 2^32
0xFFFF             8 octets of l(a)  For 2^32 <= l(a) < 2^64

   The blocks encoding a are formed by concatenating this string that
encodes l(a) with a itself, and splitting the result into 16-octet
blocks, and then padding the last block with zeroes if necessary.
These blocks are appended to the first block B0.
将 l(a)||a 分成 16 字节长的分组,必要时最后一个分组添加 0x00 补齐
   这些分组依次添加到 B_0 后面(记为 B_1、B_2……)

   After the (optional) additional authentication blocks have been
added, we add the message blocks.  The message blocks are formed by
splitting the message m into 16-octet blocks, and then padding the
last block with zeroes if necessary.  If the message m consists of
the empty string, then no blocks are added in this step.
附加认证分组添加后,我们构造明文分组,将 m 分成 16 字节长的分组
   必要时最后一个分组补 0 对齐(如果 m 为空串,则此步省略)

   The result is a sequence of blocks B0, B1, ..., Bn.  The CBC-MAC is
computed by:
最终得到 B_0||附加认证分组||明文分组,按下列公式计算 CBC-MAC

      X_1   := E( K, B_0 )
X_i+1 := E( K, X_i XOR B_i )  for i=1, ..., n
T     := first-M-bytes( X_n+1 ) -- T 作为 MAC 值

        B_0       B_1       B_2               B_n
|         |         |                 |
|         V         V                 V
|    +-->XOR   +-->XOR           +-->XOR
|    |    |    |    |            |    |
V    |    V    |    V            |    V
+----+ | +----+  | +----+          | +----+
K-->|加密 | | |加密|  | |加密 |   ...    | |加密|
+----+ | +----+  | +----+          | +----+
|    |    |    |    |            |    |
+----+    +----+    +-->      ->-+    |
|         |         |         X_n     |
V         V         V                 V
X_1       X_2       X_3               X_n+1

2.3.  Encryption -- 生成密文

   To encrypt the message data we use Counter (CTR) mode.  We first
define the key stream blocks by:
使用 Counter (CTR) 模式加密,首先计算如下密钥流
S_i := E( K, A_i )   for i=0, 1, 2, ...

   The values A_i are formatted as follows, where the Counter field i is
encoded in most-significant-byte first order:

      Octet Number   Contents
------------   ---------
0              Flags
1 ... 15-L     Nonce N
16-L ... 15    Counter i

   The Flags field is formatted as follows:

      Bit Number   Contents
----------   ----------------------
7            Reserved (always zero)
6            Reserved (always zero)
5 ... 3      Zero
2 ... 0      L'

   Another way say the same thing is:  Flags = L'.

   A_i 构成如下
    长度   1      15-L           L
   +----+-----+-----------+------------+
   |字节 |  0  | 1 .. 15-L | 16-L .. 15 |
   +----+-----+-----------+------------+
   |内容 |Flags|  Nonce N  | Counter i  | -- Counter i 的值能够在 L 字节内表示
   +----+-----+-----------+------------+    (因为 i <= l(m))
       /      \                  ^
      /        \                 |
     /          \                |
    /            \               |
   / Flags 展开后  \              |
   +----+-+-----+-+-+-+-+-+-+    |L'(L) 决定
   |位   |7|Adata|5|4|3|2|1|0|    |Nonce 的长度
   +----+-+-----+-+-+-+-+-+-+    |
   |内容 |0|  0  |M'=0 | L'  | ---+
   +----+-+-----+-+-+-+-+-+-+
                 |
                 M' 不同于 B_0(B_0 中始终不为 0)

   The message is encrypted by XORing the octets of message m with the
first l(m) octets of the concatenation of S_1, S_2, S_3, ... .  Note
that S_0 is not used to encrypt the message.
明文与密钥流异或,得到密文,S_0 不用于加密,但参与数据校验
        A_0       A_1        A_2        A_n
         |         |          |          |
         V         V          V          V
       +----+   +----+     +----+     +----+
   K-->|加密 |   |加密|     | 加密| ... |加密|
       +----+   +----+     +----+     +----+
         |         |          |          |
         |         |S_1       |S_2       |S_n
         |         |          |          |       密钥: S_1 | S_2 | ... | S_n
         |         V          V          V       XOR
         |  M_1-->XOR  M_2-->XOR  M_n-->XOR      明文: M_1 | M_2 | ... | M_n
         |         |          |          |        |
         V         V          V          V        V
        S_0       C_1        C_2        C_n      密文: C_1 | C_2 | ... | C_n

   The authentication value U is computed by encrypting T with the key
stream block S_0 and truncating it to the desired length.
T 与 S_0 的异或结果取前 M 字节,得到认证字段
U := T XOR first-M-bytes( S_0 )

2.4.  Output -- 最终输出

       取前 l(m) 字节                        取前 M 字节
       =================================    ============
       S_1/E(K,A_1) | S_2/E(K,A_2) | ... || S_0/E(K,A_0)
   XOR m                                 || X_n+1
   -----------------------------------------------------
     = 最终输出 c

   其中 X_i 计算如下
X_1   := E( K, B_0 )
X_i+1 := E( K, X_i XOR B_i )  for i=1, ..., n

8.  Test Vectors -- 使用测试数据进行计算演示

   =============== Packet Vector #1 ==================
AES Key =  C0 C1 C2 C3  C4 C5 C6 C7  C8 C9 CA CB  CC CD CE CF
Nonce =    00 00 00 03  02 01 00 A0  A1 A2 A3 A4  A5
Total packet length = 31. [Input with 8 cleartext header octets]
扣除 8 字节明文头,只有 31-8=23 字节需要处理
00 01 02 03  04 05 06 07  08 09 0A 0B  0C 0D 0E 0F
10 11 12 13  14 15 16 17  18 19 1A 1B  1C 1D 1E

   明文分组
   M_1 -- 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17
   M_2 -- 18 19 1A 1B 1C 1D 1E

   以下计算数据认证字段
   CBC IV in: 59 00 00 00  03 02 01 00  A0 A1 A2 A3  A4 A5 00 17 -- 实际就是 B_0
              |  |                                       |     |
              |  |<--------------- Nonce --------------->|     |
              
|                                            23 字节
Flags = 0 1 0 1 1 0 0 1 (binary)
| | |---| |---|
| |   |     |
| |   |   L'=1 <--> L=2
| |  M'=3 <--> M=8
| Adata=1 表示有认证字段
Reserved (always zero)

   CBC IV out:EB 9D 55 47  73 09 55 AB  23 1E 0A 2D  FE 4B 90 D6
验证 X_1 := E( K, B_0 )
C:\>perl -e "binmode STDOUT; print pack('H*','5900000003020100A0A1A2A3A4A50017')" > B_0.txt
C:\>openssl enc -aes-128-ecb -K C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF -iv 0 -nopad -in B_0.txt > X_1.txt
C:\>od -An -tx1 -v X_1.txt

eb 9d 55 47 73 09 55 ab 23 1e 0a 2d fe 4b 90 d6

   After xor: EB 95 55 46  71 0A 51 AE  25 19 0A 2D  FE 4B 90 D6   [hdr]
验证 X_1 XOR B_1 -- xor.pl 源码见后面
C:\>perl xor.pl 00080001020304050607000000000000 EB9D5547730955AB231E0A2DFE4B90D6
          00080001020304050607000000000000 B_1 附加认证数据(8 字节)
          EB9D5547730955AB231E0A2DFE4B90D6 X_1
    --------------------------------------
    XOR = EB955546710A51AE25190A2DFE4B90D6

   After AES: CD B6 41 1E  3C DC 9B 4F  5D 92 58 B6  9E E7 F0 91
验证 X_2 := E( K, X_1 XOR B_1 )
C:\>perl -e "binmode STDOUT; print pack('H*','EB955546710A51AE25190A2DFE4B90D6')" > X_1_XOR_B_1.txt
C:\>openssl enc -aes-128-ecb -K C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF -iv 0 -nopad -in X_1_XOR_B_1.txt > X_2.txt
C:\>od -An -tx1 -v X_2.txt
cd b6 41 1e 3c dc 9b 4f 5d 92 58 b6 9e e7 f0 91

   After xor: C5 BF 4B 15  30 D1 95 40  4D 83 4A A5  8A F2 E6 86   [msg]
验证 X_2 XOR B_2
C:\>perl xor.pl 08090A0B0C0D0E0F1011121314151617 CDB6411E3CDC9B4F5D9258B69EE7F091
          08090A0B0C0D0E0F1011121314151617 B_2 -- 从 B_2 开始起为明文部分
          CDB6411E3CDC9B4F5D9258B69EE7F091 X_2
    --------------------------------------
    XOR = C5BF4B1530D195404D834AA58AF2E686

   After AES: 9C 38 40 5E  A0 3C 1B C9  04 B5 8B 40  C7 6C A2 EB
验证 X_3 := E( K, X_2 XOR B_2 )
C:\>perl -e "binmode STDOUT; print pack('H*','C5BF4B1530D195404D834AA58AF2E686')" > X_2_XOR_B_2.txt
C:\>openssl enc -aes-128-ecb -K C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF -iv 0 -nopad -in X_2_XOR_B_2.txt > X_3.txt
C:\>od -An -tx1 -v X_3.txt
9c 38 40 5e a0 3c 1b c9 04 b5 8b 40 c7 6c a2 eb

   After xor: 84 21 5A 45  BC 21 05 C9  04 B5 8B 40  C7 6C A2 EB   [msg]
验证 X_3 XOR B_3
C:\>perl xor.pl 18191A1B1C1D1E000000000000000000 9C38405EA03C1BC904B58B40C76CA2EB
          18191A1B1C1D1E000000000000000000 B_3 -- B_3 作为明文最后一个分组,以 0 字节补齐
          9C38405EA03C1BC904B58B40C76CA2EB X_3
    --------------------------------------
    XOR = 84215A45BC2105C904B58B40C76CA2EB

   After AES: 2D C6 97 E4  11 CA 83 A8  60 C2 C4 06  CC AA 54 2F
验证 X_4 := E( K, X_3 XOR B_3 )
C:\>perl -e "binmode STDOUT; print pack('H*','84215A45BC2105C904B58B40C76CA2EB')" > X_3_XOR_B_3.txt
C:\>openssl enc -aes-128-ecb -K C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF -iv 0 -nopad -in X_3_XOR_B_3.txt > X_4.txt
C:\>od -An -tx1 -v X_4.txt
2d c6 97 e4 11 ca 83 a8 60 c2 c4 06 cc aa 54 2f

   CBC-MAC  : 2D C6 97 E4  11 CA 83 A8 -- 取前 8 字节

   以下计算密钥流
   S_i := E( K, A_i )   for i=0, 1, 2, ...
   A_i 是 L、Nonce、i 的函数,格式如下
       01 00 00 00  03 02 01 00  A0 A1 A2 A3  A4 A5 00 00
       |  |                                       |     |
       |  |<--------------- Nonce --------------->|     |
       |                                            Counter(0000、0001、0002...)
       Flags = 0 0 0 0 0 0 0 1 (binary)
               | | |---| |---|
               | |   |     |
               | |   |   L'=1 <--> L=2
               | |  Zero
               | 相当于 Adata=0
           Reserved (always zero)

   CTR Start: 01 00 00 00  03 02 01 00  A0 A1 A2 A3  A4 A5 00 01 -- A_1
CTR[0001]: 50 85 9D 91  6D CB 6D DD  E0 77 C2 D1  D4 EC 9F 97 -- S_1
CTR[0002]: 75 46 71 7A  C6 DE 9A FF  64 0C 9C 06  DE 6D 0D 8F -- S_2
CTR[MAC ]: 3A 2E 46 C8  EC 33 A5 48                           -- S_0 取前 M 字节
C:\>od -An -tx1 -v A_.txt
    01 00 00 00 03 02 01 00 a0 a1 a2 a3 a4 a5 00 00 -- A_0
    01 00 00 00 03 02 01 00 a0 a1 a2 a3 a4 a5 00 01 -- A_1
    01 00 00 00 03 02 01 00 a0 a1 a2 a3 a4 a5 00 02 -- A_2
   C:\>openssl enc -aes-128-ecb -K C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF -iv 0 -nopad -in A_.txt > key.txt
   C:\>od -An -tx1 -v key.txt
    3a 2e 46 c8 ec 33 a5 48 56 20 54 2c 02 2c c0 7d -- S_0
    50 85 9d 91 6d cb 6d dd e0 77 c2 d1 d4 ec 9f 97 -- S_1
    75 46 71 7a c6 de 9a ff 64 0c 9c 06 de 6d 0d 8f -- S_2

   Total packet length = 39. [Authenticated and Encrypted Output]
00 01 02 03  04 05 06 07  58 8C 97 9A  61 C6 63 D2
F0 66 D0 C2  C0 F9 89 80  6D 5F 6B 61  DA C3 84 17
E8 D1 2C FD  F9 26 E0
注意
m                                             T
----------------------------------------------================
08090A0B0C0D0E0F101112131415161718191A1B1C1D1E2DC697E411CA83A8

S_1                             S_2           S_0
--------------------------------==============----------------

50859d916dcb6ddde077c2d1d4ec9f977546717ac6de9a3a2e46c8ec33a548

C:\>perl xor.pl 08090A0B0C0D0E0F101112131415161718191A1B1C1D1E2DC697E411CA83A8 50859d916dcb6ddde077c2d1d4ec9f977546717ac6de9a3a2e46c8ec33a548
          08090A0B0C0D0E0F101112131415161718191A1B1C1D1E2DC697E411CA83A8
          50859d916dcb6ddde077c2d1d4ec9f977546717ac6de9a3a2e46c8ec33a548
    --------------------------------------------------------------------
    XOR = 588C979A61C663D2F066D0C2C0F989806D5F6B61DAC38417E8D12CFDF926E0 正确

在 CCMP 中,对称密钥 K 同时对明文数据进行加密和认证,C(Confidentiality) 和 I(Integrality) 都得到了保证
而 S(Signature) 和 A(Authentication) 是否达标,则取决于对称密钥 K 的安全性
从 IEEE 802.11i 中我们知道,K 是由著名的 EAPOL-Key 四次握手衍生得到,其安全性又取决于 PMK
PMK 又来自哪里?

IEEE 802.11i 标准中有两种工作模式:PSK 和 802.1X。
在 PSK 模式中,AP 和所有 STA 预先共享同一个密钥,该共享密钥经过简单的变换得到 PMK(后面将给出公式)
原则上 AP 无法区别不同的 STA -- 排除其他方式比如 MAC 地址过滤 -- 所以做不到 A(Authentication)
因为 AP 只知道有一个掌握了预共享密钥的家伙连上我了
至于这个家伙是谁?他的预共享密钥是不是偷来的?AP 一概不知
PSK 模式下 STA 反过来也无法认证 AP,这有点类似 GSM 网络中的伪基站

在 802.1X 模式中,安全性得到了增强,认证协议为 EAP,包含的认证子协议有 EAP-TLS/EAP-TTLS/EAP-PEAP 等
上述三种子协议都采用 TLS 隧道加密,天然支持 STA 对 AP 的认证
如果是 EAP-TLS 协议,还需要部署 STA 证书,因而可以做到相互认证,在这种情况下 SCIA,安全特性一个也不少

最后附上 xor.pl 源代码

引用 http://www.cnblogs.com/efzju/p/3199330.html

判断一个点是否在指定区域内

在图像处理时,我们会经常需要判断一个点是否位于多边形区域内。比较好用的是射线法。

射线法

算法思想非常巧妙:从待判断的点向某一个方向引射线,计算和多边形交点的个数,如果个数是偶数或者0则点在多边形外,如果是奇数,则在多边形内,如下图:

1

这里有二种特殊情况:

[/crayon]
C的实现如下:

再来个C#版的

 

值得一提的是射线法对于带岛的多边形依然有效:

2

改进:传统的射线法一开始就直接计算点和多边形的交点个数,这样的话,会花费大量的时间来作拓扑关系的判断,我们可以首先计算出最小外包矩形,迅速排除不在矩形内部的点,然后再做上面的判断。