Algorithm

什么是naive bayes 朴素贝叶斯 naive bayes，是一种概率类的机器学习算法，主要用于解决分类问题 为什么被称为朴素贝叶斯？ 为什么被称为朴素，难道仅仅是因为贝叶斯很天真吗？实际上是因为，朴素贝叶斯会假设数据属性之间具有很强的的独立性。即该模型中的所有属性彼此之间都是独立的，改变一个属性的值，不会直接影响或改变算法中其他的属性的值 贝叶斯定理 了解朴素贝叶斯之前，需要掌握一些概念才可继续 条件概率 Conditional probability：在另一个事件已经发生的情况下，另外一个时间发生的概率。如，==在多云天气，下雨的概率是多少？== 这是一个条件概率 联合概率 Joint Probability：计算两个或多个事件同时发生的可能性 边界概率 Marginal Probability：事件发生的概率，与另一个变量的结果无关 比例 Proportionality 贝叶斯定理 Bayes' Theorem：概率的公式；贝叶斯定律是指根据可能与事件的先验概率描述了事件的后验概率 边界概率 边界概率是指事件发生的概率，可以认为是无条件概率。不以另一个事件为条件；用公式表示为 $P(X)$ 如：抽到的牌是红色的概率是 $P(red) = 0.5$ ； 联合概率 联合概率是指两个事件在同一时间点发生的可能性，公式可以表示为 $P(A \cap B)$ A 和 B 是两个不同的事件相同相交，$P(A \and B)$ $P(A,B)$ = A 和 B 的联合概率 概率用于处理事件或现象发生的可能性。它被量化为介于 0 和 1 之间的数字，其中 0 表示不可能发生的机会，1 表示事件的一定结果。 如，从一副牌中抽到一张红牌的概率是 $\frac{1}{2}$。这意味着抽到红色和抽到黑色的概率相同；因为一副牌中有52张牌，其中 26 张是红色的，26 张是黑色的，所以抽到一张红牌与抽到一张黑牌的概率是 50%。 而联合概率是对测量同时发生的两个事件，只能应用于可能同时发生多个情况。例如，从一副52张牌扑克中，拿起一张既是红色又是6的牌的联合概率是 $P(6\cap red) = \frac{2}{52} = \frac{1}{26}$ ；这个是怎么得到的呢？因为抽到红色的概率为50%，而一副牌中有两个红色6（红桃6，方片6），而6和红色是两个独立的概率，那么计算公式就为：$P(6 \cap red) = P(6) \times P(red) = \frac{4}{52} \times \frac{26}{52} = \frac{1}{26}$...

散列函数（Hash function）又称散列算法、哈希函数，散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values）的指纹。这种转化是一种压缩映射，也就是散列值的空间通常远小于输入值的空间，不同的输入可能会散列成相同的输出，二不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要函数。 散列函数性质 通过使用单向散列函数，即便是确认几百MB大小的文件的完整性，也只要对比很短的散列值就可以了。那么，单向散列函数必须具备怎样的性质呢？我们来整理一下。 根据任意长度的消息计算出固定长度的散列值 能够快速计算出散列值 计算散列值所花费的时间短。尽管消息越长，计算散列值的时间也会越长，但如果不能在现实的时间内完成计算就没有意义了。 消息不同散列值也不同 难以发现碰撞的性质称为抗碰撞性（collisionresistance）。密码技术中所使用的单向散列函数，都需要具备抗碰撞性。强抗碰撞性，是指要找到散列值相同的两条不同的消息是非常困难的这一性质。在这里，散列值可以是任意值。密码技术中的单向散列函数必须具备强抗碰撞性。 具备单向性 单向散列函数必须具备单向性（one-way）。单向性指的是无法通过散列值反算出消息的性质。根据消息计算散列值可以很容易，但这条单行路是无法反过来走的。 散列函数的应用 散列函数应用具有多样性 安全加密： 保护资料，散列值可用于唯一地识别机密信息。这需要散列函数是抗碰撞(collision-resistant)的，意味着很难找到产生相同散列值的资料。如数字签名、消息认证码。 数据校验： 确保传递真实的信息：消息或数据的接受者确认消息是否被篡改的性质叫数据的真实性，也称为完整性。 错误校正：使用一个散列函数可以很直观的检测出数据在传输时发生的错误。 负载均衡： 通过hash算法，对客户端IP进行计算hash值，将取到值与服务器数量进行取模运算。 分布式存储：如一致性hash。 常用单项散列函数 MD4 MD5 MD5在1996年后被证实存在弱点，可以被加以破解，对于需要高度安全性的资料，专家一般建议改用其他算法，如SHA-2。2004年，证实MD5算法无法防止碰撞攻击，因此不适用于安全性认证，如SSL公开密钥认证或是数字签名等用途。 SHA-1 SHA-2 SHA-1：1995年发布，SHA-1在许多安全协议中广为使用，包括TLS、GnuPG、SSH、S/MIME和IPsec，是MD5的后继者。但SHA-1的安全性在2010年以后已经不被大多数的加密场景所接受。2017年荷兰密码学研究小组CWI和Google正式宣布攻破了SHA-1。 SHA-2：2001年发布，包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。SHA-2目前没有出现明显的弱点。虽然至今尚未出现对SHA-2有效的攻击，但它的算法跟SHA-1基本上仍然相似。 比特币使用的sha-256进行的数字签名 算法和变体 输出散列值长度 （bits） 中继散列值长度 （bits） 资料区块长度 （bits） 最大输入消息长度 （bits） MD5 128 128 (4 × 32) 512 无限 SHA-0 160 160 (5 × 32) 512 264 − 1 SHA-1 160 160 (5 × 32) 512 264 − 1 SHA-2 SHA-224 SHA-256 224 256 256 (8 × 32) 512 SHA-384 SHA-512 SHA-512/224 SHA-512/256 384 512 224 256 512 (8 × 64) 1024 2128 − 1 Go语言中使用散列函数 Go语言使用MD5 方式一：...

数字签名（Digital Signature），通俗来讲是基于非对称加密算法，用秘钥对内容进行散列值签名，在对内容与签名一起发送。 更详细的解说 更详细的解说 - 中文 数字签名的生成个验证 签名 ⑴ 对数据进行散列值运算。 ⑵ 签名：使用签名者的私钥对数据的散列值进行加密。 ⑶ 数字签名数据：签名与原始数据。 图：数字签名 Source：https://cheapsslsecurity.com/blog/digital-signature-vs-digital-certificate-the-difference-explained/ 验证 ⑴ 接收数据：原始数据&数字签名。 ⑵ 使用公钥进行解密得到散列值。 ⑶ 将原始数据的散列值与解密后的散列值进行对比。 Go语言中使用RSA进行数字签名 ⑴ pem解码：使用pem对私钥进行解码, 得到pem.Block结构体 ⑵ 获得私钥：使用GO x509接口pem.Block据解析成私钥结构体 ⑶ 计算hash值：对明文进行散列值计算 ⑷ 使用秘钥对散列值签名 go 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 package main import ( "crypto" "crypto/rand" "crypto/rsa" "crypto/sha256" "crypto/x509" "encoding/pem" "fmt" ) var ( private = `-----BEGIN 私钥----- MIICXQIBAAKBgQDc73afIxqYOHg80puDIMYrqUAiTi8EiTVDEiO9YE3+VxRvN0sa pe3zx1UdhgIn3iCPUzyI2vwNADId3LjuIjkdCcdB2fHrBTbcy6u0545HnY42F9aQ 7cAr168bHcqhQoKcna9i9nukO+w7So1J9C6Wr8J4e4923q7+T7z7bZeXywIDAQAB AoGBAItX5KLdywoyo3MJCdgcNaCX8MEyOmlL+HHC4ROxx78gQN0cLJw0Bu33zHEA ch+e8z4yKz3Nj6bLdtBqw6A9qXLBCfWfD/p9YKDZNFP/6+u9teUirOgiBSq7kXWy mtBm0I3pz33EomCuSJzLj/Mj/fkKs+425jPFcZboJdZpCyBhAkEA8mtGUGYuAZwV RKBDkf1bz5EyPBGV+9CyXa6pd6md61APY0j+qhb1w9ADfHKkAzfoilhpucznRhaz kAheqMPAMwJBAOlQEx2Ytc8TxfFqhF8RPTODe2N0jBBvsvJ85k7vNiQ+hnmaAray XS6pCbZdvmGHYKlz3MVGeis/UJKDdSzE0gkCQQCoZijkNPcEmz6S+5m00oFywXRa EgVUdndRaMHEpIlVK7pkyBJQab60Fc42JxUUP0RExoI7VcHbCG4YQhgvuDvNAkBQ CUolcwebe/sBcDrsqetGyqn/WjHaSZcnnDUdiu4VzOUwveaEafeRVCeiydHPfzNn rflkK2MphtTLDhGaRAKRAkASKlhV8aTBzTty/V3XMQfFVIAdHCyEIGMdjDDSzPly shZCn66IyIze8j5Q4ZLcRz6GPglHdrkBnyt4QFuGurpl -----END 私钥-----` public = `-----BEGIN 公钥----- MIGJAoGBANzvdp8jGpg4eDzSm4MgxiupQCJOLwSJNUMSI71gTf5XFG83Sxql7fPH VR2GAifeII9TPIja/A0AMh3cuO4iOR0Jx0HZ8esFNtzLq7TnjkedjjYX1pDtwCvX rxsdyqFCgpydr2L2e6Q77DtKjUn0Lpavwnh7j3berv5PvPttl5fLAgMBAAE= -----END 公钥-----` ) func digitalSign(privateKey, plainText string) (signText []byte, err error) { var ( pemBlock, _ = pem....

公开密钥密码学（英语：Public-key cryptography）也称非对称式密码学（英语：Asymmetric cryptography）是密码学的一种演算法。常用的非对称加密算法有 RSA DSA ECC 等。公开密钥加密 非对称加密算法使用公钥、私钥来加解密。 公钥与私钥是成对出现的。 多个用户（终端等）使用的密钥交公钥，只有一个用户（终端等）使用的秘钥叫私钥。 使用公钥加密的数据只有对应的私钥可以解密；使用私钥加密的数据只有对应的公钥可以解密。 非对称加密通信过程 下面我们来看一看使用公钥密码的通信流程。假设Alice要给Bob发送一条消息，Alice是发送者，Bob是接收者，而这一次窃听者Eve依然能够窃所到他们之间的通信内容。 参考自维基百科 ⑴ Alice与bob事先互不认识，也没有可靠安全的沟通渠道，但Alice现在却要透过不安全的互联网向bob发送信息。 ⑵ Alice撰写好原文，原文在未加密的状态下称之为明文 plainText。 ⑶ bob使用密码学安全伪随机数生成器产生一对密钥，其中一个作为公钥 publicKey，另一个作为私钥 privateKey。 ⑷ bob可以用任何方法传送公钥publicKey 给Alice，即使在中间被窃听到也没问题。 ⑸ Alice用公钥publicKey把明文plainText进行加密，得到密文 cipherText ⑹ Alice可以用任何方法传输密文给bob，即使中间被窃听到密文也没问题。 ⑺ bob收到密文，用私钥对密文进行解密，得到明文 plainText。 由于其他人没有私钥，所以无法得知明文；如果Alice，在没有得到bob私钥的情况下，她将重新得到原文。 RSA RSA是一种非对称加密算法，是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出，并以三人姓氏开头字母拼在一起组成的。 RSA公钥和密钥的获取：随机选择两个大的素数，p q $N = p*q$ RSA加密过程：$cipherText = plainText ^ E mod N$，$(N,e)$为公钥，$(N,d)$为私钥。 RSA解密过程：$plainText = cipherText^ D mod N$ Go语言中RSA的应用 在Go语言中生成公钥与私钥 生成秘钥流程 ⑴ 使用crypto/rsa中的GenerateKey(random io.Reader, bits int)方法生成私钥（结构体） ⑵ 因为X509证书采用了ASN1描述结构，需要通过Go语言API将的到的私钥（结构体），转换为BER编码规则的字符串。 ⑶ 需要将ASN1 BER 规则转回为PEM数据编码。pem....

对称加密，又称为 共享密钥加密算法，是指加密和解密方使用相同密钥的加密算法。对称加密算法的优点在于加解密的高速度和使用长密钥时的难破解性。 对称加密算法 DES DES（Data Encryption Standard）：数据加密标准，速度较快，适用于加密大量数据的场合。1977年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS） DES的加密和解密 DES是一种将64bit（8Byte）的明文加密成64bit的密文的对称密码算法，==它的密钥长度是56比特==。从规格上来说，DES的密钥长度是64bit，但由于每隔7bit会设置一个用于==错误检查==的比特，因此实质上其密钥长度是56bit。 DES是以64bit的明文（比特序列）为一个单位来进行加密的，这个64bit的单位称为分组。一般来说，以分组为单位进行处理的密码算法称为分组密码（blockcipher），DES就是分组密码的一种。 DES每次只能加密64比特的数据，如果要加密的明文比较长，就需要对DES加密进行迭代（反复），而迭代的具体方式就称为模式（mode）。 3DES 3DES（Triple DES）：是三重数据加密算法（TDEA，Triple Data Encryption Algorithm）块密码的通称。是基于DES，对一块数据用三个不同的密钥进行三次加密，强度更高。 3DES是基于计算机的运算能力的增强，基于DES算法，增强秘钥进行多绪加密，而不是一种块密码算法。 AES AES（Advanced Encryption Standard）：高级加密标准，是美国联邦政府采用的一种区块加密标准。 分组密码模式 **分组密码（blockcipher）**是每次只能处理特定长度的一块数据的一类密码算法，这里的一块"就称为分组（block）。此外，一个分组的比特数就称为分组长度（blocklength）。 例如，DES和3DES的分组长度都是64比特。这些密码算法一次只能加密64比特的明文．并生成64比特的密文。 AES的分组长度可以从128比特、192比特和256比特中进行选择。当选择128比特的分组长度时，AES一次可加密128比特的明文，并生成128比特的密文。 分组密码算法只能加密固定长度的分组，但是我们需要加密的明文长度可能会超过分组密码的分组长度，这时就需要对分组密码算法进行迭代，以便将一段很长的明文全部加密。而迭代的方法就称为分组密码的模式（mode）。 分组密码的模式有很多种类，分组密码的主要模式有以下5种： 明文与密文分组 **明文分组: **是指分组密码算法中作为加密对象的明文。明文分组的长度与分组密码算法的分组长度是相等的。 **密文分组: **是指使用分组密码算法将明文分组加密之后所生成的密文。 ECB模式：Electronic Code Book mode（电子密码本模式） ECB是最简单的加密模式，明文消息被分成固定大小的块（分组），并且每个块被单独加密。 每个块的加密和解密都是独立的，且使用相同的方法进行加密，所以可以进行并行计算，但是这种方法一旦有一个块被破解，使用相同的方法可以解密所有的明文数据，安全性比较差。 适用于数据较少的情形，加密前需要把明文数据填充到块大小的整倍数。 使用ECB模式加密时，相同的明文分组会被转换为相同的密文分组，因此ECB模式也称为电子密码本模式当最后一个明文分组的内容小于分组长度时（如一个分组8bit），需要用一特定的数据进行填充（padding），让值一个分组长度等于分组长度。 ECB模式是所有模式中最简单的一种。ECB模式中，明文分组与密文分组是一一对应的关系，因此，如果明文中存在多个相同的明文分组，则这些明文分组最终都将被转换为相同的密文分组。这样一来，只要观察一下密文，就可以知道明文中存在怎样的重复组合，并可以以此为线索来破译密码，因此ECB模式是存在一定风险的。 CBC模式：Cipher Block Chaining mode（密码分组链接/密码块 模式） 1976年，IBM发明了密码分组链接CBC。CBC模式中每一个分组要先和前一个分组加密后的数据进行XOR异或操作，然后再进行加密。 这样每个密文块依赖该块之前的所有明文块，为了保持每条消息都具有唯一性，在第一个块进行加密之前需要用初始化向量 IV 进行异或操作。 CBC模式是一种最常用的加密模式，它主要缺点是加密是连续的，不能并行处理，并且与ECB一样消息块必须填充到块大小的整倍数。 **当加密第一个明文分组时，由于不存在 “前一个密文分组"，因此需要事先准备一个长度为一个分组的比特序列来代替“前一个密文分组"，这个比特序列称为初始化向量（initialization vector）**通常缩写为 IV。一般来说，每次加密时都会随机产生一个不同的比特序列来作为初始化向量。 CFB模式：Cipher FeedBack mode（密文反馈模式） 密文反馈模式 CFB；在CFB模式中，前一个分组的密文加密后和当前分组的明文XOR异或操作生成当前分组的密文。所谓反馈，这里指的就是返回输入端的意思，即前一个密文分组会被送回到密码算法的输入端。 在ECB和CBC中，明文分组都是通过密码算法进行加密的，然而，在CFB模式中，明文分组和密文分组之间并没有经过"加密"这一步骤，明文分和密文分组之间只有一个XOR。 OFB模式：Output FeedBack mode（输出反馈模式） 输出反馈模式, OFB。在OFB模式中，上一个分组密码算法的输出是当前分组密码算法的输入（下图） CTR模式：CounTeR mode（计数器模式） CTR是一种通过将逐次累加的计数器进行加密来生成密钥流的流密码；即每个分组对应一个逐次累加的计数器，并通过对计数器进行加密来生成密钥流。也就是说，最终的密文分组是通过将计数器加密得到的比特序列，与明文分组进行XOR而得到的。...