阅读《MySQL Innodb无锁化设计的日志系统》（
https://zhuanlan.zhihu.com/p/53037796）后的心得：
与oracle日志子系统异曲同工的差异
1. 空洞：对于并发会话copy重做日志造成的空洞，oracle是由lgwr判断并等待持有redo copy闩锁的会话释放后，这时空洞已被填充，可以刷到磁盘了；mysql则是由log writer线程监测到空洞被填充后，再写入一段连续最大lsn的日志到磁盘
2. io方式：oracle的lgwr是direct io；mysql的log writer是写到os的page cache，后由独立的log flusher线程刷盘，比oracle多了一个过程
3. 唤醒会话：oracle由lgwr扫描所有等待的会话，只唤醒满足写入条件(事务提交log已刷盘)的会话；mysql则由独立的log flush notifier通过满足条件对应的分片消息队列来唤醒，比oracle多了一个过程
总结：mysql通过原子变量来管理全局log buffer的几个内存位置来实现无锁化，而原子操作在多核上仍不利于线性扩展。oracle的闩锁也存在类似问题，但通过私有redo缓存和多个全局log buffer(相关闩锁量与cpu核数正比)，来提升了扩展性。故整体上oracle更优
阅读《MySQL/InnoDB数据克隆插件(clone plugin)实现剖析》（
https://zhuanlan.zhihu.com/p/76255304）后的心得：
与oracle老式热备异曲同工的差异
1. page追踪：oracle老式热备实际当每行更新时将整个关联的page记录在redo日志中；mysql热备则是记录变化page的id在单独一个地方，用于page copy阶段从buffer pool读取并发送页数据到备库
2. redo归档：oracle老式热备在拷贝数据文件的全过程，只要数据文件被修改就会有redo归档；mysql热备则仅在page copy阶段启用redo归档，可看做是临时的
3. 一致性恢复：oracle老式热备存在数据块分离现象，对此应用被冻结scn及日志序列号后的redo log来恢复；mysql则通过page copy及应用clone lsn后的redo log来恢复
总结：oracle老式热备必须处于归档模式，由于记录整块而非行变化，因此重做日志写放大而增加了cpu和io的开销，由于可能判断并修复分离的块，因此延长了恢复时间；mysql通过page追踪和临时redo归档来减少应用redo的体量而缩短了恢复时间。故mysql热备整体更优，但相对oracle的现代rman备份则并不更优
posted @
2020-04-21 11:19 春秋十二月 阅读(5948) |
评论 (0) |
编辑 收藏
nginx是一款著名的高性能开源Web与反向代理服务器，支持windows和linux操作系统，因为在windows系统上还不支持SCM（服务控制管理），所以只能以控制台方式运行，但这样并不是在后台运行，也不能在系统登录前启动。针对这些问题，本方法通过改进源码，使nginx良好地支持了SCM，方便了部署运行
特点
最大地复用了nginx源码；支持SCM，并兼容控制台运行方式；统一处理异常退出而报告服务停止
实现 变换原主函数
将原来的main函数更名为ngx_main，并增加第3个参数is_scm来标识运行方式，非0表示服务方式，0表示控制台方式，流程如下
图上红色部分为插入的逻辑，其它部分为nginx原来的逻辑。由于服务初始化须将错误记录在log（日志）中，所以应在初始化log模块后调用
增加主函数
这个主函数也就是程序入口main，可被控制台或SCM调用，当被SCM调用时，注册服务以及启动服务控制调度程序，流程如下
如果以命令行启动nginx 也就是master进程（管理进程），或nginx产生worker进程（工作进程）时，那么以控制台方式调用main，进而以is_scm为0调用ngx_main，当ngx_main返回时，就表示master或worker进程退出了
服务主函数
由SCM生成的一个逻辑线程调用，流程如下
这里的逻辑线程代替了nginx的master进程，到这里就表明已经以SCM方式运行了，所以以is_scm为1调用ngx_main，当ngx_main返回时，就表明master进程退出了，应该更新服务状态为已停止，然后返回表明当前服务结束了
服务初始化 由ngx_main调用，见变换原主函数流程图，流程如下
由于在nginx实现中，有多处出现异常错误而直接退出，因此首先注册了进程退出处理器，在其内报告服务状态为已停止，这样只要当进程退出了，在SCM上就能看到已停止的状态了
服务控制处理器 由SCM的主线程调用，流程如下
调用关系 下图左边为master进程调用模块与函数，右边为worker进程调用模块与函数，委托主函数是
ngx_main 
posted @
2019-11-20 19:45 春秋十二月 阅读(847) |
评论 (0) |
编辑 收藏
传统的vss备份架构由于备份应用部署在应用服务器内，因此比较耗应用服务器的CPU和IO，特别是拷贝大量的文件，为了降低对应用服务器的干扰，可采用server-free架构，将耗时的拷贝移到另一机器即备份服务器实现，而应用服务器只负责占用资源及耗时很少的打快照。这种架构运用了vss可传输卷影拷贝的特性，要求快照处于共享存储中，适用于Windows Server 2003 sp1以上版本
协作流程图 
VSS快照代理端的SetContext要求设置成
VSS_CTX_APP_BACKUP | VSS_VOLSNAP_ATTR_TRANSPORTABLE
posted @
2019-11-06 18:01 春秋十二月 阅读(893) |
评论 (0) |
编辑 收藏1. 绑定变量作为一种优化查询处理的方法，在性能上有利有弊，是一把双刃剑。它的优势在于可以共享库缓存中的父游标，从而避免了硬解析及相关的开销；劣势在于因绑定变量扫视增加了查询优化器选择(非常)低效执行计划的风险，即使支持自适应游标共享，也引入了游标感知判断和谓词选择率估算的代价，而且在生成高效的执行计划前至少有一次是无效率的。因此，是否使用绑定变量，需要衡量实际字面值与处理数据量带来的解析执行的收益与损害，当损害大于收益时就不应该使用，反之当处理较少数据硬解析耗时比执行多时，就可以使用了
2. 存储快照一般有三种层次：物理卷、文件系统和应用程序
◆ 物理卷快照基于卷扇区映射表实现，宜采用CoFW法，因为它不必每次写io都去遍历映射表，比RoFW快
◆ 文件系统快照基于inode树即元数据复制实现，每当写io时更新快照或源inode的指向，必要时向上回溯至根inode。有的文件系统比如NetApp公司的WAFL则更优，只须复制根inode，因为每次写io时它会变但其下所有的inode不会变
◆ 应用程序快照最典型的就是数据库，原理本质与上述两种一样，基于页改变位图，当page首次(相对于快照创建时刻)改变时拷贝到快照文件(一种稀疏文件)，另外当撤消未提交事务或回滚事务时也会发生拷贝(此时快照慢慢不再稀疏)，这是为了保证快照的可用一致性
3.
数据块的加锁有单机和分布式两种情景，前者是为了同步单实例事务的并发，后者是为了协调分布式事务的同步，并与缓存一致性协议紧密联系。undo,redo,undo/redo三种日志对数据脏块与提交日志记录落盘的顺序要求各不同，因此恢复方式不同。脱服务器备份架构比较好，具有不占用应用服务器资源的优势，而微软的vss可传输卷影拷贝提供了这一支持，足见其技术的先进前瞻性
4. Oracle的
实例恢复完全靠在线重做日志，介质恢复必须靠归档重做日志，以及在线重做日志。然而在线重做日志是有限数量的，那么Oracle是怎样保证宕机经实例恢复后不丢数据？答案是检查点。检查点是数据库中一个很重要的机制，被重做日志切换触发，由DBWn执行刷新脏块，并清除老的无用的在线重做日志，以允许被覆盖
5. Linux内核的swap高速缓存和其它的缓存(比如page缓存)不太一样，因为它存在的主要原因不是为了减少磁盘IO提高性能，而是解决换入换出共享匿名页同步即并发swap的问题。那么它是唯一的方法吗？不一定，可以遍历所有的anon_vma链表，查找匿名页对应的页框是否已建立，但该方法没有swap缓存快。当然，在换入操作很多的情景，swap缓存确实能提高系统性能
6. Linux内存回收的核心是LRU链表，Oracle的buffer cache也有个LRU，这两种LRU的共同点是引用计数(标志)和非活跃链表，引用计数会影响一个对象是否移到非活跃链表，非活跃链表用于回收或覆盖这个对象。对于Linux这个对象是页框，移到非活跃链表取决于swap tendency；而Oracle则是数据块buffer及其TCH
7. Linux内核中的反向映射让我想起了Oracle中的反向键索引，它们的共同点都是为了高性能，前者是为了快速定位引用同一页框的所有页表项，从而方便共享内存的回收；后者是为了减少右侧索引叶块的竞争，从而降低缓冲区忙等待、提高并发量
8. mvcc与read uncommitted(简称RU)隔离级别的关系究竟如何？这取决于现代数据库的实现。对于Oracle，RU和RC的读实现都基于mvcc实现，换句话说Oracle其实没有脏读；对于MySQL innodb引擎，mvcc不适用于RU而只适用于RC/RR级别，因为RC/RR必须读取修改已提交的数据，但基准点不同，前者查询开始时、后者事务开始时，而RU则可读取未提交的数据，当然用mvcc模拟实现RU应该也可以，只需要读取当前新版本而非旧版本
9. 借助内核page cache的数据库或者存储引擎，一定程度上讲，是粗暴懒惰的表现，这会导致系统负载比较重的情况下，io性能很差。所以为高性能，必须得处理好direct io，设计self cache，这样一来，就避免了浪费在原先内核页缓存的页框，避免处理内核页缓存和预读的多余指令而提高了系统调用read和write的效率，同时减少了一次数据拷贝
10. SQL半连接的本质是在内连接的基础上对内表去重，即使内表有符合多个连接条件的元组，也只匹配一条，从而减少了连接返回的结果集。一般地，简单的in、exists和any子句，都采用半连接实现，但若内表本身保证了唯一性，则半连接可消除转为内连接实现，或者内表数据量很小且外表存在索引，那么也会消除半连接，生成由内表驱动外表，外表走索引的执行计划。由此一例看出，SQL优化器偏爱内连接，因为内连接带来了驱动表选择和谓词下推的灵活，便于产生更优的执行计划
11. 从Oracle数据库内核角度讲，游标代表SQL语句的句柄，包含了依赖对象及执行计划等信息，它相当于linux的文件描述符和windows的句柄。打开或缓存的游标是指对应SQL语句所占的内存(父游标句柄、父堆0和子游标句柄的chunk)被加上kgl lock和pin锁，意味着第三次后解析同样的SQL不必再从library cache hash chain中加锁查找而直接从PGA的子堆6地址中获取并调用执行计划，如此优化提高了并发度加快了查询，这正是软软解析；软软解析前必须软解析2次，目的是将library cache的执行计划在PGA中做一份链接，软解析前必须硬解析，目的是将执行计划放在library cache中。然而，如果共享池空闲内存不足，或者依赖对象发生DDL操作导致执行计划失效，那么执行计划所占chunk可以被覆盖释放，这样一来，软(软)解析时就需要重新生成执行计划了
12. Oracle的内存管理粗略地类似于Linux内核，所不同的是内存分配单元，前者叫granule通常大小4M~16M，后者叫page通常4K；数据块缓冲的分配类似伙伴算法，共享池(主要用于sql缓存)的chunk分配类似slab算法，共享池中的保留池类似基于slab的内存池
13. Oracle数据库究竟是怎样构建表数据块的读一致性版本？这是个比较复杂、细致和有趣的问题，核心流程如下
◆ 克隆数据块，若不存在则先从磁盘读，下面几步以克隆块为目标
◆ 根据ITL中的flag及lck，对所有已提交的事务做清除操作，即延迟块清除。延迟块清除为了获取足够精确的提交SCN填充到ITL，分2种情况，若事务表槽没被覆盖，则直接用其提交SCN；否则先从事务控制区获取SCN，并判断对于上界提交是否足够精确，若不够则需要回滚事务表一直找到合适的SCN或报错ORA-01555
◆ 根据ITL中的uba，反向更改所有未提交的事务，也就是应用事务的undo记录
◆ 根据ITL中的SCN，不断反向更改大于目标SCN的已提交事务，直至遇见合适的已提交事务。这里也是应用undo记录，但不同的是，除了应用行数据，还会从事务的第一个undo记录找到先前即前一个已提交事务的ITL项拷贝回当前块的对应ITL项
14. Oracle的多版本控制机制，为dml不仅提供了一致且正确的结果，还提高了并发性，可谓鱼和熊掌兼得。那么它的缺点是什么？可能会导致热表的IO增高，因为读一致性需要不断回滚多个事务对数据块的修改，直到查询开始时的数据。事务隔离级别read committed与read uncommitted的相同是不会脏读，区别是前者会不可重复读或幻读
15. Sql*plus的ARRAYSIZE对查询数据性能有重要的影响，这个值过大过小都不好，而是要接近一个数据块所拥有的行数，如此仅一次逻辑IO就拿到了一批行。那么设置合适的ARRAYSIZE就一定能提高性能吗？不一定，还要看所查询的表使用了什么索引列及表数据在磁盘上的物理布局，若数据分散即聚簇因子低，则优化器会选用全表而非索引区间扫描，去执行这个查询
16. IOT表如果为非主键列再建索引，那么就成二级索引。这时候查询数据，需要两次扫描，一是扫描二级索引得到IOT中的位置，二是扫描IOT本身匹配那个位置，之所以这样是因为行记录在IOT中的位置会变。而堆组织表，仅需一次扫描索引结构，得到rowid，再直接读磁盘获取行记录。因此IOT上再建二级索引，并非明智的选择
17. 相容性矩阵是封锁调度的核心结构; 任意一个无环优先图的封锁调度都是冲突可串行化的; 基于树协议的无环优先图的封锁调度，其整个事务集合的任意一个拓扑顺序都是等价可串行化的
18. 总结解决数据库丢失更新问题的方案
◆ 对于表不会被悲观锁锁定的情景：使用基于select+update的乐观锁方法，查询保存前映像，以便定位更新。前映像列可为全列，或新增一个时间戳列作为版本列
◆ 对于表可能会被悲观锁锁定的情景：使用select…for update nowait+update的悲观锁方法，可以以全列的hash(虚拟列)来定位更新
19. 如果能够在备库上打开闪回，那么就可以做到既让生产系统没有承担闪回的开销，又能快速地为错误或故障恢复到以前某个时刻。一举两得比较完美，重做日志的创新使用真是太棒了
20. Oracle的索引聚簇表是个创新，它能将多个不同表的行按照索引列存储在同一块中，属于物理上的join，这样一来既可减少data buffer缓存的块数而提高效率，又可提高多个相关表连接查询的性能，比如通过外键约束的父子表。最典型的应用就是数据字典，数据字典对于查询优化的成本估算很重要，由此可见oracle的设计之明智，mysql的innodb只有索引组织表，sql server有堆表和索引组织表，但它们都没有索引聚簇表
21. 分布式事务处理是工程难题。Oracle的serializable串行隔离级别以乐观锁实现，所以并发度与非串行相当，需要注意的是：串行并不是说一个事务提交了才能处理下一个，而是多个事务间没有冲突表现地像只有一个事务在运行，否则Oracle的serializable级别就不存在抛出ORA-08177错误了
22. 理清read uncommitted事务隔离级别的锁策略：读不加共享锁，写加排它锁直至提交，这里的锁是指lock；块的缓冲区并发操作必须加锁，这里的锁是指latch，若不加，那脏读读到的数据可能是错的。脏读隔离级别允许读修改但未提交的行记录，这意味着读不能被写阻塞，也不能阻塞写，所以不会申请共享锁（显式锁定读除外）
23. 与MySQL不同，Oracle的行锁无需索引列的限制，是真正的行锁，其实现为数据块的属性而非传统的锁管理器，但是它需要在事务commit或rollback时才释放，如果存在慢sql，那么导致的阻塞会比较严重
24. 隔离是实现安全的一种办法，其结果常被称作“沙箱”。从这个意义上讲Oracle很明智，因为它的事务没有也不需要read uncommitted隔离级别，Oracle最低且默认的隔离级别是read committed，因为它有基于undo的多版本控制，天生非阻塞读，根本不会脏读。我想不出read uncommitted有什么好处，除了非阻塞读及可能的高并发，要谨慎脏读是危险不安全的
25. windows内存映射和linux内存映射的实现机制不太一样，前者使用了内存区section的专用数据结构而不像后者重用了页缓存，内存区的映射完全由内存管理器负责包括物理页分配及脏页面写入器，与缓存管理器无关；缓存管理器基于内存管理器维护了文件块数据的视图，并提供了自己的延迟写入器。这两种写入器即回刷，独立并行地工作
posted @
2019-11-06 11:29 春秋十二月 阅读(8051) |
评论 (0) |
编辑 收藏 由于某些sdk或软件依赖众多的第三方库，而从官网下载到windows主机或从linux传到windows时，所依赖的so库往往丢失符号链接，给编译运行带来不便，因此编写了
ctlsolink脚本，用于自动为单个so或某目录下的众多so或创建/删除一级/二级符号链接。该脚本的用法如下:
● 第1参数为mk或rm子命令，mk表示创建，rm表示删除
● 第2参数为文件或目录
● 第3参数是可选的-r，且只能是-r，如果指定了，则表示不断递归子目录
脚本实现
考虑到so库带版本一般多为libx.so.1，libx.so.1.2，libx.so.1.2.3这三种形式(x为库名)，对于前一种创建/删除一级符号链接即可，后两种则创建/删除二级符号链接。为了精确地抽出一级和二级链接名称，这里使用awk来匹配，用shell变量的最短匹配模式从尾部逐步删除点号及数字，核心代码如下
1
if [ "$dir" != "$self_dir" ] || [ "$name" != "$self_name" ]; then
2 if echo $name | awk '{if($0~/\.so\.[0-9]{1,}\.[0-9]{1,}\.[0-9]{1,}$/) exit 0; else exit 1}'; then
3 link_name=${name%.[0-9]*}
4 link_name=${link_name%.[0-9]*}
5 link_name=${link_name%.[0-9]*}
6 link_name2=${name%.[0-9]*}
7 link_name2=${link_name2%.[0-9]*}
8 elif echo $name | awk '{if($0~/\.so\.[0-9]{1,}\.[0-9]{1,}$/) exit 0; else exit 1}'; then
9 link_name=${name%.[0-9]*}
10 link_name=${link_name%.[0-9]*}
11 link_name2=${name%.[0-9]*}
12 elif echo $name | awk '{if($0~/\.so\.[0-9]{1,}$/) exit 0; else exit 1}'; then
13 link_name=${name%.[0-9]*}
14 else
15 return
16 fi
17
18 if [ $do_mk = "yes" ]; then
19 #echo "name=$name, link_name=$link_name, link_name2=$link_name2"
20 if [ -n "$link_name2" ]; then
21 ln -sf $name $link_name2
22 ln -sf $link_name2 $link_name
23 else
24 ln -sf $name $link_name
25 fi
26 else
27 if [ -n $link_name2 ]; then
28 rm -f $link_name2
29 fi
30 rm -f $link_name
31 fi
32 fi 要注意的是，这儿不能使用%%删除最长匹配的尾部来得到
link_name，因为它的模式是
.[0-9]*，这可能会错误地匹配了so前的部分，比如libx.1.so.2得到libx，而期望的是libx.1.so
完整脚本下载：
ctlsolink 运行效果 初始状态
运行ctlsolink创建软链接后
运行ctlsolink删除软链接后
posted @
2019-11-05 18:17 春秋十二月 阅读(1868) |
评论 (0) |
编辑 收藏
为了减少程序中的硬编码，灵活按需管理字符串空间，使用了ATL中的CString类，代码如下
1 CString bstrComPathName;
2 WCHAR componentPathName[1];
3 DWORD dwNameLen = 1;
4
5 if (!GetComputerNameEx(ComputerNamePhysicalDnsFullyQualified, componentPathName, &dwNameLen))
6 {
7 DWORD dwErr = GetLastError();
8 if(ERROR_MORE_DATA==dwErr)
9 {
10 if (!GetComputerNameEx(ComputerNamePhysicalDnsFullyQualified, bstrComPathName.GetBuffer(dwNameLen), &dwNameLen))
11 {
12 zlog_error(g_zc, "GetComputerNameEx with ComputerNamePhysicalDnsFullyQualified fail: %d", GetLastError());
13 return -1;
14 }
15 }
16 else
17 {
18 zlog_error(g_zc, "GetComputerNameEx with ComputerNamePhysicalDnsFullyQualified for fail: %d", dwErr);
19 return -1;
20 }
21 }
22 bstrComPathName.ReleaseBuffer();
需要注意的是，GetBuffer方法虽提供方便了直接修改CString对象的内部缓冲区，但违背了面向对象设计的原则（由公开方法修改内部数据），因此不保证对象的完整性，在操作完成后一定要调用ReleaseBuffer
posted @
2019-07-31 12:51 春秋十二月 阅读(7925) |
评论 (0) |
编辑 收藏 在GNU make中文手册这本书中，3.14节讲到了依赖文件的自动生成，如下图
图中的规则对C源文件和Makefile在同一目录，是正确的。但是不在同一目录的又希望依赖文件在对应的目录下，比如src/log/log_file.c，希望依赖文件log_file.d生成在src/log/下。因为gcc（aix平台xlc编译器亦如此）生成的依赖文件内容中目标文件名没有带路径，例如下所示
log_file.o: src/log/log_file.c src/log/log_file.h src/log/log_type.h \
src/log/../base/io_ext.h
所以sed就找不到src/log/log_file.o而替换了，改正后的规则如下
%.d: %.c
$(CC) $(CFLAGS) $(INCS) $< $(MFLAGS) $@.$$$$;\
sed 's,$(*F).o[ :]*,$*.o $@: ,g' < $@.$$$$ > $@;\
$(RM) $@.$$$$
该规则对C源文件和Makefile在同一目录也适合，生成后的依赖文件内容如下
src/log/log_file.o src/log/log_file.d: src/log/log_file.c src/log/log_file.h src/log/log_type.h \
src/log/../base/io_ext.h
posted @
2018-11-16 12:08 春秋十二月 阅读(836) |
评论 (0) |
编辑 收藏由于traceroute只能诊断UDP通信的包路由，不能确定TCP通信的实际路由（可能变换），因此编写了本文。为方便描述，下面的IP、MAC和端口均为示例，实际诊断中可更换为具体的值
1. 如何判断客户端到服务器的TCP包，是否经过了网关
在客户端执行 tcpdump -i eno16777728 ether dst b0:b9:8a:69:65:3e and host 192.168.0.26 and tcp port 80 抓取经过网关且往返服务器的TCP端口为80的包
eno16777728 接口名称；ether 以太网链路，dst 目标（src表示源）；b0:b9:8a:69:65:3e 网关MAC地址；192.168.0.26 服务器IP地址，80 监听端口
输出结果分析
● 有输出，则表示经过了网关
● 有部分输出而TCP通信还在进行，则表示先前的包经过了网关，后来路由表项缓存被重定向更新，没经过网关了
● 不断输出，则表示一直经过网关
2. 如何判断路由表项缓存被重定向更新
在客户端执行 tcpdump -i eno16777728 src 192.168.1.1 and dst 192.168.1.45 and icmp 抓取来自网关和到达客户端的所有icmp包
192.168.1.1 网关IP；192.168.1.45 客户端（出口）IP
输出结果分析
● 没有输出，则表示没有收到rerdirect包，路由表项缓存不变
● 有输出类似ICMP redirect 192.168.0.26 to host 192.168.0.26（前面一个IP表示到达服务器的直接路由IP，后一个表示服务器IP）
● 则表示收到了ICMP重定向包，内核会更新路由表项及缓存网关为192.168.0.26，下次通信时就直接发往192.168.0.26了
3. 如何控制接收ICMP重定向
● echo 0 | tee /proc/sys/net/ipv4/conf/*/accept_redirects 禁止所有网卡接收，可避免路由表项缓存被修改
● echo 1 | tee /proc/sys/net/ipv4/conf/*/accept_redirects 启用所有网卡接收ICMP重定向消息
4. 查看、刷新路由表项缓存
● ip route get 192.168.0.26 可以从输出中看到通住目标IP的实际路由
● ip route flush cache 清空路由表项缓存，下次通信时内核会查main表（即命令route输出的表）以确定路由
posted @
2017-12-29 17:24 春秋十二月 阅读(1952) |
评论 (0) |
编辑 收藏
近期有机会，深入了SSL/TLS协议原理与细节，并分析了相关密码学内容，心得颇多，历经半月，终于写成了这份文档。
本人水平尚有限，错误难免，欢迎指正，不胜感激。
目录
部分章节预览
第3章
第5章第4节
第11章第3节
全文
下载地址：
深入理解SSL/TLS技术内幕
posted @
2016-12-15 17:16 春秋十二月 阅读(1612) |
评论 (0) |
编辑 收藏
【公开密钥】
p是512到1024位的素数
q是160位长，并与p-1互素的因子
g = h^((p-1)/q) mod p，其中h<p-1且g>1
y = g^x mod p
【私有密钥】
x < q，长160位
【签名】
k为小于q的随机数，k^-1为k模q的逆元，m为消息，H为单向散列函数
r = (g^k mod p) mod q
s = (k^-1(H(m)+xr)) mod q
【验证】
w = s^-1 mod q
u1 = (H(m)w) mod q
u2 = (rw) mod q
v = ((g^u1 * y^u2) mod p) mod q
若v = r，则签名被验证
验签推导
1. 先证明两个中间结论
因(h,p)=1（p为素数且h<p，(a1,a1)是数论中的符号，记为a1与a2的最大公约数），故依费马小定理有h^(p-1)=1 mod p，则对任意整数n，有
g^(nq) mod p = (h^((p-1)/q))^(nq) mod p
= h^(n(p-1)) mod p
= (h^(p-1) mod p)^n mod p
= (1^n) mod p = 1 (1)
对任意整数t、n，可表示为t=nq+z，其中z>0，则有
g^t mod p = g^(nq+z) mod p
= (g^(nq) mod p * (g^z mod p)) mod p
= g^z mod p
= g^(t mod q) mod p (2)
2. 再假设签名{r,s}和消息m均没被修改，令H(m)=h，开始推导v
v = ((g^u1 * y^u2) mod p) mod q
= (g^(hw mod q) * ((g^x mod p)^(rw mod q) mod p)) mod q
= ((g^(hw mod q) mod p * ((g^x mod p)^(rw mod q) mod p)) mod p) mod q
= ((g^(hw mod q) mod p * (g^(x * (rw mod q)) mod p)) mod p) mod q
= ((g^(hw) mod p * ((g^(rw mod q) mod p)^x mod p)) mod p) mod q
= ((g^(hw) mod p * ((g^(rw) mod p)^x mod p)) mod p) mod q
= ((g^(hw) mod p * (g^(rwx) mod p)) mod p) mod q
= (g^(hw+rwx) mod p) mod q
= (g^((h+rx)w) mod p) mod q (3)
又因w = s^-1 mod q
故(sw) mod q = 1
=>(((k^-1(h+xr)) mod q)w) mod q = 1
=>((k^-1(h+xr))w) mod q = 1
=>(h+xr)w = k mod q (4)
将(4)式代入(3)式中得
v = (g^(k mod q) mod p) mod q
= (g^k mod p) mod q
= r
3. 最后由(4)式知，若h、r和s任一个有变化（s变化导致w变化），则v ≠ r
posted @
2016-11-24 19:39 春秋十二月 阅读(5292) |
评论 (0) |
编辑 收藏