MathxH Chen
之前其实写了一篇[《深入了解Ed25519》](https://github.com/AlexiaChen/AlexiaChen.github.io/issues/103), 主要介绍了背景及来龙去脉，最后给了用Python实现的算法，没有列出签名公式。公式会更清晰些，这里补一下。 Ed25519的签名公式与Schnorr签名很像，可以理解为在扭曲爱德华曲线上用了Schnorr机制的签名，是Schnorr的变种，也继承了Schnorr的优点，就是相比ECDSA非常方便做门限化多签。 Ed25519就是EdDSA标准的具体实现了，有性能高，更安全等这些优点。经过 NIST 批准的曲线有多条，例如 secp256r1，secp256k1 等。但现有的 ECC 算法中的曲线被指存在后门。但是Ed25519采用的扭曲爱德华曲线参数完全公开，并说明了参数选取的意义，保证曲线中并未内置后门。同时 ED25519 采用 Schnorr 机制作为签名的构建方式，使得签名与验证的性能得到了巨大的提升。 ## 具体算法 ### 公私钥对的生成 首先公私秘钥长度为b，为256-bit， 生成元为G，Hash函数为SHA512, M是被签名的消息， l是一个大素数， 满足l.G = O , 就是对G点的标量乘法得到的是无穷远点，也就是I是曲线上子群的阶。设私钥为sk， 公钥为pk。 - 随机生成一个长度为256-bit的二进制数据作为私钥sk...
--- title: 对Nginx队列源码ngx_queue_t的一次分析 date: 2017-11-18 13:30:00 tags: - 数据结构与算法 - 双向链表 --- ## 前言 前几天公司的群里讨论了[Nginx](https://en.wikipedia.org/wiki/Nginx)内部实现的一个数据结构，ngx_queue_t。 实质上是一个[双向链表](https://en.wikipedia.org/wiki/Doubly_linked_list)，但是当时讨论没有讨论出结果来，原因我自己也被绕晕了，今天本着从问题本身出发，不被别人的想法思路所左右，不看网络上任何文章的分析，好好写测试用例来证明自己的想法，其实那天的问题是围绕着两个C语言的宏展开的，那么这篇文章也会重点讲解这两个宏的意义：offsetof 和 ngx_queue_data。所以这篇文章不会涉及到链表插入,删除等细节。 ## 正文 首先，Nginx源码实现这个数据结构，用了大量的宏，我们先用我们的思路，把关键信息抽取出来: ``` cpp #define u_char unsigned char typedef struct ngx_queue_s...
--- title: 最简单的计算机之有限自动机 date: 2018-10-15 20:30:48 tags: - 程序语言理论 - 计算理论 --- > *简单是终极的复杂* -- *达 芬奇* ## 前言 其实这算是计算理论的第二个章节，第一个章节可以去看我之前写的文章----[《程序的含义》](https://alexiachen.github.io/blog/2017/10/15/program-semantic/)。 追求简单是人类内心的本性使然，看上去好像没有太多修饰，当你仔细揣摩，你会发现，最精华的理论已经融入每个角落，越是简单的东西，其实越难吧空，需要经过千锤百炼。 现代计算机具有强大的计算能力，但是正是由于其强大，所以伴随着过多的复杂性。我们很难理解一台计算机多个子系统的全部细节，更别说理解这些子系统如何互相协作从而构成整个系统了。这些复杂性使得对真实的计算机的能力与行为进行直接推导显得不切实际，此时计算机的简化模型就显得非常有用。简单的模型只提取出真实计算机中令人感兴趣的特性，它可以帮助人们建立对计算完整的认知。 接下来，我们会逐步揭开什么是计算，最后分析这样简单的模型所能达到的计算极限。 ## 确定性有限自动机 现实中，计算机通常有大量的RAM和DISK，还有许多I/O设备（键盘等），还有CPU。有限状态机也被称作有限自动机，这是一个极简的计算机模型。它为了简单，抛弃了RAM DISK等这些特性。 ### 状态 规则...
# 线性代数学习笔记之内积空间 之前的章节主要讲解了线性代数中最重要的线性变换和算子，又由算子引申出来的本征值和本征向量，试图直达线性变换和矩阵的本质。 但是我们还忽略了其他重要的特性，例如长度和角度的概念，这几个概念隐含于我们这章要研究的內积这个概念之中。 老规矩，F表示R或C，也就是实数域和复数域。V表示F上的向量空间。 ## 內积与范数 ### 內积 (to be continued)
设椭圆曲线E是定义在有限域$\mathbb{F}_p$上的椭圆曲线，其中$a，b ∈ Fp$， 其中p是大素数，且 $p \thinspace \not = 2, p\thinspace \not = 3$ $$E: y^2=x^3+a*x+b \thinspace (\thinspace mod\thinspace p\thinspace ) $$ ## 椭圆曲线G点的阶 G点的阶就是 如果 $r*G = O$ , 那么r的最小值就是G点的阶，一般这个r是个素数，也就是一个素阶群，换个说法，r就是这个素阶群的点的个数...
并且已经Release了，虽然只是预览版。 这里有他们写的Blog文章 https://www.mongodb.com/blog/post/mongodb-releases-queryable-encryption-preview > MongoDB is the only database provider that allows customers to run expressive queries, such as equality (available now in preview) and range, prefix, suffix, substring, and...
## 前言 该篇文章介绍了用Reed-Solomon编码的思想来比较两个大文件的内容。原文请戳这里： https://hackmd.io/@Kurt-Pan/SJ6Y0DZLq# 主要是想说明一个确定性比较算法的下界。我们暂时不讨论这么技术的问题。我们重点关注下Reed-Solomon编码这个思想来解决这个问题所带来的一些思考。因为这个问题，跟我之前做Shamir secret sharing的密码学算法很像，都是根据多项式来编码一些数据，然后通过拉格朗日插值来进行恢复原始数据 ## 正文 首先定义两个文件内容，文件A的内容记为向量a = (a1,a2,a3,..., a_n), 文件B的内容记为向量b = (b1,b2,b3,... b_n)。这些向量的元素你可以看成就是文件里面的字符了。Alice拥有文件A， Bob拥有文件B。按照朴素传统的确定性算法思想，要比较两个大文件内容就是Alice 把整个文件A发送给Bob， Bob执行算法验证 a_i 是否等于 b_i 逐个字符比较。但是，我们前面说了，这个文件是大文件了。Alice的文件发送给Bob这个动作，数据传输量太大了，通信复杂度很高。由于文章说了，如果有没有更好的确定性算法比这个朴素算法还好的，那么就没有，因为这个朴素算法就是下界。有没有可能可以突破下界，争取更好的复杂度，答案是放宽条件，用非确定性算法，允许有概率出错。这样就可以突破下界了。 原文它是设计了一种reed-solomon指纹识别协议，思想借用了[RS编码](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction)。算法是把待编码的字符向量映射到一个有限域Fp下的多项式。向量字符值就是多项式的系数向量，以前我提到过的，系数向量就可以确定唯一的一个多项式。在这里，向量的大小n也就是多项式的degree了。 原始的RS编码: 把待编码的message定义为 x = (x1,x2,x3,...
# 线性代数学习笔记之本征值和本征向量 之前的学习笔记主要学到的是线性映射，并且这个线性映射是T:V -> W, 也就是一个向量空间到另一个向量空间的，也简单提到了映射到自身向量空间的线性映射T: V -> V。这种特别的线性映射叫算子，在线代中也是非常重要的。 老样子，F是实数域R或复数域C。V是F上的向量空间。 ## 不变子空间 V上的所有算子集合记为L(V,V), 设某个算子T ∈ L(V,V), 如果V有以下直和分解: V = U1 + U2 + ... + Um 那么每个Uj（1 设T ∈ L(V,V)。如果存在v...
## 前言 在GitOps那篇文章提到过IaC了，TF就是IaC的工具，它主要解决Infra Provisioning的问题。接下来我们直接步入主题吧。 ## Terraform的基本原理  就是跟之前说的一样，原理和k8s这样基于declarative 的原理一样，都是Desired state跟actual state做对比，做diff，然后变更diff部门，幂等执行。这样就是只要配置文件相同，那么能保证提供的infra环境（VPS, VM等）是一致的。 从大部分公司使用TF来看，主要是用来构建IaaS服务，比如用TF 向Azure，GCP(Google Cloud Platform)，AWS, Alibaba Cloud这样的Coud Provider申请配置Infra资源。当然还可以配置本地私有的Infra资源，比如k8s，Docker，自建的Openstack等。所以在TF生态下，有很多TF provider，有了这些provider，就可以通过TF配置对应Provider提供的Infra资源了。这些Provider你可以理解是一些第三方实现的插件，TF只是提供了接口和标准。 下面就是TF配置文件的样例:  上图是向AWS申请并创建一个VPC资源，并且给这台VPC配置了一个IPv4 CIDR block ，这个详情可以看AWS的VPC...
## 前言 这几天把去年写的[k8s教程](https://github.com/AlexiaChen/AlexiaChen.github.io/issues/145)的坑填完了，趁热打铁。看看DevOps领域的新鲜概念。 ## Infrastructure as code(Iac) 这里的基础设施是指VM server，网络，基础设施软件（DB Nginx等） IaC叫基础设施即代码，就是以前我们创建安装配置基础设施大部分都是手工创建管理，现在我们要把Infra的构建和管理自动化，既然自动化，那么肯定是写代码（配置代码）了， 大概就是这样。简而言之就是别在准备环境的过程浪费过多的时间，尽可能快速开始干正事，为了达到这个目的，就是尽可能把准备环境自动化，几行配置搞定，用工具apply配置就可以了。 能达到这个目的的工具有Ansible， Terraform， Puppet，Chef。为啥需要这么多工具呢？ 因为一个工具不能覆盖整个IaC的流程功能。 IaC的主要功能大致有3类任务功能（按顺序）: - Infra Provisioning, 就是提供基础设施环境的功能，快速创建server环境，比如快速准备几个VM的server。快速建立网络并创建LoadBalancer这些。 - configuration of provisioned Infra， 就是在已经准备好的基础设施上配置更上层的东西，比如在新建立好的几个server上快速自动化安装（管理，删除）某些基础软件（DB，Nginx等）或App - Deployment of...