密码学之椭圆曲线
我们在《几何》课本里学过二元一次方程表示直线,二元二次方程表示圆锥曲线 (圆,椭圆,双曲线和抛物线),那么二元三次方程表示什么曲线呢?答案自然就是椭圆曲线。为了方便研究,大部分的二元三次方程可以简化成魏尔斯特拉斯方程的形式。其中,系数 a 和 b 需要满足条件 $4a^3 + 27b^2 \neq 0$,该条件保证方程中不会出现非奇异点以获得平滑的椭圆曲线。
椭圆曲线的形状跟椭圆毫无关系。当初数学家们在研究如何计算椭圆弧长的时候发现需要求解如下类型的积分,由于和椭圆相关,积分中的分母项 $y =\sqrt {(x^3+ax+b)}$ 便被称作椭圆曲线。
\int_{\alpha}^{\beta}{\frac {dx}{\sqrt {x^3+ax+b}}}下图展示了一些合法的椭圆曲线,
下图展示了两种非法的椭圆曲线,分别存在一个尖点和叉点使曲线不平滑。
密码学与有限循环群现代密码学算法和协议中,消息是作为有限空间中的数字或元素来处理的。加密和解密的各种操作必须在消息之间进行变换,以使变换服从有限消息空间内部的封闭性。然而,数的一般运算诸如加减乘除并不满足有限空间内部的封闭性。所以 ...
密码学之 Diffie-Hellman 密钥交换
Deffie-Hellman(简称 DH) 密钥交换是最早的密钥交换算法之一,它使得通信的双方能在非安全的信道中安全的交换密钥,用于加密后续的通信消息。 Whitfield Diffie 和 Martin Hellman 于 1976 提出该算法,之后被应用于安全领域,比如 Https 协议的 TSL (Transport Layer Security) 和 IPsec 协议的 IKE (Internet Key Exchange) 均以 DH 算法作为密钥交换算法。
数论基础理解 DH 算法前,先介绍一些必要的数论领域知识,分别是离散对数问题和一个求模公式。
离散对数问题假定 a, p 均是素数,下面两个集合相等,证明过程请参考 Cryptography and Network Security 第八章:
{a^1 (mod\ p), a^2 (mod\ p), ... a^{p-1}(mod\ p)} = {1,2,...,p-1}上述式子可概括成以下三点,对于 1 <= x,y <= p - 1,有:
$a^x (mod\ p)$ 一定属于 {1, 2, …, p ...
Redis 详解之 —— 特性与用途
Redis 是一个使用 ANSI C 编写的开源、支持 网络 、基于 内存 、 单线程模型 、 可选持久性 的 键值对存储数据库 。Redis 是一个 K-V 的非关系型数据库(NoSQL),常见的 NoSQL 数据库有:K-V 数据库如 Redis、Memcached,列式数据库如大数据组件 HBase,文档数据库如 mongoDB。Redis 应用广泛,尤其是被作为缓存使用。
特性
速度快 ,最快可达到 10w QPS(基于 内存 ,C 语言, 单线程 架构);
基于 键值对 (key/value) 的数据结构服务器。全称 Remote Dictionary Server。包括 string( 字符串 )、hash( 哈希 )、list( 列表 )、set( 集合 )、zset( 有序集合 )、bitmap( 位图 )。同时在 字符串 的基础上演变出 位图 (BitMaps)和 HyperLogLog 两种数据结构。3.2 版本中加入 GEO( 地理信息位置 )。
丰富的功能。例如: 键过期 (缓存), 发布订阅 (消息队列), Lua 脚本(自己实现 R ...
Redis 详解之 —— 单线程高并发
redis 最基本的一个内部原理和特点,就是 redis 实际上是个单线程工作模型。如今在各大互联网公司已经大面积取代了 memcached 的应用。它可以承载相当大的 QPS。在这里,我们通过对 Redis 的线程模型和并发模型对它的高性能进行分析。
Redis 线程模型redis 内部使用文件事件处理器 file event handler,这个文件事件处理器是单线程的,所以 redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket,根据 socket 上的事件来选择对应的事件处理器进行处理。
文件事件处理器的结构包含 4 个部分:
多个 socket
IO 多路复用程序
文件事件分派器
事件处理器(连接应答处理器、命令请求处理器、命令回复处理器)
多个 socket 可能会并发产生不同的操作,每个操作对应不同的文件事件,但是 IO 多路复用程序会监听多个 socket,会将 socket 产生的事件放入队列中排队,事件分派器每次从队列中取出一个事件,把该事件交给对应的事件处理器进行处理。
来看客户端与 redis 的一次通信过程:
客户端 so ...
Linux 五种 IO 模型详解
I/O 与计算是计算机系统的最核心的两个功能,而 I/O 往往占据了相当多的资源和时间,所以如何提高 I/O 性能,成为了性能优化的极其重要的点。这里我们结合一些其他的 Linux 系统核心概念来比较基本的五种 I/O 模型。
概念引入用户空间和内核空间现在操作系统都是采用虚拟存储器,那么对 32 位操作系统而言,它的寻址空间(虚拟存储空间)为 4G(2 的 32 次方)。操作系统的核心是内核,独立于普通的应用程序,可以访问受保护的内存空间,也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核(kernel),保证内核的安全,操作系统将虚拟空间划分为两部分,一部分为内核空间,一部分为用户空间。针对 linux 操作系统而言,将最高的 1G 字节(从虚拟地址 0xC0000000 到 0xFFFFFFFF),供内核使用,称为内核空间,而将较低的 3G 字节(从虚拟地址 0x00000000 到 0xBFFFFFFF),供各个进程使用,称为用户空间。
进程切换为了控制进程的执行,内核必须有能力挂起正在 CPU 上运行的进程,并恢复以前挂起的某个进程的执行。这种行为被称为进程切 ...
TCP 三次握手的底层逻辑
TCP 三次握手是基础中的基础,所有工程师都对此熟悉不过。但这里的三次往往被忽视,究竟为何 TCP 需要三次握手?本文中,我们探讨 TCP 三次握手的底层逻辑。
这篇文章主要会从以下几个方面介绍为什么我们需要通过三次握手才可以初始化 Sockets、窗口大小、初始序列号并建立 TCP 连接:
通过三次握手才能阻止重复历史连接的初始化;
通过三次握手才能对通信双方的初始序列号进行初始化;
讨论其他次数握手建立连接的可能性;
这几个论点中的第一个是 TCP 选择使用三次握手的最主要原因,其他的几个原因相比之下都是次要的原因,我们在这里对它们的讨论只是为了让整个视角更加丰富,通过多方面理解这一有趣的设计决策。
RFC 793 - Transmission Control Protocol 文档中非常清楚地定义了 TCP 中的连接是什么,我们简单总结一下:用于保证可靠性和流控制机制的信息,包括 Socket、序列号以及窗口大小叫做连接。
所以,建立 TCP 连接就是通信的双方需要对上述的三种信息达成共识,连接中的一对 Socket 是由互联网地址标志符和端口组成的,窗口大小主要用来做流 ...
如何建立高效知识笔记管理系统
转载自:如何建立知识笔记管理系统?
人脑的工作其实很大程度上与计算机的工作机制相似,人脑的思维区是 CPU 处理思考任务 ,人脑的工作记忆区是 CPU 缓存处理工作瞬时记忆,人脑的短期记忆区是内存处理短期记忆,人脑的建立的神经突触则是数据库。但是人脑的容量毕竟有限,一种更经济的做法是,把关键的知识节点存储在大脑中,作为领域知识的索引,而大量细节问题存储于各种数字化存储设备。这便是个人知识管理系统。
什么是知识管理系统?假设有一个场景,床头有 10 本书,要在其中找到一本书,你会怎么找?一本本翻找。
但假如在美国国会图书馆中,藏书超 2.1 亿本,在里边找到某一本书,请问你如何找?
仅凭人脑是没有办法处理这么大的信息量的。那么图书馆的管理人员,是如何解决这些问题的?
当让是靠着一套管理系统,让一切规律化,规则化,系统化,把人解放出来。
同理,我们的知识管理系统就相当于这个图书管理系统,而知识就如同这一本本图书,当有了套系统去管理它们以后,我们就相当于拥有了另外的一个大脑,如此就可以把我们大脑不擅长的东西,全部扔给这个外脑,让它帮助我们记忆,整理等等。
为什么你必须要建立外脑?1. ...
操作系统中的 select、poll、epoll 机制
IO 多路复用是指内核一旦发现进程指定的一个或者多个 IO 条件准备读取,它就通知该进程。与多进程和多线程技术相比,I/O 多路复用技术的最大优势是系统开销小,系统不必创建进程 / 线程,也不必维护这些进程 / 线程,从而大大减小了系统的开销。
目前支持 I/O 多路复用的系统调用有 select,pselect,poll,epoll,I/O 多路复用就是通过一种机制,一个进程可以监视多个描述符,一旦某个描述符就绪(一般是读就绪或者写就绪),能够通知程序进行相应的读写操作,但 select,pselect,poll,epoll 本质上都是同步 I/O,因为他们都需要在读写事件就绪后自己负责进行读写,也就是说这个读写过程是阻塞的,而异步 I/O 则无需自己负责进行读写,异步 I/O 的实现会负责把数据从内核拷贝到用户空间。
IO 多路复用适用如下场合:
当客户处理多个描述符时(一般是交互式输入和网络套接口),必须使用 I/O 复用。
当一个客户同时处理多个套接口时,而这种情况是可能的,但很少出现。
如果一个 TCP 服务器既要处理监听套接口,又要处理已连接套接口,一般也要用到 I/O ...
编程之并发编程
在计算机最早期的时候,没有操作系统,执行程序只需要一种方式,那就是从头到尾依次执行。任何资源都会为这个程序服务,在计算机使用某些资源时,其他资源就会空闲,就会存在 浪费资源 的情况。
操作系统的出现为我们的程序带来了 并发性,操作系统使我们的程序能够同时运行多个程序,一个程序就是一个进程,也就相当于同时运行多个进程。
操作系统的并发性操作系统是一个 并发系统,并发性是操作系统非常重要的特征,操作系统具有同时处理和调度多个程序的能力,比如多个 I/O 设备同时在输入输出;设备 I/O 和 CPU 计算同时进行;内存中同时有多个系统和用户程序被启动交替、穿插地执行。操作系统在协调和分配进程的同时,操作系统也会为不同进程分配不同的资源。
操作系统实现多个程序同时运行解决了单个程序无法做到的问题,主要有下面三点
资源利用率,我们上面说到,单个进程存在资源浪费的情况,举个例子,当你在为某个文件夹赋予权限的时候,输入程序无法接受外部的输入字符,只有等到权限赋予完毕后才能接受外部输入。总的来讲,就是在等待程序时无法执行其他工作。如果在等待程序时可以运行另一个程序,那么将会大大提高资源的利用率。( ...
Leetcode347. 前 K 个高频元素
描述347. 前 K 个高频元素Difficulty: 中等
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
12 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
12 输入: nums = [1], k = 1 输出: [1]
提示:
你可以假设给定的 k 总是合理的,且 $1\leq k\leq m$, m 为数组中不相同的元素的个数。
你的算法的时间复杂度 必须 优于 $O (nlogn)$ , n 是数组的大小。
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。
题解思路遍历数组,记录每个数字出现的次数,保存在哈希表中,这样的时间复杂度为 $O (n)$。
我们只需要找出这个哈希表中值最大的 k 个。
在这里我们可以用堆来排序。建立一个小顶堆,遍历出现次数数组。
堆元素个数小于 k,入堆
堆元素等于 k,检查堆顶与当前出现次数的大小,堆顶更大,则至少有 k 个数字出现次数比当前值大,舍弃当前值,否则弹出堆顶,插入当前值到堆。
遍历完 ...