随笔-94  评论-224  文章-24  trackbacks-0
  置顶随笔
模板
    1. 空基类优化
    2. 元编程技术
        2.1. 选择API
        2.2. 计算最值
        2.3. 类型选择
    3. 封装GCC原子操作
    4. 定制类对象的内存管理

算法
    1. 排序
        1.1. 改进的快速排序
        1.2. 原位统计排序     
    2. 多叉树
        2.1. 深度优先存储
        2.2. 迭代器的设计
        2.3. 前序遍历
        2.4. 后序遍历
        2.5. 兄弟遍历
        2.6. 叶子遍历
        2.7. 深度遍历 
    3. 优先级队列
        3.1. 原理
        3.2. 内幕
        3.3. 外观
    4. RSA加解密的证明
    5. DSA数字签名的推导

GUI
 
    1. MFC中的WM_COMMAND传递
    2. ATL和WTL中的消息反射
    3. 工作线程与消息循环
    4. 多窗口的组合与分离
        4.1. 接口
        4.2. 实现

跨平台
    1. 用户态自旋锁
    2. 互斥锁
    3. 信号量
    4. socket管道
    5. 锁框架的设计与实现

网络
    1. 运用状态机异步接收变长包
    2. 基于OpenSSL实现的安全连接
    3. TCP/IP FAQ
        3.1. 链路层、网络层和传输层
        3.2. 插口层和应用层
    4. Linux套接字与虚拟文件系统
        4.1. 初始化和创建
        4.2. 操作和销毁
    5. Linux ICMP消息的产生与转换
    6. nginx iocp
        6.1. tcp异步连接
        6.2. udp异步接收
        6.3. scm服务控制
    7. TCP分组丢失时的状态变迁

Shell应用
    1. 自动生成并安装服务脚本
    2. nginx升级与恢复
    3. 使用awk定位反汇编输出
    4. 自动化批量编译
posted @ 2014-04-10 16:04 春秋十二月 阅读(1584) | 评论 (0)编辑 收藏
  2019年11月6日
部署图
   
   传统的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 春秋十二月 阅读(117) | 评论 (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有什么好处,除了非阻塞读及可能的高并发,要谨慎脏读是危险不安全的
posted @ 2019-11-06 11:29 春秋十二月 阅读(147) | 评论 (0)编辑 收藏
  2019年11月5日
脚本概述
   由于某些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 | aw'{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 [ -"$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 春秋十二月 阅读(148) | 评论 (0)编辑 收藏
  2019年7月31日
   为了减少程序中的硬编码,灵活按需管理字符串空间,使用了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 春秋十二月 阅读(356) | 评论 (0)编辑 收藏
  2018年11月16日
  在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 春秋十二月 阅读(464) | 评论 (0)编辑 收藏
  2017年12月29日
由于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 春秋十二月 阅读(1171) | 评论 (0)编辑 收藏
  2016年12月15日
前言
   近期有机会,深入了SSL/TLS协议原理与细节,并分析了相关密码学内容,心得颇多,历经半月,终于写成了这份文档。
   本人水平尚有限,错误难免,欢迎指正,不胜感激。

目录
         

部分章节预览
   第3章


   第5章第4节


   第11章第3节

全文
   下载地址:深入理解SSL/TLS技术内幕
posted @ 2016-12-15 17:16 春秋十二月 阅读(1166) | 评论 (0)编辑 收藏
  2016年11月24日
算法描述
【公开密钥】    
   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 春秋十二月 阅读(2404) | 评论 (0)编辑 收藏
  2016年11月18日
算法描述    
   随机选择两个大的素数 p、q ,且p ≠ q,计算n = pq、r = (p-1)(q-1),依欧拉定理,r即为与n互质的素数个数;选择一个小于r的整数e(即加密指数),求得e关于模r的逆元d(即解密指数),则{n,e}为公钥、{n,d}为私钥;根据模的逆元性质有ed ≡ 1 (mod r);设m为明文,则加密运算为m^e ≡ c (mod n), c即为密文;则解密过程 c^d ≡ m (mod n)。
   证明会用到费马小定理,即 若y为素数且x不为y的倍数, 则 x^(y-1) ≡ 1 (mod y)(费马小定理的证明需先证明欧拉定理,此处略)。符号≡表示同余,^表示,|表示整除,*表示相乘。

算法证明
 第一种证明途径   
   因 ed ≡ 1 (mod (p-1)(q-1)),令 ed = k(p-1)(q-1) + 1,其中 k 是整数
   则 c^d = (m^e)^d = m^(ed) = m^(k(p-1)(q-1)+1)
   1.若m不是p的倍数,也不是q的倍数
      则 m^(p-1) ≡ 1 (mod p) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod p)
      m^(q-1) ≡ 1 (mod q) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
      故 p、q 均能整除 m^(k(p-1)(q-1)) - 1
         => pq | m^(k(p-1)(q-1)) - 1
      即 m^(k(p-1)(q-1)) ≡ 1 (mod pq)   
         => m^(k(p-1)(q-1)+1) ≡ m (mod n)   

   2.若m是p的倍数,但不是q的倍数
      则 m^(q-1) ≡ 1 (mod q) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
         => m^(k(p-1)(q-1)+1) ≡ m (mod q)
      因 p | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod p)
         => m^(k(p-1)(q-1)+1) ≡ m (mod p)
      故 m^(k(p-1)(q-1)+1) ≡ m (mod pq) 
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

   3.若m是q的倍数,但不是p的倍数,证明同上

   4.若m同为p和q的倍数时
      则 pq | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod pq)
         => m^(k(p-1)(q-1)+1) ≡ m (mod pq)
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

 第二种证明途径
   先证明m^ed ≡ m (mod p)恒成立
   1.若p为m的因子,则p | m^ed - m显然成立,即m^ed ≡ m (mod p)
   2.若p不为m的因子,令ed = k(p-1)(q-1) + 1,则 m^(ed-1) - 1 = m^(k(p-1)(q-1)) - 1
       m^(p-1) ≡ 1 (mod p) (费马小定理)
        => m^(k(p-1)) ≡ 1 (mod p)
        => m^(k(p-1)(q-1)) ≡ 1 (mod p)
        => m^(ed-1) ≡ 1 (mod p)
        => m^ed ≡ m (mod p)
   同理可证m^ed ≡ m (mod q)
   故m^ed ≡ m (mod pq),即m^ed ≡ m (mod n)
   又因 c^d = m^e^d = m^(ed)
   故 c^d ≡ m (mod n),证毕
   
总结
 第二种比第一种简单直观,以上证明途径对RSA私钥签名与验签同样适合。
posted @ 2016-11-18 17:05 春秋十二月 阅读(1802) | 评论 (0)编辑 收藏
  2016年10月19日
脚本源码
   由于很多应用项目依赖诸多第三方开源库,这些开源库各有不同的核心目录、库目标和输出位置,这里的核心目录是指仅产生so库的工程目录,库目标是指仅产生so库的make目标,输出位置是相对于核心目录的,但不必是子目录,可用..来回溯到父目录的某位置,更高层目录的位置,依次类推。为了统一支持它们,使用了一些技巧,详见示例脚本如下
 1.PHONY: all clean lib core
 2
 3thirdlib=openssl-1.0.1u?build_ssl ACE_wrappers/ace json ncurses-6.0??lib
 4coremod=main
 5
 6dir = `echo $@ | awk -F? '{print $$1}'`
 7aim = `echo $@ | awk -F? '{print $$2}'`
 8out = `echo $@ | awk -F? '{print $$3}'`
 9
10copy=\cp -Pf ${dir}/${out}/*.so* output
11
12define MAKE_SUBDIR
13echo "${dir},${aim},${out}"\
14if [ "$(MAKECMDGOALS)" != "clean" ]; then \
15$(MAKE) ${aim} -${dir}\
16if [ "$$is_cp" -eq "1" ]; then \
17$(copy); \
18fi \
19else \
20$(MAKE) clean -C ${dir}; \
21fi 
22endef
23
24all: lib core
25
26lib: $(thirdlib)
27
28$(thirdlib)::
29    @is_cp=1; $(MAKE_SUBDIR)
30
31core: $(coremod)
32
33$(coremod)::
34    @is_cp=0; $(MAKE_SUBDIR)
35
36clean: $(thirdlib) $(coremod)

实现技巧
   1)使用?作为分隔符,所分隔的3个域依次为核心目录、库目标、输出位置;使用awk来获取各域,分别为dir、aim和out;在运行过程中,值dir一定非空,而aim为空则表示默认目标,out为空表示输出位置即为dir目录。
   2)copy为命令变量,功能为每当一个库编译完成后,将输出的so库拷贝到output下,并保持软链接;对于有的开源库,需在编译前,使用对应的选项来调用configure,使其生成so库。
   3)为了重用代码,定义了MAKE_SUBDIR命令包,参数变量为is_cp,当is_cp为1时,表示当前编译的是依赖库,否则是主程序。 
   4)thirdlib和coremod为依赖文件,使用了双冒号规则,这样一来,只要在thirdlib中加入新的依赖库,指定核心目录、库目标和输出位置即可,其它地方不用改。
posted @ 2016-10-19 15:11 春秋十二月 阅读(2871) | 评论 (0)编辑 收藏
仅列出标题  下一页